The description of this challenge can be found on
BSides website. The mission is to crack the encryption algorithm and build a fast decryptor.
The encryption is described in the following python code:
#!/usr/bin/env python
import hashlib
import sys
import base64
pin = sys.argv[1]
code = sys.argv[2]
#code = open(sys.argv[2]).read().strip()
#print "Code: ", code
hashofpass = hashlib.sha1(pin).hexdigest()[:16]
LEN = len(hashofpass)
#print hashofpass
previous = ''
result = ""
for i in range(0,len(code)):
nexta = ''
if(previous == ''):
nexta = chr(ord(code[i]) ^ ord(hashofpass[i % LEN]))
else:
nexta = chr(ord(code[i]) ^ ord(hashofpass[i % LEN]) ^ ord(previous))
previous = nexta
result += nexta
print base64.b64encode(result)
Some remarks from the previous code:
- The length of the XOR key is always 16
- The character set of the key is [0..f]
- We also know the character set of the message ([0..9-,. ])
- More than one key can decrypt an encrypted text into a plain text in this range!
- Even if it might not be obvious at first, this algorithm is actually a repetitive XOR with a 16 bytes key - simple!
The following short function transforms a text encrypted by this algorithm into a repetitive XOR encryption:
# Transform input into repeating-key XOR
def transXOR(enc):
enc = base64.b64decode(enc)
enc2 = [ascii_d[c] for c in enc]
result = [ascii_c[enc2[i] ^ enc2[i-1]]
for i in xrange(len(enc2)-1, 0, -1)][::-1]
result = ascii_c[enc2[0]] + "".join(result)
# print base64.b64encode(result)
return result
Each block, starting from the last to second, is XOR-ed with the previous one.
The following script solves this problem, and also validates the results and fixes possible errors in decryption, where multiple keys produce valid plaintexts.
#!/usr/bin/env python
import string
import base64
import sys
import re
# Example of input:
# "BgAbHU8bSx5JBBEbV1haCwkNDhxLHlUFUwIOA1RBRAsJCwsOVQJHEkYJBgZUVVIHGwAHG0EWRBJOFw8AU0RCGhkdGhBeEUcKWwkFC15VQBQQCAsIXA1dDEQVAwpfVFICEhETD14EVgVUAhYfU1xfDAsODx1KGVIGWwMLAFNGXg4QEBMVRBFMD14PGRhPREkYHwUBHU8UQRJCEgoGVkFFFx4eGhtVGk4DXwgBCl5fSh4YAAIIUwBUBk4CCxxGTkIaHxEEA1EdShpPHBwTXUlOAQEGBg1dB0IVSAcHDF9UVgAcBwYaTRxKH0Ib"
Debug = False
data = sys.argv[1]
charset = "0123456789-,. "
key_charset = "0123456789abcdef"
key_charset2 = [ord(c) for c in key_charset]
keysize = 16
ascii_c = ['\x00', '\x01', '\x02', '\x03', '\x04', '\x05', '\x06', '\x07', '\x08', '\t', '\n', '\x0b', '\x0c', '\r', '\x0e', '\x0f', '\x10', '\x11', '\x12', '\x13', '\x14', '\x15', '\x16', '\x17', '\x18', '\x19', '\x1a', '\x1b', '\x1c', '\x1d', '\x1e', '\x1f', ' ', '!', '"', '#', '$', '%', '&', "'", '(', ')', '*', '+', ',', '-', '.', '/', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', ':', ';', '<', '=', '>', '?', '@', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '[', '\\', ']', '^', '_', '`', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '{', '|', '}', '~', '\x7f', '\x80', '\x81', '\x82', '\x83', '\x84', '\x85', '\x86', '\x87', '\x88', '\x89', '\x8a', '\x8b', '\x8c', '\x8d', '\x8e', '\x8f', '\x90', '\x91', '\x92', '\x93', '\x94', '\x95', '\x96', '\x97', '\x98', '\x99', '\x9a', '\x9b', '\x9c', '\x9d', '\x9e', '\x9f', '\xa0', '\xa1', '\xa2', '\xa3', '\xa4', '\xa5', '\xa6', '\xa7', '\xa8', '\xa9', '\xaa', '\xab', '\xac', '\xad', '\xae', '\xaf', '\xb0', '\xb1', '\xb2', '\xb3', '\xb4', '\xb5', '\xb6', '\xb7', '\xb8', '\xb9', '\xba', '\xbb', '\xbc', '\xbd', '\xbe', '\xbf', '\xc0', '\xc1', '\xc2', '\xc3', '\xc4', '\xc5', '\xc6', '\xc7', '\xc8', '\xc9', '\xca', '\xcb', '\xcc', '\xcd', '\xce', '\xcf', '\xd0', '\xd1', '\xd2', '\xd3', '\xd4', '\xd5', '\xd6', '\xd7', '\xd8', '\xd9', '\xda', '\xdb', '\xdc', '\xdd', '\xde', '\xdf', '\xe0', '\xe1', '\xe2', '\xe3', '\xe4', '\xe5', '\xe6', '\xe7', '\xe8', '\xe9', '\xea', '\xeb', '\xec', '\xed', '\xee', '\xef', '\xf0', '\xf1', '\xf2', '\xf3', '\xf4', '\xf5', '\xf6', '\xf7', '\xf8', '\xf9', '\xfa', '\xfb', '\xfc', '\xfd', '\xfe', '\xff']
ascii_d = {}
for c in ascii_c:
ascii_d[c] = ord(c)
def printd(s):
if Debug:
print s
# Transform input into repeating-key XOR
def transXOR(enc):
enc = base64.b64decode(enc)
enc2 = [ascii_d[c] for c in enc]
result = [ascii_c[enc2[i] ^ enc2[i-1]]
for i in xrange(len(enc2)-1, 0, -1)][::-1]
result = ascii_c[enc2[0]] + "".join(result)
# print base64.b64encode(result)
return result
# Used below for single-char key xor decoding
def transpose(blocks):
len_b = len(blocks)
len_b0 = len(blocks[0])
t = [[blocks[j][i] for j in xrange(len_b)]
for i in xrange(len_b0)]
return t
def isGood(text):
text2 = [ascii_d[c] for c in text]
# Score: number of valid characters
for o in text2:
if o > 57:
return 0
if o < 44:
if o == 32:
continue
else:
return 0
if o == 47:
return 0
return 1
# Check for possible errors in the decrypted coordinates
# Returns position of the invalid character
def check(coords):
inv_pos = string.find(coords, '=')
if -1 != inv_pos:
return inv_pos % keysize
inv_pos = string.find(coords, ';')
if -1 != inv_pos:
return inv_pos % keysize
inv_pos = string.find(coords, '/')
if -1 != inv_pos:
return inv_pos % keysize
inv_pos = string.find(coords, '--')
if -1 != inv_pos:
# Condition needed
return inv_pos % keysize
inv_pos = string.find(coords, ',,')
if -1 != inv_pos:
return (inv_pos + 1) % keysize
inv_pos = string.find(coords, ' ,')
if -1 != inv_pos:
return (inv_pos + 1) % keysize
inv_pos = string.find(coords, ' .')
if -1 != inv_pos:
if coords[inv_pos+2] in list("0123456789"):
return (inv_pos + 1) % keysize
m = re.search('\d\-\d', coords)
if m:
inv_pos = string.find(coords, m.group(0))
if coords[inv_pos-1] in list("0123456789"):
return (inv_pos + 1) % keysize
# ,80,
m = re.search(',\d\d,', coords)
if m:
inv_pos = string.find(coords, m.group(0))
return (inv_pos + 3) % keysize
# .21.
m = re.search('\.\d\d\.', coords)
if m:
inv_pos = string.find(coords, m.group(0))
return (inv_pos) % keysize
# 7,.3
m = re.search('\d,\.\d', coords)
if m:
inv_pos = string.find(coords, m.group(0))
return (inv_pos + 2) % keysize
# ,-60,
m = re.search(',-\d\d,', coords)
if m:
inv_pos = string.find(coords, m.group(0))
return (inv_pos + 4) % keysize
# -73,
m = re.search('-\d\d,', coords)
if m:
inv_pos = string.find(coords, m.group(0))
return (inv_pos + 3) % keysize
# -61-
m = re.search('-\d\d-', coords)
if m:
inv_pos = string.find(coords, m.group(0))
return (inv_pos + 3) % keysize
# -04.
m = re.search('-0\d\.', coords)
if m:
inv_pos = string.find(coords, m.group(0))
return (inv_pos + 1) % keysize
# 03.
m = re.search('^0\d.', coords)
if m:
inv_pos = string.find(coords, m.group(0))
return (inv_pos) % keysize
#,..
if coords[0] == ',':
return 0
# 2,6199
m = re.search('\d,\d\d\d\d', coords)
if m:
inv_pos = string.find(coords, m.group(0))
return (inv_pos + 1) % keysize
inv_pos = string.find(coords, '.-')
if -1 != inv_pos:
pos = string.find(coords, '.', inv_pos + 1)
if pos-inv_pos > 6:
return (inv_pos + 1) % keysize
else:
return inv_pos % keysize
return -1
# Decrypt/encrypt function are the same
def rxor(text, key):
text2 = [ascii_d[c] for c in text]
key2 = [ascii_d[c] for c in key]
len_k = 16 # len(key)
len_t = len(text)
dec = [ascii_c[text2[i] ^ key2[i % len_k]] for i in xrange(0, len_t)]
return "".join(dec)
if __name__ == "__main__":
enc = transXOR(data)
k = [0] * keysize
blocks = [enc[i: i+keysize] for i in xrange(0, len(enc), keysize)]
# Transpose the blocks and find the key for each transposed block
# Leave the last incomplete block for easier calculations
t_blocks = transpose(blocks[:len(blocks)-1])
# all possible values for each byte of the key
all_keys = []
for i in xrange(keysize):
b = t_blocks[i]
b2 = [ascii_d[c] for c in b]
d = {}
keys_b = []
for key in key_charset2:
dec = "".join([ascii_c[c ^ key] for c in b2])
ok = isGood(dec)
if ok:
d[dec] = key
keys_b = [d[w] for w in d]
all_keys.append(keys_b)
# Take the first possible value. Check later!
k[i] = keys_b[0]
k = "".join([ascii_c[c] for c in k])
coords = rxor(enc, k)
while 1:
inv = check(coords)
if -1 == inv:
break
all_keys[inv].remove(all_keys[inv][0])
k = k[:inv] + ascii_c[all_keys[inv][0]] + k[inv+1:]
coords = rxor(enc, k)
print coords.split(' ')[3] # Original message
'''
To profile the code:
python -m cProfile -s time ./decode.py BgQaGRYXFxVAVBtERA8EAAICBw0bGhwEVVwNWFQIHR8eBAADBgkICE1YAlRCFBsaHxMWCBMZHwdaVgZQXgsSCQkKFBIRGhgaTVkDXEoYGBscGh8NFhkfB1ZfBFpbBhMICAsVFhMYHRhPVxhJSAMDDAoNBQAaEwsIXVMCVl8aGhQLDgwMAgoEHlZXAUlCHh8cDQ4IFBccHB5CSAZNTBsMCw4CAQYCGh4eVVkCUVoLCxENDA4SEhoVFkFBA0hCCQMNDwwODBYDBABLQRRAQRYWABwQEAwPAAMDX1cZUlwPGBwYGB8eEAgTEkFXDVlXBggOEwoNERIYGxxB
'''
The algorithm is generic and can be applied to decrypt any repetitive XOR encrypted text.
After OSCP exam, I was eager to start the CTP training as soon as possible. The course is mostly assembly based. I've spent most of the time in OllyDbg. Besides that, the course has a also web based module, and a networking module. All of them are very interesting and require extra reading and practice to fully understand and be able to reproduce the techniques (during the stressful exam hours!). 
