Join Log in
Score:1
akasaka avatar Crypto

Identifying an encryption algorithm and/or writing an encryption function

nf flag
akasaka

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?

71
1 + 0
Score:2
akasaka avatar Crypto
nf flag
akasaka

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.

+ 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.