On the Practical Feasibility of Harvest-Now, Decrypt-Later Attacks

1. 문제 정의 (Problem Statement)

현재 수확, 미래 복호화 (HN-DL, Harvest-Now, Decrypt-Later) 공격은 적대자가 오늘날 암호화된 통신을 기록해 두었다가, 향후 양자 컴퓨터가 개발되어 기존 키 교환 알고리즘 (RSA, ECC 등) 을 깨뜨릴 때 이를 복호화하는 위협입니다.

• 핵심 위협: 공개키 암호화 (RSA, ECC) 는 쇼어 알고리즘 (Shor's algorithm) 으로 인해 양자 컴퓨터 앞에서 무력화되지만, 대칭키 암호는 키 길이를 두 배로 늘리면 안전합니다. 따라서 적대자는 대량 데이터 암호화 자체보다는 키 교환 과정을 타겟으로 합니다.
• 경제적 오해: 기존 연구들은 HN-DL 의 실행 가능성을 주로 암호학적 취약성에 초점을 맞추거나, 양자 컴퓨터의 등장 시점 (Q-Day) 에만 집중했습니다. 그러나 본 논문은 저장 비용 (Storage Economics) 측면에서 이 문제를 재정의합니다.
• 주요 질문: 적대자가 암호화된 트래픽을 가로챌 수 있다면, 양자 컴퓨터가 등장할 때까지 (10~15 년) 그 데이터를 보관하는 것이 경제적으로 가능한가?

2. 방법론 (Methodology)

저자들은 HN-DL 공격을 정량적으로 분석하기 위해 다음과 같은 방법론을 사용했습니다.

• 오픈 소스 테스트베드 구축: TLS 1.2, TLS 1.3, QUIC, SSH 프로토콜에 대한 전체 공격 시나리오를 재현하는 오픈 소스 시뮬레이션 파이프라인을 개발했습니다.
  • 구현: 패치된 OpenSSL 3.6.0, OpenSSH 9.9p2, tshark 등을 활용하여 루프백 인터페이스에서 트래픽을 생성하고 캡처했습니다.
  • 양자 시뮬레이션: 실제 양자 컴퓨터가 존재하지 않으므로, 시뮬레이션된 양자 출력 (임시 개인키) 을 사용하여 세션 키를 유도하고, 이를 통해 캡처된 패킷을 완전히 복호화하는 과정을 검증했습니다.
• 저장 비용 모델링:
  • 프로토콜 오버헤드 비율 ($\alpha$): 세션당 저장해야 하는 데이터 양을 계산하기 위해, 실제 페이로드 ($P$) 대비 암호화 및 전송 오버헤드 (핸드셰이크, 패딩, 헤더 등) 를 포함한 총 저장 크기 $S(P)$ 를 모델링했습니다. $\alpha = S(P)/P$ 비율을 도출했습니다.
  • 몬테카를로 시뮬레이션: 트래픽 크기 분포, 저장 비용 변동성, 데이터 성장률 등을 변수로 설정하여 10,000 회 이상의 시뮬레이션을 통해 장기적인 저장 비용을 예측했습니다.
• 비용 축 분석: 적대자의 비용을 두 가지 축으로 나누어 분석했습니다.
  1. 저장 비용 (Storage): 적대자가 데이터를 보관하는 비용.
  2. 양자 계산 비용 (Quantum Workload): 데이터를 복호화하기 위해 필요한 양자 연산 비용 ($E \times T_q$).

3. 주요 기여 (Key Contributions)

1. HN-DL 의 경제적 재정의: HN-DL 공격이 암호학적 실패뿐만 아니라 저장 경제학의 문제임을 입증했습니다. 적대자가 트래픽을 가로챌 수 있다면, 데이터를 보관하는 비용은 국가 차원에서도 '경제적으로 사소한 (trivial)' 수준임을 정량화했습니다.
2. 프로토콜별 취약성 및 오버헤드 정량화:
   • TLS 1.2 (RSA), TLS 1.3, QUIC, SSH 의 각 모드별 HN-DL 취약 범위를 분석했습니다.
   • 작은 페이로드 (예: 인증 토큰) 의 경우 프로토콜 오버헤드 비율 ($\alpha$) 이 3 배~8 배까지 증가하여, 고가치 정보 위주의 수집 시 저장 비용이 더 많이 들 수 있음을 보였습니다.
3. 심층 방어 (Defense-in-Depth) 전략 제안:
   • 양자 부하 증가 전략: 저장 비용 증가 (오버헤드 팽창) 는 방어자와 공격자 모두에게 비용이 발생하지만, 양자 계산 비용 증가는 공격자만 부담하게 됩니다. 따라서 재키링 (Rekeying) 과 키 크기 확대가 더 효과적인 방어 수단임을 강조했습니다.
   • SSH 의 재키링 메커니즘 활용: SSH 는 세션 중간에 새로운 Diffie-Hellman 교환을 수행하여 양자 공격 비용을 선형적으로 증가시킬 수 있음을 입증했습니다.
   • TLS/QUIC 의 한계: 현재 TLS 1.3 과 QUIC 은 세션 중간에 새로운 난수를 주입하는 '중간 스트림 재키링'이 부재하여, 한 번의 키 교환이 깨지면 전체 세션이 노출되는 구조적 취약점이 있음을 지적했습니다.

4. 주요 결과 (Key Results)

A. 저장 비용의 경제성

• 저장 비용은 낮음: 전 세계 암호화 트래픽의 1% 를 선별적으로 수집하더라도 연간 비용은 약 10 억 달러 (O($10^9$)) 수준으로 추정됩니다. 이는 주요 국가의 국방 예산 범위 내에 있습니다.
• 테이프 아카이브의 효율성: 클라우드 스토리지보다 훨씬 저렴한 기업용 테이프 (LTO-9 등) 를 활용하면, 초기 자본 지출 (CapEx) 이후의 유지 비용은 거의 제로에 가깝습니다. AI 수요로 인한 플래시/하드디스크 가격 상승은 테이프에는 영향을 미치지 않아, 장기 보관에 테이프가 더 유리합니다.
• 결론: 적대자가 트래픽 가로채기 인프라를 갖췄다면, 데이터를 10~15 년간 보관하는 것은 경제적 장벽이 아닙니다.

B. 프로토콜별 취약성 및 공격 범위

• TLS 1.2 (RSA): 서버의 장기 키 하나만 유출되면 과거 모든 세션이 복호화됩니다.
• TLS 1.3 / QUIC: Forward Secrecy(전향적 비밀성) 가 있어 세션별 키가 다르지만, 0-RTT나 PSK(Pre-Shared Key) 재연결을 사용할 경우, 초기 세션의 키 교환이 깨지면 이후 모든 재연결 세션이 연쇄적으로 노출됩니다.
• SSH: 세션 중간에 재키링 (Rekeying) 을 수행하면, 공격자는 각 키 교환 구간마다 별도의 양자 연산을 수행해야 하므로 공격 비용이 급증합니다.

C. 방어 전략의 효과

• 재키링 (Rekeying): SSH 의 경우 64KB 마다 재키링을 수행하면, 공격자가 전체 트래픽을 복호화하기 위해 필요한 양자 연산 횟수가 37 배 증가합니다. 이는 저장 비용 증가 없이 공격자의 가장 희소 자원 (양자 컴퓨팅 시간) 을 고갈시키는 최적의 방어입니다.
• 키 크기 확대: P-256 에서 P-384 로 키 크기를 늘리면 대역폭 오버헤드는 미미하지만, 쇼어 알고리즘의 연산 복잡도가 비선형적으로 증가하여 양자 복호화 시간을 크게 늘립니다.
• ECH (Encrypted Client Hello): SNI(서버 이름 표시) 를 암호화하여 메타데이터 분석을 어렵게 만들지만, IP 주소가 고유한 경우 여전히 표적 수집이 가능하므로 완전한 방어는 아닙니다.
• 레코드 패딩 (Record Padding): 저장 공간을 인위적으로 늘리는 것은 방어자도 대역폭 비용을 지불해야 하므로 비효율적입니다.

5. 의의 및 시사점 (Significance)

1. 경제적 현실 인식: HN-DL 은 "양자 컴퓨터가 언제 나올까?"라는 기술적 질문이 아니라, "데이터를 보관할 수 있는가?"라는 경제적 문제임을 명확히 했습니다. 이미 많은 데이터가 수집되어 있을 가능성이 높습니다.
2. PQC 이전의 대응책: 포스트 양자 암호 (PQC) 로의 전환은 필수적이지만, 이 과정에는 시간이 걸립니다. PQC 전환이 완료되기 전까지, 재키링 (Rekeying) 과 키 크기 확대와 같은 구조적 방어 (Defense-in-Depth) 를 통해 공격자의 비용을 높이는 것이 중요합니다.
3. 프로토콜 개선의 필요성: TLS 1.3 과 QUIC 은 현재 세션 중간에 새로운 난수를 주입하는 메커니즘이 부재합니다. SSH 와 같은 재키링 기능을 TLS/QUIC 에 도입하는 표준화 작업 (Extended Key Update 등) 이 시급히 필요합니다.
4. 데이터 수명주기 관리: 의료 기록, 국가 기밀 등 수명이 긴 데이터는 이미 수집된 상태일 수 있으므로, PQC 전환이 완료될 때까지의 '취약 창 (Vulnerability Window)'을 최소화하기 위해 즉시 이주 (Migration) 가 필요하다는 점을 강조합니다.

요약하자면, 이 논문은 HN-DL 공격이 이론적 위협이 아니라 경제적으로 실행 가능한 현실임을 입증하고, 암호학적 전환 (PQC) 과 병행하여 공격자의 계산 비용을 높이는 구조적 방어 (재키링 등) 의 중요성을 강조했습니다.