filippo.io/mlkem768: Go 생태계를 위한 양자 내성 암호화

 (words.filippo.io)
1P by GN⁺ | ★ favorite | 댓글 1개
  • filippo.io/mlkem768은 NIST 표준화가 진행 중인 ML-KEM-768을 순수 Go로 구현해, Go 생태계에서 양자 내성 키 교환을 검토할 수 있게 함
  • 약 500줄 코드, 200줄 주석, 650줄 테스트로 구성되며 golang.org/x/crypto/sha3 외 의존성이 없어 Go 표준 라이브러리 내부 패키지로 올리기 쉬운 형태임
  • pq-crystals 참조 구현을 포팅하지 않고 FIPS 203 명세를 직접 따라 작성해, 명세만으로 상호운용 구현이 가능한지 검증함
  • 가장 까다로운 영역은 압축·해제와 상수 시간 연산이며, Barrett reduction을 사용해 참조 구현 계열에서 생길 수 있던 가변 시간 DIV 명령 위험을 피함
  • 성능 최적화가 1차 목표는 아니지만 Bob 경로는 Go의 X25519·P-256과 비슷하고 Alice 경로도 2배 미만 수준이라, 단순한 구현으로도 실사용 가능한 속도를 보임

ML-KEM-768 순수 Go 구현

  • filippo.io/mlkem768은 ML-KEM-768의 순수 Go 구현이며, 정확성과 가독성을 우선함
  • ML-KEM은 이전에 Kyber로 알려졌고, NIST 표준화 과정에 있는 양자 내성 키 교환 메커니즘임
  • 패키지는 약 500줄 코드, 200줄 주석, 650줄 테스트로 구성됨
  • 의존성은 golang.org/x/crypto/sha3뿐임
  • Go 표준 라이브러리에 upstream하는 것이 목표이며, 초기에는 opt-in crypto/tls 실험에서 쓰이는 내부 전용 패키지로 계획됨

FIPS 203을 그대로 따라간 구현 방식

  • 이 구현은 pq-crystals 참조 라이브러리를 포팅하지 않고, 다른 코드베이스를 자세히 읽지 않은 상태에서 처음부터 작성됨
  • 핵심 목표는 명세만으로 상호운용 가능한 구현을 만들 수 있는지 확인하는 것이었음
  • FIPS 203 문서는 상세한 의사코드, 완전한 정의, 일관된 타입 정보를 제공해 구현 가이드로 적합했음
  • 함수명, 변수명, 연산 순서는 리뷰와 학습을 쉽게 하기 위해 FIPS 명세를 최대한 반영함
  • ML-KEM 구현에 필요한 수학 배경은 Enough Polynomials and Linear Algebra to Implement Kyber에서 별도로 정리됨

압축·해제와 상수 시간 구현

  • 남은 핵심 구현 과제는 세 가지였음
    • 소수 3329에 대한 모듈러 산술 구현
    • [0, 3329) 값을 [0, 2ᵈ)로 매핑하고 되돌리는 압축·해제 함수 구현
    • 상수 시간 연산 보장
  • 모듈러 산술은 RSA와 타원곡선 구현 경험이 축적된 덕분에 비교적 쉬웠고, 작은 소수는 구현을 단순하게 만들었음
  • 압축과 해제가 가장 어려운 부분이었음
    • 명세는 분수와 반올림 규칙으로 추상적으로 정의함
    • 실제 구현은 상수 시간 산술과 비트 연산으로 처리해야 함
  • 참조 구현과 그 포팅 구현 다수는 컴파일러 최적화와 플랫폼에 따라 가변 시간 DIV 명령이 될 수 있는 나눗셈을 사용했음
  • 이 패키지는 처음부터 Barrett reduction을 사용해 영향을 받지 않았고, BoringSSL도 같은 접근을 사용함

