Google Capture The Flag 2017 (Quals): Introspective CRC
problem
$ nc selfhash.ctfcompetition.com 1337
0101010101010101010101010101010101010101010101010101010101010101010101010101010101
Give me some data:
Check failed.
Expected:
crc_82_darc(data) == int(data, 2)
Was:
3885922831092520253093991L
1611901092819505566274901L
solution
f = lambda x: crc_82_darc(bin(x)[2 :].zfill(82))
とすると、この関数$f : 2^{82} \to 2^{82}$の不動点を探せばよい。 特に、$x \mapsto f(x) \oplus f(0)$は線形。
したがって、線形な関数$g(x) = f(x) \oplus f(0) \oplus x$に対し$g(x) = f(0)$となるような自然数$x \lt 2^{82}$を探せばよい。 線形性より基底$\{ 1, 2, 4, \dots, 2^k, \dots, 2^{81} \}$に対する$g(1), g(2), g(4), \dots, g(2^k), \dots, g(2^{81})$だけ見ればよい。 特に$2^{81}$をvector空間と見て一次変換$g$を行列表示$A = g$して$y = f(0)$とおけば、単に$y = Ax$を解くだけとなる。 Gaussの消去法により$x$は得られ、これが答え。
CTF{i-hope-you-like-linear-algebra}
implementation
#!/usr/bin/env python3
import copy
import random
def gaussian_elimination(a, b):
n = len(a)
a = copy.deepcopy(a)
b = copy.deepcopy(b)
for y in range(n):
pivot = y
while pivot < n and not a[pivot][y]:
pivot += 1
if pivot == n:
continue
assert pivot < n
a[y], a[pivot] = a[pivot], a[y]
b[y], b[pivot] = b[pivot], b[y]
assert a[y][y] == 1
for ny in range(n):
if ny != y and a[ny][y]:
for x in range(y+1, n):
a[ny][x] ^= a[y][x]
b[ny] ^= b[y]
return b
# crc_82_darc
n = 82
def crc_82_darc(data):
poly = 0x220808a00a2022200c430
c = 0
for i, data_i in enumerate(data):
c ^= ord(data_i)
for _ in range(8):
low = c & 1
c >>= 1
if low:
c ^= poly
return c
# make a linear function
def f(x):
data = bin(x)[2 :].zfill(n)
return crc_82_darc(data)
def g(x):
return f(x) ^ f(0) ^ x
def fmt(x):
return bin(x)[2 :].zfill(n)
assert g(0) == 0
for _ in range(100):
x = random.randint(0, 2 ** n - 1)
y = random.randint(0, 2 ** n - 1)
assert g(x) ^ g(y) == g(x ^ y)
# solve the matrix
a = [ [ None for _ in range(n) ] for _ in range(n) ]
for y in range(n):
for x in range(n):
a[y][x] = int(fmt(g(2 ** x))[y])
b = list(map(int, fmt(f(0))))
c = gaussian_elimination(a, b)
# done
x = int(''.join(map(str, reversed(c))), 2)
print(fmt(x))
assert f(x) == x