I've been fascinated by the science of encryption and decryption of confidential messages for as long as I can remember. Maybe it was back when I was a kid and my elder sister showed me an instance of the Pigpen Cipher, or maybe it was when I bought Kjartan Poskitt's excellent text, Murderous Maths: Codes. At the time, I was exposed only to some really simple substitution and transposition ciphers, but they excited me to the point that I had to delve into the realm of cryptology.
Apart from learning Haskell and some Lambda Calculus during these vacations, I also decided to take the Cryptography I class on Coursera, taught by Professor Dan Boneh. A part of the Week I homework was a specific programming assignment which asked the students to attack the many-time pad. The many-time pad is just like the one-time pad; the keys, however, are not unique for individual messages. This necessarily removes the "uncrackable-ciphertext" factor that OTP is famous for: since the same key is being used for more than one message, XORing both the ciphertexts yield the XOR of their individual plaintexts. Assuming our plaintexts to be in English, we can use the redundancy of the language to break the ciphertext and retrieve them.
The assignment provided us with 10 ciphertexts encrypted using the same pad and their individual outputs encoded in hex. This was the target ciphertext:
Using the fact that XORing an alphabet with a space changes its case, I wrote a Python function which basically XORs every provided ciphertext (apart from the target) with every other ciphertext (except itself), character by character. Then I checked if any of the XORd characters was an alphabet. In case there was an alphabet at the position, say k, I used this alphabet to contruct the key. In case there wasn't, I padded a 0 in that place. Here are the functions I used:
Using this unveiled the key partially. Here's what I got:
See a lot of 0s there? Those were the places where I wasn't able to make any progress.
Then I used this key again and again, XORd individual ciphertexts to partly unveil their plaintexts, and using some common digrams and trigrams, I was finally able to retrieve the key. Although, the process was a bit time consuming. Here's the final key I got:
XORing this key with the target ciphertext unveiled the following plaintext:
The secret message is: When using a stream cipher, never use the key more than once
That's a really good advice now, isn't it?