TL;DR

256비트 keystream, combiner z3 -> LFSR

Analysis

LFSR 구조

1
import os
2
import hashlib
3
from Crypto.Cipher import AES
4
from Crypto.Util.Padding import pad
5
from Crypto.Random.random import getrandbits
6

7
flag = b"CTF{fake_flag}"
8

9
class LFSR:
10
    def __init__(self, key, taps):
11
        d = max(taps)
12
        assert len(key) == d, "Error: key of wrong size."
13
        self._s = key
14
        self._t = [d - t for t in taps]

상태는 길이 d의 비트 리스트 self._s taps는 탭 위치인데, self._t = [d - t for t in taps]로 한 번 뒤집는다.

e.g. d=17, taps[17,14]이면 self._t=[0,3], 실제로는 s[0], s[3] XOR

1
    def _sum(self, L):
2
        s = 0
3
        for x in L:
4
            s ^= x
5
        return s
6

7
    def _clock(self):
8
        b = self._s[0]
9
        self._s = self._s[1:] + [self._sum(self._s[p] for p in self._t)]
10
        return b

_clock은 맨 앞 비트를 출력하고, 탭 위치 비트를 XOR한 값을 뒤에 붙인다.

LFSR 길이가 $d$ , 탭 집합이 $T$ 일 때

$s_{t+d} = \bigoplus_{j \in T} s_{t+j}$

이며, 모든 연산은 $\mathbb{F}_2$ 에서 이뤄지기 때문에 초기 상태 비트들을 Boolean로 잡았을 때 전이식은 모두 선형 제약식으로 표현 가능

Jeff combiner

1
class Jeff:
2
    def __init__(self, key):
3
        assert key.bit_length() <= 102
4
        key = [int(i) for i in list("{:0102b}".format(key))]
5
        self.LFSR = [
6
            LFSR(key[:17], [17, 14]),
7
            LFSR(key[17:42], [25, 22]),
8
            LFSR(key[42:73], [31, 28]),
9
            LFSR(key[73:], [29, 27]),
10
        ]
11

12
    def bit(self):
13
        b = [lfsr.bit() for lfsr in self.LFSR]
14
        return b[1] if b[0]==0 else (b[1] if b[2]==0 and b[3]==0 else (1 if b[1]== 0 else 0))

102비트 정수 키를 이진수로 변환한 뒤 17 25 31 29비트로 나누어 각 LFSR에 배정한다. combiner 삼항식: 각 라운드에서 LFSR 출력들을 $b_{0, i}, b_{1, i}, b_{2, i}, b_{3,i}$ 로 두면

$s_i = b_{1,i} \oplus \left(b_{0,i} \land (b_{2,i} \lor b_{3,i})\right)$

따라서 keystream $s_i$ 가 총 256개 제공되므로 256개의 비선형 Boolean 방정식을 얻는다.

AES

1
def encrypt_flag(key):
2
    md5 = hashlib.md5()
3
    md5.update(str(key).encode('ascii'))
4
    key = md5.digest()
5
    cipher = AES.new(key, AES.MODE_ECB)
6
    ciphertext = cipher.encrypt(pad(flag, 16))
7
    data = {}
8
    data['encrypted'] = ciphertext.hex()
9
    return data
10

11
key = getrandbits(102)
12
J = Jeff(key)
13
stream = [J.bit() for _ in range(256)]
14
print(stream)
15
print(encrypt_flag(key))

output.txt 첫 줄은 256비트 keystream 배열, 두 번째 줄은 AES 결과 JSON이다.

AES 키는 102비트 정수 키를 알아내야 flag를 복호화할 수 있다. keystream이 이미 256비트로 102비트 seed보다 충분히 길기에 keystream 내부 상태를 역산하는 쪽으로 접근했다.

각 LFSR의 초기 상태 비트를 $x_{k,j}$ 라 두고 clock을 256번 전개하면 각 LFSR 출력 비트는 모두 초기 상태 비트들의 선형식으로 표현된다.

combiner를 적용하면

$s_i = x_{1,i} \oplus \left(x_{0,i} \land (x_{2,i} \lor x_{3,i})\right)$

LFSR 전이식은

$x_{k,t+d_k} = \bigoplus_{j \in T_k} x_{k,t+j}$

형태이며 이를 적용해 256 step 동안 전재하면 미지수는 102비트(17+25+31+29), 256개의 식이 생긴다. 즉, 과잉 결정된 비선형 Boolean 시스템이 된다.

Exploit

1
import ast
2
from hashlib import md5
3
from Crypto.Cipher import AES
4
from Crypto.Util.Padding import unpad
5
from z3 import *
6

7
with open('output.txt') as f:
8
    stream = ast.literal_eval(f.readline())
9
    enc = ast.literal_eval(f.readline())['encrypted']
10

11
cycles = len(stream)
12
solver = Solver()
13

14
def xor_all(bits):
15
    out = bits[0]
16
    for b in bits[1:]:
17
        out = Xor(out, b)
18
    return out

LFSR 전개 함수

1
def lfsr(prefix, length, taps):
2
    init = [Bool(f'{prefix}_{i}') for i in range(length)]
3
    idx = [length - t for t in taps]
4
    state = init[:]
5
    seq = []
6
    for _ in range(cycles):
7
        seq.append(state[0])
8
        state = state[1:] + [xor_all([state[i] for i in idx])]
9
    return init, seq
10

11
lfsrs = [
12
    lfsr('l1', 17, [17, 14]),
13
    lfsr('l2', 25, [25, 22]),
14
    lfsr('l3', 31, [31, 28]),
15
    lfsr('l4', 29, [29, 27]),
16
]

LFSR마다 초기 상태 Bool 변수 배열과 clock 출력 시퀀스를 동시에 생성한다. 탭 인덱스를 length - t로 계산해 문제 코드와 동일하게 구현했다

