Right before DEF CON, a friend of mine reached out to me toask if I would write a crypto challenge for his CTF. While it was a busy timefor me, I didn't want to pass up the chance and so I wrote two challenges forthe "Way of the Cryptologist ."

The first challenge was to turn a decryption oracle (asystem which decrypts data for you) into an encryption oracle (a system whichencrypts 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 nextchallenge. 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, wecan modify the ciphertext and produce different messages. We can also see whatchanges we've made to the ciphertext, given that we have a decryption oracle. 

As the block cipher mode used is CBC (we can tell becauseany bit flip garbles the modified block and flips the corresponding bits of thenext block) we can make arbitrary changes to any block at the cost of garblingthe previous block. Since we don't care about the contents of the decryptedmessage except that it must contain the string "foobar", this makes our workeasy.

We change one block (we'll call it block N) of theciphertext to all zeroes, and then submit the ciphertext to the decryptionoracle. 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, bothencrypted using the one-time pad (OTP) algorithm.  OTP is mathematically proven to have aproperty called "perfect secrecy" when used correctly, which means that anattacker can gain no information about the plaintext by looking at thecorresponding ciphertext. However, there are still attacks against OTP,especially when it is used incorrectly. One way to use it incorrectly thatrenders the cipher pretty much useless is to use the same key for multiplemessages. This mistake was used to decrypt messages during World War II and wasalso a problem in WEP and PPTP.

The ciphertexts are:

ecc8852cf33bd51a64b04b50a4469070e13851a3cb9bdc49dc0908af37756e08e03d2dfb0d368787785aa53223c55d8bb84f02a566db7d84582890343f02ae90e34f8048075a9ea00acfb48706d817bb126e830825c23f19c4c32c5caa39b0c5ca67652e43ecc8857ebb34c60730e75948aa53d427fc3c58a3d99f885593460de02d696a4bf76f38ea0e35ce97705eae38388b7c82b10e12a63d98739b1d7c8d712c03b4d5ec569748154789f40ccfbed34fc619b51366c2132a8d255f81a0205aac27bdd4d72e2e2e67

In case you haven't already guessed, both ciphertexts wereencrypted using the same key.  You cansee patterns in the two ciphertexts, especially at the beginning. The firstthree bytes are the same, which has only a 1 in 16,777,216 chance ofhappening by accident.

The attack against reuse of one-time pad keys begins bycalculating ciphertext1 XOR ciphertext2. Since an OTP-encrypted message is justmessage XOR key, anything XOR itself is 0 and anything XOR 0 is itself, we canbreak 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, Englishhas enough redundancy that we can recover both messages! To do this, we use a techniqueknown as "crib dragging". A "crib" is a known or guessed piece of plaintext. Wethen take this crib and "drag" it along our message1 XOR message2, XORing thecrib against various parts of the message until we see a result that makessense within the context of the message, provided by where we got theciphertexts.

I wrote a script for performing crib dragging interactively;we can see the output below, using the crib "bitcoin" as the party wasbitcoin-themed.

This input produces lots of candidate outputs. The ones mostlikely to be correct (as they use alphanumeric characters and commonpunctuation) are those preceded by asterisks:

Candidate 39 looks very promising; we see "rapher " whichcould very well be the end of the word "cryptographer". So, next we use thecrib " cryptographer":

The theme of the party was "LOL Bitcoin" so candidate 31 isthe clear choice. We continue on in this way, reconstructing more and more ofthe messages until we are given the clue to get us to the next phase of theparty 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.