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:

32510ba9babebbbefd001547a810e67149caee11d945cd7fc81a05e9f85aac650e9052ba6a8cd8257bf14d13e6f0 a803b54fde9e77472dbff89d71b57bddef121336cb85ccb8f3315f4b52e301d16e9f52f904

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:

def check_for_space(string, counter):
  for message in messages:
    if message is not string and counter < len(message):
      current_char = chr(ord(message[counter]) ^ ord(string[counter]))
      if not c.isalpha():
        return False
  return True

def constuct_key():
  for i in range (max(map(len, msgs))):
    space = False
    for message in messages:
      if i < len(message) and check_for_space(message, i):
        KEY.append(chr(ord(message[i] ^ ord(' '))))
        space = True
    if not space:
      key.append(chr(0))      #Pad 0 in places where key is not revealed.

Using this unveiled the key partially. Here's what I got:

66390000c90000cb9800002acd0000102e000000007f0000a0000000002900000000000000f800000000007000800066c 763000012000000000000d05ba98700005d00fcec0000003a00008b60bf00003c000000000000000000ed000000000000cf0 00000000000006edba8c20000007c0000000000000045020000000000ba000078009111000000000000000200c4ab000000 a900000000008a0082d10000320000000000000000050000911f3edfd73e8333e8463df984ee

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:

66396e89c9dbd8cc9874352acd6395102eafce78aa7fed28a07f6bc98d29c50b69b0339a19f8aa401a9c6d708f80c066c76 3fef0123148cdd8e802d05ba98777335daefcecd59c433a6b268b60bf4ef03c9a611098bb3e9a3161edc7b804a33522cfd20 2d2c68c57376edba8c2ca50027c61246ce2a12b0c4502175010c0a1ba4625786d911100797d8a47e98b0200c4ab000000a90 0000000008a0082d10000320000000000000000050000911f3edfd73e8333e8463df984ee

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?