[Cryptanalysis] LFSR - Known plaintext

challege.png.encrypt라는 파일을 줍니다. 설명으로 추론해보면 이 파일은 LFSR로 키를 생성해 암호화한 파일로 추정됩니다. PNG의 파일 구조를 살펴보면 우리는 PNG의 헤더 8바이트, 그리고 추가적으로 그 뒤에 바로 따라오는 4바이트를 알 수 있습니다.(PNG 구조)

즉 키의 앞 96비트를 알고 있는 상황이고, 적당히 다항식을 때려맞추면 됩니다. 이를 맞추기 위해서 $Ax=b$꼴의 선형연립방정식을 풀면 됩니다.

keystream = '110010101111111001101111011010110100110100111001011110011100101000000000111001001111110101100101' # len : 96
sz = 16
mat = [[0]*sz for i in range(sz)]
for i in range(sz):
    for j in range(sz):
        mat[i][j] = int(keystream[i+j])

A = Matrix(IntegerModRing(2),mat)
Ainv = A.inverse()
vec = [0]*sz
for i in range(sz,2*sz):
    vec[i-sz] = int(keystream[i])
b = vector(IntegerModRing(2), vec)
ans = A.solve_right(b)
print(ans)

recover = keystream[:16]
for i in range(16,96):
#    t = int(keystream[i-16])^int(keystream[i-11])^int(keystream[i-3])^int(keystream[i-1])
#    print(int(keystream[i-16]),int(keystream[i-11]),int(keystream[i-3]),int(keystream[i-1]),t)
    recover += str(int(keystream[i-16])^^int(keystream[i-11])^^int(keystream[i-3])^^int(keystream[i-1]))


print(recover == keystream)
print(recover[16:])

다항식이 몇 차인지는 sz가 최대 얼마일 때 행렬이 full rank인지를 통해 알아낼 수 있고, recover한 결과와 keystream이 일치함을 확인할 수 있었습니다. 참고로 sagemath에서는 python과 달리 ^가 XOR이 아니라 지수승이란걸 몰랐어서 좀 헤맸네요.

아무튼 찾아낸 식을 바탕으로 keystream을 복원하고 png를 찾아낼 수 있습니다.

keystream = [1,1,0,0,1,0,1,0,1,1,1,1,1,1,1,0]+[0]*2000000

for i in range(16,2000000):
  keystream[i] = keystream[i-1]^keystream[i-3]^keystream[i-11]^keystream[i-16]
p = open('challenge.png','wb')

Cipher = open('challenge.png.encrypt','rb').read()
idx = 0
for c in Cipher:
  k = 0
  for i in range(8):
    k <<= 1
    k = k | keystream[idx]
    idx += 1
#  print(c^k)
  p.write(bytes([c^k]))
p.close()