combiner

1
for i, bit in enumerate(stream):
2
    b0, b1, b2, b3 = [seq[i] for _, seq in lfsrs]
3
    solver.add(Xor(b1, And(b0, Or(b2, b3))) == BoolVal(bool(bit)))

각 라운드마다 combiner 식을 그대로 제약으로 넣는다. 관측 keystream이 0이면 BoolVal(False), 1이면 BoolVal(True)로 비교하며 매칭한다.

Key Recovery, AES Decrypti0on

1
solver.check()
2
model = solver.model()
3
key_bits = ''.join('1' if model.eval(b) else '0' for init, _ in lfsrs for b in init)
4
key_int = int(key_bits, 2)
5

6
key_md5 = md5(str(key_int).encode()).digest()
7
plaintext = AES.new(key_md5, AES.MODE_ECB).decrypt(bytes.fromhex(enc))
8
print('key =', key_int)
9
print('flag =', unpad(plaintext, 16))

각 모델에서 LFSR 초기 상태를 읽어 102비트 이진 문자열을 만든다. str(key_int)를 MD5 해시로 얻은 AES 키를 사용하여 ciphertext를 복호화하고 unpad로 PKCS#7 패딩을 제거해 flag를 확인한다.

1
python3 solve.py
2
key = 2998029425760833875497006037011
3
flag = b'CTF{LFSR_means_Losing_Faith_in_Stream_Randomness}'

1
import ast
2
from hashlib import md5
3
from Crypto.Cipher import AES
4
from Crypto.Util.Padding import unpad
5
from z3 import Solver, Bool, BoolVal, Xor, And, Or
6

7
with open('output.txt') as f:
8
    stream = ast.literal_eval(f.readline())
9
    enc = ast.literal_eval(f.readline())['encrypted']
10

11
cycles = len(stream)
12
solver = Solver()
13

14
def xor_all(bits):
15
    out = bits[0]
16
    for b in bits[1:]:
17
        out = Xor(out, b)
18
    return out
19

20
def lfsr(prefix, length, taps):
21
    init = [Bool(f'{prefix}_{i}') for i in range(length)]
22
    idx = [length - t for t in taps]
23
    state = init[:]
24
    seq = []
25
    for _ in range(cycles):
26
        seq.append(state[0])
27
        state = state[1:] + [xor_all([state[i] for i in idx])]
28
    return init, seq
29

30
lfsrs = [
31
    lfsr('l1', 17, [17, 14]),
32
    lfsr('l2', 25, [25, 22]),
33
    lfsr('l3', 31, [31, 28]),
34
    lfsr('l4', 29, [29, 27]),
35
]
36

37
for i, bit in enumerate(stream):
38
    b0, b1, b2, b3 = [seq[i] for _, seq in lfsrs]
39
    solver.add(Xor(b1, And(b0, Or(b2, b3))) == BoolVal(bool(bit)))
40

41
solver.check()
42
model = solver.model()
43
key_bits = ''.join('1' if model.eval(b) else '0' for init, _ in lfsrs for b in init)
44
key_int = int(key_bits, 2)
45

46
key_md5 = md5(str(key_int).encode()).digest()
47
plaintext = AES.new(key_md5, AES.MODE_ECB).decrypt(bytes.fromhex(enc))
48
print('key =', key_int)
49
print('flag =', unpad(plaintext, 16))

Appendix

1
import os
2
import hashlib
3
from Crypto.Cipher import AES
4
from Crypto.Util.Padding import pad
5
from Crypto.Random.random import getrandbits
6

7
flag = b"CTF{fake_flag}"
8

9
class LFSR:
10
    def __init__(self, key, taps):
11
        d = max(taps)
12
        assert len(key) == d, "Error: key of wrong size."
13
        self._s = key
14
        self._t = [d - t for t in taps]
15

16
    def _sum(self, L):
17
        s = 0
18
        for x in L:
19
            s ^= x
20
        return s
21

22
    def _clock(self):
23
        b = self._s[0]
24
        self._s = self._s[1:] + [self._sum(self._s[p] for p in self._t)]
25
        return b
26

27
    def bit(self):
28
        return self._clock()
29

30

31
class Jeff:
32
    def __init__(self, key):
33
        assert key.bit_length() <= 102
34
        key = [int(i) for i in list("{:0102b}".format(key))]
35
        self.LFSR = [
36
            LFSR(key[:17], [17, 14]),
37
            LFSR(key[17:42], [25, 22]),
38
            LFSR(key[42:73], [31, 28]),
39
            LFSR(key[73:], [29, 27]),
40
        ]
41

42
    def bit(self):
43
        b = [lfsr.bit() for lfsr in self.LFSR]
44
        return b[1] if b[0]==0 else (b[1] if b[2]==0 and b[3]==0 else (1 if b[1]== 0 else 0))
45

46

47
def encrypt_flag(key):
48
    md5 = hashlib.md5()
49
    md5.update(str(key).encode('ascii'))
50
    key = md5.digest()
51
    cipher = AES.new(key, AES.MODE_ECB)
52
    ciphertext = cipher.encrypt(pad(flag, 16))
53
    data = {}
54
    data['encrypted'] = ciphertext.hex()
55
    return data
56

57

58
key = getrandbits(102)
59
J = Jeff(key)
60
stream = [J.bit() for _ in range(256)]
61
print(stream)
62
print(encrypt_flag(key))

1
[0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0]
2
{'encrypted': 'fd37825f5f21795a4f6fbb7ce812864808396198cb158e9b5ae7b44c80c6e1371a315a6f90d1fef7b3bfc64b2674db1e692f5c84b3222853351f2048a7ffe65d'}

[D-CTF] last for sus rngs