Reverse decryption algorithm

Question

I've been working to disassemble a decryption algorithm for a particular software. The way it works is that the serial key contains all the appropriate information, gets crunched in the algorithm which outputs plaintext data (It's actually binary data but this is not that important here).

I now want to create an algorithm which will re-encrypt arbitrary data.

After some work I managed to greatly reduce the code base for the decryption process. Here is how it works :

BigUnsigned hash_func(BigUnsigned serial, BigUnsigned running_value, BigUnsigned encrypt_key)
{
    return (serial * running_value) - (((serial * running_value) / encrypt_key) * encrypt_key);
}

void do_the_thing()
{
    BigUnsigned key1 = hash_func(buSerial, buSerial, buEncryptKey);
    BigUnsigned key2 = hash_func(buSerial, key1, buEncryptKey);

    BigUnsigned result = 1;
    int key_select = 0;
    unsigned int weird_number = 0xc3530000;
    for(int i = 0; i < 8; ++i, weird_number *= 4){
        result = hash_func(result, result, buEncryptKey);
        result = hash_func(result, result, buEncryptKey);
        if(weird_number >> 30){
            key_select++;
            if(key_select < 3){
                result = hash_func(result, key2, buEncryptKey);
            }else{
                result = hash_func(result, buSerial, buEncryptKey);
                if(key_select == 4){
                    key_select = 0;
                }
            }
        }
    }
}

both buSerial and buEncryptKey are 16 unsigned int (512-bits). I don't get how I can create an algorithm that encrypt new data from this. The problem I have is that key2 is generated from the final result which I don't know beforehand.

I'm using this BigInt library

Answer 1

Do you have any more information, especially, one or two examples for buEncryptKey? Is that a prime number?

The reason i'm asking is: your hash_func is a modulo function, it calculates (serial*running_value) % encrypt_key. This makes key1 = serial^2%encrypt_key and key2 = serial*(serial^2%encrypt_key)%encrypt_key = serial^3 % encrypt_key. And polynomials modulo prime numbers are often used in CRC calculations, or Fletcher's checksum.

The rest of the loop calculates (result^4 % encrypt_key), and then result*(serial^3) % encrypt_key, or (result*serial % encrypt_key), depending on some bits in weird_number.

However, your key_select seems a bit fishy - could you please make sure that key_select is calculated this way, and isn't just (weird_number >> 30) & 0x03 ? The way weird_number is treated in the loop would make it logical to check 2 bits of it in each round (which coincides with the multiplication with 4), and i'd expect 2 of the bits in weird_number to be used to select one of your if-else cases; in your code right now, it doesn't make sense to use 2 bits of weird_number at once. (Also, it doesn't make sense NOT to mask the higher bits away, but as weird_number is just a 2-byte integer anyway, they'll get thrown away with each shift).

Once you get the maths of your function right, you might be able to find it on the internet, or maybe the people of math.stackexchange.com or crypto.stackexchange.com might have a pointer where this algorithm is used, and how to create a matching reverse function.

UPDATE

<rant>

On a totally unrelated problem at work today, i checked the contents of two different SSL client certificates. One of them said: modulus (large hex number), exponent: 0xbf0453. The other said: modulus (different large hex number), exponent: 0xcd01b7. Then i thought of your weird_number and had an idea. Then i googled for rsa algorithm. And now, i think i know what's happening.

</rant>

From Wikipedia about signing messages using RSA:

When Bob receives the signed message, he [...] raises the signature to the power of e (modulo n) [...], and compares the resulting hash value with the message's actual hash value.

This is exactly what your algorithm is doing. It optimizes the math a bit, by calculating x^4 in each loop, and then factoring in x or x^3 depending on 2 bits of the exponent. This seems to be a variation on Montgomery's ladder technique, that uses 2 bits at once instead of one bit.

e is your weird_number (50003, only the high 16 bits are used), and n is your encrypt_key. (You might want to make sure i'm correct by letting your BigInteger library calculate serial^50003 % encrypt_key) and compare the result to your "plaintext data", i didn't actually check it.)

To calculate the input, you'll need the signing algorithm, from the same paragraph in Wikipedia:

Alice wishes to send a signed message to Bob. She can use her own private key to do so. She produces a hash value of the message, raises it to the power of d (modulo n) [...], and attaches it as a "signature" to the message.

To calculate the input, you need n (which you have) and d (which you don't have). To calculate d, you need to factor n into its two generating prime numbers (p, q) where n=pq. This fits with Wolfram Alpha saying n is not a prime, but, unfortunately, finding these numbers is hard - after all, the algorithm is designed to be uncrackable. However, 512 bits isn't state of the art anymore, and the crypto.stackexchange.com guys say factorization of a 512 bit number is quite feasible today.

Still, you'll probably have to invest a lot more time to reach your goal. Sorry to deliver bad news.