PQC란 무엇인가 (2) — 앨리스와 밥이 ML-KEM으로 통신하는 과정

PQC란 무엇인가 (2) — 앨리스와 밥이 ML-KEM으로 통신하는 과정

 

지난 글에서는 PQC와 ML-KEM의 기본 개념, 그리고 격자 문제의 원리를 알아보았다.

이번에는 앨리스가 서버, 밥이 접속하는 사용자라고 가정하고, 실제 통신이 어떤 순서로 이루어지는지 살펴본다.

 

앨리스	=	서버
밥	=	사용자
이브	=	중간에서 통신을 훔쳐보는 공격자

 

 

[준비 단계] 통신 시작 전에 정할 것들

 

▶ 알고리즘 합의

• 앨리스와 밥은 서로 사용할 수 있는 암호 알고리즘 목록을 확인한다.

 

키 캡슐화	:	ML-KEM
데이터 암호화	:	AES-256-GCM
키 생성 함수	:	HKDF
전자서명	:	ML-DSA

• 실제 인터넷 프로토콜에서는 지원 알고리즘과 보안 수준을 서로 협상한다.

 

▶ 안전한 난수 준비

• PQC에서도 좋은 난수가 매우 중요하다.
• 예측 가능한 난수를 쓰면 수학 알고리즘이 안전해도 공격자가 키를 추측할 수 있다.
• 앨리스와 밥은 운영체제가 제공하는 암호학적으로 안전한 난수 생성기를 사용한다.

 

앨리스가 ML-KEM 키 쌍을 만든다

 

▶ 비밀값과 공개 행렬 생성

• 앨리스의 컴퓨터는 난수로 비밀 벡터 $s$와 작은 잡음 $e$를 만든다.
• 공개 가능한 행렬 $A$도 생성한다. (짧은 시드에서 다시 만들어낼 수도 있다.)

 

▶ 잡음이 섞인 공개값 계산

$$t = As + e \pmod q$$

공개키 pk	=	A와 t에 관한 정보
개인키 sk	=	비밀 s와 복호화에 필요한 정보

 

▶ 키 보관

• 공개키 : 누구에게나 공개 가능, 접속자에게 전달
• 개인키 : 앨리스만 보관, 외부 전송 금지, 안전한 메모리·보안장치에 저장
• 공개키만으로 개인키를 계산하기는 매우 어렵도록 설계되어 있다.

 

공개키가 진짜 앨리스의 것인지 증명한다

 

▶ 인증서 준비

• 앨리스는 자신의 신원과 공개키를 연결하는 인증서를 준비한다.

인증서에 담기는 정보
- 앨리스의 이름 또는 도메인
- 앨리스의 공개키
- 인증서 유효기간
- 사용 가능한 알고리즘
- 인증기관의 전자서명

 

▶ 공개키·인증서 전송

• 앨리스는 일반 인터넷으로 ML-KEM 공개키, 인증서, 통신에 필요한 부가정보를 밥에게 보낸다.
• 이 정보는 일반 디지털 데이터이므로 이브가 복사해서 볼 수 있다.

 

▶ 밥의 검증

• 밥은 신뢰하는 인증기관의 공개키로 인증서의 전자서명을 검사한다.

- 접속하려는 도메인과 인증서 이름이 같은가?
- 인증서 유효기간이 지나지 않았는가?
- 신뢰할 수 있는 기관에서 발급되었는가?
- 전송 중 내용이 변경되지 않았는가?
- 금지된 알고리즘은 아닌가?

검증 성공	→	받은 공개키는 앨리스의 공개키일 가능성이 충분히 높음
검증 실패	→	가짜 서버 또는 변조 가능성, 통신 중단

★ PQC를 사용하더라도 공개키 인증을 생략하면 중간자 공격을 막을 수 없다.

 

 

 

밥이 공통 비밀값과 캡슐문을 만든다

 

▶ Encaps 실행

• 밥은 인증이 끝난 앨리스의 공개키로 캡슐화 알고리즘을 실행한다.
• 매번 새로운 난수를 사용하므로, 같은 앨리스에게 여러 번 접속해도 매번 새로운 캡슐문과 비밀값이 만들어진다.

$$(K\_B, C) = Encaps(pk\_A)$$

공통 비밀값 K_B	:	밥이 자신의 메모리에 비밀로 보관, 인터넷으로 직접 보내지 않음
캡슐문 C	:	앨리스에게 전송, 공개되어도 괜찮음

☞ 밥이 먼저 $K\_B$를 만들어서 캡슐 속에 그대로 넣는 것이 아니라, ML-KEM 연산 결과로 비밀값과 캡슐문이 함께 만들어진다.

 

▶ 캡슐문 전송

• 밥은 캡슐문 $C$를 일반 인터넷으로 앨리스에게 보낸다.
• 이브는 캡슐문을 복사할 수 있지만, 앨리스의 개인키가 없으면 동일한 비밀값을 얻기 어렵다.

 

앨리스가 같은 비밀값을 복원한다

 

▶ Decaps 실행

• 앨리스는 캡슐문 $C$를 받아 개인키 $sk\_A$와 함께 역캡슐화 알고리즘에 넣는다.

$$K\_A = Decaps(sk\_A, C)$$

