TE: SSCTF 2016 - HeHeDa (Crypto & Exploit 100pts)

In this challenge, we are given the following code:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def LShift(t, k):
    k %= 8
    return ((t << k) | (t >> (8 - k))) & 0xff


def encode(p):
    ret = ""
    for i in range(8):
        ret = ('|' if (p >> i) & 1 else 'O') + ret
    return ret


A = [85, 128, 177, 163, 7, 242, 231, 69, 185, 1, 91, 89, 80, 156, 81, 9, 102, 221, 195, 33, 31, 131, 179, 246, 15, 139, 205, 49, 107, 193, 5, 63, 117, 74, 140, 29, 135, 43, 197, 212, 0, 189, 218, 190, 112, 83, 238, 47, 194, 68, 233, 67, 122, 138, 53, 14, 35, 76, 79, 162, 145, 51, 90, 234, 50, 6, 225, 250, 215, 133, 180, 97, 141, 96, 20, 226, 3, 191, 187, 57, 168, 171, 105, 113, 196, 71, 239, 200, 254, 175, 164, 203, 61, 16, 241, 40, 176, 59, 70, 169, 146, 247, 232, 152, 165, 62, 253, 166, 167, 182, 160, 125, 78, 28, 130, 159, 255, 124, 153, 56, 58, 143, 150, 111, 207, 206, 32, 144,
     75, 39, 10, 201, 204, 77, 104, 65, 219, 98, 210, 173, 249, 13, 12, 103, 101, 21, 115, 48, 157, 147, 11, 99, 227, 45, 202, 158, 213, 100, 244, 54, 17, 161, 123, 92, 181, 243, 184, 188, 84, 95, 27, 72, 106, 192, 52, 44, 55, 129, 208, 109, 26, 24, 223, 64, 114, 19, 198, 23, 82, 120, 142, 178, 214, 186, 116, 94, 222, 86, 251, 36, 4, 248, 132, 25, 211, 199, 30, 87, 60, 127, 155, 41, 224, 151, 237, 136, 245, 37, 170, 252, 8, 42, 209, 46, 108, 88, 183, 149, 110, 66, 235, 229, 134, 73, 38, 118, 236, 119, 154, 216, 217, 240, 22, 121, 174, 93, 126, 230, 228, 18, 148, 220, 172, 2, 137, 34]
B = [0, 2, 3, 7, 1, 5, 6, 4]
C = [179, 132, 74, 60, 94, 252, 166, 242, 208, 217, 117, 255, 20, 99, 225, 58, 54, 184, 243, 37, 96, 106, 64, 151, 148, 248, 44, 175, 152, 40, 171, 251, 210, 118, 56, 6, 138, 77, 45, 169, 209, 232, 68, 182, 91, 203, 9, 16, 172, 95, 154, 90, 164, 161, 231, 11, 21, 3, 97, 70, 34, 86, 124, 114, 119, 223, 123, 167, 47, 219, 197, 221, 193, 192, 126, 78, 39, 233, 4, 120, 33, 131, 145, 183, 143, 31, 76, 121, 92, 153, 85, 100, 52, 109, 159, 112, 71, 62, 8, 244, 116, 245, 240, 215, 111, 134, 199, 214, 196, 213, 180, 189, 224, 101, 202, 201, 168, 32, 250, 59, 43, 27, 198, 239, 137, 238, 50,
     149, 107, 247, 7, 220, 246, 204, 127, 83, 146, 147, 48, 17, 67, 23, 93, 115, 41, 191, 2, 227, 87, 173, 108, 82, 205, 49, 1, 66, 105, 176, 22, 236, 29, 170, 110, 18, 28, 185, 235, 61, 88, 13, 165, 188, 177, 230, 130, 253, 150, 211, 42, 129, 125, 141, 19, 190, 133, 53, 84, 140, 135, 10, 241, 222, 73, 12, 155, 57, 237, 181, 36, 72, 174, 207, 98, 5, 229, 254, 156, 178, 128, 55, 14, 69, 30, 194, 122, 46, 136, 160, 206, 26, 102, 218, 103, 139, 195, 0, 144, 186, 249, 79, 81, 75, 212, 234, 158, 163, 80, 226, 65, 200, 38, 187, 113, 63, 24, 25, 142, 51, 228, 35, 157, 216, 104, 162, 15, 89]
D = [2, 4, 0, 5, 6, 7, 1, 3]

plain = bytearray("asdfghjk123456")
key = bytearray(/*Missed*/)
assert len(key) == 8
t1 = bytearray()
for i in plain:
    t1.append(A[i])
