노트북 08 — 하이브리드 KEM: 고전 + 양자 내성

내용

노트북 08 — 하이브리드 KEM: 고전 + 양자 내성#

왜 하이브리드인가? ML-KEM은 X25519보다 암호학적 분석 기간이 짧습니다. PQC가 더 많은 실전 검증을 거치기 전까지, 실제 배포되는 프로토콜들(TLS 1.3 draft-ietf-tls-hybrid-design, SSH, IKEv2)은 두 가지를 결합합니다: 하이브리드 키는 둘 중 하나만 안전해도 안전합니다.

import hashlib
from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey
from pqc_edu.ml_kem import ml_kem_keygen, ml_kem_encaps, ml_kem_decaps
from pqc_edu.params import ML_KEM_768

프로토콜#

Alice: (x25519_sk_A, x25519_pk_A)와 (ek, dk)를 생성하고, (x25519_pk_A, ek)를 전송합니다.
Bob: (x25519_sk_B, x25519_pk_B)를 생성합니다. ss_x = x25519(sk_B, pk_A)와 (ss_mlkem, ct) = ml_kem_encaps(ek)를 계산하고, (x25519_pk_B, ct)를 전송합니다.
양쪽 모두 K = SHAKE256(ss_x || ss_mlkem || transcript, 32)를 유도합니다.

# Alice: classical + PQ keys
alice_x25519 = X25519PrivateKey.generate()
alice_x25519_pk = alice_x25519.public_key().public_bytes_raw()
ek, dk = ml_kem_keygen(ML_KEM_768)

# Bob: classical keypair + encapsulate to Alice's ek
bob_x25519 = X25519PrivateKey.generate()
bob_x25519_pk = bob_x25519.public_key().public_bytes_raw()
ss_x_bob = bob_x25519.exchange(
    __import__('cryptography').hazmat.primitives.asymmetric.x25519.X25519PublicKey
    .from_public_bytes(alice_x25519_pk)
)
ss_mlkem_bob, ct = ml_kem_encaps(ML_KEM_768, ek)

# Alice: completes both halves
from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PublicKey
ss_x_alice = alice_x25519.exchange(X25519PublicKey.from_public_bytes(bob_x25519_pk))
ss_mlkem_alice = ml_kem_decaps(ML_KEM_768, dk, ct)

transcript = alice_x25519_pk + ek + bob_x25519_pk + ct

def derive(ss_x, ss_mlkem):
    h = hashlib.shake_256()
    h.update(ss_x + ss_mlkem + transcript)
    return h.digest(32)

K_alice = derive(ss_x_alice, ss_mlkem_alice)
K_bob = derive(ss_x_bob, ss_mlkem_bob)
print('X25519 halves match      :', ss_x_alice == ss_x_bob)
print('ML-KEM halves match      :', ss_mlkem_alice == ss_mlkem_bob)
print('final hybrid K match     :', K_alice == K_bob)
print('K (hex) =', K_alice.hex())

X25519 halves match      : True
ML-KEM halves match      : True
final hybrid K match     : True
K (hex) = 04856cc20f47e23afcea8ecf7a1245e7184456adb876089f7d4abbcb9d74638f

보안 속성#

공격자가 K를 복원하려면 X25519와 ML-KEM 둘 다를 깨야 합니다. 양자 컴퓨터는 X25519를 깨지만 ML-KEM은 (추측상) 깨지 못합니다. 고전 암호 해독이 언젠가 ML-KEM을 깰 수도 있지만, X25519는 (매우 가능성 높게) 깨지 못합니다. 하이브리드는 어느 쪽 세상에서도 살아남습니다.

변조(tamper) 테스트#

ML-KEM 암호문의 한 비트를 뒤집어 봅니다. FO 변환의 implicit rejection 때문에 Alice는 에러가 아니라 의사난수 ss_mlkem을 유도합니다 — 따라서 그녀의 하이브리드 키는 쓰레기가 되지만, 변조된 것인지는 알 수 없습니다. 실제 프로토콜에서는 transcript에 대한 인증 태그가 이를 잡아냅니다.

ct_tampered = bytearray(ct); ct_tampered[0] ^= 0x01
ss_mlkem_alice_bad = ml_kem_decaps(ML_KEM_768, dk, bytes(ct_tampered))
K_alice_bad = derive(ss_x_alice, ss_mlkem_alice_bad)
print('ss_mlkem changed:', ss_mlkem_alice_bad != ss_mlkem_alice)
print('hybrid K now differs from Bob\'s:', K_alice_bad != K_bob)

ss_mlkem changed: True
hybrid K now differs from Bob's: True