One Time Pad – Homebrew CTF Challenge

A few weeks ago was AlexCTF, and in that competition there was a cryptography challenge called “Many Time Secrets” with the description: “This time Fady learned from his old mistake and decided to use onetime pad as his encryption technique, but he never knew why people call it one time pad!”

The challenge then went on to give a hex encoded message what has been xor encrypted with a key. The trick here is that the same key, in this case the flag for the challenge, was used to encrypt every line. So by guessing the some of the key, which we know starts with “ALEXCTF{” we can slowly decrypt some of the message. Then by guessing the next part of the message, we can reveal more of the key. As we guess more of the message, more of the key is known. Which allows for more of the other messages to be known, which allows fore more guessing! Following through with this gives us the whole key/flag “ALEXCTF{HERE_GOES_THE_KEY}”

When I initially started working on this challenge, I found out about an attack on a one time pad that has reused a key. The attack is the many time pad attack. The setup is similar, you have a message that has been encrypted with a key. Then you have another message encrypted with the same key. However, in this case, the key is not known, and could be gibberish for all you know. So how do we recover the message? Well there is a really cool property of the xor operation that you can take advantage of when you have multiple things encrypted with the same key.

Note: For those that do not know, ⊕ is the bitwise xor operator. This means to take the xor individually of each bit pair of the message.

Ex. 1010 ⊕ 0111 = 1101

Let’s say you have two messages, M1 and M2, and you have a key, K. For otp encryption you would simply do

M1 ⊕ K=Encrypted

You would then send the encrypted text to whoever, and given that they have the key, all they have to do is

Encrypted ⊕ K=M1

But, when you have

E1 = M1 ⊕ K and E2 = M2 ⊕ K

something really interesting happens. You can xor the two encrypted texts together and completely remove the key from the equation! In other words,

E1 ⊕ E2 = M1 ⊕ K ⊕ M2 ⊕ K = M1 ⊕ M2

We’ve completely removed the unknown key from the equation! Now if we guess part of one of the messages, we would get the corresponding part of the other message! So, for example, if you are competing in a CTF and you know the flags start with “flag{” you would be able to guess that the flag is one of the encrypted lines, then all you have to do is xor each line with the line that contains the flag and you can start guessing away to reveal the flag.

For the many time pad attack, the method of discovering the message is identical to the original challenge. However, to get to this point, additional steps are required. Now I’ll leaved you with an actual message to try out the Many time pad attack yourself! (This is a CTF challenge with one of the lines starting with “flag{“)

34 4b 2a 49 01 29 73 64 6c 66 7b 44 10 11 73 6a 4c 4d 6d 5f 61 74 25 01 4c 33 1f 78 51
1e 4a 6b 42 4e 3a 21 6c 29 7b 7a 0b 45 2a 36 2b 4c 08 79 43 69 7d 27 01 56 33 48 25 14
39 0e 23 5a 57 2a 21 65 6c 69 6d 0c 10 3f 21 6e 40 19 2a 44 60 73 2c 46 4b 7c 5e 69 5b
05 5a 6b 4f 49 2a 21 62 67 6d 3f 1c 59 35 36 2b 51 0c 6e 1c 28 69 2d 01 4c 34 5e 7f 14
19 5d 6b 4c 49 2e 75 2d 40 28 7e 05 10 2d 20 62 4f 0a 2a 5e 67 6d 6c 01 70 39 4d 6e 14
1e 41 3c 1b 48 3c 21 79 61 6d 3f 1b 55 3b 26 79 44 4d 67 55 7b 69 23 46 5d 72 1f 26 19
16 42 2a 5c 5a 7f 6f 3e 56 3f 2e 05 03 07 23 3f 45 32 67 03 3c 74 77 7e 08 32 5c 38 49

~T