Kyber does not allow explicit rejection

[bwesterb]

In this implementation, when re-encryption fails, explicit rejection is used. That is not allowed by the Kyber specification: decapsulation always has to succeed.

[thomwiggers]

Note that this is a security flaw: with explicit rejection, Kyber's IND-CCA security proof is much less tight.

[mberry]

Thanks for your eyes on this Thom, very much appreciate it.

That said, I don't see the issue here, this is a Rust library using Rust idioms, there is both implicit and explicit rejection available to end users decapsulating the shared secret, you don't have to use the Result<(),Error> if you don't want to.

Can you actually elucidate the security flaw you see with some demo code? Thanks

[thomwiggers]

Explicit rejection immediately leads to a wealth of side-channel attacks that "regular" users are not equipped to handle. For example, the decapsulate operation in api.rs introduces side-channel vulnerabilities. The FO transform is extremely vulnerable to this.

[mberry]

Can you provide a working example of this side channel attack? It's been nearly three months since this claim and I'm yet to see a working example provided or used in the wild.

Everyone is a regular user as far as this library is concerned. There's no presumptions made about the end users of the library, it's for all.

You can always contact me on foss@mitchellberry.com if you want for security issues.

[thomwiggers]

Based on your assumption that everyone using this crate is a regular, non-cryptography-expert user, the responsibility of properly handling the FO-transform lies on this crate. But because this crate returns a rejection symbol, for secure operation users of this crate currently need to make sure it becomes time-invariant and generate a fake shared secret (as required by the Kyber specification) themselves.

Explicit rejection or non-constant-time handling of rejection strictly weakens the security of Kyber

Aside from the fact that the Kyber specification strictly requires this, section 2.4 of the paper I linked before explains why the FO-transform needs to be properly implemented https://eprint.iacr.org/2019/948.pdf.

https://eprint.iacr.org/2022/1696.pdf explains exactly what the loss in security is when you use explicit rejection (or a side-channel attack reveals that the ciphertext was rejected).

If you feel that using explicit rejection is fine, I'm sure that the authors of Kyber look forward to seeing the results of your security proof in the QROM.

[koraa]

Is there any plans to fix this issue? I am considering switching to all rust-based cryptography in Rosenpass but this issue is a definite blocker.

Gaps between the proofs of security and the implementation – like the gap in this issue – preclude me from claiming any sort of provable security. This also makes it much harder to certify any product using this crate, as there is an obvious gap between specification and implementation.

[mberry]

this issue is a definite blocker

There is nothing stopping the use of implicit rejection, it's already there and was from the very beginning.

What Bas and Thom are proposing is to remove the option for explicit rejection altogether, which, to be fair, is understandable from a certain viewpoint: it's entirely in line with the spec, removes a possible footgun in rare circumstance and allows some verification guarantees, though also comes with tradeoffs which some might not want.

The irony of this whole debate is highlighted succinctly in the PR by Bas:

- crypto_kem_dec(&mut buf[KYBER_SYMBYTES..], &recv[KYBER_PUBLICKEYBYTES..], skb)?;
+ crypto_kem_dec(&mut buf[KYBER_SYMBYTES..], &recv[KYBER_PUBLICKEYBYTES..], skb);

This is in the key exchange module, the result isn't being used, there's no explicit rejection, handling error propagation exists for the linter and nothing else, it's a no-op.

there is an obvious gap between specification and implementation

This library follows the spec down to the letter, there's simply additions, like MASM, NASM, 90's mode (again a touchy topic), zeroisation, etc. No one is forced to use these, they are all feature gated.

At this point I'm tired of getting pestered about it and doubt that will stop in the near future, so I'll merge the PR and put in a explicit rejection feature with some security notes so users can decide for themselves. Hopefully that will keep everyone happy.