ML-KEM Decaps return code handling

[Joost Renes]

Hi NIST team,

 

We would like to ask NIST to clarify their position on handling return codes for Kyber / ML-KEM Decapsulation.

Even with the current API for implicit rejection, a return code could be included to the caller of the Decapsulation routine indicating whether the function has output a correct key or not.

This would essentially wrap the “implicit rejection” with an “explicit rejection”, without impacting the function or the API otherwise.

Note that return codes are anyway basically unavoidable in the context of side-channel attacks, fault attacks, failing HW, etc.

 

This has also been discussed at length last year in a different context: Implicit Rejection in Kyber (google.com)

(To be clear and to avoid confusion: we are *not* proposing to make any changes to the Decapsulation routine itself, or asking about the side-channel protection of z as in the linked thread.)

From what we understand, there is currently no known benefit from implicit rejection over explicit rejection in terms of security reduction.

On the other hand, there are clear practical benefits in being able to abort a protocol as early as possible (for example in real-time of safety-critical systems).

As also touched upon by Simon in the thread above, for protocols involving some kind of key confirmation (e.g., TLS) the “implicit” rejection is anyway not maintained.

If explicit rejection is really to be avoided in a specific context for whatever reason, the return code could of course be discarded (or not implemented at all).

 

The question is thus: Would it be considered compliant with the specification to indicate success/failure of Decapsulation to the caller?

If so, would you consider including this possibility in the specification?

If not, could you elaborate on your arguments?

 

Kind regards,

NXP PQC team

 

[Peter Schwabe]

Joost Renes <joost...@nxp.com> wrote:
> Hi NIST team,

Dear Joost, dear all,

> We would like to ask NIST to clarify their position on handling return codes for Kyber / ML-KEM Decapsulation.
> Even with the current API for implicit rejection, a return code could be included to the caller of the Decapsulation routine indicating whether the function has output a correct key or not.
> This would essentially wrap the "implicit rejection" with an "explicit rejection", without impacting the function or the API otherwise.
> Note that return codes are anyway basically unavoidable in the context of side-channel attacks, fault attacks, failing HW, etc.

> This has also been discussed at length last year in a different context: Implicit Rejection in Kyber (google.com)<https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/SJ31w0QSmIM>

> (To be clear and to avoid confusion: we are *not* proposing to make any changes to the Decapsulation routine itself, or asking about the side-channel protection of z as in the linked thread.)
> From what we understand, there is currently no known benefit from implicit rejection over explicit rejection in terms of security reduction.
> On the other hand, there are clear practical benefits in being able to abort a protocol as early as possible (for example in real-time of safety-critical systems).
> As also touched upon by Simon in the thread above, for protocols involving some kind of key confirmation (e.g., TLS) the "implicit" rejection is anyway not maintained.
> If explicit rejection is really to be avoided in a specific context for whatever reason, the return code could of course be discarded (or not implemented at all).
>
> The question is thus: Would it be considered compliant with the specification to indicate success/failure of Decapsulation to the caller?
> If so, would you consider including this possibility in the specification?
> If not, could you elaborate on your arguments?

If the caller reacts on that return code, you have explicit rejection
and you lose tightness in the QROM proofs. If you don't react on the
return code, why have any other return code than zero?


All the best,

Peter

[Joost Renes]

Hi Peter,

My understanding is that there is no difference in tightness for implicit & explicit rejection in the QROM proofs.
This is based on the messages from Christian and Andreas in the linked thread (20 Dec. 2022), where they refer to their Asiacrypt paper: https://eprint.iacr.org/2022/365.
If there is no theoretical reason to avoid explicit rejection, it would be useful to allow it (e.g., in the form of a return code) as it adds some robustness and avoids unnecessary subsequent computation in case of an implicit rejection.

Kind regards,
Joost

-----Original Message-----
From: Peter Schwabe <pe...@cryptojedi.org>
Sent: Wednesday, October 11, 2023 6:00 PM
To: Joost Renes <joost...@nxp.com>
Cc: pqc-...@list.nist.gov
Subject: [EXT] Re: [pqc-forum] ML-KEM Decaps return code handling

Caution: This is an external email. Please take care when clicking links or opening attachments. When in doubt, report the message using the 'Report this email' button

Joost Renes <joost...@nxp.com> wrote:
> Hi NIST team,

Dear Joost, dear all,

> We would like to ask NIST to clarify their position on handling return codes for Kyber / ML-KEM Decapsulation.
> Even with the current API for implicit rejection, a return code could be included to the caller of the Decapsulation routine indicating whether the function has output a correct key or not.
> This would essentially wrap the "implicit rejection" with an "explicit rejection", without impacting the function or the API otherwise.
> Note that return codes are anyway basically unavoidable in the context of side-channel attacks, fault attacks, failing HW, etc.

> This has also been discussed at length last year in a different
> context: Implicit Rejection in Kyber

