0
$\begingroup$

I have a binary code which decrypts some 64-byte data chunks.

There is a decryption key which is always static, and there is a code which does actual decryption. What I need is to find out which algorihtm does it use (probably it is something common enough which I just failed to identify) and find how to encrypt data for this code to decrypt.

The code treats both data chunks (512-bit data and 512-bit key) as series of 32 little-endian 16-bit integers, with least significant being the first one, and handles them as such. There are functions which perform addition, substraction, comparison, division and multiplication on those numbers; I named these functions superlong_add, superlong_sub etc.

Actually, both data and key are byte-inversed before processing, and then the result is byte-reversed back. So they are probably stored as big-endian, but converted to little-endian for processing. Not sure if it is useful.

Here is the actual decryption code. It is in C, but might be somewhat incorrect because it is just hand-written after disassembling binary code:

// Substract value from target, result is left in target.
void superlong_sub(uint16_t target[0x20], uint16_t value[0x20]);

// Return 1 if a > b, -1 if a < b, 0 if they are equal
int8_t superlong_compare(uint16_t a[0x20], uint16_t b[0x20]);

// Add other to target, place result in target.
// Return 1 if there was overflow, 0 otherwise
uint8_t superlong_add(uint16_t target[0x20], uint16_t other[0x20]);

// Multiply `other` by `small`, and substract the result from `target`.
// Return 1 if overflow happened, 0 otherwise.
uint8_t superlong_mulsub(uint16_t target[0x20], uint16_t other[0x20], uint16_t small);

// Multiply a by b, place result to target
void superlong_multiply(uint16_t target[0x40], uint16_t a[0x20], uint16_t b[0x20]);

// This is some "complex" operation which forms the main body of algorithm.
// It takes a buffer and a key, and applies some calculations to the buffer,
// without changing key in any way.
void decode5(uint16_t buf[0x40], uint16_t secret[0x20]) {
    // pointer starts from the middle of the big buffer,
    // and then is moved back by one position on each iteration
    // until it reaches the beginning of the big buffer.
    uint16_t* current = buf + (0x40/2); // middle
    bool flag = false;

    for(uint8_t i = 0x21; i>0; i--) {
        if(!flag) {
            if(current[31] != 0) {
                if(superlong_compare(current, secret) >= 0) {
                    superlong_sub(current, secret);
                    flag = current[31] != 0;
                } else {
                    flag = true;
                }
            }
        } else {
            // Take two most significant values from current buffer
            // to form one 32-bit number.
            // It is safe to access current[32], because this code will only be achieved
            // after we advanced the pointer at least once.
            uint32_t fc = current[32] << 16 | current[31];
            // divide by secret's most significant value (it is always 0xd015 in my case)
            fc = fc / secret[31];
            if(fc > 0xffff) {
                fc = 0xffff;
            }
            if(superlong_mulsub(current, secret, fc) == 0) {
                // no overflow in mulsub
                uint32_t tmp = superlong_add(current, secret); // 1 if overflow else 0
                tmp += current[32];
                current[32] = tmp;
                if(tmp & (1<<16) != 0) {
                    // most likely "superlong_add gave overflow and f10[32] was 0xffff"
                    tmp = superlong_add(current, secret);
                    current[32] += tmp;
                }
            }
            flag = current[31] != 0;
        }

        // advance pointer
        current --;
    }
}

// data is the encrypted data, secret is the decryption key.
// After this function exits, data buffer contains decrypted data.
void decrypt(uint16_t data[32], const uint16_t secret[32]) {
    uint16_t buffer[32];
    uint16_t bigbuf[64];

    memcpy(buffer, data, sizeof(data));

    for(int i=0x10; i>0; i--) {
        superlong_multiply(bigbuf, buffer, buffer);
        decode5(bigbuf, secret);
        memcpy(buffer, bigbuf, sizeof(buffer));
    }
    superlong_multiply(bigbuf, buffer, data);
    decode5(bigbuf, secret);
    memcpy(data, bigbuf, sizeof(data));
}

So my questions are:

  1. Is this some commonly known algorithm or something "home-made"?
  2. Does it look like a symmetric or asymmetric encryption? I.e. can I use the same key for encryption or shall it be some different key?
  3. How would I encrypt data for this algorithm to decrypt?

Thanks.

UPD This turned out to be a plain good old RSA.

The decode5 function is a modulus calculation (aka superlong_mod).

The decrypt function can look like this in Python:

def decrypt(message, N):
    tmp = message
    # calculate message ** 65536 mod N
    for _ in range(16):
        tmp = (tmp ** 2) % N
        # or: tmp = pow(tmp, 2, N)
    # and convert it to message ** 65537 mod N
    return tmp * message % N

And this is absolutely equivalent to the well known

return pow(c, 65537, N)
$\endgroup$
1
$\begingroup$

It looks homemade, like it does a minimum of transposition of characters and a lot of math to obfuscate the buffers.

This: for(int i=0x10; i>0; i++) { ... }

I do not believe that will do what you think it will do.

$\endgroup$
2
  • $\begingroup$ Huh, you're right regarding ++. Obviously that is --, this is just a typo of mine. Will edit. $\endgroup$ – MarSoft Nov 14 '20 at 23:13
  • $\begingroup$ Just a good old RSA with e value of 65537, as it turned out... $\endgroup$ – MarSoft Nov 16 '20 at 22:49

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