양자 보안 암호화 보장: corecrypto의 형식 검증을 위한 Apple의 청사진

양자 보안 암호화로의 전환은 단순히 알고리즘을 업데이트하는 문제가 아닙니다. 이는 구현 보증의 문제입니다. 양자 컴퓨팅이 현재 암호화의 기반을 위협함에 따라, 대규모로 양자 내성 알고리즘(PQA)을 배포하기 위해서는 전통적인 소프트웨어 테스트로는 제공할 수 없는 수준의 확실성이 필요합니다. Apple의 생태계 전반에서 25억 개 이상의 활성 기기를 보호하는 corecrypto와 같은 라이브러리의 경우, 단 하나의 산술적 버그도 모든 종속 애플리케이션의 보안을 위협할 수 있습니다.

이를 해결하기 위해, Apple은 ML-KEM (FIPS 203) 및 ML-DSA (FIPS 204) 구현에 대한 포괄적인 형식 검증 청사진을 개발했습니다. 기존의 테스트를 넘어 수학적 정당성 증명을 통해, Apple은 복잡한 암호화 프리미티브의 초기 배포 시 자주 발생하는 미묘한 버그를 제거하는 것을 목표로 합니다.

corecrypto를 위한 높은 기준

corecrypto에 새로운 알고리즘을 추가하는 것은 엄격한 평가 과정을 수반합니다. Apple은 새로운 프리미티브가 보안을 개선하고 안전한 설계를 갖출 뿐만 아니라, 네트워크 지연 시간과 메모리 사용량을 최소화하기 위해 높은 성능과 컴팩트한 파라미터를 유지할 것을 요구합니다.

알고리즘이 선택되면, 구현은 세 가지 핵심 기둥을 충족해야 합니다:

  1. Security: 코드는 정보 유출, 특히 타이밍 사이드 채널에 대해 강화되어야 합니다.
  2. Optimization: 구현은 기반이 되는 실리콘의 효율성을 극대화해야 합니다.
  3. Correctness: 코드는 표준 사양을 충실히 구현하고 매번 정확한 출력을 생성해야 합니다.

전통적 테스트의 한계

시뮬레이션과 독립적 검토를 포함한 전통적인 테스트는 필수적이지만 고보증 암호화에는 불충분합니다. 암호화 서브루틴은 종종 다항식 및 큰 숫자와 같은 큰 피연산자를 가진 복잡한 연산을 포함하며, 이 과정에서 연산 시퀀스 깊은 곳에서 캐리(carry) 또는 빌로우(borrow)가 발생할 수 있습니다.

이러한 "edge case" 버그는 포착하기가 매우 어렵습니다. 커뮤니티에서 언급되었듯이, 일부 버그는 구현에서 단계가 누락락된 것처럼 나타납니다. 주변 코드가 올바르게 보이기 때문에, 이러한 오류는 수동 코드 리뷰를 통과하고 표준 테스트 스위트에서 발생할 가능성이 낮은 매우 드문 입력을 통해서만 트리거됩니다.

맞춤형 형식 검증 파이프라인

기존 도구들이 ARM64 어셈블리를 지원하지 않거나 기존 개발자 툴체인을 포기해야 하는 경우가 많았기 때문에, Apple은 맞춤형 검증 파이프라인을 설계했습니다. 이 접근 방식은 고수준 FIPS 사양과 저수준 최적화된 머신 코드를 연결합니다.

검증 스택

Apple은 신뢰 체인을 구축하기 위해 전문화된 도구들의 조합을 활용합니다:

  • Cryptol & SAW: Apple은 이식 가능한 C 구현을 Cryptol로 수동으로 번역합니다. 그런 다음 Software Analysis Workbench (SAW)를 사용하여 Cryptol 모델이 실제 C 구현과 일치하는지 검증합니다. SAW는 C에 대해 추론하는 데는 뛰어나지만, 전체 FIPS 사양을 설명하는 데 필요한 수학적 표현력이 부족합니다.
  • Isabelle: 이 격차를 메우기 위해, Apple은 Galois가 구축한 맞춤형 번역기를 사용하여 Cryptol 모델을 강력한 증명 보조 도구인 Isabelle로 이동합니다. FIPS 사양 또한 Isabelle로 수동으로 번역됩니다.
  • The Proof Process: Isabelle 내에서, 엔지니어들은 구현 모델과 사양 간의 동등성을 보여주는 수학적 증명을 작성합니다. ML-KEM 및 ML-DSA의 경우, 이는 50,000단계 이상의 증명 단계를 포함했습니다. 이를 확장 가능하게 만들기 위해, Apple은 다양한 서브루틴에 걸쳐 프로세스를 간소화하기 위해 재사용 가능한 Isabelle 라이브러리(lemmas) 세트를 개발했습니다.

ARM64 어셈블리 검증

corecrypto의 가장 도전적인 측면 중 하나는 타이밍 사이드 채널을 방지하고 성능을 максима화하기 위해 직접 작성한 최적화된 ARM64 어셈블리를 사용하는 것입니다. 어셈블리를 고수준 사양에 대해 직접 증명하는 것은 매우 복잡합니다.

대신, Apple은 refinement strategy를 채택합니다: 그들은 각 ARM64 어셈블리 서브루틴이 교체된 해당 C 서브루틴와 일치함을 증명합니다. C 구현이 이미 FIPS 사양과 동등함이 증명되었으므로, 어셈블리의 정확성은 연장선상에서 확립립니다.

실제 사례 및 결과

이러한 형식 검증 방법의 적용은 실질적인적인 보안 개선을을 가져왔습니다. Apple은 초기 ML-DSA 구현에서 입력값이 예상 범위를 초과하여 암호화 계산을 잠지시적으로 손상시킬 수 있는 누락된 단계를 발견했습니다. 또한 특정 파라미터 값에 관한 제3자 증명에서의 오류를 발견하고 수정했습니다.

한계점 인정

Apple은 형식 검증이 만능 해결책은 아니라고 인정합니다. 그들의 현재 접근 방식은 검증된 C 코드를 통해 명령어를 생성할 때 컴파일러의 정확성을 가정합니다. 또한, SAW의 일부 한계로 인해 ML-DSA의 특정 메시지 크기에 대해서는 전통적인 테스트를 통해 검증해야 했습니다.

결론

형식 검증과 전통적인 시뮬레이션 및 테스트를 결합함으로써, Apple은 양자 내성 전환을 위한 고보증 베이스라인을을 구축했습니다. 그들의 형식 검증 라이브러리와 cryptol-to-isabelle 번역기를 공개한 것은 더 넓은 암호화 커뮤니티에 대한 중요한 기여이며, critical security infrastructure의 핵심적인 역할을 수행합니다.

Sources