• 캡슐문이 정상이라면 앨리스가 얻은 값은 밥이 만든 값과 같다 : $K\_A = K\_B$

 

☞ 잘못된 캡슐문 처리

• 이브가 캡슐문을 변경했을 수도 있다.
• ML-KEM은 잘못된 캡슐문도 안전하게 처리하도록 설계되어 있다.
• 구현체는 처리 시간이나 오류 메시지로 개인키 정보가 새어 나가지 않도록 주의해야 한다. (상세한 오류 메시지는 부채널 공격의 단서가 될 수 있다.)

 

 

공통 비밀값에서 실제 암호키 만들기

 

▶ 왜 그대로 쓰지 않을까?

• 공통 비밀값을 모든 용도에 그대로 쓰는 것은 좋지 않다.
• 키 생성 함수(KDF, 예: HKDF)로 목적별 키를 나눈다.

$$K\_{\text{session}} = KDF(K, \text{통신 정보})$$

 

▶ 방향별로 키를 나눈다

밥 → 앨리스 데이터 암호화 키
앨리스 → 밥 데이터 암호화 키
밥 → 앨리스 nonce 관련 값
앨리스 → 밥 nonce 관련 값
통신 확인용 키

• 용도별로 키를 분리하면 한쪽 키에 문제가 생겨도 피해가 다른 기능으로 번지는 것을 줄일 수 있다.

 

☞ 실제 보안 프로토콜에서는 지금까지 주고받은 통신 내용(알고리즘 협상, 공개키, 인증서, 캡슐문 등)의 해시값도 키 생성에 반영해서, 공격자가 앞부분 통신 내용을 몰래 바꾸기 어렵게 만든다.

 

 

실제 데이터 암호화하기

 

▶ 밥이 데이터를 암호화한다

• 밥이 앨리스에게 HELLO라는 문장을 보낸다고 가정한다.
• 밥은 nonce(같은 키에서 반복 사용하면 안 되는 값)를 준비하고, 세션키와 함께 AES-GCM으로 암호화한다.

$$(C, T) = Encrypt(K, N, P, A)$$

• $C$ : 암호문 / $T$ : 인증 태그 / $A$ : 암호화하지 않지만 위·변조 여부는 검사할 정보
• 밥은 암호문, nonce, 인증 태그, 부가정보를 일반 인터넷으로 전송한다. 세션키는 전송하지 않는다.

 

 

▶ 이브가 볼 수 있는 것과 볼 수 없는 것

이브가 볼 수 있는 것	이브가 알 수 없는 것
- 앨리스의 공개키	- 앨리스의 ML-KEM 개인키
- 인증서	- 공통 비밀값
- ML-KEM 캡슐문	- 최종 세션키
- 암호문, nonce, 인증 태그	- 원본 데이터

 

▶ 앨리스가 검증하고 복호화한다

인증 태그 정상	→	올바른 키로 만들어졌고, 데이터가 변경되지 않았을 가능성이 높음
인증 태그 비정상	→	위조·변조·전송 오류 또는 잘못된 키, 데이터 폐기

• 인증 검사가 성공하면 앨리스는 $P = Decrypt(K, N, C, A, T)$로 암호문을 복호화해서 HELLO를 얻는다.

 

응답을 보내고 연결을 종료한다

 

▶ 앨리스의 응답

• 앨리스도 WORLD라는 응답을 준비하고, 앨리스 → 밥 방향으로 할당된 세션키와 새로운 nonce로 AES-GCM 암호화해서 보낸다.
• 밥은 같은 방향별 세션키로 인증하고 복호화한다.

 

▶ 연결 종료와 키 폐기

• 파일 전송이나 인터넷 연결이 끝나면 세션을 종료한다.
• 앨리스와 밥은 이번 연결에서 쓴 세션키를 메모리에서 제거한다.
• 앨리스의 장기 개인키는 인증서 정책과 보안 정책에 따라 계속 보관하거나 정기적으로 교체한다.

세션키	:	한 연결 또는 짧은 기간에 사용
장기 개인키	:	여러 접속에서 캡슐 해제 등에 사용
인증서 서명키	:	신원 증명에 사용

 

전체 흐름 요약

[앨리스]
1. ML-KEM 공개키 pk와 개인키 sk 생성
2. 개인키 sk는 비밀로 보관
3. 공개키 pk와 인증서 전송
↓ 일반 인터넷 ↓

[밥]
4. 인증서와 공개키 검증
5. (K, C) = Encaps(pk) 실행
6. 공통 비밀값 K는 보관
7. 캡슐문 C를 앨리스에게 전송
↓ 일반 인터넷 ↓

[앨리스]
8. K = Decaps(sk, C) 실행
9. 밥과 동일한 공통 비밀값 K 획득
↓

[앨리스와 밥]
10. KDF로 목적별 세션키 생성
11. AES-GCM 등으로 실제 데이터 암호화
12. 일반 인터넷으로 암호문 전송
13. 인증 태그 확인 후 복호화
14. 연결 종료 후 세션키 폐기

 

 

다음 글에서는 ML-KEM만으로는 해결되지 않는 "신원 확인" 문제, 즉 전자서명(ML-DSA, SLH-DSA)과 하이브리드 방식, 그리고 실전 보안 이슈를 다룬다.