TL;DR

WOTS 재사용 취약점

Analysis

1
#!/usr/bin/python3
2
import math
3
import os
4
from hashlib import sha256
5

6

7
class Wots:
8
    W = 256
9

10
    def __init__(self, sk, vk):
11
        self.sk = sk
12
        self.vk = vk
13

14
    @staticmethod
15
    def _checksum_len(num_msg_digits, w):
16
        max_cs = num_msg_digits * (w - 1)
17
        return math.ceil(math.log(max_cs + 1, w))
18

19
    @classmethod
20
    def keygen(cls):
21
        num_msg_digits = 32
22
        t = cls._checksum_len(num_msg_digits, cls.W)
23
        total_chains = num_msg_digits + t
24
        sk = [os.urandom(32) for _ in range(total_chains)]
25
        vk = [cls.hash(x, cls.W) for x in sk]
26
        return cls(sk, vk)
27

28
    @classmethod
29
    def hash(cls, x, n):
30
        for _ in range(n):
31
            x = sha256(x).digest()
32
        return x
33

34
    @classmethod
35
    def _digest_digits(cls, msg):
36
        m_bytes = cls.hash(msg, 1)
37
        digits = list(m_bytes)
38

39
        t = cls._checksum_len(len(digits), cls.W)
40
        cs = sum((cls.W - 1 - d) for d in digits)
41

42
        cs_digits = []
43
        for _ in range(t):
44
            cs_digits.append(cs % cls.W)
45
            cs //= cls.W
46

47
        digits.extend(cs_digits)
48
        return digits, t
49

50
    def sign(self, msg):
51
        digits, t = self._digest_digits(msg)
52
        assert len(self.sk) == len(digits)
53
        m = self.hash(msg, 1)
54
        sig = b"".join(self.hash(x, self.W - n) for x, n in zip(self.sk, digits))
55
        return sig
56

57
    def verify(self, msg, sig):
58
        digits, t = self._digest_digits(msg)
59
        chain_count = len(digits)
60
        if len(sig) != 32 * chain_count:
61
            return False
62
        chunks = [sig[i : i + 32] for i in range(0, len(sig), 32)]
63
        vk = [self.hash(x, n) for x, n in zip(chunks, digits)]
64
        return self.vk == vk
65

66

67
if __name__ == "__main__":
68
    with open("flag.txt") as f:
69
        flag = f.read().strip()
70

71
    wots = Wots.keygen()
72
    msg1 = bytes.fromhex(input("give me a message (hex): "))
73
    sig1 = wots.sign(msg1)
74

75
    assert wots.verify(msg1, sig1)
76
    print("here is the signature (hex):", sig1.hex())
77
    msg2 = bytes.fromhex(input("give me a new message (hex): "))
78
    if msg1 == msg2:
79
        print("cheater!")
80
        exit()
81
    sig2 = wots.sign(msg2)
82
    print("here is the signature (hex):", sig2.hex())
83
    if sig1 == sig2:
84
        print("cheater!")
85
        exit()
86
    msg3 = bytes.fromhex(input("give me a newer message (hex): "))
87
    if msg3 in [msg1, msg2]:
88
        print("cheater!")
89
        exit()
90
    sig3 = bytes.fromhex(input("give me the signature (hex): "))
91
    if wots.verify(msg3, sig3):
92
        print(flag)
93
    else:
94
        print("nope")

pqs.py에 정의된 Winternitz One-Time Signature(WOTS)를 사용해 세 번의 메시지 입력을 받는다. 첫 두 메시지에 대해서는 서명을 직접 돌려주고, 세 번째 메시지에 대해서는 이용자가 제출한 서명의 유효성을 검증해 맞으면 플래그 출력.

핵심은 WOTS가 말 그대로 한 번만 안전하게 사용할 수 있다는 점인데, 서버는 두 번이나 임의 메시지에 대한 서명을 제공하기 때문에 재사용 공격이 가능하다.

WOTS 체인의 구조: 비밀키 조각 $x_i$ 에 대해 해시 함수 $H$ 를 반복 적용하여

X_i^{(k)} = H^{k}(x_i)

