The CSAW CTF 2013 online qualifiers were held last weekend (09/19/2013 through 09/22/2013). The top 10 undergraduate teams will participate in the CSAW CTF finals in November; however the qualifiers were open to everyone and a small team from Digital Operatives participated. Below is a writeup of one of the Crypto challenges.
The Crypto 300 challenge was contained entirely in a tarball that contains a custom encryption Python script and nine encrypted files. The encryption algorithm reuses a single 256-byte key to XOR each subsequent block of the input file. Simple XOR encryption of uncompressed files often leads to the key sticking out of the ciphertext when the input file contains many zeroes. This is also the case with some rudimentary binary packers that XOR data inside themselves. In the case of Crypto 300, thousands of blocks were given to us in the ciphertext files, providing many opportunities to find (0 XOR key[i]) instances scattered throughout the files. For instance, if at byte offsets 0+blocksize * x (where x is a non-negative integer) in the ciphertexts frequently contain 0x40, it is likely that byte 0 of the key is 0x40.
We created a simple Python script to count the number of times each byte value occurs at each block offset.
#!/usr/bin/python
import os
import sys
blocksize=256
prefix="output/file"
suffix=".enc"
blocks=[]
for x in range(0,9):
fxname = prefix + str(x) + suffix
try:
print "Opening " + fxname
fx = open(fxname,'rb')
except:
print "Failed to open " + fxname
continue
moretoread = True
while moretoread:
block = fx.read(blocksize)
if(len(block) < blocksize):
moretoread = False
print "Last block was " + str(len(block)) + " bytes."
blocks.append(block)
print "Extracted " + str(len(blocks)) + " blocks."
#Calculate the number of times each byte value occurs at each position in a block
histogram = [[0 for i in range(blocksize)] for j in range(blocksize)]
for block in blocks:
for b in range(0, len(block)):
val = ord(block[b])
histogram[b][val] = histogram[b][val] + 1
#Get the most used byte value for each position in the block
maxvals=[0 for i in range(blocksize)]
for hidx in range(0, len(histogram)):
bytearr = histogram[hidx]
cur_max_pos = 0
cur_max_count = 0
for idx in range(0,len(bytearr)):
count = bytearr[idx]
if count > cur_max_count:
cur_max_count = count
cur_max_pos = idx
maxvals[hidx] = cur_max_pos
f = open("newsecretkey.dat","wb")
f.write(bytearray(maxvals))
f.close()
print "Done"
count-bytes.py
With the key in ournewsecretkey.dat, we are able to decrypt all of the files from the challenge output folder with some simple Python borrowed from onlythisprogram.py.
#!/usr/bin/python
import os
import sys
import argparse
blocksize=256
parser = argparse.ArgumentParser(description="Decryption")
parser.add_argument('--infile', metavar='i', nargs='?',
type=argparse.FileType('r'), help='input file, defaults to standard in',
default=sys.stdin)
parser.add_argument('--outfile', metavar='o', nargs='?',
type=argparse.FileType('wb'), help='output file, defaults to standard out',
default=sys.stdout)
parser.add_argument('--secretkey', metavar='s', nargs='?',
type=argparse.FileType('a+'), help='output file, defaults to secretkey.dat',
default='secretkey.dat')
args = parser.parse_args()
counter=0
args.secretkey.seek(0)
keydata = args.secretkey.read(blocksize)
print "Using secret key: "
print keydata
while 1:
byte = args.infile.read(1)
if not byte:
break
args.outfile.write(chr(ord(keydata[counter % len(keydata)]) ^ ord(byte)))
counter+=1
sys.stderr.write('n' +
('Secret keyfile: %sn' % (args.secretkey.name)) +
('Input file: %sn' % (args.infile.name)) +
('Output file: %sn' % (args.outfile.name)) +
('Total bytes: %dn' % (counter)))
decrypt.py
Use the following commands with the above:
./decrypt.py --infile=output/file4.enc --outfile=file4.enc.gz --secretkey=newsecretkey.dat
gzip -d file4.enc.gz
After decryption we have nine plaintext files. The fifth file, file4.enc, is a gzip-compressed ASCII file that contains a message and the key: BuildYourOwnCryptoSoOthersHaveJobSecurity
For Hackers nostalgia, play the MIDI file0!