Obscured - De1CTF 2019

Crypto
, ,

Challenge Description

1
2
3
nc 45.32.100.6 8003（Singapore）

nc 39.108.37.223 8003 (China)

Attachment

- task.py

task.py

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
import os,random,sys,string
from hashlib import sha256
import SocketServer
import signal
from FLAG import flag

def pad(x):
    pad_length = 8-len(x)
    return pad_length*'0'+x

def hex2list(x):
    res = []
    for i in range(0,32,8):
        r = x[i:i+8]
        res.append(int(r,16))
    return res

def list2hex(x):
    res = ''
    for i in range(4):
        res += pad(hex(x[i])[2:])
    return res

# Sbox is a secret permutation from F(2^32) to itself
def Sbox(plain):
    '''
        Obscured
    '''


def encrypt(msg):
    msg = hex2list(msg)
    A , B , C , D = msg[0],msg[1],msg[2],msg[3]
    for _ in range(6):
        S = Sbox(A^C)
        A , B , C , D = A ^ B ^ S , A ^ B ^ D ^ S , A ^ C ^ D , C ^ D ^ S 
    return list2hex([A,B,C,D])


class Task(SocketServer.BaseRequestHandler):
    def proof_of_work(self):
        random.seed(os.urandom(8))
        proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
        digest = sha256(proof).hexdigest()
        self.request.send("sha256(XXXX+%s) == %s\n" % (proof[4:],digest))
        self.request.send('Give me XXXX:')
        x = self.request.recv(10)
        x = x.strip()
        if len(x) != 4 or sha256(x+proof[4:]).hexdigest() != digest: 
            return False
        return True
    
    def recvhex(self, sz):
        try:
            r = sz
            res = ''
            while r>0:
                res += self.request.recv(r)
                if res.endswith('\n'):
                    r = 0
                else:
                    r = sz - len(res)
            res = res.strip()
        except:
            res = ''
        return res.strip('\n')

    def dosend(self, msg):
        try:
            self.request.sendall(msg)
        except:
            pass

    def handle(self):
        signal.alarm(500)
        if not self.proof_of_work():
            return
        signal.alarm(450)
        secret = os.urandom(16).encode('hex')
        s = encrypt(secret)
        self.dosend('Welcome to the Crypto System.\n')
        self.dosend('You can encrypt any plain you want and if you tell me the secret I will give you the flag.\n')    
        self.dosend('The enc_secret is: '+s+'\n')
        for _ in range(20):
            self.dosend("Tell me the plaintext(hex): ")
            pt = self.recvhex(33)
            if pt=='':
                break
            if len(pt)!=32:
                self.dosend('The length must be 32!!!\n')
                continue
            ct = encrypt(pt)
            self.dosend("The result is: %s\n" % ct)
        self.dosend('Tell me the secret and I will give you the flag.\n')
        self.dosend('Secret(hex):\n')
        sc = self.recvhex(33)
        if sc==secret:
            self.dosend('Wow! How smart you are! Here is your flag:\n')
            self.dosend(flag)
        else:
            self.dosend('Sorry you are wrong!\n')
        self.request.close()


class ForkedServer(SocketServer.ForkingTCPServer, SocketServer.TCPServer):
    pass


if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 8003
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

Enryption Block Diagram

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
                                         one - Round 

                                       Message-Block
-----------------------------------------------------------------------------------------
|          A          |          B          |          C          |          D          |
-----------------------------------------------------------------------------------------
                |                |                   |   |                   |
            A-->|            B-->|               C-->|   |<--C               |<--D
                |---------------/--------------------⊕   |                   |  
                |              /                A⊕C->|   |------⊕------------|
                |             /               -------------     |            |
                |            /                |           |     |            |
                |           |                 |   S-Box   |     |            |
                |       B-->|                 |           |     |<-C⊕D       |
                |        ---|                 -------------     |            |
                |        |                         |            |            |
                |        V                     S-->|            |            |
    ------------|------->⊕<------------------------|            |            |
    |                    |                         |            |            |
    |                    |<--A⊕B⊕S                 |            |            |
    |       -------------|                         |            |            |
    |       |                                      |<--S        |            |
    |       |--------------->⊕<--------------------|------------|------------|
    |       |          ^     |   ^                 |            |      
    |       |          |     |   |                 |-----------/-----------|
    |       |       A⊕B⊕S    |   D                            /            |
    |       |                |                        C⊕D--> /             |<--S
    |       |                |<--A⊕B⊕S⊕D                    /              |
    |       |                |                   A         |---------------⊕