로 정의한다.

모수 $W = 256$ 이므로, 실제 서명에서 사용되는 체인 값은 $X_i^{(W-d_i)}$ 형태가 된다. 한 번 $k$ 가 줄어든 체인 값은 역연산이 불가능하므로, 낮은 $k$ 값의 체인을 한 번이라도 얻으면 그보다 더 낮은 높이의 체인을 모두 복원할 수 있다.

1
    def sign(self, msg):
2
        digits, t = self._digest_digits(msg)
3
        assert len(self.sk) == len(digits)
4
        m = self.hash(msg, 1)
5
        sig = b"".join(self.hash(x, self.W - n) for x, n in zip(self.sk, digits))
6
        return sig

WOTS 서명은 각 체인의 남은 높이만큼 해시를 반복하여 생성된다. 특정 메시지에 대해 얻은 서명 조각을 앞쪽(남은 체인 길이만큼)으로 더 해싱하면 동일 체인에서 더 작은 서명을 만들 수 있다.

$H^{W-d_i}(x_i)$ 를 이용해 $H^{W-d_i - \Delta}(x_i)$ 를 계산하는 것과 동일하며, 여기서 $\Delta \ge 0$

1
    wots = Wots.keygen()
2
    msg1 = bytes.fromhex(input("give me a message (hex): "))
3
    sig1 = wots.sign(msg1)
4

5
    assert wots.verify(msg1, sig1)
6
    print("here is the signature (hex):", sig1.hex())
7
    msg2 = bytes.fromhex(input("give me a new message (hex): "))
8
    if msg1 == msg2:
9
        print("cheater!")
10
        exit()
11
    sig2 = wots.sign(msg2)
12
    print("here is the signature (hex):", sig2.hex())
13
    if sig1 == sig2:
14
        print("cheater!")
15
        exit()
16
    msg3 = bytes.fromhex(input("give me a newer message (hex): "))
17
    if msg3 in [msg1, msg2]:
18
        print("cheater!")
19
        exit()
20
    sig3 = bytes.fromhex(input("give me the signature (hex): "))
21
    if wots.verify(msg3, sig3):

프로토콜은 서로 다른 세 메시지 입력을 강제하지만, 첫 두 메시지에 대한 서명을 이미 공개했기 때문에 신규 메시지를 위한 체인 높이 요구량이 기존 메시지보다 작다면 해당 체인 조각을 재활용할 수 있다.

1
    def _digest_digits(cls, msg):
2
        m_bytes = cls.hash(msg, 1)
3
        digits = list(m_bytes)
4

5
        t = cls._checksum_len(len(digits), cls.W)
6
        cs = sum((cls.W - 1 - d) for d in digits)
7

8
        cs_digits = []
9
        for _ in range(t):
10
            cs_digits.append(cs % cls.W)
11
            cs //= cls.W
12

13
        digits.extend(cs_digits)
14
        return digits, t

메시지를 32바이트 SHA-256 해시로 바꾸고, 각 바이트를 기수 256의 숫자로 취급하며 추가적으로 체크섬까지 붙인다. 덕분에 체인 개수는 $32 + t = 34$ 이고 각 체인의 필요한 해시 높이는 $0 \le d_i < 256$ 범위에 존재합니다. 체크섬은 $\mathrm{cs} = \sum_{i=0}^{31} (W-1-d_i)$ 로 계산되어 $t$ 개의 추가 체인 값에 분산된다.

취약 조건: 새로운 메시지 $m_3$ 의 각 체인 요구량 $d_3[i]$ 가 첫 두 메시지 $m_1$ , $m_2$ 의 요구량 $d_1[i]$ , $d_2[i]$ 보다 작거나 같으면, $d_3[i] \le \max(d_1[i], d_2[i]) \quad \forall i \in \{0,\dots,33\}$ 를 만족한다. 두 서명 중 하나에서 해당 체인 조각을 가져와 필요한 만큼만 앞쪽으로 추가 해시하면 새로운 서명을 합성할 수 있다.

Exploit