t2 = bytearray()
for i in range(len(t1)):
    t2.append(LShift(t1[i], B[i % 8]))
for times in range(16):
    for i in range(len(t2)):
        t2[i] = C[t2[i]]
    for i in range(len(t2)):
        t2[i] = LShift(t2[i], i ^ D[i % 8])
    for i in range(len(t2)):
        t2[i] ^= key[i % 8]
out = ""
for i in t2:
    out += encode(i)
print out

# out>>
# OO|OO||OO|||||OO|OO||O||O|O||O|||O|OOOOOOO|O|O|O|||||OO|||O|||OO||O|OOOOOO|O|OO|OO||||OO|||OOOO|||||O||||O|OO|O|O|O||OO|O||O|OO|O||O|||O||O|OO|OOOOOO||OOO|O|O|O|||O|OO|O|O||O||O||OOOOO|||OO|O|

# flag >>
# OO||O||O|O|||OOOO||||||O|O|||OOO||O|OOOO||O|O|OO|||||OOOO||||O||OO|OO||O||O|O|O|||||OOOOOO|O|O||OOOOOOO||O|||OOOO||OO|OO|||O|OO|O|||O|O|OO|OOOO|OOO|OOO|OOOO||O|OO||||OO||||OOO|O|O||OO||||O||OOO|||O|OO|OO||OO||OOOO|O|


Objective

From the code above, it seems evident that some form of encryption is going on here. We then see at the bottom of the code that there are two ciphertexts given: (1) "out" and (2) "flag". From this, we can infer that the objective of this challenge is probably to decrypt the given ciphertext for "flag". However, before we can do that, we first need to recover the symmetric key used in the cipher.

Understanding the encryption process

Before we can proceed with recovering the cipher key, we need to first understand what is going on in the encryption process:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
for i in plain:
    t1.append(A[i])
t2 = bytearray()
for i in range(len(t1)):
    t2.append(LShift(t1[i], B[i % 8]))
for times in range(16):
    for i in range(len(t2)):
        t2[i] = C[t2[i]]
    for i in range(len(t2)):
        t2[i] = LShift(t2[i], i ^ D[i % 8])
    for i in range(len(t2)):
        t2[i] ^= key[i % 8]
out = ""
for i in t2:
    out += encode(i)

In lines 1-2, we see that each character in the plaintext is mapped to another character from the list "A" and added to the byte array "t1".

In lines 4-5, we left-rotate the bitstring of each character in the byte array "t1" by a given amount. The amount of rotation depends only on the position of this character in the byte array.

In lines 6-12, we perform some sort of position-dependent obfuscation (lines 7-10) and XOR operation with the corresponding key 16 times over.

In lines 13-15, we encode each byte in the byte array "t2" into a bitstring with "0" representing the binary 0 and "|" representing the binary 1.

Notice that throughout the entire encryption process, each character in the plaintext is encrypted independently from the other characters. This is a crucial observation which we will leverage on to recover the cipher key.

Recovering the cipher key

Since each character in the plaintext is encrypted using only one byte from the key, we can essentially get a set of candidate keys for each position using the known-plaintext attack. From the given code, we know that the ciphertext "OO|OO||OO|||||OO|OO||O||O|O||O|||O|OOOOOOO|O|O|O|||||OO|||O|||OO||O|OOOOOO|O|OO|OO||||OO|||OOOO|||||O||||O|OO|O|O|O||OO|O||O|OO|O||O|||O||O|OO|OOOOOO||OOO|O|O|O|||O|OO|O|O||O||O||OOOOO|||OO|O|" contains the partial plaintext "asdfghjk123456". Using this information, we bruteforce all 256 possible keys for each position to arrive at a set of candidate keys. However, this is not good enough since it does not produce only 1 key. We then observe that the cipher uses a block size of 8, and splitting the partial plaintext into blocks we get "asdfghjk" + "123456". Intuitively, we would append "78" behind the partial plaintext to get a longer known plaintext. Doing this allowed us to narrow the list of candidate keys to only 1 key. Therefore, this is likely the symmetric key that we're seeking.

Decrypting the flag

This process is relatively straightforward as it only involves the reverse of every step in the encryption process described above. Once we decrypt the flag using the key obtained in the previous step, we get the flag "SSCTF{1qaz9ol.nhy64rfv7ujm}". Hurray!

Here's the code that I used in entirety (it contains some ugly code as I was coding in a rush):


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
import itertools

