Zenn
🐈

Kyberのimplicit rejectionについて

に公開
Security
耐量子計算機暗号
pqc
kyber
tech

Kyber (ML-KEM)では、Decryption Failureが発生した際に暗黙的に出力をrejectする。
要は出力がrejectされたかどうか、つまりDecapsulation failureが発生したかどうかまで隠す？
実装的な観点ではimplicit rejectionがあったかどうかは簡単にわかると思うので、実装すべきかどうか、もしくはセキュア実装するべきかよく理解できていない。
結局Kyberはimplicit rejectionのまま標準化されたのでNIST的にはそこもちゃんと実装しろということなんだと思う。

同じ議論が2022年にNISTメーリスでされていたのでまとめる。

NXPの問題提起

NXPのTobiasさん（業界では普通によく見かけるというか、有名な人）が次の内容を投稿している。
要はimplicit rejection用のzは秘密なんか？保護いるんか？ということ。
学術的にはzは保護しないことが多く、その場合（少なくとも実用上は）explicitでいいんじゃないか？と提案

Hi PQC mailing list,
We have been studying the implicit rejection and have some observations regarding the role of the long-term secret value ‘z’ in Kyber.
In Kyber.CCAKEM.Dec, ‘z’ is used to implement implicit rejection as

if c = c’ then
return K := KFD(\bar{K}’ || H(c) )
else
return K := KDF( z || H(c) )

We look at this from a high-assurance implementation (i.e., side-channel protected) point of view.
If ‘z’ requires the same level of protection against physical attacks as the secret key ‘s’ then this results in significant costs in storage (storing shares of the masked ‘z’). Moreover, the branch K := KDF( z || H(c) ) needs an DPA-protected KDF (assuming ‘z’ is secret) which is not necessarily the case for the K := KFD(\bar{K}’ || H(c) ) branch.

Academic works have commonly left this part unprotected in masked implementations of Kyber / Saber (cf. [1-4]), which removes the unpredictability property of the rejection mechanism (‘z’ is assumed to be leaked in full).
Therefore, for high-assurance implementations a switch to an explicit rejection mechanism would be preferable and improve the efficiency.

If implicit rejection is a design goal which is desirable (but is it really?) we suggest one of the following.
What about optionally randomizing ‘z’?
This could be achieved by using K := KDF( (z xor R) || H(c) ) where ‘R’ denotes an optionally true random element.
For ‘R==0’ it implements the current solution as specified in the specification while for ‘R==random’ it randomizes the input to the KDF, which removes the strict DPA-protection requirement and makes high assurance implementations much simpler.

What do you (= the Kyber team, NIST and the entire PQC community) think about such a change to the rejection?
Any obvious downsides we overlooked?

Best regards
NXP PQC Team

[1] https://eprint.iacr.org/2020/733.pdf
[2] https://eprint.iacr.org/2021/483.pdf
[3] https://eprint.iacr.org/2022/158.pdf
[4] https://eprint.iacr.org/2022/389.pdf

Implicit rejection必要だよ派

Danien J. Bernstein

特にDJBが強くimplicit rejectionをsecure実装することを求めており、他の人は実用上はexplicitでもいいんじゃね？という図式のように見える。

以下DJBの意見

  • implicit rejectionはfragileなので安易にいじるべきじゃない。鍵と同じレベルでzも保護すべき
  • zの漏洩（改竄？）によるCCA2セキュリティが破られている論文をいくつか引用
  • KEM鍵を利用する共通鍵暗号に強力な認証機能があれば問題ないかもしれないが、それは結果論的。NISTは明確にIND CCA2 KEMを要求しているためimplicitははずせない。
  • 証明がついていても、タイトさがないとセキュリティレベルが想定よりも低かったということが起きるので、なるべく強いレベルにすべき
  • implicitとexplicitが同じレベルというのは証明が弱すぎ。

Thom Wiggers

KEMTLSの設計時に、IND-CPAでいいかと思ったら”一度だけのCCA” IND-1CCAセキュリティが必要だった。このような間違いが往々にして起きるので基本は厳密にCCA2にしてほしい。

Explicit rejectionでいいんじゃね？派

Simon Hoerder

上位プロトコルでエラー処理が入っていた場合implicit rejectionは役割を果たしてないので、security proof以外に意味があるのか？

Mike Hamburg

氏ははじめImplicit rejectionがQROMに対する証明をタイトにするのに必要だと述べており、implicit擁護派の立場だったが、途中から必要性が薄いのでは？という立場に移っている？

Andreas Hülsing

NXPの質問は、zのサイドチャネル耐性に関するものであり、これまでのDJBの議論はちょっとずれている。質問は、サイドチャネルを通してexplicitになるケースが大丈夫かどうか

Christian Majenz

explicitとimplicitのsecurity lossはほぼ同じ

結局？

結局ML-KEMはimplicit rejectionで標準化されたので、理論的なセキュリティレベルもちゃんと確保するような方向へ動いたと思われる。
しかしimplicit rejectionはQROMに対するセキュリティレベル向上の話なので、正直ここをちゃんと守らないといけないという実感があんまり湧かない。特にサイドチャネルに対して。

量子計算機が実用化されたとして、zが未対策ならサイドチャネルでz取ってから攻撃するということになるのか？
でも2回復号オラクルにアクセスすればrejectかどうかわかる気がするのでそっちの方が簡単そうだけど・・・QROMがよくわかってないのでわからん。

Discussion