2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ you should try to find sensible keys of 8 bits at a time instead of finding possible 32 bit keys. $\endgroup$ – Name Jun 12 '16 at 15:52
  • $\begingroup$ Do you understand what this (((mysecretvalue>>(8*(i%4)))&255)) does ? $\endgroup$ – Biv Jun 13 '16 at 7:05
  • $\begingroup$ Shifts 8 bits to the left (or right?) and the &255 is related to keeping it 8 bits long or something? $\endgroup$ – Tom Jun 13 '16 at 7:31
  • $\begingroup$ 8*(i%4) is going to equal 0, 8, 16, 24 (then repeat), due to i incrementing. So the shift varies, and you are right the &255 is taking the lowest byte of the shifted value. It's not anything like a modern cipher that would be used for anything meaningful, you basically use educated guesses and stats to break this. $\endgroup$ – Neil Slater Jun 13 '16 at 12:20
3
$\begingroup$

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 = 28−1 = 111111112 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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