A-->|       |                |                   |         |               |
    |       |                |                   V         V               |
    |-------|----------------|---------------------------->⊕               |
            |                |                             |               |
            |                |                             |               |
            |                |                             |               |
            |<--A⊕B⊕S        |<--A⊕B⊕S⊕D                   |<--A⊕C⊕D       |<--A⊕C⊕D⊕S
            |                |                             |               |
            |                |                             |               |
            V                V                             V               V
-----------------------------------------------------------------------------------------
|          A          |          B          |          C          |          D          |
-----------------------------------------------------------------------------------------

Observation

NSUCRYPTO-2017 TwinPeaks inspire this challenge, but in a quick view, we can see that server uses a custom encryption algorithm (similar to TwinPeaks) to encrypt a 16-byte block of random bytes. Our goal is to get the secret just by knowing the ciphertext, and the server also allows us to encrypt our plaintext 20 times. However, we can solve the challenge just by using six queries.

Encryption Algorithm

Function

1
2
3
4
5
6
7
def encrypt(msg):
    msg = hex2list(msg)
    A , B , C , D = msg[0],msg[1],msg[2],msg[3]
    for _ in range(6):
        S = Sbox(A^C)
        A , B , C , D = A ^ B ^ S , A ^ B ^ D ^ S , A ^ C ^ D , C ^ D ^ S 
    return list2hex([A,B,C,D])

If we notice the encryption algorithm, most of the part of the algorithm is just XORing and a Sbox, which is an unknown function, but how can we even think of decrypting an unknown encryption algorithm (either with or without the key), which turns out since the whole encryption process excluding Sbox is just XORing it is more likely to get the repetition of the same data and get cancelled out and this makes it feasible to make equations and get what we want.

Let’s observe what’s happening in each round

Round 1

1
2
3
4
5
S0  =    Sbox(A0 ^ C0)
A1  =    A0     ^    B0  ^   S0
B1  =    A0     ^    B0  ^   D0  ^   S0
C1  =    A0     ^    C0  ^   D0
D1  =    C0     ^    D0  ^   S0

Round 2

1
2
3
4
5
S1  =    Sbox(A1 ^ C1)                      =   Sbox(B0 ^ C0 ^ D0 ^ S0)
A2  =    A1     ^    B1  ^   S1             =   D0     ^    S1
B2  =    A1     ^    B1  ^   D1  ^   S1     =   C0     ^    S0  ^   S1
C2  =    A1     ^    C1  ^   D1             =   B0
D2  =    C1     ^    D1  ^   S1             =   A0     ^    S0  ^   S1

Round 3

1
2
3
4
5
S2  =    Sbox(A2 ^ C2)                      =   Sbox(B0 ^ D0 ^ S1)
A3  =    A2     ^    B2  ^   S2             =   C0     ^    D0  ^   S0  ^   S2
B3  =    A2     ^    B2  ^   D2  ^   S2     =   A0     ^    C0  ^   D0  ^   S1  ^   S2
C3  =    A2     ^    C2  ^   D2             =   A0     ^    B0  ^   D0  ^   S0
D3  =    C2     ^    D2  ^   S2             =   A0     ^    B0  ^   S0  ^   S1  ^   S2

Round 4

1
2
3
4
5
S3  =    Sbox(A3 ^ C3)                      =   Sbox(A0 ^ B0 ^ C0 ^ S2)
A4  =    A3     ^    B3  ^   S3             =   A0     ^    S0  ^   S1  ^   S3
B4  =    A3     ^    B3  ^   D3  ^   S3     =   B0     ^    S2  ^   S3
C4  =    A3     ^    C3  ^   D3             =   C0     ^    S0  ^   S1
D4  =    C3     ^    D3  ^   S3             =   D0     ^    S1  ^   S2  ^   S3

Round 5

1
2
3
4
5
S4  =    Sbox(A4 ^ C4)                      =   Sbox(A0 ^ C0 ^ S3)
A5  =    A4     ^    B4  ^   S4             =   A0     ^    B0  ^   S0  ^   S1  ^   S2  ^   S4
B5  =    A4     ^    B4  ^   D4  ^   S4     =   A0     ^    B0  ^   D0  ^   S0  ^   S3  ^   S4
C5  =    A4     ^    C4  ^   D4             =   A0     ^    C0  ^   D0  ^   S1  ^   S2
D5  =    C4     ^    D4  ^   S4             =   C0     ^    D0  ^   S0  ^   S2  ^   S3  ^   S4

Round 6