A = [85, 128, 177, 163, 7, 242, 231, 69, 185, 1, 91, 89, 80, 156, 81, 9, 102, 221, 195, 33, 31, 131, 179, 246, 15, 139, 205, 49, 107, 193, 5, 63, 117, 74, 140, 29, 135, 43, 197, 212, 0, 189, 218, 190, 112, 83, 238, 47, 194, 68, 233, 67, 122, 138, 53, 14, 35, 76, 79, 162, 145, 51, 90, 234, 50, 6, 225, 250, 215, 133, 180, 97, 141, 96, 20, 226, 3, 191, 187, 57, 168, 171, 105, 113, 196, 71, 239, 200, 254, 175, 164, 203, 61, 16, 241, 40, 176, 59, 70, 169, 146, 247, 232, 152, 165, 62, 253, 166, 167, 182, 160, 125, 78, 28, 130, 159, 255, 124, 153, 56, 58, 143, 150, 111, 207, 206, 32, 144,
     75, 39, 10, 201, 204, 77, 104, 65, 219, 98, 210, 173, 249, 13, 12, 103, 101, 21, 115, 48, 157, 147, 11, 99, 227, 45, 202, 158, 213, 100, 244, 54, 17, 161, 123, 92, 181, 243, 184, 188, 84, 95, 27, 72, 106, 192, 52, 44, 55, 129, 208, 109, 26, 24, 223, 64, 114, 19, 198, 23, 82, 120, 142, 178, 214, 186, 116, 94, 222, 86, 251, 36, 4, 248, 132, 25, 211, 199, 30, 87, 60, 127, 155, 41, 224, 151, 237, 136, 245, 37, 170, 252, 8, 42, 209, 46, 108, 88, 183, 149, 110, 66, 235, 229, 134, 73, 38, 118, 236, 119, 154, 216, 217, 240, 22, 121, 174, 93, 126, 230, 228, 18, 148, 220, 172, 2, 137, 34]
B = [0, 2, 3, 7, 1, 5, 6, 4]
C = [179, 132, 74, 60, 94, 252, 166, 242, 208, 217, 117, 255, 20, 99, 225, 58, 54, 184, 243, 37, 96, 106, 64, 151, 148, 248, 44, 175, 152, 40, 171, 251, 210, 118, 56, 6, 138, 77, 45, 169, 209, 232, 68, 182, 91, 203, 9, 16, 172, 95, 154, 90, 164, 161, 231, 11, 21, 3, 97, 70, 34, 86, 124, 114, 119, 223, 123, 167, 47, 219, 197, 221, 193, 192, 126, 78, 39, 233, 4, 120, 33, 131, 145, 183, 143, 31, 76, 121, 92, 153, 85, 100, 52, 109, 159, 112, 71, 62, 8, 244, 116, 245, 240, 215, 111, 134, 199, 214, 196, 213, 180, 189, 224, 101, 202, 201, 168, 32, 250, 59, 43, 27, 198, 239, 137, 238, 50,
     149, 107, 247, 7, 220, 246, 204, 127, 83, 146, 147, 48, 17, 67, 23, 93, 115, 41, 191, 2, 227, 87, 173, 108, 82, 205, 49, 1, 66, 105, 176, 22, 236, 29, 170, 110, 18, 28, 185, 235, 61, 88, 13, 165, 188, 177, 230, 130, 253, 150, 211, 42, 129, 125, 141, 19, 190, 133, 53, 84, 140, 135, 10, 241, 222, 73, 12, 155, 57, 237, 181, 36, 72, 174, 207, 98, 5, 229, 254, 156, 178, 128, 55, 14, 69, 30, 194, 122, 46, 136, 160, 206, 26, 102, 218, 103, 139, 195, 0, 144, 186, 249, 79, 81, 75, 212, 234, 158, 163, 80, 226, 65, 200, 38, 187, 113, 63, 24, 25, 142, 51, 228, 35, 157, 216, 104, 162, 15, 89]
D = [2, 4, 0, 5, 6, 7, 1, 3]

out = "OO|OO||OO|||||OO|OO||O||O|O||O|||O|OOOOOOO|O|O|O|||||OO|||O|||OO||O|OOOOOO|O|OO|OO||||OO|||OOOO|||||O||||O|OO|O|O|O||OO|O||O|OO|O||O|||O||O|OO|OOOOOO||OOO|O|O|O|||O|OO|O|O||O||O||OOOOO|||OO|O|"
pplain = "asdfghjk123456" + "78"
flag = "OO||O||O|O|||OOOO||||||O|O|||OOO||O|OOOO||O|O|OO|||||OOOO||||O||OO|OO||O||O|O|O|||||OOOOOO|O|O||OOOOOOO||O|||OOOO||OO|OO|||O|OO|O|||O|O|OO|OOOO|OOO|OOO|OOOO||O|OO||||OO||||OOO|O|O||OO||||O||OOO|||O|OO|OO||OO||OOOO|O|"

