노트북 01 — 프로토콜 개요

내용

노트북 01 — 프로토콜 개요#

코드를 작성하기 전에, 위협 모델, 프로토콜(하이브리드 X3DH + 대칭 래칫), 그리고 각 빌딩 블록이 어디에서 오는지 정리합니다.

위협 모델#

이 장난감 세계에서 Alice와 Bob은 공개 채널(공유 파일 큐)을 통해 메시지를 주고받기를 원합니다. 우리가 가정하는 공격자는 다음과 같은 능력을 가집니다:

모든 암호문을 도청(Eavesdrop) 할 수 있음
암호문을 변조(Tamper) 할 수 있음 (이를 탐지하기 위해 AEAD 사용)
Alice의 장기(long-term) 개인키를 나중에 탈취(compromise) 할 수 있음 (전방 비밀성 목표)

다음에 대해서는 방어하지 않습니다:

메타데이터 프라이버시 (송신자/수신자는 평문)
능동적인 서버 사칭 (TOFU 외에는 PKI 없음)
부인 가능성(deniability), 후방 비밀성(future secrecy) (DH 래칫 없음)
우리의 파이썬 코드에 대한 사이드 채널 또는 결함 공격

KEM만으로는 부족한 이유#

다음과 같이 생각할 수 있습니다: Alice와 Bob 각각 ML-KEM 키쌍을 가지고 있으니, Alice는 매번 Bob의 공개키로 캡슐화(encapsulate)만 하면 된다. 기밀성(confidentiality)에는 동작하지만 두 가지 문제가 있습니다:

전방 비밀성 없음: Bob의 ML-KEM 개인키가 내일 노출되면, 공격자는 지금까지 보낸 모든 메시지를 복호화할 수 있습니다.
효율적인 연속 통신 불가: 매 메시지마다 전체 KEM 핸드셰이크를 다시 해야 합니다 — 5바이트짜리 “ok” 메시지에 대해서도 암호문이 ~1KB 수준으로 유지됩니다.

Signal은 RSA/ECC에 대해 Double Ratchet으로 이 문제를 해결했습니다. 우리는 그 중 단순한 대칭 전용(symmetric-only) 절반을 사용합니다.

하이브리드 X3DH (단순화)#

Alice가 Bob에게 보내는 첫 메시지에서 1회성 핸드셰이크가 실행됩니다:

Alice는 임시(ephemeral) X25519 키쌍 \((eph_{sk}, eph_{pk})\)를 생성합니다.
Alice는 고전 공유 비밀을 계산합니다: \(dh = X25519(eph_{sk}, bob_{pub})\).
Alice는 Bob에게 포스트 양자 공유 비밀을 캡슐화합니다: \((k_{kem}, c_{kem}) = \text{ML-KEM-Encaps}(bob_{ek})\).
Alice는 루트 키를 유도합니다: \(SK = \text{HKDF-SHAKE256}(salt, dh \| k_{kem}, info)\).
Alice는 \((eph_{pk}, c_{kem}, \text{본문 암호문})\)을 보냅니다.
Bob은 \(dh = X25519(bob_{sk}, eph_{pk})\), \(k_{kem} = \text{ML-KEM-Decaps}(bob_{dk}, c_{kem})\)을 통해 동일한 \(SK\)를 유도합니다.

이제 양쪽 모두 96바이트의 유도 자료를 가지게 됩니다: 32B 루트 키 + 32B Alice→Bob 체인 키 + 32B Bob→Alice 체인 키.

하이브리드: 공격자가 \(SK\)를 복원하려면 X25519와 ML-KEM-768을 모두 깨야 합니다. Shor 알고리즘(X25519를 깨지만 ML-KEM은 깨지 못함)을 막고, 알려지지 않은 격자(lattice) 공격(오늘날 ML-KEM은 깨더라도 X25519는 깨지 못할 가능성)도 막아냅니다.

