SIGINT CTF 2013 - Writeup crypto - kacke
Points: 400 Description: We intercepted following message: 28 c0 65 a3 f9 60 05 a4 09 d9 b0 01 20 0f 15 54 87 10 It is encrypted using a 4 byte key with the Kassandra cloud encryption Can you crack it? You find the kassandra clound encyption service here: 188.40.147.119 9001 This flag does not have a SIGINT_ prefix!
Sample connection to kassandra cloud encryption service:
nc 188.40.147.119 9001 [==================================================================================================] KASSANDRA Cloud Krypto Evaluation (KACKE™) We deliver to you: High performance CloudCrypt™ for your sensitive data Because Trust is important [==================================================================================================] please enter your secret key:aaaa please enter your plaintext:hhhhhhhhhhhhhhhhhh 84 84 90 09 48 84 09 90 90 09 84 90 09 84 90 84 09 09 please enter your secret key:aaaa please enter your plaintext:bhhhhhhhhhhhhhhhhh 84 84 90 09 18 84 09 90 90 09 84 90 09 84 90 84 09 09 please enter your secret key:aaaa please enter your plaintext:_hhhhhhhhhhhhhhhhh 90 90 09 84 f1 90 84 09 09 84 90 09 84 90 09 90 84 84
We know, that we need a 4 byte key. The length of the plain message is the same as the length of the cipher message. Therefore, we look for 18 byte plain text message. After analysis we found that the key and the plain message are xored and, afterwards, shifted.
The Following table shows the relationship between key, plain text message and cipher message:
- key: 4 byte key. the column shows the position of the key wich will be xored with the position of the plain message
- pp: position of the plain text message
- pc: position of the xored byte in the final result (cipher message)
key| pp -> pc -------------- a | 1 -> 5 b | 2 -> 4 c | 3 -> 1 d | 4 -> 15 a | 5 -> 18 b | 6 -> 16 c | 7 -> 3 d | 8 -> 10 a | 9 -> 14 b | 10 -> 8 c | 11 -> 7 d | 12 -> 2 a | 13 -> 9 b | 14 -> 13 c | 15 -> 6 d | 16 -> 12 a | 17 -> 17 b | 18 -> 11
After many, many, many hours we found the algorithm for the shift operation. The first byte of the plain text message will be circular shifted 5 positions left. Therefore, the fifth byte in the resulting cipher message is pc[4] = (key[0]^pp[0]) << 5 | (key[0]^pp[0]) >> 3. For all other bytes of the plain text message always use the result of the previous cipher message to find the value for the shift operation. Always use the 3 lower bits for the circular shift. So, for the second step pc[3] = (key[1]^pp[1]) << (pc[4] &0x07) | (key[1]^pp[1]) >> (8 - pc[4] &0x07).
Now, we can analyze the given cipher text after reverting the shift operation. Brute forcing the 4 bytes of the key byte by byte gives all possible values for the key which result in printable plain text. Afterwars, we only use combinations where all resulting characters are in the allowed range of input characters (0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_.!?) for the kassandra service.
The following script executes the relevant steps and outputs a list of all possible plain text messages.
import sys
import string
mapping = [5, 4, 1, 15, 18, 16, 3, 10, 14, 8, 7, 2, 9, 13, 6, 12, 17, 11]
cipher = [0x28, 0xc0, 0x65, 0xa3, 0xf9, 0x60, 0x05, 0xa4, 0x09, 0xd9, 0xb0, 0x01, 0x20, 0x0f, 0x15, 0x54, 0x87, 0x10]
def formatb(v):
return bin(v)[2:].zfill(8)
def format(v):
v = v[2:]
if len(v) < 2:
v = "0"+v
return str(v)
def shift(cip, sh):
cip1 = ((cip << sh) & 0xff)
cip2 = (cip >> (8-sh))
cip3 = (cip1 | cip2)
return format(str(hex(cip3)))
def isprintable(c):
return c in '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_.!?'
def brute(xoredcipher, keypos):
possiblekeys = []
for k in '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_.!?':
valid = True
for i in range(0, len(xoredcipher)):
if i % 4 == keypos-1:
p = ord(k) ^ int("0x"+xoredcipher[i], 16)
if not isprintable(chr(p)):
valid = False
break
if valid:
possiblekeys.append(k)
return possiblekeys
def decipher(xoredcipher, key):
res = ""
for i in range(0, len(xoredcipher)):
c = int("0x"+xoredcipher[i], 16) ^ ord(key[i%4])
res = res+chr(c)
return res
def deshift():
xoredcipher = []
previous = ""
# find the plain text and the key
for i in range(0, len(cipher)):
# position in the cipher text for the input value position i
pos = mapping[i] - 1
# reverse the cipher text for the position pos
c = cipher[pos]
if i == 0:
sh = 5
else:
sh = previous & 0x07
xorc = shift(c, sh)
xoredcipher.append(xorc)
previous = c
return xoredcipher
# revert the shift operation in the cipher message and reposition the bytes to the plain message so that
# plain[i] = xoredcipher[i]^key[i%4]
xoredcipher = deshift()
print str(xoredcipher)
# find the possible values for each key position
keys = []
for i in range(0, 4):
keys.append(brute(xoredcipher, i+1))
print "values for key pos["+str(i)+"]: "+str(keys[i])
# for all combinations of the key values generate the possible plain message
for k1 in keys[0]:
for k2 in keys[1]:
for k3 in keys[2]:
for k4 in keys[3]:
key = k1+k2+k3+k4
val = decipher(xoredcipher, key)
print key+": "+val
After analyzing the resulting plain text messages we find a possible flag with the encryption key "l33t":
StrangeOraclesSuck
Unfortunately, we solved the challenge not earlier than after the end of the CTF. Therfore, we don't know for sure if this result was the correct flag.