목표는 $d_3[i] \le \max(d_1[i], d_2[i])$ 를 모든 $i$ 에 대해 만족하는 $(m_1, m_2, m_3)$ 조합을 찾는 것입니다. 각 $d[i]$ 값은 거의 균일 분포라 가정할 수 있으므로, 두 메시지에 대해 최대값을 취했을 때의 기대치는 $\mathbb{E}[\max(U_1, U_2)] = \sum_{k=0}^{255} \frac{k(2k+1)}{256^2} \approx 177.97$

평균적으로 요구 높이의 70% 이상을 덮을 수 있기 때문에 전체 체인에 대해 조건을 만족시키는 확률이 무작위 탐색으로도 충분히 높ek

POC에선 os.urandom(16)으로 임의 메시지를 뽑아 Wots._digest_digits를 호출해 세 메시지의 요구량 배열을 계산하고 조건을 만족하는 조합이 나올 때까지 반복했다

조건을 만족하는 m1, m2를 확보하면 이를 그대로 원격 서비스에 전송해 각각 sig1, sig2를 받습니다.

멀티 체인 서명 조합

받은 서명을 32바이트 단위 체인 조각으로 분해
각 체인에 대해 $d_3[i] \le d_1[i]$ 이면 sig1의 해당 조각을 채택하고, 그렇지 않고 $d_3[i] \le d_2[i]$ 이면 sig2의 조각을 선택
선택한 조각을 Wots.hash(chain, original_height - target_height)만큼 추가 해싱하면 정확히 $d_3[i]$ 높이에 해당하는 체인 값을 얻는다

$\widetilde{C}_i = H^{h_i - d_3[i]}(C_i)$ 로 계산, 여기서 $h_i$ 는 선택한 원본 체인의 높이 모든 체인 조각을 순서대로 이어 붙이면 m3에 대한 위조 서명 sig3_forged가 완성

m3와 합성한 서명을 서버에 제출하면 wots.verify가 통과하고 플래그를 받을 수 있다.

조건을 만족하는 메시지 세 개 찾기

1
from pqs import Wots
2
import os
3

4
def digest(msg):
5
    digits, _ = Wots._digest_digits(msg)
6
    return digits
7

8
while True:
9
    m1 = os.urandom(16)
10
    m2 = os.urandom(16)
11
    d1 = digest(m1)
12
    d2 = digest(m2)
13
    thresh = [max(a, b) for a, b in zip(d1, d2)]
14
    m3 = os.urandom(16)
15
    d3 = digest(m3)
16
    if all(c <= t for c, t in zip(d3, thresh)) and len({m1, m2, m3}) == 3:
17
        break

m1 = a97d6818b5d4fde820a2a19293018542
m2 = 510b8bff8daf959b85770d5ca66410c8
m3 = f006e1fa0480c576d7659f024d0bd89d

$d_3 \preceq \max(d_1, d_2)$ 입니다.

서명 합성 로직

1
chunks1 = [sig1[i:i+32] for i in range(0, len(sig1), 32)]
2
chunks2 = [sig2[i:i+32] for i in range(0, len(sig2), 32)]
3
forged_chunks = []
4
for target, h1, h2, c1, c2 in zip(d3, d1, d2, chunks1, chunks2):
5
    if target <= h1:
6
        forged_chunks.append(Wots.hash(c1, h1 - target))
7
    elif target <= h2:
8
        forged_chunks.append(Wots.hash(c2, h2 - target))
9
    else:
10
        raise AssertionError("조건 불충족")
11
forged_sig = b"".join(forged_chunks)

위와 같이 체인별로 조건을 체크하며 위조 서명 생성

1
andsopwn@meow:~/ctftemp/hspace/crypto/pqs$ python3 exploit.py
2
[x] Opening connection to 13.125.132.168 on port 15151
3
[x] Opening connection to 13.125.132.168 on port 15151: Trying 13.125.132.168
4
[+] Opening connection to 13.125.132.168 on port 15151: Done
5
[DEBUG] Received 0x19 bytes:
6
...
7
[DEBUG] Sent 0x21 bytes:
8
    b'f006e1fa0480c576d7659f024d0bd89d\n'
9
[DEBUG] Received 0x1d bytes:
10
    b'give me the signature (hex): '
