EasyCTF 2018: Not OTP

Event	Challenge	Category	Points	Solves
EasyCTF 2018	Not OTP	Cryptography	100	¯\(ツ)/¯

Description

It seems we’ve intercepted 2 strings that were both encrypted with what looks like OTP! Is it possible to decrypt them? file

TL;DR

Here you have to decrypt a Two Time Pad. This is done by xoring the two ciphertexts together and dragging a crib (“easyctf{”) to reveal partial information about the plaintexts. By repeated tries you can successfully decrypt the flag.

Resolution

Like the title says, it’s most likely not a One Time Pad because if it was, it would be impossible to decrypt without knowing the key. Since there are 2 ciphertexts, the first thing that came to my mind was “And if it was a Two Time Pad ?”.

I xored the two ciphertexts together and got the following message :

>>> c1 = "38445d4e5311544249005351535f005d5d0c575b5e4f481155504e495740145f4c505c5c0e196044454817564d4e12515a5f4f12465c4a45431245430050154b4d4d415c560c4f54144440415f595845494c125953575513454e11525e484550424941595b5a4b".decode('hex')
>>> c2 = "3343464b415550424b415551454b00405b4553135e5f00455f540c535750464954154a5852505a4b00455f5458004b5f430c575b58550c4e5444545e0056405d5f53101055404155145d5f0053565f59524c54574f46416c5854416e525e11506f485206554e51".decode("hex")
>>> def xor(m,k):
...     r = ""
...     for i in range(len(m)):
...         r += chr(ord(m[i]) ^ ord(k[i%len(k)]))
...     return r
...
>>> p = xor(c1,c2)
>>> p
'\x0b\x07\x1b\x05\x12D\x04\x00\x02A\x06\x00\x16\x14\x00\x1d\x06I\x04H\x00\x10HT\n\x04B\x1a\x00\x10R\x16\x18E\x16\x04\\I:\x0fE\rH\x02\x15NY\x0e\x19S\x18I\x1e\tF\x0b\x17V\x11\x1d\x00\x06U\x16\x12\x1eQL\x03L\x0e\x01\x00\x19\x1fA\x0c\x0f\x07\x1c\x1b\x00F\x0e\x1c\x11\x14\x7f\x1d\x1aP<\x0c\x16T\x00-\x01\x13_\x0e\x14\x1a'

Now I can start looking for some known plaintext (crib). I already know that the flag begins with “easyctf{” so I can start with that. I replaced all the non interesting characters with “#” for readability.

class="prettyprint">>>> def crib(m, c):
...     for i in range(len(m)-len(c)+1):
...         p = xor(m, "\x00"*i+c)
...         s = ""
...         for e in p:
...             if e in "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ{}0123456789_ ?!.,'":
...                 s += e
...             else:
...                 s += "#"
...         print s
...
>>> crib(p, "easyctf{")
<...>
#####D###A#######I#H##HT##B###R##E###I##E#H##NY##S#I##F##V####U###QL#L######m###of########P###T####_###
#####D###A#######I#H##HT##B###R##E###I##E#H##NY##S#I##F##V####U###QL#L#####Aintext u######P###T####_###
#####D###A#######I#H##HT##B###R##E###I##E#H##NY##S#I##F##V####U###QL#L#####A#jfobc2hg#####P###T####_###
<...>

I got what seems to be a part of the original plaintext.

The maths behind it

If c1 = p1 xor k

and c2 = p2 xor k

then p = c1 xor c2 = p1 xor k xor p2 xor k = p1 xor p2

That’s why, by guessing part of p1 we get a part of p2. I just dragged the crib all the way through p and once I saw a probable plaintext, I knew I had found the good offset.

Now that I know part of the plaintext, I can try to extend it by guessing : “ plaintext used “

>>> crib(p, " plaintext used ")
<...>
#####D###A#######I#H##HT##B###R##E###I##E#H##NY##S#I##F##V####U###QL#L## is easyctf{otp_##P###T####_###

” flag is easyctf{otp_“

>> crib(p, " flag is easyctf{otp_")
<...>
#####D###A#######I#H##HT##B###R##E###I##E#H##NY##S#I##F##V####U#fv4le of plaintext used ##P###T####_###

And so on, until I arrived to the point I knew that much of p1 and p2 :

p1 = “ to a sample of plaintext used “

p2 = “to guess! flag is easyctf{otp_”

At that point, I got stuck because I couldn’t guess the rest of the plaintext. That’s why I decided to look at the key ! How ? By dragging the plaintext I recovered over the ciphertext and not over p :

k = c1 xor p1 = c2 xor p2

>>> crib(c1, " to a sample of plaintext used ")
<...>
8D#NS#TBI#SQS_####W##OH#UPNIW##_LP#####DEH#VMN#QZ_O#F#JEC21, 158, 103, 244, 67, 182, 213EN#R#HEPBIAY#ZK
<...>
>>> crib(c2, "to guess! flag is easyctf{otp_")
<...>
3CFKAUPBKAUQEK###ES##_#E_T#SWPFIT#JXRPZK#E_TX#K_C#W#XU#NTD 1 158, 103, 244, 67, 182, 213XTAnR##PoHR#UNQ

Because the key follows an easy to guess pattern, I could apply the same technique as before and get the flag :

>>> crib(p, " to a sample of plaintext used in codebreaking")
<...>
#####D###A#######I#H##HT##B###R##E###I##E#H##NY##S#I##F##ver guess! flag is easyctf{otp_ttp_cr1b_dr4gz}

Flag

The complete flag was easyctf{otp_ttp_cr1b_dr4gz} 😀

ENOENT