pqRPKI: A Practical RPKI Architecture for the Post-Quantum Era

이 논문은 양자 컴퓨팅 시대에 RPKI 의 RSA 기반 취약점을 해결하면서도 대용량 데이터 처리 효율성을 극대화하기 위해, 다중 계층 머클 트리 사다리 (MTL) 와 매니페스트 기반의 새로운 검증 워크플로우를 도입하여 저장소 크기와 유효성 검사 시간을 획기적으로 단축한 실용적인 사후 양자 RPKI 아키텍처인 'pqRPKI'를 제안합니다.

핵심

1. 문제 상황: "거대한 도서관의 재건축"

배경:
현재 인터넷은 'RPKI'라는 시스템을 통해 "이 IP 주소는 이 회사가 사용해도 된다"라고 인증합니다. 마치 도서관에서 책 (IP 주소) 을 누구에게 빌려줄지 (라우터) 인증하는 시스템과 같습니다.

위협:
지금 이 시스템은 'RSA'라는 자물쇠를 사용합니다. 하지만 미래에 등장할 **'양자 컴퓨터'**는 이 자물쇠를 순식간에 뚫어버릴 수 있습니다. 그래서 더 강력한 새로운 자물쇠 (PQ, 양자 내성 암호) 로 바꿔야 합니다.

난제:
문제는 새로운 자물쇠가 너무 크고 무겁다는 것입니다.

• 비유: 기존 자물쇠가 '열쇠' 하나만 있다면, 새로운 자물쇠는 '열쇠 + 두꺼운 설명서 + 안전장비' 덩어리입니다.
• 현실: 인터넷에는 수백만 개의 인증서가 있습니다. 이 모든 것을 무거운 새 자물쇠로 바꾸면, 데이터 양이 3~4 배나 불어나고, 확인하는 데 시간이 너무 오래 걸려 인터넷이 마비될 수 있습니다.

---

2. 해결책: "pqRPKI" (스마트 도서관 관리법)

저자들은 단순히 자물쇠만 바꾸는 게 아니라, 도서관의 관리 방식 자체를 바꿉니다. 이를 pqRPKI라고 부릅니다.

비유 1: "개별 책에 자물쇠를 다는 대신, '목록표'에 자물쇠를 다는 것"

• 기존 방식 (비효율적): 도서관의 책 (인증서) 수백만 권 하나하나에 무거운 새 자물쇠를 다는 것입니다. 책이 무거워지고, 관리자가 모든 책을 확인하는 데 시간이 걸립니다.
• pqRPKI 방식 (효율적): 책 자체는 가볍게 유지합니다. 대신, **책 목록표 (Manifest)**라는 한 장의 종이에 모든 책의 위치와 내용을 요약한 '해시 값'을 적고, 이 목록표 한 장에만 강력한 새 자물쇠를 다는 것입니다.
  • 효과: 책 (데이터) 은 그대로 가볍고, 보안은 목록표 하나로 강력하게 지킬 수 있습니다.

비유 2: "레고 탑 쌓기 (MTL)"

• 기존 방식: 책이 하나 바뀔 때마다, 도서관 전체를 다시 세우고 모든 책에 새 자물쇠를 다시 다는 식입니다.
• pqRPKI 방식 (MTL - 메르클 트리 사다리):
  • 책을 작은 그룹 (사다리의 한 칸) 으로 묶습니다.
  • 책이 하나 바뀌면, 그 그룹의 '그룹장'만 다시 확인하고, 그 그룹장만 상위 '총괄장'에게 보고합니다.
  • 핵심: **목록표 (Manifest)**를 '0 단계'의 특별한 칸으로 만들어, 자주 바뀌는 정보 (책 목록, 취소된 책) 만 이 칸에 모으고, 나머지 책들은 그대로 둡니다.
  • 결과: 책이 하나 바뀔 때, 전체를 다시 세울 필요 없이 바뀐 부분만 빠르게 수정할 수 있습니다.

---

3. pqRPKI 의 놀라운 성과

이 방식을 적용한 실험 결과, 다음과 같은 놀라운 변화가 일어났습니다.

1. 데이터 크기 줄이기:

   • 무거운 새 자물쇠를 모든 책에 다는 방식 (기존 방식) 이라면 데이터가 3 배 이상 불어납니다.
   • 하지만 pqRPKI 는 기존 데이터 크기와 거의 비슷하게 유지하면서 (오히려 30~60% 줄이기도 함) 보안을 강화했습니다.
   • 비유: 무거운 안전장비를 입지 않고도, 문 하나만 튼튼하게 잠가서 건물을 안전하게 지킨 것과 같습니다.

2. 속도 향상 (2 분 이내):

   • 기존에는 모든 책을 확인하는 데 20~40 분이 걸렸습니다.
   • pqRPKI 는 2 분도 안 걸려 전 세계 모든 인증서를 다시 확인하고 업데이트할 수 있습니다.
   • 비유: 도서관 사서가 매일 아침 모든 책을 다시 세는 대신, 목록표만 확인하고 즉시 새로운 책을 배치할 수 있게 된 것입니다.

