August 19, 2019 09:00

안녕하세요, 이번 글에서는 Linear Feedback Shift Register에 대해 알아보도록 하겠습니다.

Linear Feedback Shift Register

Linear Feedback Shift Register(a.k.a LFSR)는 현재 상태에서의 선형 연산을 통해 다음 상태를 생성하는 레지스터입니다.

예를 들어 상태는 4비트이고 다음 입력값은 1-indexed 기준 4번째 비트와 3번째 비트의 XOR으로 생성된다고 해봅시다. 만약 현재 상태가 1011일 경우 $1 \oplus 1 = 0$이기에 다음 입력값은 0이고, 다음 상태는 0101이 됩니다. 그 다음 입력값은 $0 \oplus 1 = 1$이고, 다음 상태는 1010입니다. 아래의 그림을 참고해보세요.

4번째 비트와 3번째 비트의 XOR로 만들어지는 LFSR을 $x^4+x^3+1$의 특성다항식을 가진다고 표현하기도 합니다.

LFSR의 초기 값은 seed라고 불립니다. seed가 정해지면 LFSR의 이후 모든 상태 또한 결정적입니다. 또한 상태가 $k$-bit일 때 가능한 서로 다른 상태의 수는 $2^k$개이기 때문에 반드시 LFSR은 유한한 cycle을 이루게 됩니다. 그리고 이 cycle의 최대 주기는 $2^k-1$입니다.

아래의 코드는 상태가 16비트이고 16, 15, 13, 5번째 비트를 XOR해서 다음 입력값을 만들어내는 LFSR의 코드입니다. 상태에서 MSB가 1번째 비트, LSB가 16번째 비트를 의미합니다. 즉 lfsr = 0b1111000011110000에 대해 1번째 비트는 1, 16번째 비트는 0입니다.

lfsr = 0b1111000011110000
while True:
  bit = (lfsr ^ (lfsr >> 1) ^ (lfsr >> 3) ^ (lfsr >> 11)) & 1
  lfsr = (lfsr >> 1) | (bit << 15)

암호학에서의 LFSR

LFSR은 암호학에서 스트림 암호의 난수를 생성하는 용도로 많이 사용됩니다. 적절한 다항식을 택할 경우 주기가 충분히 크고 0과 1이 사실상 무작위에 가깝게 등장하기 때문에 난수로 사용하는데 문제가 없습니다.

그런데 앞에서 언급한 것과 같이 일단 seed가 정해지고 나면 LFSR이 만들어내는 값은 고정이 됩니다. 그렇기에 일단 난수가 공개되면 암호의 기밀성이 지켜질 수 없는 상황에서는 주의가 필요합니다.

예시를 위해 OTP와 같이 평문에 난수를 XOR하는 아주 단순한 암호를 생각해봅시다. LFSR의 상태는 64비트이고 특성다항식은 $x^64+x^48+x^30+x^3+1$입니다.

P = open('flag').read()
lfsr = int.from_bytes(os.urandom(8), sys.byteorder) # 64-bit random seed
C = bytes()
for i in range(len(P)):
  k = 0
  for _ in range(8):
    bit = (lfsr ^ (lfsr >> 16) ^ (lfsr >> 34) ^ (lfsr >> 61)) & 1
    lfsr = (lfsr >> 1) | (bit << 63)
    k = (k << 1) ^ bit
  C += bytes([P[i] ^ k])
print(C.hex())

C로부터 flag를 복원해내기 위해서는 lfsr의 출력값을 찾아내야 합니다. 64비트를 전수조사하는 것은 $O(2^{64})$의 시간복잡도를 필요로 하므로 사실상 불가능에 가깝습니다.

그런데 만약 flag 파일이 mp4라는 단서가 있으면 어떻게 될까요? mp4 파일의 헤더는 00 00 00 18 66 74 79 70 이므로 첫 8바이트(=64비트)에 대해 어떤 LFSR의 출력이 XOR되었는지를 알 수 있습니다. 그리고 그 이후의 LFSR의 출력은 자명하게 알아낼 수 있으므로 이를 이용해 원본 파일을 알아낼 수 있습니다. 혹시 헷갈리는 부분이 있다면 root-me.org의 LFSR-Known plaintext 문제를 한 번 풀어보시면 이해가 갈 것입니다. 풀이 링크

Correlation Attack

위의 예시에서 보듯 LFSR의 출력 비트를 그대로 난수로 사용하는 것은 암호학적 관점에서 위험부담이 좀 있습니다. 대신 여러 개의 LFSR을 사용하고 이들의 연산 결과를 난수로 사용하는 경우 설령 출력 결과의 일부분을 알아내더라도 나머지 부분을 알아낼 수 없는 경우가 많습니다.

예를 들어 LFSR 3개의 bit이 각각 x, y ,z이라고 할 때 (x*y)^(y*z)^(x*z)을 OTP에서의 키스트림으로 활용하는 것입니다. 이런 상황에서 어떤 식으로 LFSR 3개의 seed를 복원할 수 있을까요? 이럴 때 쓸 수 있는 공격이 Correlation Attack입니다. 아래의 표를 살펴봅시다.

