Reversing algorithm using bitwise OR operator

3therk1ll 0
Viewed 59

I'm working on a problem whereby I am trying to take a string which has been encrypted using a known algorithm and key to it's original plaintext value.

The algorithm uses an XOR operating and bit shifting to encrypt the plaintext.

I have been working on the assumption which appears partially correct, that this process can be reversed by performing a bit shift in the opposite direction and then an XOR operation, as below.

WHERE
c = a ^ b
THEN
a = c ^ b

The encryption function generates a key via rand() which is seeded by a known value, the result of time(NULL). Given the known seed for rand() I can regenerate the keys.

This generally works fine and I am able to generate some of the correct characters from the encrypted input. You can see in the screenshot below some of the original string, "ABCDEFGHIJKLMNO" being decoded correctly.

enter image description here

The problem I have (I think) is the below line within the encryption function.

input[pos] = input[pos] << key | input[pos]  >> 8 - key;

My understanding is the bitwise OR within C is lossy and cannot be reversed or original inputs recovered. I am slightly stumped on how to overcome this issue without creating a new script to simply brute force each position by encrypting all possible characters and looking for a match.

This is an example of what I am doing with an encryption and decryption function. Note that the encryption function is what comes with the exercise and I don't have the option of modifying it.

How can I overcome this or is it simply not possible?

#include <stdio.h>
#include <stdint.h>

void decrypt(int pos);
void encrypt(int pos);

char input[] = "ABCDEFGHIJKLMNO";

int main() {

    long input_len = sizeof(input);
    // Hardcoding for consistency when testing
    // int seed = time(NULL);
    int seed = 1663606418;
    srand(seed);

    for(int i = 0; i < input_len; i++) {
        encrypt(i);
    }

    printf(input);
    printf("\n\n");

    // Reseeding to get the same order for rand() when decrypting
    srand(seed);
    for(int i = 0; i < input_len; i++) {
        decrypt(i);
    }

    printf(input);
}

void encrypt(int pos) {
        int r1 = rand();
        int key = rand() & 7;
        input[pos] = input[pos] ^ r1;
        input[pos] = (input[pos] << key) | (input[pos]  >> 8 - key);
}

void decrypt(int pos) {
        int r1 = rand();
        int key = rand() & 7;
        input[pos] = (input[pos] >> key) | (input[pos]  << 8 - key);
        input[pos] = input[pos] ^ r1;
}
encryption c
1 Answers

The OR operation in input[pos] << key | input[pos] >> 8 - key is not intended to OR overlapping bits, so it would not lose information. It is intended to perform a “rotate” operation, where the bits are rotated left by key positions, and the ones that are rotated out of the low eight bits by that are made to reappear coming “from the right.” That is what the >> 8 - key part does.

However, your input elements have a char type, which is likely signed. The encryption gives some of them negative values. Then, when decryption operators on input[pos], the negative value is widened to an int, likely using two’s complement. This yields extra set bits above the eight bits it should operate on, so the data used in the operations is wrong.

One fix would be to change char input[15] = "ABCDEFGHIJKLMNO"; to unsigned char input[15] = "ABCDEFGHIJKLMNO";.

Another would be to change input[pos] = (input[pos] >> key) | (input[pos] << 8 - key); to:

unsigned char t = input[pos];
input[pos] = t >> key | t << (8 - key);

A similar change should be made in encryption, too. Either the use of non-ASCII characters or an r1 with bit 7 set can result in negative values, in input[pos], causing the same issue.

Eric Postpischil0
Related