Score:0

cracking a one time pad using key reuse

cn flag

There is a one time pad which works as follows: given message "hello" and key "asdfg", it produces "hwoqu". It only works with the 26 english letters. The output is (h(7) + a(0))%26 = h(7), (e(4) + s(18))%26 = w(22) etc.

So I have two ciphertexts created as above using a single key for both ciphertexts. I'm supposed to be able to crack the plain texts without needing access to the key.

What is the procedure to do this?

So far, I've tried XORing the two cipher texts, i.e. for each letter in c1 and c2, convert to its corresponding numeric value and XOR the nth letter of c1 with nth letter of c2, to genate c3.

I'm then supposed to use that with a guess word like "the" by exoring that against c3. This is the part where I'm stuck, I don't know what I'm supposed to be looking for here.

Edit:

So since its a addition rather than a XOR, this is what I wrote:

c1 = "ujhantamawmuzvgkterrykub"
c2 = "bpgxmkymbbpyxmogoehdefgh"

pad encrypt and decrypt:

def oneTimePad(message, code):
    message_out = ""
    for i in range(len(message)):
        
        index = (letters.find(message[i]) + letters.find(code[i]))%26
        message_out+= letters[index]

    return message_out

def otpDecrypt(cipher, key):
    message_out = ""

    for i in range(len(key)):
        index = (letters.find(cipher[i]) - letters.find(key[i]))%26
        message_out+= letters[index]
    return message_out

the cracker:

def padCracker(m1, m2, guess): # m1, m2 list of nums
    m3 = list(map(lambda x, y: (x + y) %26, m1, m2))
    check = [] # m3 + guess mod 26
    guessNum = list(map(lambda c : letters.find(c), guess))
    for i in range(len(m3)-len(guess)+1):
        check = list(map(lambda x, y: (x+y)%26, guessNum, m3[i: i+len(guess)]))
        print(check, end="")
        
        string = ""
        for num in check:
            string += letters[num]

        print(string)       


print(padCracker(m1,m2, "bcd"))

this suggests that c1 starts with "the" and c2 with "and" with key "bcd" but I don't know how to get the rest of the key

SAI Peregrinus avatar
si flag
Hint: Does the encryption use XOR? What does it use? How does that relate the ciphertexts?
Shiny_and_Chrome avatar
cn flag
I suppose this doesn't actually use XOR. It just adds key and plaintext letter just like a vigenere cipher. So, what is the procedure to then undo the vigenere cipher, and how do I use the relationship between c1 and c2 to get at the plaintext?
SAI Peregrinus avatar
si flag
It adds keystream letter and plaintext letter mod 26. The decryption is the same. The relation to perform the usual two-time-pad attacks (eg crib dragging) is to add the ciphertexts mod 26. https://crypto.stackexchange.com/questions/59/taking-advantage-of-one-time-pad-key-reuse has several good answers.
Shiny_and_Chrome avatar
cn flag
thanks, that helped a lot. So I add the letters of the two ciphertexts because that is what was done during encrpytion, whereas if it had been XORed, I would also do the XOR of the two ciphertexts? If I understand crib dragging correctly, I take a guess word like "the" or "and" or "have", convert it to its numerical value then add each letter to the corresponding letter in the c3, if the result is something readable, then that gives me another potential guess word to then build up what the message is.
SAI Peregrinus avatar
si flag
Yep. This is basically the same OTP as normal, just with XOR on bits replaced with addition mod 26 on English letters.
Shiny_and_Chrome avatar
cn flag
I still can't get the damn thing to work. I've done the c3 = (c1+c2) % 26, then (c + guess) % 26, but don't know where to go from there. The whole crib thing is not clicking. I've updated my original post to show what I tried.
in flag
The point is that $x\mapsto x\oplus k=y$ is weak to any statistical analysis of $x$. For example, if $x$ is likely to be $x_0$, then $k$ is likely to be $y\oplus x_0$, the worst case scenario being that if we know $x$ and $y$, then we know $k$.
Score:0
tw flag

let $a = c_1 \oplus c_2$ the procedure is to try common bigrams and trigrams on every position of $a$, a trigram includes things like "the", you should note that not everything is crackable considering the readability of the plaintexts, if the two plaintexts were things like ")@#JRDIOHFf", "\$E)#(JRFNIf", you couldn't crack them.

But if the plaintexts are meaningful sentences, such as "the red fox jumped the fence", and "you were not there yesterday",

a[0:3] $\oplus$ "the" would produce "you", since they are both english words with meaning, there is a high possibility that "the" and "you" are the starting values of the two plaintexts.

Python Example that I wrote

m1 = b"the red fox jumped the fence"
m2 = b"you were not there yesterday"
key = b"1398jepfohn43p8nfp3fnvvno02D"
c1 = bytearray(len(m1))
c2 = bytearray(len(m2))

# encrypt m1
for i in range(len(m1)):
    c1[i] = m1[i] ^ key[i]

# encrypt m2
for i in range(len(m2)):
    c2[i] = m2[i] ^ key[i]

# calculate ciphertext1 ^ ciphertext2 to cancel out the key
a = [b""]*len(c1)
for i in range(len(c1)):
    a[i] = c1[i] ^ c2[i]

# calculate the at every position of a
common_trigram = b"the"
length = len(a) - 3 # 3 is the length of common_trigram
tries = [""]*length
a_indexes = [0]*length # indexes of a that corrosponds to the tries
for i in range(length):
    for j in range(3): # 3 is the length of common_trigram
        tries[i] += chr(a[i+j] ^ common_trigram[j])
        a_indexes[i] = i+j-2

# you can check if tries[i] is human readable or not and at what index is it human readable.

print(tries)
print(a_indexes)

# this line of code proves that it calculates it correctly
for i in range(3):
    print(chr(a[a_indexes[19+i]] ^ common_trigram[i])) # 19 is where "yes" is located, a_indexes shows the corrosponding indexes


# as you can see from the output, "the" produces "you" in the beginning and produces "yes" (for YESterday) for m2 when m1 equals "the"
# From this single trigram I learned
m1 = "the"
m2 = "you"
m1[19:22] = "the"
m2[19:22] = "yes"

You then try many other bigrams and trigrams to calculate the potential plaintexts. If you calculate one of them. The other one can be found using

$m_1 = a \oplus m_2$

$m_2 = a \oplus m_1$

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.