Sunday, February 16, 2014

Olympic CTF 2014 - Find da key writeup

I didn't solved this task during the competition, and today I've finally solved it. Since I haven't found a write-up for it, I decided to write my own solution.

Freestyle 200 - Find da Key
Author: vos
Task is very unusual: find the key. stego.txt

We have a file with base64 encoded lines. After decoding of all of them we get the text about Steganography from wikipedia.
First encoded line: U3RlZ2Fub2dyYXBoeSBpcyB0aGUgYXJ0IGFuZCBzY2llbmNlIG9m
Decoded text: Steganography is the art and science of
After trying to encode to base64 just decoded lines it's possible to discover that the last bytes are sometimes changing. For example for a line:
IHdyaXRpbmcgaGlkZGVuIG1lc3NhZ2VzIGluIHN1Y2ggYSB3YXkgdGhhdCBubyBvbmV=
Decoded text: " writing hidden messages in such a way that no one"
And again encoded to base64:
IHdyaXRpbmcgaGlkZGVuIG1lc3NhZ2VzIGluIHN1Y2ggYSB3YXkgdGhhdCBubyBvbmU=
The last byte (before pad character "=") changed from V to U. Then to solve this task, we need to know base64 encoding and decoding algorithm. I've used the description from RFC 4648.
So after reading and understanding the algorithm (especially pads adding ), its possible to make an assumption: if one pad (=)  is at the end of encoded data then two bits are available for hiding data, if two pads (==) then four bits are available for hiding, and if no pad then no bits are available.
Here is a solution source code in Python:
def get_base64_diff_value(s1, s2):
 base64chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
 res = 0
 for i in xrange(len(s1)):
  if s1[i] != s2[i]:
   return abs(base64chars.index(s1[i]) - base64chars.index(s2[i]))
 return res

def solve_stego():
 with open('stego.txt', 'rb') as f:
  file_lines = f.readlines()

 bin_str = ''
 for line in file_lines:
  steg_line = line.replace('\n', '')
  norm_line = line.replace('\n', '').decode('base64').encode('base64').replace('\n', '')

  diff = get_base64_diff_value(steg_line, norm_line)
  pads_num = steg_line.count('=')
  if diff:
   bin_str += bin(diff)[2:].zfill(pads_num * 2)
  else:
   bin_str += '0' * pads_num * 2

 res_str = ''
 for i in xrange(0, len(bin_str), 8):
  res_str += chr(int(bin_str[i:i+8], 2))
 print res_str

solve_stego()
The flag is: Base_sixty_four_point_five
P.S. The task is truly unusual, and it is the first time I met a method of hiding data in Base64.

2 comments:

  1. Replies
    1. This script need Python 2 version, did you use this version to lauch the script?

      Delete