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!