0
$\begingroup$

With a Cipher text of

7ECC555AB95BF6EC605E5F22B772D2B34FF4636340D32FABC29B 
73CB4855BE44F6EC60594C2BB47997B60EEE303049CD3CABC29B 
64C6401BAF45F6A930435F3DF875C4E102F8742A45C824AFCA9B 
7AC24F5EAF17F0A0754D5834BC3CC3A90ABD7B2A52C222ABC89B 
72C24A52B550B3B8624D4F22F86BD2B30ABD642C498122A1D29B 
73CC5457BF17E7A4750C5423B178D0A44FFF756355C03CABC28A 
74CC0155B443B3A8795F4224AA7E97B507F2632606CF3FA0D59B

It is assumed that each line is a different message encrypted with the same pad.

I have tried countless lengths of words that are supposed to lead me somewhere to the decryption of this cipher, however isn't it just downright impossible to "guess" your way to the answer?

Crib dragging does not seem to work since there seem to be too many possibilities…

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Mar 4 '16 at 18:42
  • $\begingroup$ With that many messages, crib dragging should become easier, not harder... They are more likely to have things like "the" cropping up, plus once you find a word in one of the texts, you can be confident that you have it right if all the ciphertexts work. At any rate, I am currently working on two ciphertexts with the same key and I wrote a program that speeds it up immensely. A little trick I found useful is that, with a text file of all english words, it isn't actually that difficult to write an algorithm that is pretty good at predicting if a text sample could be a fragment of english words. $\endgroup$ – trevorKirkby Jul 21 '16 at 20:10
2
$\begingroup$

I'm going to assume this isn't homework because otherwise reading this answer would count as cheating. If it is homework please tell me so I can delete this answer.

Crib dragging does work, you just need to be more persistent. I wrote a script (available via GitHub) that answers your question:

#Use this tool to solve multi-time pads
#Written on 4th march 2016
#Took me a good 30 minutes
#How this tool works:
#Suppose you guess a crib " the "
#We have n messages each of length k
#For each of the n messages and at each position k we want to guess the crib
#However, we can make our lives vastly easier if we guess the other way round:
#Instead of guessing each message separately, we guess at the same position for all the messages at the same time
#This will make it easier to spot when crib for message m at position k produces the wrong output for any other message
#Therefore, what this program does is to guess for each combination of message and position the crib for all messages at position k
#Suppose at message m position k the plaintext is " the ", then we can derive the key at position k with the length of our crib
#Once we have derived that part of the key we then apply it to the rest of the messages to see if we get a sensible output
#Therefore for any crib there are n * k outputs where n is the number of ciphertexts and k is the length of each ciphertext
#Each output is n strings of characters representing the "decoded" portion of each message at position k

#Todo: Use a dictionary to automate this.

from itertools import combinations
a="7ECC555AB95BF6EC605E5F22B772D2B34FF4636340D32FABC29B"
b="73CB4855BE44F6EC60594C2BB47997B60EEE303049CD3CABC29B"
c="64C6401BAF45F6A930435F3DF875C4E102F8742A45C824AFCA9B"
d="72C24A52B550B3B8624D4F22F86BD2B30ABD642C498122A1D29B"
e="73CC5457BF17E7A4750C5423B178D0A44FFF756355C03CABC28A"
f="74CC0155B443B3A8795F4224AA7E97B507F2632606CF3FA0D59B"
crib = " the ".encode("hex")
#data = [line.strip() for line in open("20k.txt", 'r')]

binary_a = a.decode("hex")
binary_b = b.decode("hex")
binary_c = c.decode("hex")
binary_d = d.decode("hex")
binary_e = e.decode("hex")
binary_f = f.decode("hex")
L1=[binary_a,binary_b,binary_c,binary_d,binary_e,binary_f]

def xor_strings(xs, ys,i=0):
    return "".join(chr(ord(x) ^ ord(y)) for x, y in zip(xs[i:], ys))

def initial_drag(crib):
    '''for combo in combinations(L1, 2):
        xored= xor_strings(combo[0], combo[1]).encode("hex")
        print combo[0].encode("hex"), combo[1].encode("hex")
        print xored
        for i in range(27):
            print xor_strings(xored.decode("hex"),the2.decode("hex"),i)'''
    for cipher in L1:
        for position in range(len(cipher)-len(crib)):
            key = xor_strings(cipher,crib.decode("hex"),position).encode("hex") #when we XOR our crib with the ciphertext, we should get back the key
            for c in L1:
                print xor_strings(c,key.decode("hex"),position), cipher.encode("hex"),position #we then XOR the key we got back with the other ciphertexts
            print ""

def crib_drag(crib,ciphertext,position):
    key = xor_strings(ciphertext,crib.decode("hex"),position).encode("hex")
    for c in L1:
        print xor_strings(c,key.decode("hex"),position), c.encode("hex"),position #we then XOR the key we got back with the other ciphertexts