a_idx = {}
for i in range(len(A)):
    a_idx[A[i]] = i
c_idx = {}
for i in range(len(C)):
    c_idx[C[i]] = i

def LShift(t, k):
    k %= 8
    return ((t << k) | (t >> (8 - k))) & 0xff

def RShift(t, k):
    return LShift(t, 8-k)

def partition(string, l):
    return [string[i*l:(i+1)*l:] for i in range(len(string)/l)]

def encode(p):
    ret = ""
    for i in range(8):
        ret = ('|' if (p >> i) & 1 else 'O') + ret
    return ret

def decode(string):
    bitstring = ""
    for c in string:
        if c == '|':
            bitstring += '1'
        else:
            bitstring += '0'
    return int(bitstring, 2)

def getOut(plain, key):
    plain = bytearray(plain)
    assert len(key) == 8
    t1 = bytearray()
    for i in plain:
        t1.append(A[i])
    t2 = bytearray()
    for i in range(len(t1)): # len = 14
        t2.append(LShift(t1[i], B[i % 8]))
    for times in range(16):
        for i in range(len(t2)):
            t2[i] = C[t2[i]]
        for i in range(len(t2)):
            t2[i] = LShift(t2[i], i ^ D[i % 8])
        for i in range(len(t2)):
            t2[i] ^= key[i % 8]
    out = ""
    for i in t2:
        out += encode(i)
    return out

def getIn(out, key):
    chunks = partition(out, 8)
    t2 = bytearray()
    t1 = bytearray()
    for chunk in chunks:
        t2.append(decode(chunk))
    for times in range(16):
        for i in range(len(t2)):
            t2[i] ^= key[i % 8]
        for i in range(len(t2)):
            t2[i] = RShift(t2[i], i ^ D[i % 8])
        for i in range(len(t2)):
            t2[i] = c_idx[t2[i]]
    for i in range(len(t2)):
        t1.append(RShift(t2[i], B[i % 8]))
    plain = []
    for v in t1:
        plain.append(chr(a_idx[v]))
    return "".join(plain)

def getCandidates(plain, out):
    defaultKeys = [1,2,3,4,5,6,7,8]
    obtainedKeys = [[] for i in range(8)]
    for c in plain:
        idx = plain.index(c)
        this_block = partition(out, 8)[idx]
        sth = idx*'x' + c
        for k in range(256):
            defaultKeys[idx % 8] = k
            ob = getOut(sth, defaultKeys)
            if partition(ob, 8)[-1] == this_block:
                obtainedKeys[idx % 8].append(k)
    return obtainedKeys

def getUniqueCandidates(candidates):
    uniqC = set()
    for candidate in itertools.product(*candidates):
        uniqC.add(candidate)
    return uniqC

def getFlag():
    candidates = getCandidates(pplain, out)
    candidates = getUniqueCandidates(candidates)
    for candidate in candidates:
        if pplain in getIn(out, candidate):
            print getIn(flag, candidate)

# out>>
# OO|OO||OO|||||OO|OO||O||O|O||O|||O|OOOOOOO|O|O|O|||||OO|||O|||OO||O|OOOOOO|O|OO|OO||||OO|||OOOO|||||O||||O|OO|O|O|O||OO|O||O|OO|O||O|||O||O|OO|OOOOOO||OOO|O|O|O|||O|OO|O|O||O||O||OOOOO|||OO|O|

# flag >>
# OO||O||O|O|||OOOO||||||O|O|||OOO||O|OOOO||O|O|OO|||||OOOO||||O||OO|OO||O||O|O|O|||||OOOOOO|O|O||OOOOOOO||O|||OOOO||OO|OO|||O|OO|O|||O|O|OO|OOOO|OOO|OOO|OOOO||O|OO||||OO||||OOO|O|O||OO||||O||OOO|||O|OO|OO||OO||OOOO|O|


Moral of the Story

Using a 8-byte key does not necessarily mean that your cipher is 8-byte strong. If you are using the bytes in the key independently to encrypt information, your cipher is only as strong as each byte in the key. Therefore, the lesson learnt here is to use a proper cipher suite so that you don't make rookie mistakes like these.


Comments

Post a Comment