1
$\begingroup$

I am currently trying to reverse engineer a piece of software that uses a seemingly-custom encryption algorithm.

After disassembling the decryption part of the code, I've come up with the following code that decrypts the data file just as well as the original software:

void decrypt_one_run(uint8_t* four_bytes_to_decrypt, uint8_t* four_bytes_key) {
    uint8_t local_buffer[4] = { 0 };

    for (int i = 0; i < 4; i++) local_buffer[i] = four_bytes_to_decrypt[i] ^ four_bytes_key[i];

    local_buffer[3] = (local_buffer[3] >> 2) | (local_buffer[3] << 6);
    local_buffer[2] = (local_buffer[2] >> 5) | (local_buffer[2] << 3);
    local_buffer[1] = (local_buffer[1] >> 7) | (local_buffer[1] << 1);

    uint8_t magic_index = (local_buffer[0] ^ local_buffer[1]) ^ (local_buffer[2] ^ local_buffer[3]);

    four_bytes_to_decrypt[3] = (local_buffer[3] << 7) | (local_buffer[2] >> 1);
    four_bytes_to_decrypt[2] = (local_buffer[2] << 7) | (local_buffer[1] >> 1);
    four_bytes_to_decrypt[1] = (local_buffer[1] << 7) | (local_buffer[0] >> 1);
    four_bytes_to_decrypt[0] = (local_buffer[0] << 7) | (local_buffer[3] >> 1);

    local_buffer[3] = magic_table[magic_index];

    local_buffer[2] = (local_buffer[3] >> 7) | (local_buffer[3] << 1);
    local_buffer[1] = (local_buffer[3] >> 6) | (local_buffer[3] << 2);
    local_buffer[0] = (local_buffer[3] >> 5) | (local_buffer[3] << 3);

    for (int i = 0; i < 4; i++) four_bytes_to_decrypt[i] += local_buffer[i];
}

Where magic_table is an array of 256 values, first of which are 0x0, 0x1, and the further ones are seemingly random (but no repetitions, and all values of the table cover the whole range of 0x00..0xFF).

This routine is getting called with a pointer to the next 4 bytes in the file being decrypted, and a pointer to a 4 byte key in a circular buffer, and is able to successfully decrypt the file (I can see human-readable data inside it).

But for the test purpose, let's imagine we have only 4 bytes in total to encrypt/decrypt, and a single 4 byte key.

In order to construct the inverse routine that would encrypt the data I tried to take a simple bruteforce approach — iterate over magic_table until I find a value, subtracting which from the buffer in a similar fashion would give its index as a result.


bool encrypt_one_run(uint8_t* inbuf, uint8_t* four_bytes_key) {
    for (int i = 0; i < 256; i++) {
        uint8_t magic_buffer[4] = { 0 };
        magic_buffer[3] = magic_table[i];
        magic_buffer[2] = (magic_buffer[3] >> 7) | (magic_buffer[3] << 1);
        magic_buffer[1] = (magic_buffer[3] >> 6) | (magic_buffer[3] << 2);
        magic_buffer[0] = (magic_buffer[3] >> 5) | (magic_buffer[3] << 3);

        uint8_t local_inbuf[4] = { 0 };
        for (int j = 0; j < 4; j++) local_inbuf[j] = inbuf[j] - magic_buffer[j];

        uint8_t local_buf[4] = { 0 };
        local_buf[3] = (local_inbuf[3] >> 7) | (local_inbuf[0] << 1);
        local_buf[2] = (local_inbuf[2] >> 7) | (local_inbuf[3] << 1);
        local_buf[1] = (local_inbuf[1] >> 7) | (local_inbuf[2] << 1);
        local_buf[0] = (local_inbuf[0] >> 7) | (local_inbuf[1] << 1);

        uint8_t magic_chk = ((local_buf[0] ^ local_buf[1]) ^ (local_buf[2] ^ local_buf[3]));
        if (magic_chk == i) {
            printf("Magic value found!!! 0x%x (%i)\n", magic_buffer[3], i);
            
            local_buf[3] = (local_buf[3] << 2) | (local_buf[3] >> 6);
            local_buf[2] = (local_buf[2] << 5) | (local_buf[2] >> 3);
            local_buf[1] = (local_buf[1] << 7) | (local_buf[1] >> 1);
            
            for (int j = 0; j < 4; j++) local_buf[j] ^= four_bytes_key[j];
            // Output the encrypted value
            for (int j = 0; j < 4; j++) inbuf[j] = local_buf[j];

            return true;
        }
        else if (i == 255) {
            printf("Could not guess magic value!!!\n");
            return false;
        }
        else {
            continue;
        }
    }

    return false;
}

Now, when I encrypt something with encrypt_one_run I get a cipher, and feeding that back into decrypt_one_run gives me back the plaintext... except for times when it doesn't.

Quite often, on certain plaintext (some out of all possible combinations from 00 00 00 00 to FF FF FF FF), I see the encryption routine fail to guess the magic number (the string "Could not guess magic value!!" is printed).

What of my assumptions about the algorithm is not correct? Is it possible to create an encryption function in such a fashion at all?

Or could this be an off-the-shelf standard algorithm that I'm not aware of?

$\endgroup$

1 Answer 1

2
$\begingroup$

Turns out, what I am looking at here is an instance of a Feistel cipher.

The Feistel cipher structure involves splitting the plaintext being encrypted in half (in this case, 4 bytes were taken off an 8 byte input), and processing one half through a function (called the Feistel function) with an equal length round key. After that the result is XORed with the remaining half of plaintext, and the halves are swapped around before the next round happens.

One of the key features of the Feistel cipher architecture is that the Feistel function might be irreversible, which helps hinder analysis, but due to the nature of repeated XORs and swaps, the whole cipher is guaranteed to be reversible if the round keys are "fed" in reverse order.

Indeed, the Feistel function provided in the original post is not reversible — to perform an inverse transform, you would need to know the index inside the "magic table" to infer the values you need to subtract from the plaintext, but that would affect the actual bits that are used to calculate that index in the direct transform. And the bruteforce approach inverse function does not even converge (leading to my original question).

However, going a level up and feeding the round keys from the key array in the opposite order indeed encrypted the message, which was then successfully decrypted using the same key material in direct order and no modifications to the algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.