ML-KEM-768만 대상으로 삼은 이유

  • 구현은 ML-KEM의 세 보안 수준 -512, -768, -1024 중 ML-KEM-768만 대상으로 함
  • Kyber 팀은 새로운 암호해석에 대한 더 보수적인 보안 여유를 위해 -512보다 -768 사용을 권장함
  • -1024는 256비트 보안 수준과 같은 이유, 즉 규정 준수와 강도 맞춤(strength matching)을 위한 선택지로 설명됨
  • 실험 또는 표준화 중인 대부분의 프로토콜이 ML-KEM-768에 모였기 때문에 단일 수준 대상화가 비용을 거의 늘리지 않음
  • 단일 대상화는 움직이는 부분을 줄여 가독성, 보안, 성능에 유리함
    • 예를 들어 1·4·10·12비트 정수 직렬화를 범용 인코더 하나로 처리하지 않고 전용 인코더·디코더로 나눔
    • ML-KEM-768만 대상으로 했기 때문에 5비트와 11비트 인코딩을 구현할 필요가 없었음

테스트 전략과 공개 테스트 벡터

  • 테스트는 이 패키지의 보안 보증 전략에서 가독성 다음으로 중요한 축임
  • 기본 테스트는 키 생성, 캡슐화, 디캡슐화 라운드트립과 95% 이상 테스트 커버리지를 포함함
  • 추가 테스트 범위는 다음을 포함함
    • NIST 및 다른 구현에서 얻은 테스트 벡터와의 상호운용성 확인
    • 3329 모듈러 덧셈·뺄셈·곱셈의 모든 입력 조합을 변수 시간 방식으로 계산한 기대값과 비교
    • 압축·해제를 math/big.Rat 기준으로 전수 테스트
    • 사전 계산 상수가 정의와 일치하는지 확인
    • 모든 함수 입력에서 길이가 너무 길거나 짧을 때 적절한 오류가 나는지 확인
    • Sophie Schmieg가 제공했고 향후 Wycheproof에 포함될 테스트 벡터 실행
  • 자체 테스트 벡터는 다른 구현에서도 재사용할 수 있도록 CCTV 프로젝트의 일부로 공개됨
  • CCTV 벡터는 각 중간 단계와 부분 알고리듬을 테스트·디버깅할 수 있는 중간값을 포함함

특수 테스트 벡터가 잡아내는 오류

  • Negative test vectors는 계수가 3329보다 큰 잘못된 캡슐화 키를 제공함
    • Kyber와 NIST 팀의 벡터는 정상 입력 중심이어서 이런 벡터가 자주 요청됨
    • 3329부터 2¹²-1까지의 모든 값과 모든 계수 위치를 개별 테스트함
    • 나머지 계수를 공유해 1–3MiB 데이터를 12–28KiB로 압축함
  • “Unlucky” vectors는 XOF 읽기가 비정상적으로 많이 필요한 경우를 테스트함
    • SampleNTT에서 SHAKE-128 XOF로부터 575바이트 이상 읽어야 하는 공개 키이며, 일반적으로는 확률 2⁻³⁸로 발생함
    • Sophie의 벡터는 더 브루트포스되어 최대 591바이트가 필요함
  • strcmp vectors는 ML-KEM.Decaps에서 strcmp()를 쓰는 구현을 실패하게 만듦
    • 디캡슐화에서 ciphertext와 K-PKE.Encrypt 출력을 비교할 때 0바이트가 있으면 strcmp()가 비교를 조기 종료할 수 있음
  • Accumulated vectors는 참조 pq-crystals 구현에서 파생됨
    • 300MB 랜덤 벡터 출력을 저장하지 않고, 결정적 RNG로 테스트 중 재생성한 뒤 해시를 기대값과 비교함
    • 참조 구현의 10k개를 넘어 100만 개 랜덤 테스트 해시도 만들 수 있음
  • 완료 후 추가된 여러 테스트에서도 filippo.io/mlkem768 문제는 발견되지 않았고, negative vector가 주요 구현의 결함을 찾은 보고 사례는 최소 1건 있음

성능 결과

  • 성능은 이 패키지나 Go 암호화 패키지의 1차 목표가 아니지만, 유용할 만큼 충분히 빨라야 함
  • ML-KEM은 충분히 빠르며, 이 단순 구현도 어셈블리 최적화된 Go의 P-256 및 X25519 구현과 경쟁 가능한 수준임
  • 비교는 키 설정에서 각 측이 수행해야 하는 전체 작업을 기준으로 해야 함
    • ECDH는 고정 베이스포인트 1회를 포함해 스칼라 곱셈 2회를 수행함
    • KEM은 한쪽에서 키 생성과 디캡슐화를, 다른 쪽에서 캡슐화를 수행함
    • ECDH는 대칭적이지만 ML-KEM 키 설정은 비대칭적임
  • 벤치마크에서 “Alice”는 키 생성과 디캡슐화를 수행하고, “Bob”은 캡슐화를 수행함
    • 디캡슐화에는 입력 ciphertext와 결과가 맞는지 확인하기 위한 전체 암호화가 포함됨
    • Alice는 암호화, 복호화, 키 생성을 수행해 Bob보다 오래 걸림
  • 결과적으로 Bob은 X25519 또는 P-256만큼 빠르고, Alice는 그 2배 미만임
  • BoringSSL과 libcrux 같은 빠른 ML-KEM 구현과 비교하면 이 패키지는 대략 2배 시간이 걸림

