CTF 문제들을 둘러보다 Crypto 분야에서 이 개념을 사용하는 문제가 있어서 여기에 개념만 간략히 정리해보려고 한다.
디지털 회로에서, 현재 상태에 대한 선형 연산(linear function)으로 다음 상태를 만드는 레지스터다. 해당 연산에는 다양한 종류들이 있겠지만, 일반적으로 쓰이는 건 XOR이라고 한다.
LFSR의 초기값은 시드(seed)라고 부르며 다음 상태를 생성하는 연산에 관여하는 비트는 tap이라고 한다. 또 가장 오른쪽에 있는 비트를 output bit라고 한다.
기본적인 내용은 다음과 같다. LFSR의 초기값을 다음과 같은 8bit 정수로 놓는다.
현재의 상태는 0x59라고 말할 수 있다. LFSR의 tap이 8번째, 6번째, 5번째 비트라고 가정해보자.
현재 상태의 output bit과 tap들을 순차적으로 XOR 연산시킨 값을 제일 왼쪽으로 보낸다. 이해하기 쉽게 그림으로 다시 표현해봤다.
다음 상태는 0x2C가 되었다. 같은 방식으로 다음 상태를 계속 생성할 수 있다.
여기서는 8비트의 LFSR을 예시로 들었는데, 이 경우 LFSR는 최대 255 (=2^8-1, 0 제외) 개의 값을 가질 수 있다. 물론 모든 경우에 대해서 항상 경우의 수가 255가 되는 것은 아니다. m-bit의 LFSR에 대해서, 특정 조건을 만족하면 LFSR의 사이클(cycle)이 극대 길이(maximal length)를 가진다고 하며, 이 길이는 2ᵐ-1이 된다.
현대대수학을 아직 배우지 않아서 확실히 이해한 것은 아니지만, 아래에 더 자세하게 작성해 봤다.
Fibonacci LFSR
가장 일반적인 방식의 LFSR이다. 위에 소개한 방법을 사용하는 LFSR가 Fibonacci LFSR이다.
위키에 C로 작성된 예시 코드가 있지만 직접 8bit LFSR을 구현해 봤다. (MSVC)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include <stdio.h>
#include <stdint.h>
uint8_t LFSR8(uint8_t state, uint8_t taps) {
uint8_t reg = state;
uint8_t b = 0;
for (int i=0 ; i<8 ; i++)
if ((taps >> i) & 1u) b ^= reg >> i;
b = ((b^reg)&1)^reg;
__asm {
ror b, 1
}
return b;
}
int main() {
uint8_t seed = 0x59;
uint8_t taps = 1u<<0 | 1u<<2 | 1u<<3;
printf("Next state: 0x%X\n", LFSR8(seed, taps));
return 0;
}
|
이외에도 Galois LFSR, Xorshift LFSR라는 방식들이 위키에 써 있는데 아직은 굳이 알아볼 필요가 없어서 여기에 따로 정리하진 않으려고 한다.
Feedback Polynomial
LFSR에서 다음 상태를 생성하기 위해 사용되는 tap들의 배열을 유한체의 개념을 사용해 수학적으로 표현할 수 있다. 이렇게 표현되는 다항식을 feedback polynomial 또는 reciprocal characteristic polynomial이라고 하는데 한국어로 정확한 표현을 몰라서 feedback polynomial 이라고 쓰겠다.
위에서 사용되었던 예시를 다시 가져와보면, tap의 배열은 0b00001101이고 5번째, 6번째, 8번째 비트가 tap에 해당된다.
이 배열은 GF(2⁸) 의 원소로 나타낼 수 있고, 다항식 형태로는 x⁸+x⁶+x⁵+1 로 표현할 수 있다. 마지막의 1은 결과가 입력되는 비트를 의미한다.
이런 식으로, m-bit LFSR의 tap의 배열을 GF(2ᵐ) 의 원소에 대응시킬 수 있고, 이를 다항식으로 표현한 것이 feedback polynomial 이다.
위에서 간략히 설명할 때 특수한 경우에 대해서 m-bit LFSR의 사이클이 2ᵐ-1이 된다고 했다.
이를 구체적으로 설명하자면, feedback polynomial이 GF(2ᵐ)의 primitive element의 minimal polynomial이면 해당 다항식을 특성다항식으로 가지는 LFSR의 사이클은 항상 2ᵐ-1이라는 것이며, 역도 성립한다.
Reference
https://en.wikipedia.org/wiki/Linear-feedback_shift_register
http://www.secmem.org/blog/2019/08/19/Linear-Feedback-Shift-Register
