Writeup: HackCon 2019 - OTP

(Updated: )
writeups
, , , ,

Information

  • category : crypto
  • points : 100

Description

hackerman is so dank that he decided to play around with OTPs.
he did the following:
message1 ^ key = cipher1
message2 ^ key = cipher2

He gives you cipher1 and cipher2 and challenges you to find the concatenation of messages 1 and 2.
Are you dank enough to find this?
Oh and also, ‘meme’ is so popular that hackerman used the word in both his messages.
cipher1 is : ‘\x05F\x17\x12\x14\x18\x01\x0c\x0b4’,
cipher2 is : ‘>\x1f\x00\x14\n\x08\x07Q\n\x0e’
Both without quotes

Writeup

It’s known that the One Time Pad conserves the perfect secrecy only if the key is used just once. What if (as the challenger) we use the key two times?

1
2
c1 = m1 xor key
c2 = m2 xor key

If we xor c1 and c2 we obtain: c1 xor c2 = m1 xor key xor m2 xor key = m1 xor m2.

So xoring the two ciphertexts can leaks information about the two plaintexts. There’s a famous trick to use in this cases called crib-dragging where we guess a substring and we xor the guessed substring with m1 xor m2.

If we know that m1 has a substring " the ", xoring it with m1 xor m2 we can get a valid part of the plaintext of m2. Usually we don’t know if the substring guessed is from m1 or m2, but this doesn’t prevent use to decrypt both of them.

In our case we have two short messages, and this made our decryption algorithm/guessing a lot easier.

Let’s write an exploit for testing the various cases interactively.

exploit.py : 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/env python3

def xor_string(s1, s2):
    if(len(s1) == 1 and len(s1) == 1):
        return bytes([ord(s1) ^ ord(s2)])
    else:
        return bytes(x^y for x, y in zip(s1, s2))

def main():
    c1 = b'\x05F\x17\x12\x14\x18\x01\x0c\x0b4'
    c2 = b'>\x1f\x00\x14\n\x08\x07Q\n\x0e'

    while True:
        crib = input("insert crib : ")
        c = xor_string(c1, c2)
        for i in range(0, len(c)):
            res = xor_string(crib.encode(), c[i:len(crib.encode()) + i])
            try:
                print("result : " + str(res.decode()))
            except UnicodeDecodeError:
                continue

if __name__ == '__main__':
    main()

We are very advantaged because we know the start of m1 and the end of m2. When we xor the start of m1 with m1 xor m2 we obtain the start of m2, viceversa when we xor the end of m2 with m1 xor m2 we obtain the end of m1. We can decrypt the flag in just two step because the len(start) + len(end) = 10 bytes = len(m1) = len(m2).

Launching the exploit:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
$ python exploit.py 
insert crib : d4rk{                 | start m1
result : _meme                      | start m2
result : =#tuk
result : s2l{}
result : b*bm&
result : z$t6z
result : t2/jA
result : bisQ
result : 95H
result : e
result : ^
insert crib : }c0de                 | end m2
result : F:'b{
result : $t6zu
result : je.tc
result : {} b8
result : cs69d
result : meme_                      | end m1
result : {>1^
result :  b

Flag

d4rk{meme__meme}c0de