11
[DEBUG] Sent 0x881 bytes:
12
    b'ed12346520602a607ae4134b39c6dd1c0c780c6a772d15719d3a776134094548bd1027a1c4e8c99b1b6ea2df64369267638b314373825bd37c211a408ced6f27075c100b8a4a450124246c41d7e63a00410c066a336aaafa5eba4e4cfb42e00301c8b0e2e69d19aefd966139a5ac7a86b397719abcbf7874477fe47dc287012f55f306d6946e0702f6d608198644d2af1d0e54fe77878c8a6ab7c4dac718c8b72aeecbfed76d2b8a45acf1cd414ae3fc5fc9a4f46657c051fefbe8fbdfbfc0731c3071514d6394d489dcad40a2678af90177a2f0f44c785868982afe0b6b3a7afbdfa651a5961edc75f7c665954e90db9ef55568448717ee8b704325a92b317d2700e6b5ffe484e307b3154adbe86108d53c2d3df214f61e8c3c1890778b32cb508ad4823199f35f16eb016100753213c6a7668deeaaecf3a98d9ae18dc3a7f1f3c569c2b80542b783d30ad5afe8cfd76d2171d614b98eb3f12e0b7338ded9c27945efc4ccb9e377612777285c74220632d503902917bf9eee9330d3da32af1e3c2f8d47d21d71f6182bf1273d2fa77323ecd12126e6246a999397a56586cb87ae2eeb45d3ee26a409cfbd63d767571e88ba03ce10ce10b252c96f587f6704a4884081c12b4550ef4873d98f11223c43da8f8993750db3ce8b73b58074f7d879b3e3026f74183bbe21897d6f5bdd4efda17872309e056ceb62f785aa997d781e0c922ecf54ea37ef67c0a8e2d16d3b17a00a5e3b1aef49915eddd7de24b4574a1fda431febd4c8347bdaf48878dfc3fde8c5819adba13ea4c7f654b915fde1606cf8d028a23d2a8583a3514c9631f88e74b13ae2462c45f609f3f4c9b702efb52259d28f386033a28017302bb45d5efdb8029ff0c0feefece6d2e51612fedd8b51f32b6fb99b8deccc71291d388e2aafb26a514a483d54673ae5eb9cbb64dff6d38f9c621dcf391de3af38fa0e2ef521ea69bf6191f5af4c076423dce2be5521735db3a063045073ae33f5a1801b5dca90ef527086527839d7a921a3745bdf032287f038edf21fa8ae5fee9e59282bab53f48de598ad2113c981843ea72449e98e055a23597899cb3da889196f2082445f12c817d765d2180d0da93bd4d9c67c513972b4c26047848b7b43a55fbcb3f6ed5017d1ce743c91cd37c5fb7f236fd2551e91212f129a7093f7a33bc004bc4f76c6a92e74f7342ecde08369fe6a956d6460d147c4cf039476faf19e819ca586a7f047e2cbbb488a3f092662b06b04a737de78db704d004405d6eabaa24efde95379d92f4021b567af5ca5ffa1e16cb365fe57fdbbc4db0813749fff3c896cc650c9c4d22db85737b1c2c3510d805ab8ea0dd9c0f910cbe00a1c0e1200bcb18c019f9fa0fec315c7455e0dec193e950322fa10c02c81c294a982f82378c1f54a268e304958cfb43ccea1cb1ddc9a176b58402d328113cab760f872803ea63e0add551757feed2284ddeda678bf98c933052aefe46afee9006c087d74501e9052c69f604b8eff76f056fbc03eac3979ca\n'
13
[x] Receiving all data
14
[x] Receiving all data: 0B
15
[DEBUG] Received 0x29 bytes:
16
    b'hspace{15398c41921c577a779cfac0e5af4ee1}\n'
17
[x] Receiving all data: 41B
18
[+] Receiving all data: Done (41B)
19
[*] Closed connection to 13.125.132.168 port 15151
20
hspace{15398c41921c577a779cfac0e5af4ee1}

[CLUB LEAGUE] pqs writeup

TL;DR

Analysis

Exploit