Here, since the key is used more than one time, an attack called âcrib draggingâ can be used to attack the cipher-text.
Many Time Pad Attack â Crib Drag
The one time pad (OTP) is a type of stream cipher that is a perfectly secure method of encryption. Itâs very simple to implement and is perfectly secure as long as the length of the key is greater than or equal to the length of the message. Thatâs its major downfall. However, it also requires that the key never be used more than once. This tutorial shows what happens when you re-use a key to encrypt more than one message. I also show how to uncover the plain-text of two messages that have been encrypted with the same key, without even knowing the key. I use a method called crib dragging.
Letâs begin with a brief description of OTP and how it works. Letâs take the following message and key:
message = "Hello World"
key = "supersecret"
If we convert both the message and key to hex strings, we get the following:
message = "48656c6c6f20576f726c64"
key = "7375706572736563726574"
If we do a simple XOR of the two hex strings we get the following cipher-text:
cipher-text = "3b101c091d53320c000910"
If we XOR the cipher-text with the key, we can recover the plain-text. Thatâs how OTP works. Without the key, you have no way of uncovering the plain-text.
Letâs consider what happens when you have two messages encrypted with the same key. Take the following two messages and key:
message1 = "Hello World"
message2 = "the program"
key = "supersecret"
If we convert each message and the key to hex strings, and then encrypt each message using a simple XOR with the key, weâll get the following cipher-texts:
cipher-text1: "3b101c091d53320c000910"
cipher-text2: "071d154502010a04000419"
Letâs say that all we have is the two cipher-texts and the knowledge that they were encrypted with a supposed OTP; however, they were both encrypted with the same key. To attack this encryption and uncover the plain-text, follow the steps below.
- Guess a word that might appear in one of the messages
- Encode the word from step 1 to a hex string
- XOR the two cipher-text messages
- XOR the hex string from step 2 at each position of the XOR of the two cipher-texts (from step 3)
- When the result from step 4 is readable text, we guess the English word and expand our crib search.
- If the result is not readable text, we try an XOR of the crib word at the next position.
Step 1 seems difficult (guessing a word that might appear in one of the messages), but when you think about it, the word âtheâ is the most commonly used English word. So, weâll start with assuming âtheâ is in one of the messages. After encoding âtheâ as a hex string, weâll get â746865â. That takes care of steps 1 and 2. If we XOR the two cipher-texts, weâll get the following result:
cipher-text1 XOR cipher-text2 = "3c0d094c1f523808000d09"
The next step is to XOR our crib word â746865â at each position of the XOR of the cipher-texts. What weâll do is slide â746865â along each position of â3c0d094c1f523808000d09â and analyze the result. After the first XOR, we get the following result:
3c0d094c1f523808000d09
XOR 746865
ââââââââââââââââââââââââââââââââââ
48656c
When we convert the hex string â48656câ to ASCII, we get the following text, âHelâ. This takes us to step 5 from above. Because this looks like readable text, we can assume that the word âtheâ is in the first position of one message. If we didnât get readable text, we would slide 48656c one position to the right and try again (and keep repeating until the end of 3c0d094c1f523808000d09).
Note that we donât know which message contains the word âtheâ. It could be in either message1
or message2
. Next, we need to guess what the word âHelâ is when fully expanded. It could be âHelpâ, âHelloâ, etc. If we guess âHelloâ, we can convert âHelloâ to a hex string, we get ââ. We then XOR it with the XOR of the two cipher-texts (just like we did with âtheâ). Hereâs the result:
3c0d094c1f523808000d09
XOR 48656c6c6f
ââââââââââââââââââââââââââââââââââ
7468652070
â7468652070â, when converted to ASCII, is âthe pâ. We then repeat the process, guessing what âthe pâ might be when expanded and then XOR that result with the XOR of the cipher-texts. Granted, guessing what âthe pâ might expand to is not super easy, but you get the idea. If we were to guess âthe programâ, convert it to a hex string, and XOR it with the XOR of the cipher-texts, weâll get âHello Worldâ.
This is called crib dragging. My suggestion is to first try â the â (note the spaces before and after). Most cipher-texts that youâll try cracking will contain that word somewhere in the text. If the result of your crib drag yields gibberish, then you can be sure â the â isnât in either of the plain-text messages. So, try another commonly used English word or phrase and keep trying until the result yields something that looks like readable text. Then you can just expand your guess and keep XORing until you uncover the plain-text messages.