]> git.somenet.org - pub/jan/ctf-seminar.git/blob - writeups/ilm0/seccon.md
ilm0 - fixed formatting
[pub/jan/ctf-seminar.git] / writeups / ilm0 / seccon.md
1 # <u>SECCON 2019 Online CTF</u>
2
3
4
5 ## Crazy-Repetition-of-Codes
6
7 **category**: crypto
8
9 **description**:
10
11 \-
12
13 ___
14
15 We get a python source code for some kind of encryption.
16
17 ### Recon + solution
18
19 **crc.py**
20
21 ```python
22 import os
23 from Crypto.Cipher import AES
24
25 def crc32(crc, data):
26   crc = 0xFFFFFFFF ^ crc
27   for c in data:
28     crc = crc ^ ord(c)
29     for i in range(8):
30       crc = (crc >> 1) ^ (0xEDB88320 * (crc & 1))
31   return 0xFFFFFFFF ^ crc
32
33 key = b""
34
35 crc = 0
36 for i in range(int("1" * 10000)):
37   crc = crc32(crc, "TSG")
38 assert(crc == 0xb09bc54f)
39 key += crc.to_bytes(4, byteorder='big')
40
41 crc = 0
42 for i in range(int("1" * 10000)):
43   crc = crc32(crc, "is")
44 key += crc.to_bytes(4, byteorder='big')
45
46 crc = 0
47 for i in range(int("1" * 10000)):
48   crc = crc32(crc, "here")
49 key += crc.to_bytes(4, byteorder='big')
50
51 crc = 0
52 for i in range(int("1" * 10000)):
53   crc = crc32(crc, "at")
54 key += crc.to_bytes(4, byteorder='big')
55
56 crc = 0
57 for i in range(int("1" * 10000)):
58   crc = crc32(crc, "SECCON")
59 key += crc.to_bytes(4, byteorder='big')
60
61 crc = 0
62 for i in range(int("1" * 10000)):
63   crc = crc32(crc, "CTF!")
64 key += crc.to_bytes(4, byteorder='big')
65
66 flag = os.environ['FLAG']
67 assert(len(flag) == 32)
68
69 aes = AES.new(key, AES.MODE_ECB)
70 encoded = aes.encrypt(flag)
71 assert(encoded.hex() == '79833173d435b6c5d8aa08f790d6b0dc8c4ef525823d4ebdb0b4a8f2090ac81e')
72 ```
73
74 If we try running the code we get an OverflowError:
75
76 `Traceback (most recent call last):`
77   `File "crc.py", line 15, in <module>`
78     `for i in range(int("1" * 10000)):`
79 `OverflowError: range() result has too many items`
80
81 The self-defined function crc32 calculates a CRC value(see TD) and this value is later added step-by-step to the key variable:
82
83 ```python
84 def crc32(crc, data):
85   crc = 0xFFFFFFFF ^ crc
86   for c in data:
87     crc = crc ^ ord(c)
88     for i in range(8):
89       crc = (crc >> 1) ^ (0xEDB88320 * (crc & 1))
90   return 0xFFFFFFFF ^ crc
91 ```
92
93 First it seemed, that this function sometimes returns random values, not the correct crc, but later this turned out to be due to the signing of results.
94
95 We test it if our theory works in practice too, the only difference seems to be, that this function always returns an unsigned 32-bit CRC value:
96
97 `print(crc32(0,"HELLO"))` > 3242484790
98 `print((binascii.crc32('HELLO')) % (1<<32))` > (-1052482506 % (1<<32)) > 3242484790
99
100 I focused for a long time here on finding some kind of mathematical vulnerability or a smart solution, but brute forcing seemed to be the only solution.
101
102 The code "builds" the ciphertext in 5 steps, these can be sequentially reversed, as they were sequentially appended. Let's reverse them one by one:
103
104 ```python
105 for i in range(int("1" * 10000)):
106   crc = crc32(crc, "TSG")
107 ```
108
109 The operation does not use the CRC value as intended,rather than it will return it after `int("1" * 10000)` runs. We can make our code faster after reaching the first cycle (when the CRC value equals 0) and taking the modulus of the remaining steps.
110
111 ```python
112 def get_crc(s):
113     crc = 0
114     steps = 0
115     for i in range(0, int("1" * 10000)):
116         crc = ((binascii.crc32(s)) % (1<<32))
117         if crc == 0:
118             steps = (i % 2 ** 32) + 1
119             break
120     rest = int("1" * 10000) % steps
121     crc = 0
122     for i in range(0, rest):
123         crc = ((binascii.crc32(s)) % (1<<32))
124     return crc % 2 ** 32
125 ```
126
127 With this function we find the first cycle in the operation, then we apply apply it with the remaining value. 
128
129 An other problem was being able to use the `for` construct with our big range, normally we would get an Overflow error, but we can work around this by using `long_range` from the crypto_commons library instead.
130
131 Armed with this knowledge and tools (reversing the CRC operation takes some time, but not unrealistically long, ~8 mins/part) we can construct our attack:
132
133 ```python
134 step1 = get_crc("TSG")    # 2962998607L
135 step2 = get_crc("is")     # 3836056187L
136 step3 = get_crc("here")   # 2369777541L
137 step4 = get_crc("at")     # 3007692607L
138 step5 = get_crc("SECCON") # 1526093488L
139 step6 = get_crc("CTF!")   # 3679021396L
140
141 step1_bytes = long_to_bytes(step1)
142 step2_bytes = long_to_bytes(step2)
143 step3_bytes = long_to_bytes(step3)
144 step4_bytes = long_to_bytes(step4)
145 step5_bytes = long_to_bytes(step5)
146 step6_bytes = long_to_bytes(step6)
147
148 combined_key = "".join(step1_bytes,step2_bytes,step3_bytes,step4_bytes,step5_bytes,step6_bytes,)
149
150 ciphertext_bytes = "79833173d435b6c5d8aa08f790d6b0dc8c4ef525823d4ebdb0b4a8f2090ac81e".decode("hex")
151 cipher = AES.new(combined_key, AES.MODE_ECB)
152 print(aes.decrypt(ciphertext_bytes))
153 ```
154
155 It will take approximately an hour to get our results, we receive: SECCON{Ur_Th3_L0rd_0f_the_R1NGs}
156
157
158
159 ### Technical details
160
161 Cyclic redundancy check (CRC):
162
163 > It is an error-detecting code used to determine if a block of data has been corrupted.
164
165 [https://www.cardinalpeak.com/understanding-the-cyclic-redundancy-check/]
166
167 CRC32 is calculated with the following polynomial formula:
168
169 x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1
170
171 This value is appended to transmitted data block to check the integrity of the received data. When the received data is divided by the received CRC value the rest should be 0.
172
173 As we saw, CRC operations are relatively easily reversible (even in our case, when they were not used in the way they were intended to). This makes them unsuitable for applications in cryptography.
174
175
176
177 ### Lessons learned
178
179 - Approaching more complex crypto challenges
180 - CRC codes
181
182
183
184 ## coffee_break
185
186 **category**: crypto
187
188 **description**:
189
190 The program "encrypt.py" gets one string argument and outputs ciphertext.
191
192 Example:
193
194 $ python encrypt.py "test_text"
195 gYYpbhlXwuM59PtV1qctnQ==
196 The following text is ciphertext with "encrypt.py".
197
198 FyRyZNBO2MG6ncd3hEkC/yeYKUseI/CxYoZiIeV2fe/Jmtwx+WbWmU1gtMX9m905
199
200 ___
201
202 ### Recon + solution
203
204 We are presented with a simple encryption scheme and a ciphertext:
205
206 **encrypt.py**:
207
208 ```python
209 import sys
210 from Crypto.Cipher import AES
211 import base64
212
213
214 def encrypt(key, text):
215     s = ''
216     for i in range(len(text)):
217         s += chr( ( ((ord(text[i]) - 0x20) + (ord(key[i % len(key)]) - 0x20)) % (0x7e -            0x20 + 1)) + 0x20)
218     return s 
219
220 key1 = "SECCON"
221 key2 = "seccon2019"
222 text = sys.argv[1]
223
224 enc1 = encrypt(key1, text)
225 key=key2 + chr(0x00) * (16 - (len(key2) % 16))
226 cipher = AES.new(key, AES.MODE_ECB)
227 ```
228
229 The first thing that becomes clear is that the encryption simply uses some kind of character substitution.
230
231 We are working with a cipher in ECB mode so we do not need an IV. We can use this same cipher to reverse the last step. Also, we are in the fortunate position of having access to all the keys used.
232
233 ```python
234 ciphertext = "FyRyZNBO2MG6ncd3hEkC/yeYKUseI/CxYoZiIeV2fe/Jmtwx+WbWmU1gtMX9m905"
235 cipertext_2 = cipher.decrypt(base64.b64decode(ciphertext)).decode("ascii")
236 ```
237
238 Now let's take a close look at the encryption function:
239
240 ```python
241 def encrypt(key, text):
242     s = ''
243     for i in range(len(text)):
244         s += chr( ( ((ord(text[i]) - 0x20) + (ord(key[i % len(key)]) - 0x20)) % (0x7e -            0x20 + 1)) + 0x20)
245     return s 
246 ```
247
248 We can reverse this operation by applying the operations in the reverse direction, so "+" for "-" and vice versa. The only tricky part is the modulo operation % (0x7e - 0x20 + 1) -> %95, but after some thinking around one can realize that most probably the flag is made up of human-readable ascii characters, and this operation will only apply to those characters with a value smaller than 32: we can work around this by simply adding 95 to these characters:
249
250 ```python
251 def decrypt(key, s):
252     plaintext = ""
253     for i in range(len(s)):
254         char_value = ord(s[i]) - ord(key[i % len(key)]) + 0x20
255
256     if(char_value < 0x20):
257         char_value += 95
258     
259     plaintext += chr(char_value)
260 return plaintext
261 ```
262
263 Applying this function to the AES deciphered text with the key that was used for the encrypt function:
264
265 ```python
266 print(decrypt(key1, ciphertext_2))
267 ```
268
269 we get back the flag: SECCON{Success_Decryption_Yeah_Yeah_SECCON}
270
271 ### Technical details
272
273 AES ECB mode:
274
275 ![aes_ecb.png](seccon/aes_ecb.png)
276
277 [https://upload.wikimedia.org/wikipedia/commons/thumb/d/d6/ECB_encryption.svg/600px-ECB_encryption.svg.png]
278
279 This mode of operation is easily reversible, as there is no IV used and the steps are not chained.
280
281
282
283 ## Sandstorm
284
285 **category**: misc, steg
286
287 **description**:
288
289 I've received a letter... Uh, Mr. Smith?
290
291 ![sandstorm.png](seccon/sandstorm.png)
292
293 ___
294
295 ### Recon + solution
296
297 We receive a strange image, we should find a hidden message. The description reveals us, that we should work with some kind of steganography method. After trying around with Stegsolve and https://georgeom.net/StegOnline/ I did not find anything. But the image itself looks very unusual, maybe there's something in the noise. I tried different noise reduction and enhancement filters in gimp, but I only received even blurrier images. After a talk presented on 10.12.2019 I became aware that one should look into the description and not necessarily in the image itself first. The text "My name is Adam" reveals the underlying algorithm.
298
299 We are dealing with the Adam7 steganography algorithm, which has 7 passes as the name shows. To even numbered levels some unusual asymmetric rules apply, but the levels 1, 3, 5 can be easily reached with the application of matrix operations.
300
301 ```python
302 import cv2
303 import numpy
304
305 image = cv2.imread('./sandstorm.png')
306
307 for level in range (1,4):
308     image = image[0::2,0::2]
309     filename = "level_" + str(7-level*2)
310     cv2.imwrite(filename + '.png', image) 
311 ```
312
313 On level 1 we find a QR-code, which resolves to the flag: 
314
315 ![key.png](seccon/key.png)
316
317 SECCON{p0nlMpzlCQ5AHol6}
318
319 ### Technical details
320
321 Adam7 interlacing algorithm:
322
323 > Adam7 is an interlacing algorithm for raster images, best known as the interlacing scheme optionally used in PNG images. An Adam7 interlaced image is broken into seven subimages, which are defined by replicating this 8×8 pattern across the full image.
324
325 ```
326 1 6 4 6 2 6 4 6
327 7 7 7 7 7 7 7 7
328 5 6 5 6 5 6 5 6
329 7 7 7 7 7 7 7 7
330 3 6 4 6 3 6 4 6
331 7 7 7 7 7 7 7 7
332 5 6 5 6 5 6 5 6
333 7 7 7 7 7 7 7 7
334 ```
335
336 [https://wikivisually.com/wiki/Adam7_algorithm]
337
338 The algorithm works with 8 x 8 rasters, this matrix represents which pixels are assigned to which levels. As mentioned in the solution part, the uneven numbered levels can be extracted with symmetrical and commutative matrix operations.
339
340 The fastest way to get to the first level would be to only take every 8th pixel horizontally and vertically.
341
342 ### Lessons learned
343
344 - Look for clues in the task description!