1
2
3
4
5
S5  =    Sbox(A5 ^ C5)                      =   Sbox(B0 ^ C0 ^ D0 ^ S0 ^ S4)
A6  =    A5     ^    B5  ^   S5             =   D0     ^    S1  ^   S2  ^   S3  ^   S5
B6  =    A5     ^    B5  ^   D5  ^   S5     =   C0     ^    S0  ^   S1  ^   S4  ^   S5
C6  =    A5     ^    C5  ^   D5             =   B0     ^    S2  ^   S3
D6  =    C5     ^    D5  ^   S5             =   A0     ^    S0  ^   S1  ^   S3  ^   S4  ^   S5

Exploit Idea

If we notice the equations of Round-6, we can say that a6, b6, c6, d6 are equal to a0, b0, c0, d0 with a lot of S's xored since it is just the bunch of s’s that are xored extra if we can able to cancel them out we can find a0, b0, c0, d0.

Equations

1
2
3
4
A6  =   D0     ^    S1  ^   S2  ^   S3  ^   S5
B6  =   C0     ^    S0  ^   S1  ^   S4  ^   S5
C6  =   B0     ^    S2  ^   S3
D6  =   A0     ^    S0  ^   S1  ^   S3  ^   S4  ^   S5

Rearranging them gives us:

1
2
3
4
D0  =   A6     ^    S1  ^   S2  ^   S3  ^   S5
C0  =   B6     ^    S0  ^   S1  ^   S4  ^   S5
B0  =   C6     ^    S2  ^   S3
A0  =   D6     ^    S0  ^   S1  ^   S3  ^   S4  ^   S5

So, to recover the plaintext, we need to know the values of all S's. Here, in this case, we can recover at most of 2 s values S2 and S3 If we know A0 and C0 by rearranging the equations:

1
2
3
4
5
6
7
8
9
10
B6 ^ D6 :
            C0  ^   S0  ^   S1      ^       S4  ^   S5

                             ⊕
            
            A0  ^   S0  ^   S1  ^   S3  ^   S4  ^   S5
        ------------------------------------------------
                    A0  ^   C0  ^   S3

S3  =   B6  ^   D6  ^   A0  ^   C0

now with the value of S3 and B0 we can recover s2 as well:

1
2
3
C6  =   B0  ^   S2  ^   S3  
                        
                            ==> S2  =   C6  ^   B0  ^   S3

Since we should know the plaintext to recover S2 and S3, we cannot recover the S-values of the secret. This leads us to use the queries and try to get the S values we need. If we look at all the s-equations:

1
2
3
4
5
6
S0  =   Sbox(   A0 ^ C0                     )
S1  =   Sbox(   B0 ^ C0 ^ D0 ^ S0           )
S2  =   Sbox(   B0 ^ D0 ^ S1                )
S3  =   Sbox(   A0 ^ B0 ^ C0 ^ S2           )
S4  =   Sbox(   A0 ^ C0 ^ S3                )
S5  =   Sbox(   B0 ^ C0 ^ D0 ^ S0 ^ S4      )

Since we can recover S2 and S3, if we could craft the plaintext to get the output of the Sbox function, we can recover all the S0-S5 values and will be able to recover the secret. My idea is to craft the message such that B0 ^ C0 ^ D0 ^ S0 will give the value we need so we get the value of S2 which is Sbox(value needed) but we don’t know the value of S0, so if we craft our msg having A0 = m, B0 = m, C0 = m ^ x, D0 = Sbox(x) value of S0 will be Sbox(x) since S0 = Sbox( A0 ^ C0 ) = Sbox( m ^ m ^ x ) = Sbox(x) and in the equation of S1 -> B0 ^ C0 ^ D0 ^ S0 = m ^ m ^ x ^ Sbox(x) ^ Sbox(x) = x so S1 = Sbox(x) = S0 = D0 now in the equation of S2 -> B0 ^ D0 ^ S1 = B0 since S0 == S1 == D0 and B0 == m now the value of S2 is Sbox(m) the value we need, but for to do all this we need a pair of input and output values of Sbox() for that we can send 0 as message then the equations are like:

1
2
3
4
5
6
S0  =   Sbox(   A0 ^ C0                 )   =   Sbox(   0   )
S1  =   Sbox(   B0 ^ C0 ^ D0 ^ S0       )   =   Sbox(   S0  )
S2  =   Sbox(   B0 ^ D0 ^ S1            )   =   Sbox(   S1  )
S3  =   Sbox(   A0 ^ B0 ^ C0 ^ S2       )   =   Sbox(   S2  )
S4  =   Sbox(   A0 ^ C0 ^ S3            )   =   Sbox(   S3  )
S5  =   Sbox(   B0 ^ C0 ^ D0 ^ S0 ^ S4  )   =   Sbox(   S4  )

