XMSS(Extended Merkle Signature Scheme)

블록체인과 양자컴퓨팅

2025.03.25 - [Blockchain/Base] - 양자 컴퓨팅과 블록체인

2025.03.25 - [Development/Cryptography] - XMSS(Extended Merkle Signature Scheme)

양자 내성을 가지는 암호 알고리즘인 XMSS에 대하여 확인해 본다.

개요

기존 비대칭 공개키 알고리즘이 소인수분해, 이산 수학적으로 풀기 어려운 구조이기 때문에 private key를 유추할 수 없는 구조이지만, 양자 컴퓨터를 이용하여 Shor's algorithm을 적용하면 이를 유추할 수 있게 된다.

이를 대비하기 위하여 양자 컴퓨터로 암호학적 문제 해결이 어려운 충돌 저항성 기반 해시를 통한 서명 알고리즘을 사용하는 XMSS에 대하여 확인해 본다.

XMSS는 Merkle tree와 단일 사용(one-time) 서명 방식을 결합한 양자 내성 디지털 서명 알고리즘으로써 2018년에 IETF RFC 8391로 표준화가 진행되었다.

XMSS 구조

XMSS는 개요에서 언급되었듯이 구조의 큰 구성은 One-time siganture(OTS) Scheme과 Merkle tree가 주요한 컴포넌트로써 사용된다. 각각의 XMSS에 적용되는 특성은 아래와 같다.

• OTS scheme
  • XMSS에서 사용되는 OTS는 WOTS+ (Winternitz OTS Plus) 이다.
  • OTS로 생성된 키는 서명 시 단 한번만 사용된다.
  • 연산이 빠르고 해시 함수만을 기반으로 한다.
• Merkle tree
  • 많은 수의 OTS 공개키를 Merkle tree의 리프 노드로 구성한다.
  • Merkle root의 해시값이 XMSS의 공개키가 된다.
  • 서명 시에는 사용된 OTS의 인증 경로(authentication path)를 함께 첨부한다.
  • OTS 개인키는 한번만 서명에 사용 가능하기 때문에 XMSS는 어떤 키가 서명에 사용되었는지에 대한 상태(statte)를 반드시 기록하고 있어야 한다.

XMSS 내 OTS(WOTS+) 수행 과정

XMSS에 사용되는 WOTS+에 대해 확인한다. WOTS+는 기존 WOTS에 보안이 강화된 패치를 수행한 plus 버전이다. WOTS+는 RSA처럼 소인수분해의 해를 찾는 난해함을 사용한 암호 알고리즘이 아닌 해시 함수만을 사용하여 만든 단일 메시지 서명 방식이다.

WOTS+는 plaintext 메시지의 해시값을 숫자로 보고 해당 숫자를 반복 해시하여 서명을 생성하는 것이 핵심 아이디어이다. 그렇기 때문에 WOTS+의 보안은 사용하는 해시 함수에 전적으로 의존한다.

논문 내의 WOTS+ 수행 과정을 축약하여 설명한다.

파라미터

WOTS+의 수행 과정 전에 사용 되는 주요 파라미터를 정의하면 아래와 같다.

• $n$ : $n\in\mathbb{N}$ 으로, 논문 상에는 "the security parameter"로 정의된다. 이는 bits 갯수이며 출력 해시값의 길이와 같다. (e.g. SHA-256 > $n=256$)
• $w$ : Winternitz 매개 변수 ($w\in\mathbb{N},w>1$)
• $l$ : 메시지를 $l$개의 블록으로 분해하는 값

파라미터 중 $l$의 생성을 확인하면

$$l_1=\lceil n/\text{log}(w) \rceil, l_2=\lfloor \text{log}(l_1(w-1))/\text{log}(w) \rfloor + 1$$
$$l=l_1+l_2$$

이다.

비밀키

먼저 복수개의 비밀키(secret signature key) $SK$를 생성한다. 비밀키는 $l$개로 생성된다. 각 $sk_i$는 $n$-bit string이며 $1\geq i\geq l$이다. Pseudorandom generator $\mathbf{GEN}$을 이용하여 비밀키가 생성된다.

$$sk_i \gets \mathbf{GEN}_l(f_{\text{SEED}}(i))$$

최종적으로 비밀키 $SK$는 $sk_i$들의 집합이다.

$$SK=(sk_1,sk_2,...,sk_l)$$

앞서 확인한 $l$을 확인하면, 만약 $n$이 SHA-256처럼 $n=256$이고, $w=16$ 일 시

$$l_1=\lceil 256/4 \rceil = 64, l_2=\lfloor\text{log}(64\times 15)/4 \rfloor = 3$$

이므로 $l=64+3=67$이 된다. 따라서 이 예시에서는 비밀키는 67개의 256비트 값이 된다.

공개키

공개키 $PK$는 각 $sk_i$를 $w-1$번 해시하여 생성한다. 각 공개키는 아래와 같이 생성되며

$$pk_i=f_{sk_i}^{w-1}(x)$$

이다. $w=16$ 일 때 $pk_i$는 해시를 15번 적용($w-1$)하여 공개키를 생성한다. 최종적으로 공개키 $PK$는 $pk_i$들의 집합이다.

$$PK=(pk_1,pk_2,...,pk_l)=(f_{sk_1}^{w-1}(x),f_{sk_2}^{w-1}(x),...,f_{sk_l}^{w-1}(x))$$

