filippo.io/mlkem768: Goエコシステム向けの耐量子暗号

 (words.filippo.io)
1 ポイント 投稿者 GN⁺ 2024-02-02 | 1件のコメント | WhatsAppで共有
  • 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命令リスクを回避している
  • 性能最適化が第一目標ではないものの、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で別途整理されている

圧縮・展開と定数時間実装

  • 残る主要な実装課題は3つだった
    • 素数 3329 に対するモジュラー算術の実装
    • [0, 3329) の値を [0, 2ᵈ) にマッピングし、元に戻す圧縮・展開関数の実装
    • 定数時間演算の保証
  • モジュラー算術はRSAや楕円曲線の実装経験が蓄積されていたおかげで比較的容易で、小さな素数は実装を単純にした
  • 圧縮と展開が最も難しい部分だった
    • 仕様は分数と丸め規則によって抽象的に定義している
    • 実際の実装では定数時間算術とビット演算で処理する必要がある
  • 参照実装とその多くの移植実装は、コンパイラ最適化とプラットフォームによっては 可変時間のDIV命令になり得る除算を使っていた
  • このパッケージは最初から Barrett reduction を使っていたため影響を受けず、BoringSSLも同じアプローチを採用している

ML-KEM-768だけを対象にした理由

  • 実装はML-KEMの3つのセキュリティレベル -512、-768、-1024 のうち ML-KEM-768 だけを対象にしている
  • Kyberチームは、新しい暗号解読に対してより保守的な安全余裕を持たせるため、-512 より -768 の使用を推奨している
  • -1024 は256ビットセキュリティレベルと同じ理由、すなわち規制準拠と強度合わせ（strength matching）のための選択肢として説明されている
  • 実験中または標準化中のほとんどのプロトコルがML-KEM-768に集まっているため、単一レベルを対象にしてもコストはほとんど増えない
  • 単一対象化は動く部分を減らし、可読性、セキュリティ、性能に有利である
    • たとえば1・4・10・12ビット整数のシリアライズを汎用エンコーダ1つで処理せず、専用のエンコーダ・デコーダに分けている
    • 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でテスト中に再生成した後、ハッシュを期待値と比較する
    • 参照実装の1万件を超えて、100万件のランダムテストのハッシュも作成できる
  • 完了後に追加された複数のテストでも filippo.io/mlkem768 の問題は見つかっておらず、negative vectorが主要実装の欠陥を見つけた報告例は少なくとも1件ある

性能結果

  • 性能はこのパッケージやGo暗号化パッケージの第一目標ではないが、有用といえるだけ十分に速い必要がある
  • 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側で2つの処理が連続して実行される場合に行列を保存すれば約 10%の時間短縮が可能
    • sha3 の読み取り経路でコピーを減らせる可能性がある
    • その後はフィールド実装の最適化が必要になる

ML-KEM実装でKyber v3をサポートする

  • NISTはKyber Round 3提出版にいくつかの小さな変更を加えており、FIPS草案の1.3節に要約されている
  • Kyber v3または「draft00」基準の実験的プロトコルがいくつかあり、主要なデプロイ済みPQ TLS鍵交換もここに含まれる
  • 別パッケージなしで、ML-KEM実装によりKyber v3をサポートできる
  • 変更の1つは、公開鍵の非正規係数エンコーディングという例外ケースに検証を追加したこと
    • 正常な実装はそのような鍵を作らないため、FIPS草案どおり拒否できる
    • この動作はKyber-on-ML-KEM実装を識別可能にするが、それ以外には有害ではない
  • もう1つの変更は、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を2回ハッシュする
    • implicit rejectionの出力は設計上予測不可能で、相互運用の対象ではないため問題にならない

関連記事

1件のコメント

 
GN⁺ 2024-02-02
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 で自動生成するようにしよう、みたいに範囲がどんどん広がってしまうんです :)

  • このアルゴリズムや実装の品質を判断する能力はないが、変数名にUnicodeを使うのはとても気に入っている
    ρ, σ := G[:32], G[32:]
    どういうわけか "rho" や "sigma" を見るよりずっといい

    • 同意しにくい。見た目は格好いいが、実際のコードではあまり見たくない
      まずキーボードでどう入力すればいいのか分からない。そして多くの人は、これらの記号の名前も知らないはず。もちろん、そのコードを見る人たちは知っている可能性が高いだろうが、親切なコードではないと思う
      明確さが肝心で、"rho" や "sigma" はかなり明確。しかも定数 "n" と定数 "η" も一緒にあると、混乱を招くにはうってつけ
    • まったく気に入らない。自分のキーボードにない文字は入力手順が増えて摩擦が大きすぎる。さらに ρ を p と読み間違えて、変なコンパイルエラーに遭遇しそう
      文字にアクセント記号やセディーユを付けるのはどうだろう？ 複雑さが増すだけ。最小公分母に合わせるほうがいい
    • Go は変数名にUnicode の下付き文字を許可しているのか？
      確認してみた言語のうち、Perl、Python、JavaScript は Chrome と Firefox では許可されず、PHP は許可していた

  • これを作った人は、https://github.com/FiloSottile/age も作ったまさにその人
    このツールは本当に気に入っている

    • もっともらしい否認可能性が組み込まれていないのは残念。少なくとも2つのファイルを暗号化し、どの鍵を提供するかに応じて、そのうちの1つを復号できるべき、という意味
      この種のツールの多くにあるセキュリティ上の弱点のように見える。可能な鍵が1つだけなら、ハンマーを持った人がその鍵を白状させることができる。しかし鍵の数が分からなければ、いくつか渡して、実際に保護したいファイルは隠したまま、攻撃者が去ってくれることを期待できる
    • このツールを好きになりたいのだが、典型的な使い方を説明するマニュアルやチュートリアルが不足している。コマンドラインの使い方の話ではなく、鍵をどう管理し配布すべきか、何に注意すべきかを知りたい
      技術の上に乗る社会的なレイヤー全体が、自分には不明瞭。Alice と Bob が登場する例示的なストーリーがあるとよい
    • Age は悪くないが、停滞しているように見える。最後のリリースは2022年で、argon のような、より現代的なパスワードベースの鍵導出関数を使っていない
      秘密情報の保存・共有用に設計されたものを探しているなら、rot を見てもよい: https://github.com/candiddev/rot

  • 仕様: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf 記事内でもリンクされている