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
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}'