# Step 1. Do an initial crib drag through all possible key fragments for your crib.
initial_drag(crib)

# Step 2. Once you have found a valid key fragment, expand on that fragment. I did this manually in the interpreter.
crib_drag(" the ".encode("hex"),L1[4],5)
crib_drag("ble pr".encode("hex"),L1[0],4)
crib_drag("able pr".encode("hex"),L1[0],3)
crib_drag("able pri".encode("hex"),L1[0],3)
crib_drag("nese puzzle".encode("hex"),L1[1],3)
crib_drag("chinese puzzle ".encode("hex"),L1[1],0)
crib_drag("notable prisoner ".encode("hex"),L1[0],0)
crib_drag("do not disturb those ".encode("hex"),L1[5],0)
crib_drag("notable prisoner is freed ".encode("hex"),L1[0],0)

The difference between the method I used and the one posted elsewhere is that I drag the crib over all ciphertexts at the same time, whereas the one posted in the blog only compared a pair of ciphertexts at a time, making it much more prone to false positives compared to my method.

If you start with crib dragging using the as the crib then you will find

le pr
se pu 
ree o 
 clea
g tra 
 the  
t dis 

When you assume that the 5th position of 73cc5457bf17e7a4750c5423b178d0a44fff756355c03cabc28a begins with the. This stands out because almost all the other results you get will have weird symbols or obviously nonsensical combinations of letters whereas this one looks like a possible fragment of a grammatically correct English sentence. From there onwards you just keep lengthening the crib to get the rest of the key.

$\endgroup$
  • $\begingroup$ This is a homework problem it isn't "worth" anything, im just a bit frustrated that I cant seem to get it, otherwise do you have a script like that for python3? I dont have python2 $\endgroup$ – Kamijou Mar 5 '16 at 2:02
1
$\begingroup$

Some time ago I made a simple algorithm to guess many time pad solutions almost automatically. I lost the sources, but let me explain it in detail here for newcomers. The cipher in OTP (one time pad) is achieved by xoring message with truly random key of same length. $$ message \oplus key = cipher $$ When we xor two ciphers together magic happens. $$ cipher1 \oplus cipher2 =\\ (message1 \oplus key) \oplus (message2 \oplus key) =\\ message1 \oplus message2 $$ This beautifully removes the random key that cannot be guessed from the equation.

Now the algorithm is like this. We start with computing xors of all ASCII characters that we think might be in the message. Usually it was the best to start with a-z(space)A-Z. We want to have a dictionary that will give us a list of all possible characters that could come of each result. For example a value if $0$ could be any character, because $$ a \oplus a = \text{0x61} \oplus \text{0x61} = 0$$ But fortunately some of the xors are very unique, and hold only 2-6 possibilities. They help alot! $$ (space) \oplus q = \text{0x20} \oplus \text{0x71} = \text{0x51}$$ This means that when in the next stage you will get a value of $0x51$ You know that one of the messages has a space and other one has the letter "q" You just don't know which is which. Sometimes You have to guess.

Now we take every pair of ciphers and we xor them together. If my math is correct you will get 21 results. Now in every result we use our computed lookup dictionary and we check what characters could they be. When I was playing with that this algorithm guessed correctly around 80% of characters. The rest was trail and error.

When You guessed even one message You can easily just xor it with the cipher to get the OTP key. $$cipher \oplus message = key$$

$\endgroup$
  • $\begingroup$ Am I doing things right by finding the hex of a random word like "the" and XOR'ing it against 2 cipher texts which have been XOR'ed together? $\endgroup$ – Kamijou Mar 5 '16 at 2:18
  • $\begingroup$ According to what I read, yes. If you are lucky and a part of the message is "the" the result of your operation will be three characters of the second message, that's usually a readable text. If you are unlucky and none of the messages contain "the" in that location, it will result in gibberish. Usually the gibberish contains at least one character outside of a-z(space)A-Z. The longer the word You test the lower the probability for a false positive. $\endgroup$ – Filip Franik Mar 5 '16 at 8:59
  • $\begingroup$ Is there anything I can do to speed this process up? Ive tried over 20 words but cant make any progress (literally have spent 3 hours just going back and forth trying to make sense of any key just crib dragging anything) Its really starting to get frustrating now. $\endgroup$ – Kamijou Mar 5 '16 at 9:11
  • $\begingroup$ May I suggest writing a script in python? You can automate the procedure. Script can automatically detect when the result contains only a-z(space)A-Z characters. $\endgroup$ – Filip Franik Mar 5 '16 at 9:56
  • $\begingroup$ I don't think I would be able to write one, but as e-sushi has posted below an automated crib dragger, however it doesnt seem to work for me $\endgroup$ – Kamijou Mar 5 '16 at 9:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.