벤치마크 수치와 최적화 여지

  • 측정 수치는 다음과 같음
    • macOS arm64에서 ECDH/P256-8은 49.43µs, ECDH/X25519-8은 77.46µs
    • 같은 환경에서 RoundTrip/Alice-8은 109.4µs, RoundTrip/Bob-8은 56.19µs
    • Linux amd64에서 ECDH/P256-4는 78.88µs, ECDH/X25519-4는 115.6µs
    • 같은 환경에서 RoundTrip/Alice-4는 223.8µs, RoundTrip/Bob-4는 114.7µs
  • 구현은 힙 할당을 줄이는 등 고성능 Go 패턴을 따름
  • x/crypto/sha3를 힙 할당 없이 사용할 수 있도록 재작업했지만, Apple M2에서 부정적 효과가 있어 아직 병합하지 않았고 위 벤치마크에도 포함되지 않음
  • 남은 최적화 여지는 명확함
    • 키 생성과 디캡슐화가 같은 값에서 행렬을 샘플링하므로, Alice 측에서 두 작업이 연속 수행될 때 행렬을 저장하면 약 10% 시간 절약 가능
    • sha3 읽기 경로에서 복사를 줄일 가능성이 있음
    • 이후에는 필드 구현 최적화가 필요함

ML-KEM 구현으로 Kyber v3 지원하기

  • NIST는 Kyber Round 3 제출본에 몇 가지 작은 변경을 했고, FIPS 초안 1.3절에 요약됨
  • Kyber v3 또는 “draft00” 기준 실험 프로토콜이 몇 가지 있으며, 주요 배포 PQ TLS 키 교환도 여기에 포함됨
  • 별도 패키지 없이 ML-KEM 구현으로 Kyber v3를 지원할 수 있음
  • 변경 중 하나는 공개 키의 비정규 계수 인코딩이라는 예외 사례에 검증을 추가함
    • 정상 구현은 그런 키를 만들지 않으므로 FIPS 초안대로 거부할 수 있음
    • 이 동작은 Kyber-on-ML-KEM 구현을 식별 가능하게 만들지만, 그 외에는 해롭지 않음
  • 다른 변경은 CSPRNG 입력에 적용되던 해싱 단계를 제거한 것임
    • 입력 바이트가 랜덤이므로 어떤 당사자도 차이를 구분할 수 없음
  • 가장 큰 변경은 공유 비밀에 ciphertext를 해시하던 동작임
    • 이 차이는 상호운용을 막을 수 있음
    • ML-KEM으로 공유 비밀 K를 만든 뒤 SHAKE-256(K || SHA3-256(c))[:32]를 적용하면 Kyber 공유 비밀을 만들 수 있음
    • ML-KEM 추상화를 깨지 않아도 됨
  • Kyber와 ML-KEM은 모두 디캡슐화에서 implicit rejection을 위해 비밀과 ciphertext를 해시함
    • ML-KEM 위에 위 키 파생을 적용하면 implicit rejection에서 ciphertext를 두 번 해시함
    • implicit rejection 출력은 설계상 예측 불가능하고 상호운용 대상이 아니므로 문제가 되지 않음

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • Kudelski Security에서 인사드림. 최근 Go용 양자 내성 암호 라이브러리 중 거의 유일하게 존재하던 다른 하나를 중단해야 했기 때문에 아주 시의적절함
    전체 이야기는 https://research.kudelskisecurity.com/2024/02/01/the-kybersl...에 있음

    • Kyber-512는 NIST의 NSA 측 멤버들이 의도적으로 약화한 것 아니었나?

  • 이런 것이 필요해질 만큼 양자 컴퓨팅이 실제로 어느 수준까지 와 있는지 궁금함
    AI처럼 실제로 뭔가가 등장했다기보다, 기존 이름 아래 새 제품을 내놓기 위해 정의만 바뀌는 상황이 된 건가?

    • 암호학은 양자 컴퓨터 위협을 다루는 방식이 특이함. 오늘 암호화된 데이터와 연결 중 일부가 30년, 50년 뒤에도 복호화 가능해지면 안 되기 때문임
      그래서 질문은 “양자 컴퓨터가 곧 오나”가 아니라 “향후 반세기 안에 양자 컴퓨터가 그럴듯하게 등장할 수 있나”가 됨. 정밀한 합의는 없지만 답이 “아니다”는 아니므로 지금 이런 흐름이 생김
      그래서 서명보다 PQC 키 교환 쪽에서 진전이 더 많이 보임. 오늘의 서명 검증은 50년 뒤 양자 컴퓨터의 영향을 받지 않지만, 암호화는 영향을 받음
    • 지금의 양자 컴퓨터를 막자는 이야기가 아님
      공격자가 오늘의 암호문을 저장해 두었다가 미래에 복호화할 수 있다는 게 위험임. 양자 안전 암호로 빨리 전환할수록, 미래 공격에 취약한 “밀린 암호문”을 덜 남기게 됨
    • 만약 답이 “NSA가 이미 프로덕션에서 양자 암호분석을 돌리고 있고 ECDH는 완전히 깨진 것으로 봐야 한다”라면, 그걸 아는 사람이 말해 주는 순간 엄청난 곤란에 처할 것임
      실제로 그럴 가능성은 낮아 보이지만, 이 질문은 어느 정도 답하기 어려움. 현재로서는 알려진 위협은 아니지만, 그 잠재성에 대해 얼마나 편집증적으로 볼지는 주관적임
    • 최근 2년쯤 사이에 NIST가 몇 가지 양자 후 암호 알고리즘을 정했고, 이후 구현도 점점 늘고 있음. 양자 컴퓨팅은 아직 멀었지만 “지금 시작해서 나쁠 게 있나?”라는 태도로 보임
      확실히는 모르지만, 타원곡선 암호도 대중적으로 쓰이기 훨씬 전에 구현은 꽤 되어 있었을 것 같음. 그 당시를 겪은 사람이 틀렸다면 바로잡아 줬으면 함
    • 양자 컴퓨터가 RSA-2048을 깨려면 현재 물리 큐비트의 품질은 대략 10배, 수량은 1만 배 늘어야 함. 아주 거친 숫자임
      다음으로 지켜볼 주요 이정표는 구성하는 물리 큐비트보다 충실도가 1000배 나은 논리 큐비트임. 그게 나오면 물리 큐비트 품질은 충분하고 이제 수량 확장만 시작하면 된다는 신호가 됨

  • 관련 논의에 John Arundel의 최신 Go 버전 기반 암호 시스템 구현 입문서가 도움이 될 수 있음. 마지막 섹션에 양자 후 암호가 잠깐 나오며, NIST PQ가 표준화되면 나중에 John이 이 라이브러리를 넣어 책을 업데이트할 수도 있겠음
    Explore Go: Cryptography (Go 1.22 edition):
    https://bitfieldconsulting.com/books/crypto

  • 틀렸다면 정정 부탁하지만, 순수 Go로 작성됐다면 타이밍/전력 부채널 공격에 취약해지는 것 아닌가?

    • Go는 C보다 더 취약하다고 보기 어렵고, 오히려 덜할 수도 있음. 차이는 Go에는 주요 컴파일러가 하나이고 보통 최적화를 과하게 하지 않는 반면, C에서는 컴파일러가 의도를 알아채고 더 효율적인 가변 시간 분기로 바꾸지 못하게 점점 복잡한 요령을 써야 한다는 데 있음
      이 구현은 비밀값에 따라 달라지는 코드 경로를 피하도록 작성됐음. 물리적 접근이 필요한 전력 부채널은 Go의 위협 모델 밖임
    • “모든 핵심 연산은 상수 시간으로 수행된다”고 되어 있음
      프로젝트 문서까지 링크를 따라가 봤어야 했는데, 이 부분을 고려하고 있는 것 같음
    • 전력 부채널 공격에 면역인 언어가 있나? 그 발상 자체가 말이 안 되는 것 같음
      타이밍 공격에 관해서도, Go가 다른 언어보다 타이밍 부채널에 더 취약해지는 이유가 무엇인지 모르겠음

  • Java, C# 같은 다른 언어용 구현체를 아는 사람이 있나?

  • draft00/kyber v3로도 동작할 수 있다는 점이 멋짐
    SHA-3 없이 빠른 Kyber 90’s 모드를 지원하려면 얼마나 어려울까? 아마 그 경우에는 추상화를 깨야 할 것 같음

    • 해시를 바꾸려면 포크가 필요함. 이 구현은 CPU 시간의 약 20%만 SHA-3에 쓰이므로 이득이 크지는 않음
      필드 구현을 최적화하면 그 비율은 올라가겠지만, 표준화되지 않고 테스트도 덜 된 모드를 쓸 만할 정도는 거의 아닐 것임

  • 관련은 없지만 Filo, 32비트 시스템 콜 테이블은 아직도 ‘coming soon’이잖아 :')

    • 하하, 인정. 그 페이지를 손보려고 생각할 때마다 커널 소스에서 CI로 자동 생성하게 만들자는 식으로 범위가 계속 커져서 그래 :)

  • 이 알고리즘이나 구현의 품질을 판단할 능력은 없지만, 변수명에 유니코드를 쓰는 건 아주 마음에 듦
    ρ, σ := G[:32], G[32:]
    어쩐지 "rho", "sigma"를 보는 것보다 훨씬 낫다

    • 동의하기 어려움. 보기에는 멋지지만 실제 코드에서는 별로 보고 싶지 않음
      우선 키보드로 어떻게 입력해야 할지 모르겠음. 그리고 대부분은 이 기호들의 이름도 모를 것임. 물론 그 코드를 보는 사람들은 알 가능성이 더 높겠지만, 친절한 코드는 아니라고 봄
      명확성이 핵심이고 "rho"나 "sigma"는 꽤 명확함. 게다가 상수 "n"과 상수 "η"도 같이 있으면 혼동을 부르기 딱 좋음
    • 전혀 마음에 들지 않음. 내 키보드에 없는 문자는 입력 단계가 추가되어 마찰이 너무 큼. 또 ρ를 p로 잘못 읽어서 이상한 컴파일 오류를 만나게 될 것 같음
      문자에 악상 부호나 세디유를 붙이는 건 어떨까? 복잡성만 늘어남. 최소 공통분모에 맞추는 편이 좋음
    • Go가 변수명에 유니코드 아래첨자를 허용하나?
      확인해 본 언어 중 Perl, Python, JavaScript는 Chrome과 Firefox에서 허용하지 않았고, PHP는 허용했음

  • 이걸 만든 사람이 https://github.com/FiloSottile/age도 만든 바로 그 사람임
    이 도구가 정말 마음에 듦

    • 그럴듯한 부인 가능성이 내장되어 있지 않은 건 아쉬움. 최소 두 파일을 암호화하고, 어떤 키를 제공하느냐에 따라 그중 하나를 복호화할 수 있어야 한다는 뜻임
      이런 종류 도구 대부분의 보안상 약점처럼 보임. 가능한 키가 하나뿐이면 망치를 든 사람이 그 키를 털어놓게 만들 수 있음. 하지만 키 개수를 알 수 없다면 몇 개를 내주고 실제 보호 파일은 숨긴 채 공격자가 떠나길 바랄 수 있음
    • 이 도구를 좋아하고 싶은데, 전형적인 사용법을 설명하는 매뉴얼이나 튜토리얼이 부족함. 명령줄 사용법을 말하는 게 아니라, 키를 어떻게 관리하고 배포해야 하는지, 무엇을 조심해야 하는지를 알고 싶음
      기술 위에 얹히는 사회적 계층 전체가 나에게는 불명확함. Alice와 Bob이 등장하는 예시 이야기가 있으면 좋겠음
    • Age는 괜찮지만 정체된 것 같음. 마지막 릴리스가 2022년이고, argon 같은 더 현대적인 비밀번호 기반 키 도출 함수를 쓰지 않음
      비밀 저장/공유용으로 설계된 걸 찾는다면 rot를 봐도 좋음: https://github.com/candiddev/rot

  • 명세: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf 기사에서도 링크되어 있음

답변달기