About Crib Dragging
The one-time pad is perfectly secure
encryption technique, assuming that these three conditions are satisfied:
• The key(pad) is delivered securely without interception.
• The key(pad) is used only once. *
• The key(pad) is truley random.
A crib drag attack takes advantage of the vulnerability of reusing a pad.
The One-Time Pad
Similar to the caesar cipher, by using modular addition we combine the key and message together, but
instead of shifting by just one number, we shift each messagei by keyi then modulus 26.
Caesar cipher - Message: HELLO, Key: 5
|Message to Int||(7+5) Mod 26||(4+5) Mod 26||(11+5) Mod 26||(11+5) Mod 26||(14+5) Mod 26|
|(Messagei + 5) Mod 26||12||9||16||16||19|
With the caesar cipher encryption technique we see that we just shifted each letter in the message(HELLO) to the right by the key(5 spaces), this resulted in the final message "MJQQT". This method is very unsecure because we can brute force the encypted message with a worst case of 26(the max amount of shifts possible). This type of mapping is considered one-to-one mapping because each letter is mapped to exactly one other letter (e.g. "L" always transforms to "Q"). Therefore, once we have the key(5), we can always assume that an encrypted message containing Q always refers to L. This is not the case for One-Time Pads, we will see that below.
One-Time Pad - Message: HELLO, Key: MYKEY
|Message to Int||(7+12) Mod 26||(4+24) Mod 26||(11+10) Mod 26||(11+4) Mod 26||(14+24) Mod 26|
|(Messagei + keyi) Mod 26||19||2||21||15||12|
With a one-time pad we see that each letter in the message is shifted by a new value. The complexity of a one-time pad is 26n, but this is not what makes a one time pad so secure, even if we brute force all possiblities, we still do not know which key is correct. For example: If we receive the message "HMM" that has been encrypted by a one-time pad, the worst case is 263 possiblities. So we brute force every combination, but which result is the decrypted message? This will result in every combination of three letters including: "HEY", "CAT", "BYE". We cannot possiblity know what the original message is without the key.
For computers it is faster to employ the XOR operation for one-time pads. For this example, we will be using strings
that are converted to HEX.
Assume we have two messages: "Hello World!" and "Easy 2 Crack", we are going to ecrypt them with the key "secretkey123". The first thing we are going to do is convert them from ASCII to HEX format.
Message 1 ASCII: Hello World!
Message 2 ASCII: Easy 2 Crack
Key ASCII: secretkey123
Message 1 HEX: 48656c6c6f20576f726c6421
Message 2 HEX: 45617379203220437261636b
Key HEX: 7365637265746b6579313233
Then we can encrypt each HEX string with the key by using an XOR operation.
Message 1 ⊕ Key: 48656c6c6f20576f726c6421 ⊕ 7365637265746b6579313233 = Cipher 1
Message 2 ⊕ Key: 45617379203220437261636b ⊕ 7365637265746b6579313233 = Cipher 2
Encrypted Message 1(Cipher 1): 3b000f1e0a543c0a0b5d5612
Encrypted Message 2(Cipher 2): 3604100b45464b260b505158
Now, for future reference, we can XOR Cipher 1 and Cipher 2 together.
Cipher 1 ⊕ Cipher 2: 0d041f154f12772c000d074a
Let us assume that Alice is sending the messages Cipher 1 and Cipher 2 to Bob, but Eve has intercepted them, how can Eve decrypt the messages? Well if the messages were both encrypted with seperate random one-time pads then it would be impossible for Eve to decrypt the messages, but what if Eve knows that Alice and Bob have been reusing their one-time pad? This is where crib dragging comes in.
Eve can attempt to guess words(Crib Words) to drag along the XOR'd messages. For example: If Eve guesses "Hello" as their Crib Word, first Eve will want to convert this to HEX. Hello then becomes: 48656c6c6f, now Eve can "drag" this word across the XOR'd messages
If Eve now converts the result 4561737920 to ASCII, Eve will see that the result ended up being "Easy ". This is a good result, and is probably the correct answer(We already know the answer, but Eve doesn't), this is because "Easy " is a readable word, usually if your crib word fails it will give you gibberish. Since "Easy " is probably the start Cipher 2 now Eve can continue guessing until the messages are decrypted.