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!
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}. $$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):
return tuple(ZZ(v).digits(2, padto=n))[::-1]
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 = [0] * 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}'