Any pointers on this troublesome algorithm?
 

For a few weeks now, I've been trying to figure out a cryptography problem that I just couldn't wrap my mind around, and I think I might need guidance and/or recommendations on where to learn more about the math/logic behind it.

I've got an program whose decryption method I want to reverse engineer; I know the exact decryption routine and subroutines, I know the encryption key(s) used in the process, and I've already analyzed it and created a fully working PoC decrypter whose input is legitimate license file data and whose output is the decrypted license data in a hex dump-like format (only 64 bytes).

I have multiple license files (which they allow)—all of which are radically different in terms of original encrypted data, but whose decrypted data is all the exact same except for one single 4-byte value, which is seemingly random and pre-determined upon license file generation. In other words, every license file decrypts to the same exact values each time, but that one DWORD in the decrypted data is different across the different license files; the other remaining 60 bytes are exactly the same across all of the files.

To exemplify this, I've noted the data of 3 legitimate license files below:
However, when each of these files is decrypted, they produce the following output, respectively:
In terms of algorithm specifics, it's a 17-pass loop whose output is directly fed as its input. On the first step of decryption, the input data is recursively multiplied against itself to produce a temporary key. However, the only exception is the last pass (pass 17), during which the output of step 16 is multiplied against the original encrypted file data to produce the temporary key.

With my current level of knowledge, I'm not sure how this would be able to be reversed, since one of the first steps would involve knowledge of the final output, which would be seemingly impossible. =/

At this stage, I need help reversing the process. I only want to create a PoC encrypter; I don't want to patch the program or otherwise bypass the mechanism. Is there anywhere I can go from here?

It's verbosely commented and kind of messy-ish, but you can find the source code for my PoC decrypter here:


NOTE: I decided to post in General Discussion because of the educational opportunities I'm hoping to gain from this (so I can start contributing more), but feel free to delete this thread if it's too request-y for this section. ^^;

It's an interesting algorithm. I looked, but I am not good enough to solve it :(

Just wanted to let you know that some people saw this and tried. Maybe others have thoughts?

From the description you provide I can guess it is something asymmetric.
16 steps may be x^2 16 times, then step 17 +x. Totally 65537 prime.
Then full algo may be powmod(data, 0x10001, N), where N == magic?

void decode_1(unsigned int *src, unsigned int iter, unsigned int *dest) = bigint.mul
void decode_2(unsigned int *src, unsigned int *key) = bigint.sub

...Woah. I think that just kind of blew my mind. It makes a lot more sense, now that I look at it and step through it as a whole instead of as individual functions.

I manually calculated the return values in each step of the process using your advice, with the first 16 iterations being (x^2)%N where x is the data, and the last being (x*y)%N where x is the data and y is the original data, and sure enough, the result was exactly as expected!

Checking your proposed algorithm of (data ^ 0x10001) % N, it also yields the exact same results, which is kind of unreal to me at this point that it can be simplified so easily. Thank you so much! :D

You described it at such a base level and with such ease that I can't help but be impressed; for the sake of additional learning opportunities, how would you suggest that I build upon these kinds of skills? Would reversing crackme challenges be helpful, or would you recommend something else?

You can be even better. Recipe: read books, get online courses, take part in the forums and conferences and, for sure, work a lot in the area you like. If you will do at least half of noted above you become a real pro very soon. ;)

Your algorithm is one form of fast binary exponentiation, known as exponentiation by squaring. It is a common algorithm for asymmetric cryptography since it is much more efficient than naive multiplication. It is, for instance, an important core of RSA and algorithms based on discrete logarithms. Variations do also exist for other domains, such as the double-and-add algorithm for elliptic curves.

For x ** e mod n, you calculate x * (x ** 2) ** ((n-1)/2) if n is odd (square and multiply), otherwise (x**2)**(n/2) (square).

To exemplify:

x=17
e=33
n=73

33 is the same as 0b100001.

1. square -> 17 * 17 = 70 mod 73 = x ** {0b10}
2. square -> 70 * 70 = 9 mod 73 = x ** {0b100}
3. square -> 9 * 9 = 8 mod 73 = x ** {0b1000}
4. square -> 8 * 8 = 64 mod 73 = x ** {0b10000}
5. square -> 64 * 64 = 8 mod 73 = x ** {0b100000}
multiply -> 8 * 17 = 63 mod 73 = x ** {0b100001}

In (not so great) python code it looks as

Ahh, just did a bit of research into some of the specifics of prime calculations and discrete logarithms in cryptography, and this does certainly seem to match up with that. Thanks for the detailed explanation, t3xc0d3!

I can't find anything on easily reversing modular exponentiation other than brute force, but would brute force really be the only option to approaching this with such large inputs?

Generally speaking, yes. If a general algorithm that is simpler than brute force would exist, then the cryptosystems would not longer be secure. To be exact, it is it known if simpler methods exist. It *might* be the case, but they have not been found.

One thing you might try is to analyse if they have been included their secret key somewhere. You will not find anything, if they have done their homework. However, I have found private RSA keys in binaries several times...

In addition, if you are able to determine which algorithm they use and which configuration (e.g., which prime values, ...) they use, you might be able to find an attack vector. If they used a insecure configuration (e.g., too short primes), you win. The analysis can (will) be really cumbersome.

>> I have found private RSA keys in binaries several times...
thats just a biggest mistake whatsoever :)

The general number field sieve is faster than a naive brute force, and there are a variety of other techniques to reduce prime checking in DLs. It is sub-exponential but seems to be above polynomial in time to find a solution.

I would suggest studying discrete mathematics, computer algebra, cryptography and algorithms if you want to be great at reversing these types of scenarios. Sitting and looking at assembly code is not so helpful if you are not versed in the algorithms and mathematics behind what is going on. However it is a theoretical and long journey to master. You can known Fermat's little theorem and Carmichael numbers and other useful tools in primality testing and modular exponentiation and so forth.

An example solution which is more efficient than exhaustive brute force is as follows: given b^l=n (mod p) and you want to solve for the smallest l with just normal integer sizes:

If you can explain the mathematics behind it, then you will be at a very good problem solving level in this area.

After working on this off and on for quite a while, I can't seem to really find any way to crack this. However, one thing I have noticed is that each of the generated ciphertext all have a GCD of 9. Is it a common expectation of RSA-generated ciphertexts to have a similar GCD, or does the fact that they all have a GCD > 1 mean that the possibilities can be reduced by any amount?

Thanks again for the helpful advice! I've been studying crypto more, but couldn't quite find whether this situation was expected or whether it indicated a vulnerability in this particular implementation.

It looks like it is not encryption/decryption but RSA signature verification/signing:

Notice the 0001 which generally indicates PKCS#1 v1.5 RSA signing/private key.

See the RFC for yourself on page 9.

What you show is not "decryption" but "verification" using the public exponent of a signature. After all the 0xFF there is a 0x00, then an ASN.1 code and finally a hash of a message being signed.

So you are looking for a private key used to sign messages.

Using chosen plaintext attacks, you might find a way to break this so that you can sign messages without even knowing the private key as long as you can verify signed messages and if the padding is bad. I suggest looking up chosen ciphertext attacks against RSA and look up Bleichenbacher in particular.

If the public exponent is low enough (like e=3), then you can forge messages almost certainly. Using mere small numbers and cube/cube root properties if the padding is not checked properly.