표를 잘 살펴보시면 x, y, z와 result가 일치할 확률이 75%임을 알 수 있습니다. 만약 입력과 출력 사이에 관련이 없다면 확률이 50%일텐데 (x*y)^(y*z)^(x*z) 식에서는 확률이 75%가 되었고 이를 이용한 공격이 Correlation Attack입니다.

만약 3개의 LFSR이 각각 32=bit 였다고 할 때 입력과 출력 사이에 관련이 없었다면 seed를 복원하기 위해 총 $2^{96}$ 가지의 모든 경우에 대해 keystream과 동일한 것이 나오는지를 다 확인해보아야 하지만, 75%의 확률로 일치한다는 단서를 이용하면 keystream과 대략 75% 정도 비슷한 seed들에 대해서만 확인을 해보면 되기 때문에 시간복잡도를 소량 낮출 수 있습니다. 더 나아가 3개 중 어느 하나의 seed를 알게 된 경우, LFSR의 stream과 keystream과 일치하는 정도를 일종의 Scoring Function으로 두어 나머지 LFSR의 seed 또한 복원이 가능합니다. 2019 0CTF의 zer0lfsr 문제가 Correlation Attack에 관한 문제이니 한 번 시도해보시는 것을 추천드립니다. 풀이 링크

High Order Correlation Attack

이번에는 키스트림의 비트를 1개의 LFSR에서 만들되, 매 순간 새롭게 추가되는 비트를 그대로 사용하는 것이 아니라 비선형적인 연산을 통해서 키스트림의 비트를 만든다고 해봅시다.

예를 들어 LFSR의 다항식은 $x^16+x^12+x^7+x^5+x^2+1$이고 키스트림의 비트는 lfsr[14] * lfsr[10] * lfsr[4] + lfsr[12] * lfsr[6] + lfsr[8]로 계산을 하는 것입니다. 만약 곱셈이 없고 전부 선형 덧셈으로만 키스트림의 비트를 만들어낸다면 단순한 행렬의 연산을 통해 seed를 복원할 수 있습니다. 그러나 비선형 연산이 들어감으로 인해 분명 seed에 따라 키스트림이 deterministic한 것은 맞지만, 키스트림이 주어진다고 해도 seed를 복원하는 것이 굉장히 까다롭습니다.

실제로 Toyocrypt라는 암호는 128-bit LFSR로 $l_{127} + \prod_{i=0}^{62}l_il_{a_i} + l_{10}l_{23}l_{32}l_{42} + l_{1}l_{2}l_{9}l_{12}l_{18}l_{20}l_{23}l_{25}l_{26}l_{28}l_{33}l_{38}l_{41}l_{42}l_{51}l_{53}l_{59} + \prod_{i=0}^{62}l_i$를 출력 bit으로 활용합니다. 최대 63차 다항식까지 존재하기에 처리가 굉장히 껄끄럽습니다.

하지만 한 가지 사실을 관찰한다면 차수를 획기적으로 낮출 수 있는데, ** 63차 항은 $\frac{2^{63}-1}{2^{63}}$의 확률로 0이다. ** 라는 점입니다. 63개의 값 중에 어느 하나라도 0이면 해당 항은 0이 되어버리니 사실상 0이라고 생각을 해도 무방합니다. 이를 이용해 출력 bit를 만들어내는 식의 차수를 63차 식에서 4차 식으로 줄일 수 있고, 더 나아가 $l_{23}l_{42}$라는 공통 인자로 식을 가다듬으면 3차 식으로 떨굴 수 있습니다.

Toyocrypt의 완전한 공격을 위해서는 이 사실과 더불어 2000년에 제시된 XL algorithm에 대한 이해가 추가되어야 하지만 XL algorithm에 대한 설명은 이 글에서 제외하겠습니다. 개인적으로 공부를 하고 싶다면 논문을 참고해보세요.

2019 WCTF에서 r3kapig 팀이 toy라는 이름의, Higher Order Correlation Attack을 이용하나 toyocrypt보다는 단순화시킨 문제를 출제했습니다. 한 번 시도해봅시다. Github Link

결론 및 제언

이번 글에서 특히 CTF에서 중국 팀이 좋아하는 LFSR에 대해 알아보았습니다.

LFSR은 algebraic attack이 굉장히 많이 나오는 분야로 다른 암호학 분야와 비슷하게 대수학적 지식이 아주 많이 필요합니다. 동시에 위에서 언급한 Toyocrypt의 경우 2000년에 개발된 암호인데 2000년 초반에 바로 합리적인 시간복잡도로 공격에 성공했을만큼, 스트림 암호는 블록 암호에 비해 훨씬 더 취약점이 잘 찾아질 수 있음에 유의해야합니다.

덧붙여, fast correlation attack이라는 것이 있는데 아직 제대로 이해하지 못하고 있습니다. 혹시 이해에 성공하신 분이 있다면 도와주시면 감사하겠습니다 :p