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!