> (google.com)<https://eur01.safelinks.protection.outlook.com/?url=https
> %3A%2F%2Fgroups.google.com%2Fa%2Flist.nist.gov%2Fg%2Fpqc-forum%2Fc%2FS
> J31w0QSmIM&data=05%7C01%7Cjoost.renes%40nxp.com%7C2da2d70a60114f731987
> 08dbca731d8b%7C686ea1d3bc2b4c6fa92cd99c5c301635%7C0%7C1%7C638326367980
> 225566%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJ
> BTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000%7C%7C%7C&sdata=jkLLiKhX5ctyECVmIYC4
> MWmeynwJzy3%2FN51DnyJRD%2FM%3D&reserved=0>

[Mike Hamburg]

Dear all,

I expect that explicit rejection would be fine for Kyber.  Essentially it gives the attacker an oracle for “is this C in the image of encapsulate()?” (not quite because of failures, but something in that direction) and I strongly doubt that this can really be used for an attack on Kyber beyond the known decaps failure attacks.  Still, I’m not sure how well-established security is in the proofs, and also there are usability questions as well.

Kathrin / Andreas / Christian can maybe comment on this, but does that Asiacrypt paper have comparable resource-tightness to implicit rejection proofs?  My recollection is that the reductions for implicit rejection have constant-factor time and space overhead, but the black-box explicit rejection ones use compressed oracles or measure-rewind-measure and so incur on the order of q quantum memory cost.  I’m also not aware of a Kyber-specific proof that removes this cost, but maybe there is one.  Also, is Kyber known to be \gamma-spread for appropriate \gamma?

I would have supported removing this security feature if it could have been done and analyzed earlier in the process, but in my opinion it’s a little late now and it would be better to leave the requirement for implicit rejection.

Regards,

— Mike

-- 
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/AM9PR04MB8161250E8F31DA01C394A277FFCCA%40AM9PR04MB8161.eurprd04.prod.outlook.com.

[D. J. Bernstein]

Joost Renes writes:
> If there is no theoretical reason to avoid explicit rejection

