- The agreements that NIST has with the patent holders appear to apply only to the version of Kyber that will be FIPS approved. If Kyber (as of round 3) is unchanged, then that IPR protection applies to the version we have today (and so anyone using that is retroactively protected). On the other hand, if we make a change (for any reason), that would leave the current implementors unprotected.
Aside from the fact that it would be a change very late in the process,
we can think of only one disadvantage:
* From an input/output behavior point of view, computing the rejection
key K' in Decapsulation is only needed if c' != c. Not computing this
rejection key would save hashing over c, so there is some incentive
for implementers to speed up Decapsulation by only computing
(K', -) <- G(z, c) in the rejection case. This creates a timing
side-channel that essentially gives an attacker explicit rejection.
Note that this is not a disaster: As mentioned above, FO with explicit
rejection is now also proven secure in the QROM. However, the
reduction either incurs an additive q^2 / \sqrt{\delta} term as
tightness loss (where q is the sum of all random oracle queries and
\delta is the failure probability) or it requires to analyze the
failure bound in the extractable QROM, which has not been done so far.
Dear all,
* I support the proposal by Peter, I think it is the cleanest and
best way.
* Regarding the key combiners, I may be wrong, but to me it seems as if there is no difference in computation time. The ciphertext has to influence the final derived key in any case. For computation time it seems to me that it does not matter if the ciphertext is hashed into the key in the FO transform or in the KEM combiner. It is just moving cost around. Please correct me if I am wrong.
Cheers,
Andreas
--
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/CAMjbhoXPMxWXDthrS9p%3Dyygm1w00jwqyj%2BtkP-Tc_jKoHT_WmA%40mail.gmail.com.
It is just moving cost around.
On Apr 28, 2023, at 08:51, 'dustin...@nist.gov' via pqc-forum <pqc-...@list.nist.gov> wrote:
This Message Is From an External SenderThis message came from outside the Laboratory.
--
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/14437cb4-5452-4be6-86bc-af10d382ad03n%40list.nist.gov.
"Markku-Juhani O. Saarinen" <mjos....@gmail.com> wrote:
> Hi Peter,
Hi Markku, hi all,
> Nowadays in NIST specifications random numbers (key material) is required
> to be generated by one if the (D)RBGs specified in SP 800-90A/B/C. It can't
> be a "system random." Standard RBGs have the required security properties
> (with proofs) and the output has already been subject to cryptographic
> conditioning.
I'm assuming that Kyber will be used in all kind of environments with
all kind of randomness sources -- not all FIPS certified. In most
contexts, the hash is a cheap way to not leak the output of whatever RNG
is used on the system.
> It's safe to leave that hash out -- anyway this isn't a random number
> generation standard.
In a way, that's the point of this hash. If we had any control over the
RNG, I'd probably be much less worried about releasing output of the RNG.
> In side-channel secure implementation the redundant masked Keccak
> unnecessarily correlates the otherwise independent, uniform shares of the
> 256-bit m. So it makes the algorithm a bit slower but also slightly weaker.
I see, fair point; it's another tradeoff then. How much of a difference
does it make in terms of *performance* in a masked environment?
Hi,
I very strongly agree that one should never leak the RNG output. We know that signal intelligence agencies in the past have compromised RNG standards, tried to increase the amount of leaked information, and completely controlled crypto equipment manufacturers.
https://en.wikipedia.org/wiki/Dual_EC_DRBG
https://datatracker.ietf.org/doc/html/draft-rescorla-tls-extended-random-00
https://en.wikipedia.org/wiki/Crypto_AG
Having an extra hash seems like a small price to pay but does not provide enough protection if the RNG outputs so few values so that a powerful attacker controlling the RNG can test all the hash values. Who knows how many crypto suppliers that are secretly controlled by signal intelligence agencies today?
Applying supply chain security and zero trust principles, I think implementations should always mix different sources of randomness together, using e.g., RFC 8937
My view:
- I think the hash should definitely stay.
- The NIST specification should explain why the hash is needed based on past attacks and also recommend mixing different sources of randomness together.
If someone controlling both Kyber and the RNG wants to optimize it away, they can still do that, but I don't think a HW module should be certified without the hashing.
Ruben Niederhagen wrote
>I could imagine that Google & Cloudflare & Co know what they are doing
In the past, Google did not even use encryption between their global datacenters in the completely naive thought that nobody would eavesdrop on their fibers when they crossed country boarders.
Cheers,
John
--
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://protect2.fireeye.com/v1/url?k=31323334-501cfaf3-313273af-454445554331-f16909323b41e245&q=1&e=8f574f91-5213-430a-ad09-9d4f4eb1f38e&u=https%3A%2F%2Fgroups.google.com%2Fa%2Flist.nist.gov%2Fd%2Fmsgid%2Fpqc-forum%2FDF491D60-E7C4-4718-BF6D-D9ABDFB0587E%2540polycephaly.org.
Having an extra hash seems like a small price to pay but does not provide enough protection if the RNG outputs so few values so that a powerful attacker controlling the RNG can test all the hash values.
Applying supply chain security and zero trust principles, I think implementations should always mix different sources of randomness together, using e.g., RFC 8937
My view:
- I think the hash should definitely stay.
- The NIST specification should explain why the hash is needed based on past attacks and also recommend mixing different sources of randomness together.
From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of Ruben Niederhagen <ru...@polycephaly.org>
Date: Saturday, 29 April 2023 at 14:33
To: pqc-forum <pqc-...@list.nist.gov>
Subject: Re: [pqc-forum] Discussion about Kyber's tweaked FO transform
> On Apr 29, 2023, at 19:04, Markku-Juhani O. Saarinen <mjos....@gmail.com> wrote:
>
> Non-compliant implementations have complete liberty to drop the unnecessary re-hashing of random based on their own assessment of their own RNGs.
>
> This is because the "Line 2" re-hash is a no-op from interoperability and functionality viewpoint: Google & Cloudflare & Co may just remove it from non-FIPS crypto stacks in their desire to shave some microseconds off from the handshake, and no one will notice.
I could imagine that Google & Cloudflare & Co know what they are doing - and that they would use a secure RNG in concert with this optimization.
In contrast, someone unexperienced using a software library of a Kyber implementation (that is true to the standard) might get some benefit from this if the system RNG happens to be weak…
Ruben
--
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://protect2.fireeye.com/v1/url?k=31323334-501cfaf3-313273af-454445554331-f16909323b41e245&q=1&e=8f574f91-5213-430a-ad09-9d4f4eb1f38e&u=https%3A%2F%2Fgroups.google.com%2Fa%2Flist.nist.gov%2Fd%2Fmsgid%2Fpqc-forum%2FDF491D60-E7C4-4718-BF6D-D9ABDFB0587E%2540polycephaly.org.
--
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/GVXPR07MB96787151A407C81D9F0620B689689%40GVXPR07MB9678.eurprd07.prod.outlook.com.
This is because the "Line 2" re-hash is a no-op from interoperability and functionality viewpoint: Google & Cloudflare & Co may just remove it from non-FIPS crypto stacks in their desire to shave some microseconds off from the handshake, and no one will notice.
--
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/102ed46f-635a-444b-b949-e42d94b9912fn%40list.nist.gov.
Hi Markku,Thank you for your discussions: they have been very helpful to me.I would like to understand more. I don't present any view of a group or organization in this discussion.May I ask a question: why do you need to mask the hash function at that step (step 2) ? I am not a side channel person, but m is freshly generated every time Encap is called.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CA%2BiU_qk0rPMHvAY2ObjoycVnf5%3DpdV7WeMOVKC0XDz9nDJawzA%40mail.gmail.com.
--
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/ZE4fpaKbHbew7HZE%40disp3269.
This discussion questioning the need to protect RNG output seems to condense to the argument between theoreticians and practitioners.
From the theoretician’s point of view, a good standard is one that uses and documents a nice set of assumptions, not worrying about the “real world”. Such as – “employ a good TRNG, and if you don’t (for whatever reason) – too bad for you. Be smarter next time.”
From the practitioner’s point of view – a good standard is one that makes a good balance between requiring properties that one can reasonably rely upon (such as, hash function employed is collision-free and a good “randomizer”), and protecting against effects that (for whatever reason!) can go bad in the field. Such as – TRNG sometimes fail, etc. etc.
Needless to say, in this argument I’m 100% on the practitioners’ side, and fully support hashing the RNG output. Even if in many cases it is unnecessary. My use cases can afford it, and, most likely, so can yours.
P.S.
> If someone controlling both Kyber and the RNG wants to optimize it away, they can still do that, but I don't think a HW module should be certified without the hashing
My gut feeling is that the above is exactly correct. Except I might replace “should” with “could” – as in “I doubt a sane certifying organization would entertain approving such an implementation.”
--
V/R,
Uri
There are two ways to design a system. One is to make it so simple there are obviously no deficiencies.
The other is to make it so complex there are no obvious deficiencies.
- C. A. R. Hoare
From: <pqc-...@list.nist.gov> on behalf of Iluminada Baturone <iluminad...@gmail.com>
Date: Monday, May 1, 2023 at 17:25
To: pqc-forum <pqc-...@list.nist.gov>
Cc: John Mattsson <john.m...@ericsson.com>, Ruben Niederhagen <ru...@polycephaly.org>
Subject: [EXT] Re: [pqc-forum] Discussion about Kyber's tweaked FO transform
Hi, it is very important to use TRNGs (True Random Number Generators) in cryptographic systems. The foundations of a TRNG should be supported by a physico-mathematical model to be trusted, a TRNG should be self-callibrated (to avoid attacks)
ZjQcmQRYFpfptBannerStart
|
ZjQcmQRYFpfptBannerEnd
Hi,
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/4e1ab1f2-9af3-4805-8b46-d232a6a3ee87n%40list.nist.gov.
This discussion questioning the need to protect RNG output seems to condense to the argument between theoreticians and practitioners.
--
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/0E473856-8398-494C-916E-6463ADEADC9A%40ll.mit.edu.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CA%2BiU_qnsJpNnokX3HEMX4BL%3DGaTg95aYcNu-gcBVsdu7tXG%2B0Q%40mail.gmail.com.
The Kyber spec does not include measures against a malfunctioning (or even malicious) CPU or RAM, and doing so would be considered a layering violation.
People deal with issues like this by applying what’s usually called “common sense”.
It’s pretty good (in most cases, for many people) in telling what’s reasonable to defend against (and at what cost), and what isn’t.
I’m aware of the claim that it became a rare commodity nowadays, but I remain cautiously optimistic. 😉
In my (fairly extensive) experience I’ve seen few (if any) of malicious CPUs or RAM (and rather few malfunctioning but passing self-test), but plenty of broken or failing (T)RNGs that can’t be “caught” in real-time.
It should not attempt to defend against a malfunctioning or maliciously chosen random number generator, since that equally would be a layering violation.
While I’m all broken up about a possibility of a layering violation, IMHO we should attempt to defend against malfunctioning RNG. 😉
On the other hand, I doubt anybody interoperating with you would be able to detect that your implementation skipped a hash call, so you’re free to do so on your own if you feel it’s too expensive... Of course, good luck getting your implementation certified – but that’s not my problem. ;-)
If we don't trust unhashed random number generator outputs, we should add this hash call to the random number generator spec.
A reasonable recommendation.
It still does not sweeten the suggestion to remove “Kyber hash”.
“Idealists think they can control the real-world environment with their pens. Realists know better.” ;-)
Like I said before – our purpose is not to cover our backs with paper trail. “But I told you that you had to use a good reliable TRNG that doesn’t break!”
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAEEbLAZHwfB5-Atc-YxQNsmfhFYkYuwFuK9EuyTc3NWv3Sx_wQ%40mail.gmail.com.