3. 이중 운영 (Dual-Stack) 가능:

   • 새로운 시스템으로 완전히 바꾸기 전, 기존 시스템 (RSA) 과 새 시스템 (PQ) 을 동시에 쓸 수 있습니다.
   • 비유: 새 문 (양자 자물쇠) 을 설치하더라도, 기존 문 (구형 자물쇠) 도 열어두어 방문객이 혼란을 느끼지 않게 합니다. 데이터 양은 거의 늘지 않습니다.

---

4. 요약: 왜 이것이 중요한가요?

이 논문은 **"양자 컴퓨터가 오더라도 인터넷이 붕괴되지 않도록, 단순히 자물쇠만 바꾸지 말고 '관리 시스템'을 똑똑하게 고쳐야 한다"**는 것을 보여줍니다.

• 기존 방식: "무거운 자물쇠를 모두에 다세요." → 데이터 폭증, 속도 저하.
• pqRPKI: "책은 가볍게 두고, '목록표' 하나만 강력하게 잠가세요." → 데이터는 가볍고, 속도는 빠르고, 보안은 강력함.

이 기술이 실제 적용되면, 우리는 양자 컴퓨터 시대에 들어와도 인터넷의 길 찾기 시스템이 더 빠르고 안전하게 작동할 수 있게 됩니다. 마치 도서관이 더 커졌는데도, 사서가 더 빠르게 책을 찾아주는 것과 같은 효과입니다.

기술 요약

1. 문제 정의 (Problem)

• 양자 위협: 현재 RPKI 는 RSA-2048 을 기반으로 하는데, 이는 대규모 양자 컴퓨터에 의해 쉽게 해독될 수 있습니다.
• 단순 교체의 비효율성: NIST 표준의 양자 내성 서명 알고리즘 (예: Falcon, ML-DSA) 을 단순히 RSA 로 교체하는 것은 RPKI 의 대량 처리 모델에 적합하지 않습니다.
  • 용량 폭증: PQ 서명과 공개키는 기존 RSA 보다 훨씬 큽니다 (Falcon 은 약 3 배). RPKI 저장소에는 수만 개의 객체 (ROA, 인증서 등) 가 포함되어 있어, 모든 객체에 PQ 서명을 적용하면 저장소 크기와 대역폭이 급격히 증가합니다.
  • 검증 비용: 모든 의존자 (RP, Relying Party) 가 주기적으로 전 세계 저장소를 다운로드하고 검증해야 하므로, CPU 및 네트워크 부하가 가중됩니다.
  • 이중 스택 (Dual-stack) 전환의 어려움: 양자 내성으로의 전환은 장기간의 이중 스택 (RSA + PQ) 운영을 필요로 하는데, 이는 저장소 크기와 동기화 오버헤드를 더욱 악화시킵니다.
• 기존 Merkle 트리 설계의 부적합성: DNSSEC 등에 적용된 Merkle 트리 방식은 RPKI 에 직접 적용하기 어렵습니다. 각 객체에 인증 경로 (authentication path) 를 포함하면 객체 크기가 불필요하게 커지고, 빈번한 메타데이터 (Manifest) 갱신으로 인해 전체 트리를 다시 서명해야 하는 '재서명 폭풍 (re-sign storm)'이 발생할 수 있습니다.

2. 방법론 (Methodology)

pqRPKI 는 RPKI 의 고유한 특성 (전체 저장소 주기적 다운로드, Manifest/CRL 의 빈번한 갱신) 을 활용하여 다음과 같은 구조적 설계를 도입합니다.

A. 다중 계층 Merkle Tree Ladder (MTL) 와 Manifest 통합

• 검증 자료의 이동: 기존 방식처럼 각 객체 (인증서 등) 에 Merkle 인증 경로를 포함하는 대신, **Manifest(파일 목록 및 해시)**로 검증 자료 (리프 인덱스 및 인증 경로) 를 이동시켰습니다.
  • 이로 인해 개별 객체의 크기는 유지되며, 인증 메타데이터는 중앙 집중화된 Manifest 에만 저장됩니다.
• Depth-0 Rung 모델링: Manifest 와 CRL(인증서 폐기 목록) 을 빈번하게 갱신되는 'Depth-0 rung(단일 리프)'로 모델링하여, 메타데이터 변경이 객체 트리의 루트나 다른 객체들에 영향을 미치지 않도록 격리했습니다.
• 상위 - 하위 계층 집계: RIR(지역 인터넷 등록 기관) 에서 하위 CA(국가 인터넷 등록 기관 등) 의 MTL 루트를 집계하여 상위 계층에서 단일 PQ 서명으로 보호하는 계층적 구조를 유지합니다.

B. ladder-guided 동기화 및 대량 검증 워크플로우

