SECCON ONLINE 2019 | Crazy Repetition of Codes

#seecononline2019

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")

print(key)

# flag = os.environ['FLAG']
# assert(len(flag) == 32)
#
# aes = AES.new(key, AES.MODE_ECB)
# encoded = aes.encrypt(flag)
# assert(encoded.hex() == '79833173d435b6c5d8aa08f790d6b0dc8c4ef525823d4ebdb0b4a8f2090ac81e')

CRCの問題。crc = CRC32(crc, "TSG") を "1" * 10000 回ほど行った結果が鍵の一部になっている。当然こんな計算が間に合うはずもないので、何かしら計算量を削減しなければならない。

解法1

CRCは単なる多項式の剰余なので繰り返し二乗法ができそう。

PR.<x> = PolynomialRing(GF(2))
QR.<x> = PR.quotient(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)

def crc32(data):
    crc = QR(0)
    for c in data:
        for i in range(8):
            if ord(c) & (1 << i):
                crc += x ^ (32 - i - 1)
        crc *= x ^ 8
    return crc

def crc32_concat(a, b):
    return (a[0] * b[1] + b[0], a[1] * b[1])


def crc32_pow(data, times):
    result = (sum(x^i for i in range(32)), x^32)
    power = (crc32(data), x^(8 * len(data))) # (poly, size)
    while times:
        if times % 2 == 1:
            result = crc32_concat(result, power)
        power = crc32_concat(power, power)
        times = times // 2
    return result


def crc32_tonum(poly):
    return sum((2 ^ i) * int(1 - v) for i, v in enumerate(reversed(poly.list())))


from Crypto.Util.number import *
key = ''
for s in ["TSG", "is", "here", "at", "SECCON", "CTF!"]:
    z = crc32_pow(s, int("1" * 10000))
    crc = crc32_tonum(z[0])
    key += long_to_bytes(crc, 4)
print(repr(key))

はい。kmykさんのコードの写経ですね。

from Crypto.Cipher import AES

key = b"\xb0\x9b\xc5O\xe4\xa5\x92{\x8d?\xef\x85\xb3E\xbf?Z\xf6V\xb0\xdbIiT"
aes = AES.new(key, AES.MODE_ECB)
print(
    aes.decrypt(
        bytes.fromhex(
            "79833173d435b6c5d8aa08f790d6b0dc8c4ef525823d4ebdb0b4a8f2090ac81e"
        )
    )
)

SECCON{Ur_Th3_L0rd_0f_the_R1NGs}'