Since we can recover S2 and S3 values and S3 = Sbox(S2), we have an input-output pair. Let x = S2 and y = S3. Now we can craft our message to get the Sbox(m) of m we need. For that the msg will be A0 = m, B0 = m, C0 = m ^ x, D0 = y and by recovering S2 from the ciphertext, we get Sbox(m).

Sbox

1
2
3
4
5
6
7
8
9
10
11
12
13
def SBox(m):
    x = inp = 3452694591    # hardcoded the values
    y = out = 2745719712
    A0 = m
    B0 = m
    C0 = m ^ x
    D0 = y
    pt = list2hex([A0, B0, C0, D0])
    # encrypt here
    ct = encrypt(pt)
    A6, B6, C6, D6 = hex2list(ct)
    s2 = C6 ^ B0 ^ A0 ^ C0 ^ B6 ^ D6  # Read the really long hypothesis
    return s2   # Sbox(m)

Now we officially have an oracle which gives the output of Sbox(), and all we need is to get all the 5 S values to recover the secret.

Recovering Sbox - Values

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
start = io.recvuntil('): ')
secret = res.search(start).group()
A6, B6, C6, D6 = hex2list(secret)
m1 = B6 ^ D6
m2 = B6 ^ D6 ^ C6
m3 = C6 ^ A6 ^ B6

S4 = SBox(m1)
S3 = SBox(m2)
S5 = SBox(m3)

m4 = C6 ^ A6 ^ S6
m5 = B6 ^ D6 ^ S4

S0 = SBox(m5)
S2 = SBox(m4)

#m6 = B6 ^ C6 ^ D6 ^ S0
m6 = C6 ^ A6 ^ B6 ^ S5
S1 = SBox(m6)

Now we have the required values to recover the plaintext.

Recovering Secret