ML-KEM-Encaps/Decaps의 구성과 하이브리드화 근거는 자매 도서의 ML-KEM 사양과 하이브리드 KEM을 참고하세요.

        sequenceDiagram
    autonumber
    participant A as Alice
    participant B as Bob
    Note over A,B: Bob의 장기 (X25519, ML-KEM) 공개키가 공개되어 있음
    A->>A: 임시 X25519 생성 (eph_sk, eph_pk)
    A->>A: dh = X25519(eph_sk, bob_x25519_pub)
    A->>A: (k_kem, c_kem) = ML-KEM.Encaps(bob_ml_kem_pub)
    A->>A: SK = HKDF(salt, dh ‖ k_kem, info)
    A->>A: SK 분할 → root_key, ck_a2b, ck_b2a
    A->>B: { eph_pk, c_kem, ciphertext, nonce }
    B->>B: dh = X25519(bob_x25519_sk, eph_pk)
    B->>B: k_kem = ML-KEM.Decaps(bob_ml_kem_sk, c_kem)
    B->>B: SK = HKDF(salt, dh ‖ k_kem, info)
    B->>B: SK 분할 → 동일한 root_key, ck_a2b, ck_b2a
    Note over A,B: 양쪽이 일치하는 96 B 키 자료 보유

대칭 래칫#

루트 키가 설정되면, 양쪽은 방향별로 **체인 키(chain key)**를 가집니다. 메시지 \(i\)를 암호화하려면:

message_key_i   = HKDF(chain_key, info="msg_key")
new_chain_key   = HKDF(chain_key, info="chain_advance")
chain_key      := new_chain_key

각 message_key_i는 ChaCha20-Poly1305 AEAD와 함께 정확히 한 번만 사용됩니다. HKDF가 단방향이기 때문에:

전방 비밀성: 메시지 \(i+1\) 시점의 chain_key를 알아내도 메시지 키 0..i는 드러나지 않습니다.
후방 비밀성 없음: 메시지 \(i+1\) 시점의 chain_key를 알아내면 메시지 \(i+1\) 이후의 메시지는 드러납니다.

Double Ratchet의 DH 단계는 주기적으로 새로운 DH 교환을 다시 실행하여 후방 비밀성 부재를 해결합니다. 여기서는 그 부분을 생략했습니다 — 노트북 03에서 이 한계가 정확히 어디에서 드러나는지 보여줍니다.

        flowchart LR
    CK0[chain_key i] -->|HKDF info=msg_key| MK[message_key i]
    CK0 -->|HKDF info=chain_advance| CK1[chain_key i+1]
    MK --> AEAD[ChaCha20-Poly1305]
    PT[평문 i] --> AEAD
    AEAD --> CT[암호문 i]
    CK1 -.->|다음 메시지| CK1B[chain_key i+1]

와이어 포맷#

모든 메시지는 base64로 인코딩된 바이트 필드를 포함하는 JSON 객체입니다:

{
  "version": 1,
  "sender": "alice",
  "recipient": "bob",
  "msg_index": 0,
  "kem_ciphertext": "base64...",
  "ephemeral_pk": "base64...",
  "nonce": "base64...",
  "ciphertext": "base64...",
  "sent_at": "2026-04-22T15:30:00Z"
}

첫 메시지에만 kem_ciphertext와 ephemeral_pk가 포함됩니다 — 이후 메시지는 이미 설정된 체인에 의존합니다. 우리의 전송 계층은 각 메시지를 ~/.pq-messenger/inbox/<recipient>/<uuid>.json 파일 한 개로 작성합니다.

읽는 순서#

02: 실제 키로 하이브리드 X3DH를 단계별로 따라가 봅니다.
03: 전방 비밀성을 시연하고, 동시에 키 노출 시 래칫의 한계를 보여줍니다.
04: 파일 큐를 통해 두 프로세스로 실시간 세션을 실행합니다.