• 상향식 (Bottom-up) 검증: RP 는 Manifest 를 먼저 확인하여 변경된 객체만 식별한 후, 변경된 리프 노드부터 시작하여 트리를 재구성 (bottom-up) 합니다. 공유된 내부 노드를 한 번만 해싱하여 중복 계산을 제거합니다.
• 차이점 국소화 (Diff Localization): 인증된 Manifest 를 통해 변경된 파일만 다운로드하고, 삭제된 파일은 'D(Deleted)' 플래그로, 비공개 객체는 'H(Hidden)' 플래그로 표시하여 인덱스 재구성을 방지합니다.

C. 하위 호환성 및 점진적 전환

• 기존 ROA 객체 형식과 인코딩을 변경하지 않습니다.
• Manifest 를 확장 (additive extension) 하여 기존 RSA 검증기와 새로운 pqRPKI 검증기가 동시에 작동할 수 있도록 하여, 점진적인 전환 (Dual-stack) 을 지원합니다.

3. 주요 기여 (Key Contributions)

1. RPKI 전용 양자 내성 인증 아키텍처: MTL 을 RPKI 저장소 구조에 맞게 재설계하여 객체 크기를 작게 유지하면서도 양자 내성을 제공합니다.
2. Manifest 기반 동기화 및 대량 검증 워크플로우: 인증된 Manifest 를 통해 변경 사항을 국소화하고, 하향식 동기화와 상향식 검증을 결합하여 대역폭과 CPU 비용을 절감합니다.
3. 운영 호환성 및 실용적인 전환 경로: 기존 ROA 객체를 변경하지 않고, RSA 와 PQ 를 동시에 지원하는 이중 스택 배포를 가능하게 하여 점진적인 도입을 용이하게 합니다.
4. 실제 프로토타입 및 평가: 실제 RPKI 저장소 데이터를 기반으로 한 구현 및 평가를 통해 성능 향상을 입증했습니다.

4. 실험 결과 (Results)

연구진은 7 일간의 실제 RPKI 저장소 데이터를 기반으로 pqRPKI 를 평가했습니다.

• 저장소 크기 감소:
  • PQ 전용 모드: 평균 저장소 크기가 546.8 MB로 축소되었습니다. 이는 단순한 Falcon 적용 (1,582.7 MB) 대비 65.5%, ML-DSA 적용 (3,241.6 MB) 대비 83.1% 감소한 수치입니다.
  • 이중 스택 모드: 기존 RSA 기반 RPKI 대비 오직 3.4% (약 29.2 MB) 의 추가 오버헤드만 발생했습니다. 이는 기존 해시 값을 리프 커밋먼트로 재사용하여 데이터 중복을 피했기 때문입니다.
• 검증 및 동기화 속도 향상:
  • 전체 검증 시간: 한 사이클의 전체 저장소 검증 시간이 102.7 초로 단축되었습니다 (기존 RSA 대비 51.8% 빨라짐, ML-DSA 대비 약 4 배 빠름).
  • 종단간 전파 시간 (PP to Router): ROA 발행/폐기부터 라우터 적용까지의 시간이 118.3 초로 감소하여, 기존 20~40 분 주기에서 2 분 미만의 운영 주기가 가능해졌습니다.
  • 동기화 지연: 콜드 동기화 (Cold sync) 시 기존 RSA 대비 46.5% 빨라졌고, ML-DSA 대비 76.2% 빨라졌습니다.
• 운영 민첩성:
  • 분당 업데이트 처리 시간은 평균 112.3 ms로, 기존 RSA 시스템보다 3.7 배 빠릅니다.
  • 삭제된 객체에 대한 인덱스 재구성을 방지하기 위해 'D' 플래그를 사용하는 방식은 일시적인 저장소 증가 (약 2%) 를 허용하지만, 서명 및 검증 성능을 크게 향상시킵니다.

5. 의의 및 결론 (Significance)

pqRPKI 는 양자 컴퓨팅 시대에 RPKI 가 직면한 보안 위협과 운영 확장성之间的矛盾 (Trade-off) 를 해결하는 획기적인 솔루션입니다.

• 구조적 최적화: 단순히 암호 알고리즘을 교체하는 것을 넘어, RPKI 의 데이터 흐름과 검증 모델을 재설계하여 양자 내성 서명의 큰 오버헤드를 효과적으로 상쇄했습니다.
• 실용성: 기존 인프라를 크게 변경하지 않고도 점진적으로 도입할 수 있으며, 이중 스택 전환 기간 동안에도 저장소 크기와 대역폭을 현실적으로 유지합니다.
• 실시간 보안 강화: 검증 및 동기화 속도의 비약적 향상은 RPKI 를 '실시간' 방어 메커니즘으로 전환시켜, 라우팅 해킹 (Prefix Hijacking) 에 대한 대응 시간을 획기적으로 단축시킵니다.

결론적으로, pqRPKI 는 양자 내성 암호화를 대규모 인터넷 인프라에 적용할 수 있는 실용적이고 확장 가능한 청사진을 제공하며, 향후 RPKI 의 표준 아키텍처로 자리 잡을 가능성이 높습니다.