Monday, 31 July 2017

Taking advantage of one-time pad key reuse

Today we will have pleasure play with cryptoanalysis of One-Time Pad.

We have following scenario:
Someone was using the same key for several different messages. We were able to capture these ciphertexts and we we want to decrypt them.
We know that sender was very lazy and used the same key for each messages.

We know that:
c_i = m_i XOR k
c_i - cipher text
m_i - message in plaintext
k - key which has been used to encrypt messages (every time the same)

Captured ciphertexts:

ciphertext #1:
ciphertext #2:
ciphertext #3:
ciphertext #4:
ciphertext #5:
ciphertext #6:
ciphertext #7:
ciphertext #8:
ciphertext #9:
ciphertext #10:
We know how XOR works, and we should exploit the knowledge
c_i XOR c_j = m_i XOR m_j XOR k XOR k = m_i XOR m_j
 So, if we guess some part of message (for example i) then we should get a part of plain text comes from message j - becuase:
m_i XOR m_i XOR m_j = m_j
The most popular word in English are for example: The, he, ing, etc.
Let's write a short script to decrypt the messages

First version of the script

We have done final code as below

Now we are able to guess each of the messages.

m_1 = we can factor the number 15 with quantum computers. We can also factor the number 15 with a dog trained to bark three times - Robert Harley
m_2 = Euler would probably enjoy that now his theorem becomes a corner stone of crypto - Annonymous on Euler's theorem
m_3 = The nice thing about Keeyloq is now we cryptographers can drive a lot of fancy cars - Dan Boneh
m_4 = The ciphertext produced by a weak encryption algorithm looks as good as ciphertext produced by a strong encryption algorithm - Philip Zimmermann
m_5 = You don't want to buy a set of car keys from a guy who specializes in stealing cars - Marc Rotenberg commenting on Clipper
m_6 = There are two types of cryptography - that which will keep secrets safe from your little sister, and that which will keep secrets safe from your government - Bruce Schneier
m_7 = There are two types of cyptography: one that allows the Government to use brute force to break the code, and one that requires the Government to use brute force to break you
m_8 = We can see the point where the chip is unhappy if a wrong bit is sent and consumes more power from the environment - Adi Shamir
m_9 = A (private-key) encryption scheme states 3 algorithms, namely a procedure for generating keys, a procedure for encrypting, and a procedure for decrypting.?
m_10 = The Concise OxfordDictionary (2006) defines crypto as the art of writing o r solving codes.
goal = The secret message is: When using a stream cipher, never use the key more than once