The Way of the Cryptologist
Right before DEF CON, a friend of mine reached out to me to ask if I would write a crypto challenge for his CTF. While it was a busy time for me, I didn't want to pass up the chance and so I wrote two challenges for the "Way of the Cryptologist ."
The first challenge was to turn a decryption oracle (a system which decrypts data for you) into an encryption oracle (a system which encrypts data for you). The decryption oracle script looked like this:
The script takes a single URL parameter "c" and decrypts it. The initial ciphertext provided gives the first half of a URL to the next challenge. The script then checks the decrypted message to see if the string "foobar" is in it. If so, it provides the second half of the URL.
Since the script does not perform any integrity checking, we can modify the ciphertext and produce different messages. We can also see what changes we've made to the ciphertext, given that we have a decryption oracle.
As the block cipher mode used is CBC (we can tell because any bit flip garbles the modified block and flips the corresponding bits of the next block) we can make arbitrary changes to any block at the cost of garbling the previous block. Since we don't care about the contents of the decrypted message except that it must contain the string "foobar", this makes our work easy.
We change one block (we'll call it block N) of the ciphertext to all zeroes, and then submit the ciphertext to the decryption oracle. We then take the decrypted value of block N+1 and XOR it with the string "AAfoobar" and use this as the new value of ciphertext block N. This results inblock N+1 decrypting to "AAfoobar" which completes our challenge.
The next challenge provides you with two ciphertexts, both encrypted using the one-time pad (OTP) algorithm. OTP is mathematically proven to have a property called "perfect secrecy" when used correctly, which means that an attacker can gain no information about the plaintext by looking at the corresponding ciphertext. However, there are still attacks against OTP, especially when it is used incorrectly. One way to use it incorrectly that renders the cipher pretty much useless is to use the same key for multiple messages. This mistake was used to decrypt messages during World War II and was also a problem in WEP and PPTP.
The ciphertexts are:
ecc8852cf33bd51a64b04b50a4469070e13851a3cb9bdc49dc0908af37756e08e03d2dfb0d368787785aa53223c55d8bb84f02a566db7d84582890343f02ae90e34f8048075a9ea00acfb48706d817bb126e830825c23f19c4c32c5caa39b0c5ca67652e43ecc8857ebb34c60730e75948aa53d427fc3c58a3d99f885593460de02d696a4bf76f38ea0e35ce97705eae38388b7c82b10e12a63d98739b1d7c8d712c03b4d5ec569748154789f40ccfbed34fc619b51366c2132a8d255f81a0205aac27bdd4d72e2e2e67
In case you haven't already guessed, both ciphertexts were encrypted using the same key. You can see patterns in the two ciphertexts, especially at the beginning. The first three bytes are the same, which has only a 1 in 16,777,216 chance of happening by accident.
The attack against reuse of one-time pad keys begins by calculating ciphertext1 XOR ciphertext2. Since an OTP-encrypted message is just message XOR key, anything XOR itself is 0 and anything XOR 0 is itself, we can break down ciphertext1 XOR ciphertext 2 as follows:
Ciphertext1 XOR ciphertext2
Message1 XOR key XOR Message2 XOR key
Message1 XOR Message2 XOR key XOR key
Message1 XOR Message2 XOR 0
Message1 XOR Message2
This is where it gets interesting. As it turns out, English has enough redundancy that we can recover both messages! To do this, we use a technique known as "crib dragging". A "crib" is a known or guessed piece of plaintext. We then take this crib and "drag" it along our message1 XOR message2, XORing the crib against various parts of the message until we see a result that makes sense within the context of the message, provided by where we got the ciphertexts.
I wrote a script for performing crib dragging interactively; we can see the output below, using the crib "bitcoin" as the party was bitcoin-themed.
This input produces lots of candidate outputs. The ones most likely to be correct (as they use alphanumeric characters and common punctuation) are those preceded by asterisks:
Candidate 39 looks very promising; we see "rapher " which could very well be the end of the word "cryptographer". So, next we use the crib " cryptographer":
The theme of the party was "LOL Bitcoin" so candidate 31 is the clear choice. We continue on in this way, reconstructing more and more of the messages until we are given the clue to get us to the next phase of the party access challenge.
My interactive crib dragging tool will be open-source, free, and publicly available soon. Note that this attack on reused keys in the OTP algorithm also works with any stream cipher, so despite the fact that few people actually use OTP in a modern context, many people use stream ciphers and reuse keys, making this script rather useful in general.