# SECCON 2019 CTF Quals - Crazy Repetition of Codes (crypto)¶

The challenge abbreviation is CRC, so we can guess what this challenge is about:

import os
from Crypto.Cipher import AES

def crc32(crc, data):
crc = 0xFFFFFFFF ^ crc
for c in data:
crc = crc ^ ord(c)
for i in range(8):
crc = (crc >> 1) ^ (0xEDB88320 * (crc & 1))
return 0xFFFFFFFF ^ crc

key = b""

crc = 0
for i in range(int("1" * 10000)):
crc = crc32(crc, "TSG")
assert(crc == 0xb09bc54f)
key += crc.to_bytes(4, byteorder='big')

crc = 0
for i in range(int("1" * 10000)):
crc = crc32(crc, "is")
key += crc.to_bytes(4, byteorder='big')

crc = 0
for i in range(int("1" * 10000)):
crc = crc32(crc, "here")
key += crc.to_bytes(4, byteorder='big')

crc = 0
for i in range(int("1" * 10000)):
crc = crc32(crc, "at")
key += crc.to_bytes(4, byteorder='big')

crc = 0
for i in range(int("1" * 10000)):
crc = crc32(crc, "SECCON")
key += crc.to_bytes(4, byteorder='big')

crc = 0
for i in range(int("1" * 10000)):
crc = crc32(crc, "CTF!")
key += crc.to_bytes(4, byteorder='big')

flag = os.environ['FLAG']
assert(len(flag) == 32)

aes = AES.new(key, AES.MODE_ECB)
encoded = aes.encrypt(flag)
assert(encoded.hex() == '79833173d435b6c5d8aa08f790d6b0dc8c4ef525823d4ebdb0b4a8f2090ac81e')


In order to decrypt the flag, we need to compute the standard $CRC32$ function on strings build by repeating a short chunk $11\ldots11$ times, where the number has 10000 digits! There is no hope to perform this number of operations (at least during the CTF). However, if we recall that $CRC32$ is an affine function, we can speed this up by using fast matrix exponentiation.

In fact, the simplest solution is to recall that the order of $CRC32$ is $2^{32}-1$, and for any fixed chunk the order will divide this number. Therefore, we can simply reduce int("1" x 10000) modulo $2^{32}-1$, and run the code directly. After replacing the crc32 implementation with zlib.crc32, it takes just a couple of minutes to compute the answer!

py import os from Crypto.Cipher import AES from zlib import crc32 key = b"" crc = 0 for i in range(int("1" * 10000) % (2**32-1)): crc = crc32(b"TSG", crc) assert(crc == 0xb09bc54f) key += crc.to_bytes(4, byteorder='big') crc = 0 for i in range(int("1" * 10000) % (2**32-1)): crc = crc32(b"is", crc) key += crc.to_bytes(4, byteorder='big') crc = 0 for i in range(int("1" * 10000) % (2**32-1)): crc = crc32(b"here", crc) key += crc.to_bytes(4, byteorder='big') crc = 0 for i in range(int("1" * 10000) % (2**32-1)): crc = crc32(b"at", crc) key += crc.to_bytes(4, byteorder='big') crc = 0 for i in range(int("1" * 10000) % (2**32-1)): crc = crc32(b"SECCON", crc) key += crc.to_bytes(4, byteorder='big') crc = 0 for i in range(int("1" * 10000) % (2**32-1)): crc = crc32(b"CTF!", crc) key += crc.to_bytes(4, byteorder='big') flag = bytes.fromhex("79833173d435b6c5d8aa08f790d6b0dc8c4ef525823d4ebdb0b4a8f2090ac81e") aes = AES.new(key, AES.MODE_ECB) encoded = aes.decrypt(flag) print(repr(encoded)) 

The idea is to construct the $32\times 32$ matrix $M$ and the 32-bit vector $c$ such that $CRC32_s(x, s) = M\times x \oplus c$ (where $s$ is the short string chunk used to build the string). This can be done in 33 black-box calls to $CRC32$: evaluating it at the zero vector and at all unit vectors.

Finally, observe that the $e$-time repetition of $CRC32$ is expressed as $$CRC32^e(x, s) = M\times (\ldots M\times(M\times x \oplus c) \oplus c \ldots )\oplus c = M^e\times x \oplus (M^{e-1} \oplus M^{e-2} \oplus \ldots M \oplus I) \times c,$$ where $I$ is the $32\times32$ identity matrix.

In our case $x=0$ so we only need to evaluate the sum $M^{e-1} \oplus M^{e-2} \oplus \ldots M \oplus I$. This can be done using standard geometric series formula (luckily, $M\oplus I$ is invertible):

$$(M^{e-1} \oplus M^{e-2} \oplus \ldots M \oplus I) = \frac{M^e\oplus I}{M\oplus I}.$$
In :
from sage.all import *
from Crypto.Cipher import AES

def crc32(crc, data):
crc = 0xFFFFFFFF ^^ crc
for c in data:
crc = crc ^^ ord(c)
for i in range(8):
crc = (crc >> 1) ^^ (0xEDB88320 * (crc & 1))
return 0xFFFFFFFF ^^ crc

def frombin(v):
return ZZ(tuple(map(int, v))[::-1], base=2)

def tobin(v, n):

E = int("1" * 10000) % (2**32-1)
ID = identity_matrix(GF(2), 32, 32)

def rep(s):
print("Computing for", repr(s))
# build the vector
c = crc32(0, s)

# build the matrix
m = matrix(GF(2), 32, 32)
for i in range(32):
v =  * 32
v[i] = 1
v = frombin(tuple(v))
v = crc32(v, s) ^^ c
v = tobin(v, 32)
m.set_column(i, v)
c = vector(GF(2), tobin(c, 32))

matsum = (m**E + ID) * ~(m + ID)
res = matsum * c
return int(frombin(res)).to_bytes(4, byteorder="big")

key = b""
key += rep("TSG")
key += rep("is")
key += rep("here")
key += rep("at")
key += rep("SECCON")
key += rep("CTF!")

flag = bytes.fromhex("79833173d435b6c5d8aa08f790d6b0dc8c4ef525823d4ebdb0b4a8f2090ac81e")
aes = AES.new(key, AES.MODE_ECB)
encoded = aes.decrypt(flag)
print(encoded)

Computing for 'TSG'
Computing for 'is'
Computing for 'here'
Computing for 'at'
Computing for 'SECCON'
Computing for 'CTF!'
b'SECCON{Ur_Th3_L0rd_0f_the_R1NGs}'