서명 생성

입력 메시지 $M$의 해시값을 $h=H(M)$라 할 때 $h$를 $l$개의 블록으로 나눈다. (정확하게 메시지는 $l_1$개로 나뉘고 $l_2$ 길이의 checksum으로 전체 $l$개가 된다.) 나뉜 각 블록을 $(b_1,...,b_l)$ 이라 표현하면 각각의 index에 대응하는 비밀키로 서명 $\sigma_i$를 생성한다.

$$\sigma_i=f_{sk_i}^{b_i}(x)$$

최종적으로 서명 $\sigma$는 $\sigma_i$들의 집합이다.

$$\sigma=(\sigma_1,\sigma_2,...,\sigma_l)=(f_{sk_1}^{b_1}(x),f_{sk_2}^{b_2}(x),...,f_{sk_l}^{b_l}(x))$$

서명 검증

서명 검증자는 각 $\sigma_i$에 대하여 연산을 수행하여 원래 공개키와 일치하는지 비교함으로써 서명을 검증한다.

$$(f_{\sigma_1}^{w-1-b_1}(pk_0),...,f_{\sigma_l}^{w-1-b_l}(pk_0))?=(pk_1,...,pk_l)$$

XMSS 내 Merkle tree 인증 경로

먼저, XMSS 내 merkle tree의 node는 아래와 같이 정의된다.

$$\text{NODE}_{i,j}=h_K( (\text{NODE}_{2i,j-1}) \oplus b_{l,j}) || (\text{NODE}_{2i+1,j-1}) \oplus b_{r,j}) )$$

WOTS+의 키들을 merkle tree의 리프 노드로 사용하고, 루트 해시가 XMSS의 공개키가 되는 구조이다. $i$번째 메시지의 서명값을 $\text{SIG}=(i,\sigma,\text{AUTH})$라고 할 때 인증 경로(authentication path) $\text{AUTH}$는 아래와 같이 표현된다. 아래의 $H$는 merkle tree의 height이다.

$$\text{AUTH}=(\text{AUTH}_0,...,\text{AUTH}_{H-1})$$

그림처럼 $i$의 $pk$를 사용했을 시 인증 경로를 포함해야 한다. 이해를 위해 간단한 예를 들어본다. 4개의 WOTS+ 공개키 $pk$가 있다고 가정하면 merkle tree는 아래와 같이 구성된다.

      Root
     /    |
   H01     H23
  /  |     /  |
pk0 pk1  pk2 pk3

H01은 pk0와 pk1의 hash이며, H23도 마찬가지이다. Root는 H01과 H23의 해시이다. 이 때 메시지를 pk2를 사용하여 검증했다면 검증자는 pk2가 merkle root에 포함되는 것을 증명해야 한다. pk2의 sibling node pk3와 부모의 sibling H01을 가지며 인증 경로는 pk3와 H01이 된다. 서명 검증자는 인증 경로 데이터를 사용하여 연산을 통해 계산된 Root가 XMSS 공개키와 일치하는지 확인한다.

XMSS의 양자 저항성

위에서 간단히 확인한 내용을 바탕으로 XMSS가 어떠한 속성을 가지고 있기 때문에 양자 내성을 보유하는지 확인해본다.

해시 함수 기반

XMSS는 해시 함수만을 사용하기 때문에 Shor's algorithm 같은 양자 알고리즘에 직접적으로 영향을 받지 않는다. Shor's algorithm은 소인수분해, 이산 로그 문제를 빠르게 풀 수 있지만 해시 함수 구조를 깰 수는 없기 때문이다.

또한 해시의 역상을 빠르게 찾는 Grover's algorithm에도 대응할 수 있다. Grover's algorithm은 해시의 역상을 찾는 난이도를 반으로 줄이지만 XMSS가 충분히 긴 해시 출력을 사용하여 대응할 수 있다.

OTS의 one-time 설계

OTS는 1회 사용이므로 공개키나 서명에서 정보를 반복적으로 노출하지 않기 때문에 정보 유출로 인한 키 복원 가능성을 차단한다.

결론

블록체인 입장에서 양자 컴퓨터로 인한 가장 큰 위험성은 공개키 암호 알고리즘이 뚫리는 것이다. 이를 위해 양자 내성 암호를 적용하는데, 여러 방식 중 해시 함수를 통한 암호 알고리즘 기법인 XMSS의 구조를 간단히 확인해보았다. 비밀키/공개키의 비대칭키를 사용하지만 내용을 확인 했을 시 소인수분해의 내용은 제거되고 오직 해시함수로만 알고리즘을 구성하는 것을 확인했다.

QRL(Quantum Resistant Ledger) 프로젝트는 XMSS를 사용하여 양자 내성 블록체인을 만드는 프로젝트이다. 실제로 XMSS를 이용하여 양자 내성을 방어하려는 모습도 확인된다. QRL의 github은 여기이다. 블록체인을 python으로 구현해 놓은듯 보인다.

참고한 XMSS 논문은 여러 attack에 대한 대응성을 확인한다. 수학적으로 어떻게 대응하는지에 대한 확인이 필요하면 참고한 XMSS 논문을 확인하면 좋을것 같다.

참고
https://eprint.iacr.org/2011/484.pdf