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| 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.

Defragmented Brains 2013-2016