Reversing a known encryption algorithm (4-byte repeating key XOR)

Question

I've been practicing for an upcoming CTF competition, and I've finally reached the cryptography stage. I'm a complete newbie in this field (my knowledge is essentially that bcrypt is awesome and md5 sucks haha).

This is the challenge:

This is my cipher algorithm:

mysecretvalue = ???;
mysecretmessage = ???;
for (i=0;i<strlen(mysecretmessage);i++)
{
    mysecretmessage[i] ^= ((mysecretvalue>>(8*(i%4)))&255);
}
echo strhex(mysecretmessage);

and my output:
e971de14d87fc406c67fc41ac570c3528a4ec216da7fc2168a78df018a70d50bde3ed31bcb72dc16c479d500863ee71ad07fc2178b3ee012d96dc71cd87a9007c53ec41bcf3ec31ade7b901ad93edd0ad97bd301cf6ac612c66bd553c3709017cf7dd91ecb729e53ed71df178a49df01c13f

Decode it! ;)

I'm more interested in a general method of solving such challenges, however if you want to solve this one as an example it will be appreciated as well!

P.S This is all the info the challenge provides. I couldn't find a function named strhex so I assume it's pseudo-code albeit it does look pretty similar to Javascript.

Answer 1

The actual "encryption" is done on this line:

mysecretmessage[i] ^= ((mysecretvalue>>(8*(i%4)))&255);

Clearly, this line XORs every byte (or at least, every element; but it makes sense to assume that this is indeed a byte array) of mysecretmessage with some value derived from mysecretvalue and the byte counter i.

So what does the expression ((mysecretvalue>>(8*(i%4)))&255) actually return?

The counter i only appears in the subexpression i%4, which divides it by 4 and returns the remainder. So from this we can already tell that, whatever else the expression might be doing, its value will repeat every 4 bytes. So we're looking for a repeating 4-byte key that, when XORed with the byte sequence given in hex below, will yield a meaningful (and thus presumably the original) message.

(In fact, all that the rest of the expression ((mysecretvalue>>(8*(i%4)))&255) is doing is taking a 32-bit integer mysecretvalue and extracting the i%4-th 8-bit byte from it. It does this by shifting the bits of mysecretvalue right by 8*(i%4) bits, and then taking the bitwise AND of the result with 255 = 2⁸−1 = 11111111₂ in binary to extract the lowest 8 bits of it.)

So this is basically XOR encryption with a 4-byte repeating key. If your message was exactly 4 bytes long, and the key was randomly chosen, then this would be an unbreakable one-time pad. Since the message is longer than the key, however, it becomes a "many-time pad", which is easy to break.

There are many standard techniques and even automated tools to break this type of repeated-key encryption. A simple approach is to split the message into 4-byte segments, take the first byte of each segment, and search for a byte that, when XORed with each of these bytes, yields mostly printable ASCII characters, with frequencies approximating those of English text. Then repeat for the second byte of each segment, and so on.

Another method is "crib dragging". Basically, you guess an $n$-byte sequence (the "crib") which is likely to occur in the plaintext message, and try to XOR it with each consecutive $n$-byte substring of the ciphertext. Likely cribs for English text include the most common English words surrounded by spaces, like "the" (5 bytes), "and" (5 bytes), "that" (6 bytes) and so on.

Each crib in each position will yield a candidate key (or a partial key) which you can then use to try to decrypt the message and see if the result makes sense. (If the crib is longer than the expected key length, you can immediately rule out most positions by checking whether the candidate key repeats as expected.) This process can also be fully or partially automated using statistical analysis tools.

Once you have the message and the repeating 4-byte key, simply writing out the key bytes in hex, from right to left (since the encryption code starts with the lowest byte), will then give you the mysecretvalue in hex if you want it.