The basic asymmetry is that the IND-CCA2 security level of explicit
rejection is trivially proven to be _at most_ the IND-CCA2 security
level of implicit rejection (since anyone can add an implicit-rejection
wrapper; see, e.g., Theorem 3 of https://eprint.iacr.org/2019/590),
whereas the opposite hasn't been proven for Kyber.

The idea that implicit rejection and explicit rejection are now in the
same proof situation comes from (1) disregarding this basic asymmetry
and (2) pointing to a different symmetry between much looser proofs.

---D. J. Bernstein

[Joost Renes]

Hi Dan,

Again, my understanding from the messages of Christian & Andreas was that implicit and explicit rejection did have equal non-tightness in the QROM proofs.
Perhaps this understanding was wrong, it would be nice if Kathrin, Christian or Andreas have a chance to comment.
Is there a reason to believe the explicit rejection variants have worse security?

Kind regards,
Joost

-----Original Message-----

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20231011181032.1950014.qmail%40cr.yp.to.

[Joost Renes]

Hi Mike,

 

Thanks for the comments.

 

In the end (virtually) every protocol will react to the implicit rejection one way or another, making it explicit.

Either by having explicit key confirmation, timing out, encrypting with the wrong key, etc.

Perhaps there are counterexamples, but I would expect it’s a clear minority.

So we can disallow reacting to decapsulation failures to try and hang on to implicit rejection, but do we really increase security in scenarios where Kyber is deployed?

 

KR,

Joost

[Blumenthal, Uri - 0553 - MITLL]

In the end (virtually) every protocol will react to the implicit rejection one way or another, making it explicit.

Either by having explicit key confirmation, timing out, encrypting with the wrong key, etc.

 

This makes sense. The only difference that I see is how long it would take to “signal” rejection.

 

Perhaps there are counterexamples, but I would expect it’s a clear minority.

 

I’m not aware of any counterexamples.

 

So we can disallow reacting to decapsulation failures to try and hang on to implicit rejection, but do we really increase security in scenarios where Kyber is deployed?

 

I tend to agree.

 

Mike, Peter – from the practical security point of view, what do we gain (besides being able to mark a checkbox on paper that QROM proof looks really nice 😉) from pushing “rejection detection” a few steps down in the protocol? Because nobody is likely to use KEM on its own – it would be a part of some kind of a protocol that inevitably has to determine at some point whether the key is good or not.

 

Thanks!

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/AM9PR04MB816182D9CF261A194464042FFFCCA%40AM9PR04MB8161.eurprd04.prod.outlook.com.

[D. J. Bernstein]

Joost Renes writes:
> Again, my understanding from the messages of Christian & Andreas was
> that implicit and explicit rejection did have equal non-tightness in
> the QROM proofs.

Yes, there's a symmetry between the QROM inequalities that basically say

(1) cost of IND-CCA2 break of Kyber >= (cost of breaking the PKE) / (very large factor)

and

(2) cost of IND-CCA2 break of Kyber-explicit >= (cost of breaking the PKE) / (very large factor)

if the much more basic theorem

(3) cost of IND-CCA2 break of Kyber >= cost of IND-CCA2 break of Kyber-explicit

is disregarded.

---D. J. Bernstein

[David A. Cooper]

Speaking only for myself. I do not know whether there is a security benefit to implicit rejection versus explicit rejection in the case of Kyber. However, I disagree with the idea that the way that most protocols will react to implicit rejection will make it explicit.

If you assume that the attacker generates ciphertexts according to the encaps() function and so knows what the shared secret key should be, then it is true that things like key confirmation would essentially make an implicit reject as a result of a decapsulation failure explicit. However, there have been years of attacks against the RSA PKCS #1 v1.5 padding scheme (see, for example, https://eprint.iacr.org/2023/1442.pdf) that involve the attacker creating ciphertexts for which the attacker does not know the corresponding plaintext. The attacks work because the attacker gains knowledge by finding out whether the decrypted ciphertext satisfied the padding schemes requirements. It is my understand that, while it is difficult to do in practice with RSA PKCS #1 v1.5, implicit rejection would avoid the problem. Key confirmation would not turn the implicit rejection into an explicit one, since the attacker has no way to verify the MAC on the confirmation message, and so can't tell whether the MAC was created with a key that the private key holder thought was as shared secret key or a random "rejection" key.

Perhaps with Kyber, unlike with RSA, we don't need to worry about cases in which the attacker generates ciphertexts without any way of knowing what the corresponding shared secret key would be if decapsulation were to succeed. However, at least with RSA that is not the case, and things like key confirmation or encrypting with the wrong key do not make rejection explicit, since the attack can't determine whether the "wrong" key was used to perform the encryption or compute the MAC for key confirmation.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/7E0071C0-AEE4-4DB3-B6A9-3A8C7E0AF710%40ll.mit.edu.

[Mike Hamburg]

Hi David,

I agree with you that this is the threat, and the Bleichenbacher attack on RSA is a great example.

Per https://eprint.iacr.org/2019/590.pdf theorem 4, adding key confirmation is at least as strong as implicit rejection (in the QROM for the hash used to produce the key confirmation, assuming Kyber is almost injective, etc)… but only if the attacker lacks a side channel that shows whether the ciphertext was rejected.

I do not think Kyber is like RSA-PKCS #1 v1.5 in this way: it’s more like RSA-OAEP in that valid messages must be produced by a hash function.  But as far as I know, that structure alone doesn’t tightly-provably prevent the problem, at least not in the QROM.

Regards,

— Mike

[Mike Hamburg]

On Oct 11, 2023, at 10:21 PM, Mike Hamburg <mi...@SHIFTLEFT.ORG> wrote:

Hi David,

I agree with you that this is the threat, and the Bleichenbacher attack on RSA is a great example.

Per https://eprint.iacr.org/2019/590.pdf theorem 4, adding key confirmation is at least as strong as implicit rejection (in the QROM for the hash used to produce the key confirmation, assuming Kyber is almost injective, etc)… but only if the attacker lacks a side channel that shows whether the ciphertext was rejected.

I do not think Kyber is like RSA-PKCS #1 v1.5 in this way: it’s more like RSA-OAEP in that valid messages must be produced by a hash function.  But as far as I know, that structure alone doesn’t tightly-provably prevent the problem, at least not in the QROM.

Sorry, correcting myself here: valid ciphertexts are produced by processing the message with its hash.  This should make it hard for the attacker to produce something where they don’t know whether it’s a valid ciphertext or not, unlike with Bleichenbacher’s attack.  Whoops, — Mike

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/C851CAA2-A71B-4F45-8D77-030F992F46E2%40shiftleft.org.

[Joost Renes]

Hi David,

 

I think your concern is valid, but Kyber is quite different from RSA by virtue of using Fujisaki-Okamoto at all (either implicit or explicit).

 

Not familiar with the proofs Mike refers to, so cannot comment on them.

But informally, the point of FO in the first place is to reject ciphertexts that were not honestly generated (via Encaps).

So with explicit rejection an adversary can learn either that 1) the ciphertext they provided was not generated via Encaps, which will essentially always happen unless they used Encaps, or 2) the ciphertext they provided was generated via Encaps, in which case they may as well have used Encaps themselves.

I do not see how Bleicherbacher-type attacks are possible in this scenario.

KR,

Joost

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/01D1FBAC-6076-469B-8AE4-630ADD9C0120%40shiftleft.org.

[Kathrin Hövelmanns]

Dear All,

Thanks, Mike, for describing the characteristics of our reduction for FO with explicit rejection. Indeed, it is not memory-tight due to the use of the compressed oracle technique (which comes with an order q memory overhead). And there is indeed the open task of proving that Kyber has gamma-spreadness for appropriate gamma.

Disregarding memory overhead, our Asiacrypt paper gives provable security bounds for the explicit reject variant of FO that are very similar to the best bounds for implicit reject FO. Both bounds are not tight. As pointed out already by Dan, implicit reject is at least as secure as explicit reject. Together this means that the real security of explicit rejection could be lower than the real security of implicit rejection, within the tightness gap.

Best wishes,
Kathrin, Andy and Chris.