1
2
3
4
5
6
7
8
9
10
tab6 = {
    'A6': ['D0', 'S1', 'S2', 'S3', 'S5'],
    'B6': ['C0', 'S0', 'S1', 'S4', 'S5'],
    'C6': ['B0', 'S2', 'B3'],
    'D6': ['A0', 'S0', 'S1', 'S3', 'S4', 'S5']

A0 = B0 = C0 = D0 = 0
for op in tab0.keys():
    exec(op+' = '+' ^ '.join(tab0[op]))
print list2hex([A0, B0, C0, D0])

Sending this secret to the server gives us the flag.

Exploit

- The variable names in the exploit are different!

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
import time
from pwn import *
from hashlib import sha256
from string import printable
from pwnlib.util.iters import bruteforce
import re
res = re.compile(r'[a-z0-9]{32}')
io = remote('45.32.100.6', 8003)
#io = remote('localhost', 8003)
cookie, hash = io.recvline().strip().split(' == ')
cookie = cookie.split('XXXX+')[1][:-1]


def brute_force(hash, s):
    return bruteforce(lambda x: sha256(x+s).hexdigest() == hash, string.  digits+string.ascii_letters, length=4)


io.sendline(brute_force(hash, cookie))
# POC till here

# def gen(n):
#     sub = {
#             "S{}".format(n+1):["S{}".format(n+1)],
#             "A{}".format(n):"A{} B{} S{}".format(n-1,n-1,n).split(),
#             "B{}".format(n):"A{} B{} D{} S{}".format(n-1,n-1,n-1,n).split(),
#             "C{}".format(n):"A{} C{} D{}".format(n-1,n-1,n-1).split(),
#             "D{}".format(n):"C{} D{} S{}".format(n-1,n-1,n).split(),
#     }
#     if n==0:
#         sub = {
#                 "S1":['S1'],
#                 "A0":['A0'],
#                 "B0":['B0'],
#                 "C0":['C0'],
#                 "D0":['D0'],
#                 }
#     return sub

# chars = "ABCD"
# def parser(n):
#     def gf(l):
#         re = []
#         s = set(l)
#         for op in s:
#             if l.count(op)%2!=0:
#                 re.append(op)
#         return re
#     game = n
#     subn = gen(n)
#     while(n>0):
#         subm = gen(n-1)
#         for c in chars:
#             k = c+str(game)
#             currents = subn[k][:]
#             for op in currents:
#                 if op[0] == 'S': continue
#                 subn[k].remove(op)
#                 subn[k] = subn[k]+subm[op]
#         n-=1
#     for c in chars:
#         k = c+str(game)
#         check = subn[k][:]
#         subn[k] = gf(check)
#     return subn


def pad(x):
    pad_length = 8-len(x)
    return pad_length*'0'+x


def hex2list(x):
    res = []
    for i in range(0, 32, 8):
        r = x[i:i+8]
        res.append(int(r, 16))
    return res


def list2hex(x):
    res = ''
    for i in range(4):
        res += pad(hex(x[i])[2:])
    return res


# def check(inp, out):
#     a0,b0,c0,d0 = hex2list(inp)
#     a6,b6,c6,d6 = hex2list(out)
#     s4 = b6 ^ d6 ^ a0 ^ c0
#     s3 = c6 ^ b0 ^ s4
#     print s3, s4
#     print a0 ^ b0 ^ c0 ^ s3, s4
#     return a0 ^ b0 ^ c0 ^ s3, s4


# local
x = inp = 0
y = out = 10

x = inp = 3452694591
y = out = 2745719712

# Table of [ABCD6]
# tab6 = parser(6)
tab6 = {
    'A6': ['S2', 'S1', 'S5', 'S3', 'D0'],
    'B6': ['S0', 'S1', 'S4', 'S5', 'C0'],
    'C6': ['S2', 'S3', 'B0'],
    'D6': ['S3', 'S1', 'S0', 'S5', 'S4', 'A0']
}

# Table of [ABCD]0
tab0 = {
    'D0': ['S3', 'S2', 'S6', 'S4', 'A6'],
    'C0': ['S2', 'S1', 'S6', 'S5', 'B6'],
    'B0': ['S3', 'S4', 'C6'],
    'A0': ['S2', 'S1', 'S6', 'S5', 'S4', 'D6']
}

# Sn based on 6's
## S1 = f(S4 ^ B6 ^ D6)
tabSn6 = {
    'S1': ['S4', 'B6', 'D6'],
    'S2': ['S5', 'A6', 'B6', 'C6'],
    'S3': ['C6', 'A6', 'S6'],
    'S4': ['B6', 'C6', 'D6'],
    'S5': ['B6', 'D6'],
    'S6': ['A6', 'B6', 'C6'],
}

# Sn based on 0's
## S1 = f(a0 ^ c0)
tabSn0 = {
    'S1': ['A0', 'C0'],
    'S2': ['B0', 'C0', 'D0', 'S1'],
    'S3': ['B0', 'D0', 'S2'],
    'S4': ['A0', 'B0', 'C0', 'S3'],
    'S5': ['A0', 'C0', 'S4'],
    'S6': ['B0', 'C0', 'D0', 'S1', 'S5'],
}


def encrypt(pt, io=io):
    time.sleep(0.5)
    if io.can_recv():
        io.recv()
    io.sendline(pt)
    #out = io.recv().splitlines()[0].split()[-1]
    out = io.recv()
    out = res.search(out).group()
    return out


# function to find f(m)
def SBox(m):
    A0 = m
    B0 = m
    C0 = m ^ x
    D0 = y
    pt = list2hex([A0, B0, C0, D0])
    # encrypt here
    ct = encrypt(pt)
    A6, B6, C6, D6 = hex2list(ct)
    s3 = C6 ^ B0 ^ A0 ^ C0 ^ B6 ^ D6  # Read the really long hypothesis
    return s3


# main function
# io.recv() # localonly
start = io.recvuntil('): ')
secret = res.search(start).group()
A6, B6, C6, D6 = hex2list(secret)
m1 = B6 ^ D6
m2 = B6 ^ D6 ^ C6
m3 = C6 ^ A6 ^ B6

S5 = SBox(m1)
S4 = SBox(m2)
S6 = SBox(m3)

m4 = C6 ^ A6 ^ S6
m5 = B6 ^ D6 ^ S4

S1 = SBox(m5)
S3 = SBox(m4)

#m6 = B6 ^ C6 ^ D6 ^ S1
m6 = C6 ^ A6 ^ B6 ^ S5
S2 = SBox(m6)

A0 = B0 = C0 = D0 = 0
for op in tab0.keys():
    exec(op+' = '+' ^ '.join(tab0[op]))
print list2hex([A0, B0, C0, D0])


# de1ctf{12759ff07f5f8145dfd661cb0f35e1a4}

Flag

de1ctf{12759ff07f5f8145dfd661cb0f35e1a4}