Is it possible to calculate the input variable of a specific encryption function without brute-forcing it?

Question

I didn't know where to post this question, here or SO but I feel it's more of a math problem.

Lately I have been reverse engineering a game, and figured out how it takes user input, encodes it, and verifies it against a specific value to see if the user input is a correct cheat code or not. The game has a unique id for every player and a specific key that it uses for this function. The algorithm looks like this:

userInput = ReadUserInput();
userInputEncrypted = userInput MOD encryptionKey;
for i = 0; i<16; i++{
    userInputEncrypted = userInputEncrypted^2 MOD encryptionKey;
}
userInputEncrypted = userInputEncrypted * userInput;
userInputEncrypted = userInputEncrypted MOD encryptionKey;

if (userInputEncrypted == correctValue)
    //Bingo!

Now my problem is this: I know what the correct values are, and I know the encryptionKey, is there a way mathematically to do this in reverse and instantly calculate what the starting userInput should be?

Or am I doomed to bruteforce it as the modulo that occurs 16 times gives me no other choice?

As you can see in the last step, the algorithm re-uses the starting userInput, so my hopes lie there.

Thanks in advance!

Answer 1

Let $m$ be the encryption key, and $x$ be the userInput, modulo $m$. Then, as mentioned by mihaild, the encryption algorithm is essentially

$$x ^ {2^{16} + 1} \equiv a \pmod m$$

Let $E = 2^{16} + 1 = 65537$. To reverse the encryption, we need to find $D$ such that $$x^{ED}\equiv x \pmod m$$ for all $x, 0 \le x < m$ and thus $$a^D\equiv x \pmod m$$

The way to do that, is to solve $$ED \equiv 1 \pmod \phi(m)$$ where $\phi()$ is Euler's Totient function.

For the given $$m = 19474436171537127533$$ $$\phi(m) = 19474436152198143420$$

Once we know $\phi(m)$, we can find $D$ by using the extended Euclidean algorithm, since $$ED - k\phi(m) = 1$$ for some $k$, provided that E is coprime to $\phi(m)$. That's certainly true in this case. In fact, $E$ is prime, and $$phi(m) \equiv 35631 \pmod E$$

Below is a short Sage Python script that performs the necessary calculations. For convenience, I used Sage to find $\phi(m)$, but its easy to calculate it from the prime factors of $m$:
$p = 1065734711$, and
$q = 18273249403$,
since $$\phi(pq) = (p-1)(q-1)$$ when $p$ and $q$ are prime.

Sage isn't necessary for the subsequent calculations, since plain Python has arbitrary precision integer arithmetic, and an efficient power modulus function.

Code

m = 19474436171537127533
#print(factor(m))
#m = 1065734711 * 18273249403
#print(euler_phi(m))
phi = 19474436152198143420
E = 65537 # 2^16 + 1
#print(xgcd(E, phi))
# g, s, t : g = s * E + t * phi
# (1, -6901944375041675347, 23227)
#D = -6901944375041675347
#print(D+phi)
D = 12572491777156468073
# D*E % phi == 1
#print(D*E % phi)

@interact
def test(n=12345):
    # Encrypt
    a = pow(n, E, m)
    print(a)
    # Decrypt
    x = pow(a, D, m)
    print(x)

Output

10240177983085547351 
12345

And here's a live version of the script that you can play with, running on the SageMathCell server. (The script isn't stored on the server, it's encoded into the URL).

FWIW, this is essentially the process of cracking RSA, except that proper RSA uses a much larger modulus; these days it's recommended that $m$ be at least 1024 bits so $p$ & $q$ can't feasily be found.

Answer 2

It's essentially solving $$x ^ {2^{16} + 1} \equiv a \pmod n$$ ($x$ is the input, $a$ is the correct value, $n$ is the encryption key). It is called the discrete root problem, and it can be found quite efficiently if the factorization of $\phi (n)$ is known, if not - this problem is probably hard.