⛳

【耐量子計算機暗号・PQC】ML-KEM（CRYSTALS-KYBER）標準について

2024/08/22に公開

Security

CRYSTAL-Kyberは2024/8/11にFIPS 203 ML-KEM (Module-Lattice-Based Key-Encapsulation

Mechanism)としてNIST標準化された。
https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.pdf
特にKyberとの違いに焦点を当てて読んでみる。

ちなみに標準化文書ではshallが必須の要求、shouldが推奨の意味で使われている。

標準化文書のAppendix C にKyberとの違いが書かれているのでそれを読んでみる。

 Key-Encapsulation MechanismAlice側でKeygenを行い公開鍵を公開、Bob側で公開鍵を使ってShared secret K（のシード）を暗号化して送信。Alice側で復号というよくあるKEMである。

Decapsのみ決定的、KeyGenとEncapsは確率的アルゴリズムになる。
Kyberではpublic key, secret keyと呼び方をしていたがそれは廃止された。ML-KEMには
Encapsulation key: ek
Decapsulation key: dk
Encryption key: ek_{PKE}
Decryption key: dk_{PKE}
Shared secret key: K

5種類の鍵があり、ek, dkがこれまでの公開鍵、秘密鍵に対応している。ek, dkの一部が実際に暗号化/復号に使われるek_{PKE}, dk_{PKE}となる。

 パラメータML-KEM-512 (security category 1)
ML-KEM-768 (security category 3)
ML-KEM-1024 (security category 5)

の3つが標準化された。これらはKYBER時代から変わってないはずである。
可能な限り強いパラメータを使うことが推奨されており、NISTをML-KEM-768をデフォルトとして推奨している。

 Requirements for ML-KEM Implementations
 Controlled access to internal functionsサブルーチン的な関数（MK-KEM.KeyGen_internalなど）はテスト目的以外で直接呼び出すべきでない。

乱数生成はcryptographic moduleで行わなければならない。

 Approved usage of the shared secret key256-bit shared secret key Kはそのまま共通鍵の鍵として使ってもよい。

256bit以上の鍵が必要な場合はSP 800-108/800-56Cのような方法でshared secret keyを伸長しなければならない。

 Randomness generation乱数生成はSP 800-90A, SP 800-90B, SP 800-90Cのような承認されたRBGを使わなければならない。

ML-KEM-512/-768/-1024に対してはそれぞれ最低128/192/256ビットセキュリティのRBGを使わなければならない。

 Input checkingEncapsulationとDecapsulationの入力はチェックされなければならない。

しかし、これらのチェックはEncap/Decapパーティで行う必要はなく、毎回行う必要もない。

代わりに、これらのチェックが実行されたことの保証は、他の手段で得ることができる（SP 800-227）。
具体的なチェック内容は以下

Encapsulation input check

Decapsulation input check
ここは正直あんまりわかっていない。このチェックは明示的にEncaps/Decapsアルゴリズムに含まれていないし、各パーティが実行する必要もないらしい。誰がやるんだろう？

 Destruction of intermediate valuesアルゴリズム中間値は攻撃に利用される恐れがあるため、中間値が不要になり次第すぐにすぐに破棄されることを保証しなければならない。

各アルゴリズムの出力のみがメモリに保持され、それ以外のすべてのデータはアルゴリズム終了前に破棄されなければならない。
例外が二つある。

破棄ってどうやるんだろう？

 No floating-point arithmetic浮動小数点演算を使ってはならない。

 KyberとML-KEMの違い。Appendix Cに記載の内容

 Shared secret keyの固定長化KyberではEnc/Decで共有されるshared secret keyをKDF(SHAKE-128)で作っていた。SHAKEはXOFなので可変長出力であり、必要とされる長さのshared secret keyを出力できるように定義されていたが、XOFの利用が禁止され、256ビット固定長になった。
KyberのEncaps関数

ML-KEMのEncaps関数
上のように、shared secret Kはメッセージmと公開鍵ekのハッシュを直接使うようになりシンプルになった。このshared secret は共通鍵暗号の鍵として直接使用してよい。

256bit以上の鍵が必要な場合はSP 800-108/800-56Cのような方法を使うことが要求されている。

 メッセージハッシュの廃止KyberのEncaps関数

ML-KEMのEncaps関数
Kyberではメッセージmを直接使うのではなく、そのハッシュ値をシードとして利用していた。これはmのエントロピーが低い場合を考慮したものだが、ML-KEM標準ではmの生成にNIST標準のRBGを使うことを要求しているため（つまり乱数生成はちゃんと行われている前提であるため）、このステップは廃止された。

 FO変換上二つのEncapの変更に合わせて、Decapも変更された。

KyberのDecaps関数

ML-KEMのDecaps関数

 入力チェックInput checkingに記載の内容

 Domain separation鍵生成のシードにk \in \{2,3,4\}を含めてドメイン分離を行うように。

 細かな違い全て決定的なinternal algorithmが定義された。乱数生成はinternalアルゴリズムの外側で行う。