Crib Drag writeup

Crib Drag:
solved by AuPhishYellow member cookthebook for sCTF 2015

Crib drag is based upon a core principle in cryptography. Whenever you're given two cipher texts of the same length, you can be almost sure they were encrypted with the "one" time pad. The one time pad is where you take a key of the same length as the plaintext and bitwise xor it with the key. This would be completely secure if you use the key once, but if you use it twice, like they did in this challenge, it can be easily broken. Here is some algebra to show you exactly how my script solves the challenge, keep in mind if a xor b = c, then a xor c = b. And a xor a = 0.

c - cipher text
k - key
p - plaintext

c1 = p1 xor k
c2 = p2 xor k
c1 xor c2 = p1 xor k xor p2 xor k
= p1 xor p2 xor k xor k
= p1 xor p2 xor 0
= p1 xor p2

Thus, by simply xoring the ciphertexts together, we get the xor of the plaintexts. Now, let's say p1 includes the string "cookthebook". If we do every single possible position of "cookthebook" in a string of spaces and "cookthebook" and xor it with the xor'd plaintexts, we will get some part of p2. Here is an example:

p1 = "Iam cookthebook"
p2 = "Hello world!!!!"

p1 xor p2 xor " "*4 + "cookthebook" = 4 bytes + "o world!!!!"

From here, it can be easily seen that p2 should be "Hello world!!!!". This is exactly what this script does with c1 and c2:

------------------------------------------------------------------------
c1 = "2d0710181b01111f0817171401071c11091a0a"
c2 = "3c091311111a1a0e180003120d1a0811091a0a"

C1 = list()
C2 = list()

for i in range(len(c1)/2):
	C1.append(c1[i*2:i*2+2])
	C2.append(c2[i*2:i*2+2])

P = list()

C = zip(C1,C2)

for (i,j) in C:
	xor = hex(int(i,16)^int(j,16)).replace('L','').replace('0x','')
	if len(xor) == 1:
		xor = '0' + xor
	P.append(xor)

#Insert plaintext prediction here
test = 'guess'

printme = ''
for (i,j) in zip(list(test),C2):
	printme += chr(ord(i)^int(j,16))

print printme
------------------------------------------------------------------------

This script simply tests every single possible position of the "test" variable and prints all of the results. Note that the last four bytes are the same in each ciphertext, so no matter what you set "test" to be, the last position will always look like "test". Try running the script with test = "guess" and you will notice that it fits nicely with one of the outputs. From there, simply start reconstructing each phrase until "test" is as long as the cipher text. The flag will be the common key between the ciphertexts.