Hacky Easter 2015 – Too Many Time Pad

Introduction

Welcome back to another Hacky Easter 2015 instalment! Today’s challenge is a cryptographic one, and is all about misusing one-time pads!

banner_challenge_27

The Challenge

The banner for the challenge was this:

Challenge 27 Introduction.
Challenge 27 Introduction.

So we have got some very interesting hints here! Firstly we know that the encryption keys have been reused, so this should have a major impact on the security of their communication. We also know that the encrypted messages only contain lower-case letters and spaces, a fact that will aid our cryptanalysis later.

What is One-Time Pad (OTP)?

OTP is a method of encrypting messages so that only the people in possession of the decryption keys can decrypt and read the messages. To this end, OTP is the only truly unbreakable option that is known to man!

So why doesn’t everyone use OTPs, I hear you ask. Well, there are two sides to every story and this one is no exception. The OTP is a symmetric encryption scheme, meaning that if Alice wants to send a message to Bob then they both must have and use the same keys for encrypting and decrypting the messages. As such, the fundamental problem is the key distribution for all communicating parties. Furthermore, both parties must be able to synchronize between their key-changes, the message can’t exceed the length of the encryption key and the key must be truly random.

Encrypting with the OTP works by producing cipher messages C from plain text P and key K by doing C = P XOR K. The pain-text can be then retrieved by the receiver by performing P = K XOR C. Iff K is only used once then you can not decrypt the ciphertext reliably. As an example, suppose we have:

P = I am guilty..<br />
K = 1616c6870aed0a735c1fc394b353e92679c2ed2d<br />
C = P XOR K = 5f36a7ea2a8e651c30

While technically we could go through all the possible keys with one of them revealing our incriminating secrets (which for some reason we felt compelled to share over the internet…), there is a K’ key that would reveal the plaintext Joe is guilty, and one has no way of proving that one message is more plausible than the other. The weakness in reusing one time pad keys is introduced by the properties of XOR, due to the fact that A XOR A = 0. If

M1 = P1 XOR K and<br />
M2 = P2 XOR K, then if<br />
S1 = M1 XOR M2 = (P1 XOR K) XOR (P2 XOR K) = P1 XOR P2

We have effectively removed the key from the process and now the messages are encrypting each other. This is a problem because now all we have to do in order to recover the original messages P1 and P2 is guess which words are in the messages, something that is far less trivial than trying to guess the key!

You can read more about the OTP here.

Analysis – Crib Dragging

As we said earlier, if a guessed word is contained in a message that is part of S1 then this  will reveal the word in the other message that is part of S1. This process is called crib-dragging, as a crib is the word you are XORing with S1. The process of crib-dragging works as follows:

  1. Select a common word, the crib.
  2. Compute crib XOR S1 for each position of S1, such that if the crib is located in any position within S1’s constituent messages it will reveal information about the other message.
  3. If the crib reveals a new word or recognizable partials then try to expand on those by guessing the rest of the word or structure of the message (like additional letters or spaces), otherwise use a new crib and repeat the process.

Grabbing Wikipedia’s list of the most common words in English, we can see that words like “the, to, for, from, a, in, on, he, it” are the most prevalent words. However, words like “i, a, on” are not that useful, because they will not yield partial strings large enough for us to recognize potential words in other messages. A good crib to start of with is “the” as it is long enough and common enough, and variants with spaces.

I wrote the following python script to help me:

#!/usr/bin/env python<br />
import binascii<br />
messages = [<br />
'60c46964f83879618e2878de539f6f4a6271d716',<br />
'63c37a6ca177792092602cc553c9684b',<br />
'68d82c6bf4767f79dd617f9642d768057f63c1',<br />
'6c8a7b6ce06a3161dd6a60d755d42d4d6d67',<br />
'71c26929e96931698e2865d816d3624b687cd6',<br />
'6cda6d6df87764709c6c7bd357d361556d77']<br />
ux_messages = [binascii.unhexlify(m) for m in messages]</p>
<p>def drag(word):<br />
    for z in xrange(2, 3): # set the ranges here to work with a range of messages<br />
        for y in xrange(z+1,z+2): #set range here as well<br />
            print &quot;Processing messages {:d} and {:d}&quot;.format(z,y)<br />
            m1 = ux_messages[z]<br />
            m2 = ux_messages[y]<br />
            test = [ord(c) for c in word]<br />
            res = xor(m1,m2)<br />
            for i in xrange(0,len(res)-len(test)+1):<br />
                #this works, don't touch/read<br />
                print &quot;{:3d}: {:s}&quot;.format(i,&quot;&quot;.join([chr(test[j]^ord(res[i+j])) for j in xrange(0,len(test))]))<br />
def xor(str1,str2):<br />
    return &quot;&quot;.join([chr(ord(str1[i])^ord(str2[i])) for i in xrange(0, len(str1 if len(str1) &lt;= len(str2) else str2))])</p>
<p>drag(&quot;..crib.to.drag...&quot;)<br />
pt_m2 = &quot;mr bunny is the spy&quot;<br />
k = xor(pt_m2, ux_messages[2])<br />
for ctm in ux_messages:<br />
    print xor(ctm,k)

In the beginning I decided to overcomplicate things, as always, by assuming that the encryption keys had been reused pair-wise in some fashion rather than for all the messages, and this assumption turned out to be wrong. So dragging ‘ the was a good start, and if XORed with all the messages would yield strings like ‘lond‘,’ s the‘,’lack ha‘,’ven ‘ and we could lengthen these partials by trying out the words london, is the or has the, black hat and seven. Repeating this process will eventually reveal one of the messages, ‘i wear a black hat‘. XORing this with its encrypted version will give us the key, and XORing the key with the messages we were given yields:

enemy has the bonbon<br />
five oh oh seven<br />
mr bunny is the spy<br />
i wear a black hat<br />
the hq is in london<br />
ipadyoupadweallpad<br />

ipadyoupadweallpad was the solution. Bingo!

Egg 27, it can pad as well!
Egg 27, it can pad as well!

Conclusion

We have completed another hard challenge! As with the previous challenge, Jad & Ida, there were plenty of hints to the correct path. It was a fun one and pretty frustrating at times (bomb is a much more reasonable word in this setting than bonbon, but there you go), and I came across some interesting articles and demonstrations about how it was used and how it can fail!

For all its impracticalities and hard operational security constraints, OTP is a pretty interesting scheme! OTP’s strength is in the name, the encryption key should only be used once!

Advertisements
Hacky Easter 2015 – Too Many Time Pad

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s