Hackover CTF 2016 - vigenere writeup

Posted at — Oct 9, 2016

We’ve got a message encrypted with the Vigenere cipher after being compressed with zlib, which of course makes a usual dictionary attack unviable. The key is random but its length is known beforehand, from the original source code, and equals 10.

From the ZLIB RFC 1950 we know that, when there is a dictionary present (which is true in our case), the first 6 bytes of the zlib stream describing the compression mode and the dictionary id will be fixed, so compressing any data with the parameters present in the source code and xoring it with the encrypted file will net us the first 6 bytes of the key:

import os
import zlib
import binascii

common_trigrams = ['men', 'sth', 'oft', 'tis', 'edt', 'nce', 'has', 'nde',
                   'for', 'tio', 'ion', 'ing', 'ent', 'tha', 'and', 'the',
                   ' a ']
zdict = b''.join(x.encode() for x in common_trigrams)
comp = zlib.compressobj(level=9, zdict=zdict)

sample = os.urandom(500)
compressed_sample = comp.compress(sample) + comp.flush()

with open("cybertext.bin","rb") as f:
	data = f.read()
	key_start = bytes([compressed_sample[x] ^ data[x] for x in range(6)])

print(binascii.hexlify(key_start))

tr@karabut.com:~/work/hackover16/vigenere$ python3 keystart.py 
b'9e8e515d95d3'

Now, trying out all the 256**4 possibilities for the rest of the key is a little bit tedious, but the challenge is luckily made 64 times easier by a very convenient design decision present in the source code:

# Running the key schedule before using the key
# We use the same idea as in DES: Encode some parity bits. This will
# improve the confusion rate when encrypting the compressed bytes.
key = bytearray(key)
key[6] &= 0b00000110
key[6] ^= self.byte_parity(key[0])
for i in range(5):
	key[6] ^= self.byte_parity(key[i+1]) << (3 + i)
self.key = key

So, knowing the first 6 bytes, we need to guess only two bits of the 7th, and the rest can be bruteforced in a reasonable time just by trying to decompress the given data and checking the results for the flag. We have four bits to crack, let’s get four threads to run:

import threading
import zlib
import binascii

common_trigrams = ['men', 'sth', 'oft', 'tis', 'edt', 'nce', 'has', 'nde',
                   'for', 'tio', 'ion', 'ing', 'ent', 'tha', 'and', 'the',
                   ' a ']
zdict = b''.join(x.encode() for x in common_trigrams)

class crackThread(threading.Thread):

	def __init__(self, key_start, data, t):
		threading.Thread.__init__(self)
		self.key_start = key_start
		self.data = data
		self.t = t

	def run(self):
		crack(self.key_start, self.data, self.t)

def byte_parity(b):
	p = 0
	while b:
		p ^= 1 if b & 1 else 0
		b >>= 1
	return p

def xor(a, b, out):
        for i in range(len(a)):
                out[i] = a[i]^b[i%len(b)]

# dirty, works for this case but would need
# fixing when len(a)%10 >= 7
def xor3bytes(a, b, out):
	for i in range(len(a)//10):
		out[i*10+7] = a[i*10+7]^b[7]
		out[i*10+8] = a[i*10+8]^b[8]
		out[i*10+9] = a[i*10+9]^b[9]

def crack(key_start, data, t):
	parity = t << 1
	parity ^= byte_parity(key_start[0])
	for i in range(5):
		parity ^= byte_parity(key_start[i+1]) << (3 + i)

	guess = bytearray(key_start + bytes([parity]) + bytes(3))

	# let's prepare most of the data so we have less to xor in loop
	result = bytearray(len(data))
	prepared = bytearray(len(data))
	xor(data, guess, prepared) 
	xor(data, guess, result)

	for n in range(0xff**3):
		guess[9] = n & 0xff
		guess[8] = (n >> 8) & 0xff
		guess[7] = (n >> 16) & 0xff

		try:
			xor3bytes(prepared, guess, result)

			# unfortunately we have to re-create the object here
			decomp = zlib.decompressobj(zdict=zdict)
			message = decomp.decompress(result)
			if "hackover" in message.decode():
				print(message)
				print(binascii.hexlify(guess))

		except zlib.error as e:
			pass

with open("cybertext.bin","rb") as f:
	data = f.read()
	key_start = b'\x9e\x8e\x51\x5d\x95\xd3'

	for t in range(4):
		crackThread(key_start, data, t).start()

After some time, we get this:

tr@karabut.com:~/work/hackover16/vigenere$ python3 crack.py 
b'Dear cyber space hacker,\n\nthis is the cyber text which you have successfully decrypted. Therefore you are\nthe best candidate for volunteering in our cyber fire brigade! Help to extinguish\ncyber fires caused by cyber attacks with cyber bombs. Drive with a big red cyber\ncar to all the cyber places and show them your cyber water! Capture flags, e.g.\nhackover16{freiwilligeCyberFeuerWehr}, out of burning cyber buildings! Of course\nsuch is great experience in the cyber fire brigade can not be paid, but you still\nlike to join, right?\n\n'
b'9e8e515d95d3b7bea8b8'

Trickery Index

Hackover CTF 2016 - vigenere writeup