Discussion about Kyber's tweaked FO transform

[Peter Schwabe]

Dear all,

At the fourth NIST PQC Standardization Workshop we sketched a few
possible changes to Kyber that could be considered in the
standardization phase; we followed up on those in two e-mails with
subjects "Kyber decisions, part 1: symmetric crypto" and "Kyber
decisions, part 2: FO transform". The points we brought up for
discussion in the first e-mail received quite some feedback and
eventually NIST decided to not integrate any of the changes. The second
mail received way fewer replies, but Markku asked us for a more concrete
description of the proposed change. Apologies that this request remained
unanswered for so long! In this mail we would like to follow up and make
the suggested change more concrete.

Currently, Kyber's tweaked FO transform looks as follows:

Encaps(pk):
(K,r) <- G(m,H(pk))
c <- Encrypt(m,pk,r)
K' <- KDF(K,H(c))
return K',c


Decaps(SK=(sk,pk,z),c):
m' <- Decrypt(sk,c)
(K,r) <- G(m',H(pk))
c' <- Encrypt(m',pk,r)
if(c' == c)
K' <- KDF(K,H(c))
else
K' <- KDF(z,H(c))
return K'


The concrete proposal would be to change this to:

Encaps(pk):
(K,r) <- G(m,H(pk))
c <- Encrypt(m,pk,r)
return K,c

Decaps(SK=(sk,pk,z),c):
m' <- Decrypt(sk,c)
(K,r) <- G(m',H(pk))
c' <- Encrypt(m',pk,r)
(K',-) <- G(z,c)
if(c' != c)
K <- K'
return K


Note that this is the standard FO transform with implicit rejection,
except that the hash of the public key is fed as an additional argument
into G to derive (K, r). As a reminder, this provides some protection
against multi-target decryption-failure attacks and makes Kyber
"contributory", i.e., ensures that the shared key depends on
high-entropy input from both parties.

The advantages of this change would be the following:

* Encaps avoids hashing over the ciphertext. In our AVX2 optimized
implementation this translates to a speedup of ~17%. Note that the
speedup on most other platforms and for masked implementations is
going to be smaller than that.

* More importantly, this change simplifies proofs and leads to better
bounds without requiring a new failure-bound analysis. More
specifically, the only direct proofs of the FO originally used by
Kyber that we could come up with produces a bound with an additive
C(q + q_dec + 1)^3/2^{256} term where C is some constant, q is the
number of the adversary queries to the random oracle, and q_dec is the
number of the adversaries decryption queries. This is caused by having
to deal with collisions in H (when computing H(c)). Alternative proofs
via explicit rejection either lead to a worse bound or require to
analyze the failure bound in the extractable QROM, which has not been
done so far.

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.


All the best,

The CRYSTALS-Kyber team

[Scott Fluhrer (sfluhrer)]

Actually, there is another advantage to leaving Kyber as it is:

- 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.

> --
> 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/ZC7Zl9XnA3f/BX/d%40disp3269.

[Tony Arcieri]

On Thu, Apr 6, 2023 at 9:14 AM 'Scott Fluhrer (sfluhrer)' via pqc-forum <pqc-...@list.nist.gov> wrote:

- 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.

Can't this potentially be resolved by simply asking the patent holders for an exemption? It seems worth a try at least.

There's a long history of using suboptimal cryptography due to patents, and it would be nice to avoid it here if it can be resolved with a conversation with the right people.

--

Tony Arcieri

[Bas Westerbaan]

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.

There is another small disadvantage. In general, to get an IND-CCA2 robust hybrid of two KEMs, you need something like H( ss1 || ss2 || ct1 || ct2) as a combiner, assuming fixed-length ss and ct. If the two KEMs, however, already mix in ct separately, as is the case for Kyber now and DHKEM(X25519) in HPKE, then we can forgo hashing in ct. This is a marginal concern, such as for HPKE, as for for instance TLS we're hashing in ct anyway as part of the transcript. Having said this, I don't feel strongly about it either way.

Best,

 Bas

 

[Andreas Hülsing]

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.

[Bas Westerbaan]

 It is just moving cost around.

Yeah, that's correct.

 Bas 

[Bas Westerbaan]

I'm sorry, I spoke too early: it's indeed just moving cost around for encapsulation, but decapsulation is slightly more expensive as c is always hashed  to compute K'. Nonetheless, for TLS 1.3 kex we can forgo hashing c because of the transcript, so there the proposal improves performance. For HPKE we'd make decapsulation slightly slower, but it's not a big deal. I'm ok with the proposal.

[dustin...@nist.gov]

All,

NIST is planning to incorporate the CRYSTAL-Kyber team's suggestion of tweaking the FO transform into the draft standard, as described in Peter Schwabe's earlier post.  Any comments or feedback are welcome.

Dustin

[Blumenthal, Uri - 0553 - MITLL]

I support this decision. 

TNX

Regards,

Uri

On Apr 28, 2023, at 08:51, 'dustin...@nist.gov' via pqc-forum <pqc-...@list.nist.gov> wrote:



All, NIST is planning to incorporate the CRYSTAL-Kyber team's suggestion of tweaking the FO transform into the draft standard, as described in Peter Schwabe's earlier post. Any comments or feedback are welcome. Dustin On Thursday, April 20,

ZjQcmQRYFpfptBannerStart

This Message Is From an External Sender

This message came from outside the Laboratory.

 

ZjQcmQRYFpfptBannerEnd

--

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]

Hi All,

Just one minor note:

The pseudo-code describing current Encaps() in Peter's April 6 mail didn't include line 2 of Kyber 3.02, which is a hash from 256 bits to 256 bits m<-H(m). I assume (hope) that removing this hash is also a part of the delta.

Old Algorithm 8, on page 10 of 20210804 spec:

Kyber.CCAKEM.Enc(pk):
1. m <-$ 256-bit random
2. m <- H(m)    # delta: hopefully gone as well -- redundant
3. (K,r) <- G(m,H(pk))
4. c <- Encrypt(m,pk,r)
5. K' <- KDF(K,H(c)) # delta: gone, saves H(c) computation
6. return K',c  # just returns K

The new proposal streamlines this to:

1. m <-$ 256-bit random
2. (K,r) <- G(m,H(pk))
3. c <- Encrypt(m,pk,r)
4. return K,c

The concrete proposal for new decaps was:

Decaps(SK=(sk,pk,z),c):
1. m' <- Decrypt(sk,c)
2. (K,r) <- G(m',H(pk))
3. c' <- Encrypt(m',pk,r)
4. (K',-) <- G(z,c)  # this requires H(c)
5. if(c' != c) then K <- K'
6. return K

Looks good to me.

As noted by Peter in his original e-mail, it is very tempting to perform the computation of K' on line 4 of decaps only in case of mismatch c' != c. Based on discussions with other practitioners, current side-channel secure modules tend to already treat the comparison result as public information because of the proofs mentioned. If some implementation performs the computation up to and including the c' = c comparison securely but computes that particular hash conditionally, I wouldn't even flag that as a vulnerability right now.

Cheers,
-markku

[Peter Schwabe]

"Markku-Juhani O. Saarinen" <mjos....@gmail.com> wrote:
> Hi All,

Dear Markku, dear all,

> Just one minor note:
>
> The pseudo-code describing current Encaps() in Peter's April 6 mail didn't
> include line 2 of Kyber 3.02, which is a hash from 256 bits to 256 bits
> m<-H(m). I assume (hope) that removing this hash is also a part of the
> delta.

In my description I left it out because I didn't want to distract from
the proposed changes. I would this part as it is to make sure that Kyber
does not reveal output of the system RNG to the recipient.

All the best,

Peter

> > <https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/WFRDl8DqYQ4/m/54var7dfAQAJ>.

> > Any comments or feedback are welcome.
> >
> > Dustin
> >
> > On Thursday, April 20, 2023 at 7:35:50 AM UTC-4 b...@cloudflare.com wrote:
> >
> >> I'm sorry, I spoke too early: it's indeed just moving cost around for
> >> encapsulation, but decapsulation is slightly more expensive as c is always
> >> hashed to compute K'. Nonetheless, for TLS 1.3 kex we can forgo hashing c
> >> because of the transcript, so there the proposal improves performance. For
> >> HPKE we'd make decapsulation slightly slower, but it's not a big deal. I'm
> >> ok with the proposal.
> >>
> >> On Thu, Apr 20, 2023 at 12:44 PM Bas Westerbaan <b...@cloudflare.com>
> >> wrote:
> >>
> >>> It is just moving cost around.
> >>>>
> >>> Yeah, that's correct.
> >>>
> >>> Bas
> >>>
> >>
>

> --
> 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.

[Peter Schwabe]

"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?

Cheers,

Peter

[Markku-Juhani O. Saarinen]

On Sat, Apr 29, 2023 at 10:32 AM Peter Schwabe <pe...@cryptojedi.org> wrote:

"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.

Peter,

This seems little backwards. Only FIPS-compliant implementations are forced to follow the specification to the letter. 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.

 

> 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.

But you have that. :)  Kyber will become a FIPS standard: It can and -- and I'm sure it will -- state that the random bits come from an approved RBG, with a security level that matches the PQ Security category. ( It makes no sense to, say, use a RBG with 128-bit security level to feed Kyber-1024; you need a RBG at 256-bit security level initialized with appropriate amount of entropy. )

> 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?

Ok, so I ran some experiments with masked Kyber.

I commented that initial "Line 2" masked hash out (which is easy to do as it is a "nop" with no wider implications) and ran a prototype RTL model on verilator to get cycle-accurate full-system measurements with and without.

Kyber 512: 5.6% faster Encaps

Kyber 768: 4.8% faster Encaps

Kyber 1024: 3.8% faster Encaps

This is a first-order implementation; The % speedup depends on the masking order and how slow your masked Keccak is in relation to the rest of the algorithm. This particular implementation has hardware acceleration for for most aspects of Kyber, including Keccak. A pure MCU implementation may have a higher %, especially with high-order masking.

To clarify the thing about "correlations" I was talking about: Additional processing of "m" just provides more data to the attacker in the power or electromagnetic traces. This relative increase is larger than 5% since the traces also contain cycles where the target is not processing sensitive variables like "m" or "K". Even in basic TVLA testing of Encaps (random-vs-fixed "m"), having more sensitive data in the traces means that you need correspondingly fewer invocations of the evaluation target.

ps. I wanted to check open source implementations to get additional data -- but I can see that there's a flaw in the sensitivity analysis of https://eprint.iacr.org/2022/058.pdf and the implementation of the implementation https://github.com/masked-kyber-m4/mkm4/blob/main/crypto_kem/kyber768/m4/kem.c as it apparently performs no masking in the Encaps function.

It should be clear that that the shared secret K (and the process to derive it -- including the m variable) are equally sensitive in encapsulation as they are in decapsulation.

 

Cheers,

- markku

Dr. Markku-Juhani O. Saarinen <mj...@iki.fi>

[Ruben Niederhagen]

> 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

[John Mattsson]

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.

[Markku-Juhani O. Saarinen]

(Apologies to some recipients for sending this message twice-- used from e-mail alias, causing a bounce from the maling list.)

On Sat, Apr 29, 2023 at 2:54 PM 'John Mattsson' via pqc-forum <pqc-...@list.nist.gov> wrote:

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.

John,

Indeed the ciphertext output is deterministic function of "m" and "pk" so the enumeration attack that you describe applies regardless. Kyber allows a low-entropy "m" to be brute forced from the ciphertext with the knowledge of the ciphertext and public key, with or without the extra hash.

- Folks should note that this "m" quantity is not transmitted in clear. To get to "m" you need to decrypt the message first; if you don't have the secret key, you would need to break Kyber itself (or brute force m, as above). So the attack model of a passive eavesdropper does not really apply here.

- If one is actually worried about bad low entropy, one would definitely use more than 256 bits as an input in the first place. This hash just permutes it in-place -- entropy remains the same. However, this "condensation of entropy" is exactly what things like the vetted conditioners in SP 800-90B are for.

- In actual reality the operating systems and crypto stacks leak randomness via countless of other places without protection; cryptographic nonces, padding, TCP sequence numbers, etc, so it is much more readily available to a passive eavesdropper that way, rather than by basically breaking Kyber.

 

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.

I suggest raising any concerns about RBGs with the committees that standardize and certify RBGs. https://csrc.nist.gov/projects/random-bit-

There is some work there that discusses specifically mixing of different entropy sources, and my understanding is that such generators have been certified (typically "secondary sources" are not credited with entropy though -- only the primary ES is -- but the standards allow mixing in additional data, if done appropriately.)

I don't know how this discussion diverged into random number generators, but here's my personal take:

NIST has of course previously horribly stumbled in this area. However I have been pleased to see that in parallel to the PQC Competition (since ~2018) there has been a substantial improvement in RBG standards, with things like the introduction of entropy evaluation based on SP 800-90B in FIPS certification, and removing any role of SP 800-22 in FIPS RNG certification. Recently there has been convergence with BSI AIS 20/31 which was previously considered the "golden standard" for RNGs (and widely used in most Common Criteria high-assurance protection profiles); for example stochastic models are becoming a requirement with FIPS too. We are gradually arriving at a situation where AIS 20/31 and 800 90-A/B/C may be interchangeable. with good RNGs satisfying the requirements of both.

Cheers,

- markku

 

Dr. Markku-Juhani O. Saarinen <mj...@iki.fi>

 

 

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.

[Bas Westerbaan]

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.

We will not remove that hash, and prefer it not to be removed from the standard.

Bas

[Ruben Niederhagen]

> On Apr 29, 2023, at 22:54, Markku-Juhani O. Saarinen <mjos....@gmail.com> wrote:
>
> Kyber allows a low-entropy "m" to be brute forced from the ciphertext with the knowledge of the ciphertext and public key, with or without the extra hash.

>
> - Folks should note that this "m" quantity is not transmitted in clear. To get to "m" you need to decrypt the message first; if you don't have the secret key, you would need to break Kyber itself (or brute force m, as above). So the attack model of a passive eavesdropper does not really apply here.

The hashing of raw RNG output in Kyber is not about entropy. Imagine a scenario where a server is using a PRNG who’s output leaks the internal state (e.g., a simple 256-bit LSFR or a more sophisticated DualEC-DRNG-like scenario). Then, the attacker can simply connect to the server as regular client and perform key exchange. Now, if the raw RNG output is not hashed, the attacker obtains the internal state and can compute the keys of all future connections to the server. If the raw RNG output is hashed, this attack is not possible.

Ruben

[Quynh Dang]

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.

Regards,

Quynh. 

--

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.

[Markku-Juhani O. Saarinen]

On Sat, Apr 29, 2023, 23:29 Quynh Dang <quy...@gmail.com> wrote:

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.

Hi Quynh,

Indeed there is no technical reason to hash fresh random bits, and step 2 is not helpful for side-channel security either (it is little bit bad actually). That's why I hope it is removed.

As the thread has demonstrated, the reasons why some people think that random bits are not random bits seems to be personal/anecdotal and varies; for many it has to do with deliberately bad random number generators like Dual_EC_DRBG that have been inserted maliciously (as a backdoor) into NIST standards and some crypto implementations in the past. This was a huge embarrassment for NIST about a decade ago. There is also talk of "system random"; I don't think that this refers to anything specific, but during my 25 years of cryptography engineering there have been occasional design errors and bugs in system random number generators. I don't think extra hashing would have really mattered then, though. 

Cheers,

Markku

[Ruben Niederhagen]

> On Apr 30, 2023, at 06:30, Quynh Dang <quy...@gmail.com> wrote:
>
> 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.

There are different types of side-channel attacks with a varying attack cost and attack strength. Simple power analysis (SPA) requires only one single trace - but it can be defended against relatively easily, e.g., using ‘basic’ masking. Differential Power Analysis (DPA) uses several (many) correlated traces, is harder to defend against, and typically requires higher degrees of masking - or additional countermeasures.

Indeed a scenario, where the relevant data m is different in each consecutive run, should be ‘easier’ to protect - but in the end it all comes down to the exact attack scenario, device, and attacker capabilities… (Is it a smart card or some other device that the attacker has physical access to? How long does the attacker have access? Or is it a server in a physically well protected server room? Is, e.g., HertzBleed an issue then? …)

Ruben

[Daniel Apon]

Hi Markku,

Would you be okay with a single step that read something like "sample M <- UniformDist(Support)," perhaps with commentary about the onus is on the implementer to do so properly?

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.

[Peter Schwabe]

"Markku-Juhani O. Saarinen" <mjos....@gmail.com> wrote:
> On Sat, Apr 29, 2023 at 10:32 AM Peter Schwabe <pe...@cryptojedi.org> wrote:


> Peter,

Hi Markku, hi all,

> This seems little backwards. Only FIPS-compliant implementations are forced
> to follow the specification to the letter. 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 think we agree on most points, but we have a different perspective,
because we're looking at two different scenarios of how cryptographic
systems are built. You are in the business of building a whole system
that gets FIPS certified; in this scenario you include the hash in the
RNG where it belongs and obviously wouldn't include it in Kyber.

I expect that Kyber will be used in many scenarios like the one Ruben
described: the crypto implementation, the RNG, and the application are
built independently. Application developers will link against some
crypto library (which will include a Kyber implementation that is tested
against testvectors from the standard) and deploy that software on many
systems that provide randomness through *some* RNG. Should those RNGs
include the hash? Yes, of course. Are we sure that all of them do? I'm
not. Of course, as you stated in a another message, the RNG output may
leak through all kind of other sources, but the hash in Kyber's Ecnaps
is a cheap "defense-in-depth" mechanism to ensure that we don't add
another source of leakage.

As you wrote in another message, the RNG output is of course not leaked
to a passive observer, but if Kyber is deployed in, e.g., TLS, you can
query the RNG (or the output of the hash) of the server by making a
connection. If you'd like to learn output of the server's RNG, that's
just as good.

This is actually not clear to me, but maybe this is a discussion for a
different thread. I can see two arguments why it would need less
protection in Encaps than in Decaps:

* In Encaps you can get only one trace for a given m, whereas in Decaps
you can get an arbitrary number of traces.

* In Decaps, learning m also allows you to recover the long-term secret,
which obviously is not the case in Encaps.


Cheers,

Peter

[Sophie Schmieg]

I strongly agree with Markku here (and in fact in our current implementation, this hash is absent [1]). Having an insecure random number generator in a system is a threat in many ways, and the higher level primitive trying to repair potential issues of the lower layer is in my opinion folly. A secure random number generator, by definition, does not leak its internal state, and neither previous nor future outputs should be inferable from any number of bytes of known output (save for negligible advantage yada yada terms and conditions apply). If Kyber is used with an insecure random number generator (for example the xkcd one [2]), it is trivially broken in any case. This hash serves to protect against a single type of random number generator failure, the case of a backdoored random number generator, where the backdoor owner needs the actual output, but cannot activate their backdoor with a hash of the output. In other words, this hash defends against the usage of DUAL_EC_DRBG and not much else. The alternative defense against DUAL_EC_DRBG would be to simply not use DUAL_EC_DRBG. After all, in addition to likely being backdoored, it is also definitely not quantum safe.

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. It should not attempt to defend against a malfunctioning or maliciously chosen random number generator, since that equally would be a layering violation. If we don't trust unhashed random number generator outputs, we should add this hash call to the random number generator spec. Note that higher level protocols like TLS will often include random nonces to avoid replay attacks, which will be visible to the other party (and in fact everyone else) regardless. Adding this hash call to the random number generator spec (if we assume the non-DUAL_EC_DRBG random number generator would otherwise be insecure, which for the record, I don't) would fix that problem as well.

[1] https://boringssl.googlesource.com/boringssl/+/refs/heads/master/crypto/kyber/kyber.c#691

[2] https://xkcd.com/221/

--
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.

--

Sophie Schmieg | Information Security Engineer | ISE Crypto | ssch...@google.com

[Iluminada Baturone]

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) before being operative, and the raw data (before any possible conditioning) it provides should be tested to detect quickly and with a high probability any failure in the noise source (by using the recommended Health Tests). 

If a TRNG is so well designed, the raw bits provided have high entropy and no hash is required for post-processing them.

You can see experimental results of the entropy of raw bits provided by TRNGs based on RIng Oscillators in FPGAs in:

https://idus.us.es/bitstream/handle/11441/140518/10.1109jiot.2022.3224298aceptada.pdf?sequence=1&isAllowed=y

Regards,

Iluminada

[Blumenthal, Uri - 0553 - MITLL]

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

This Message Is From an External Sender This message came from outside the Laboratory.

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.

[Sophie Schmieg]

On Mon, May 1, 2023 at 2:53 PM Blumenthal, Uri - 0553 - MITLL <u...@ll.mit.edu> wrote:

This discussion questioning the need to protect RNG output seems to condense to the argument between theoreticians and practitioners.

I'm making my argument very much from the perspective of the practitioner. At scale, SHA3 calls become very expensive, to the point that optimizing away a full SHA3-256 call for no loss of security is way too tempting to give up on. This is especially true for a hash call that is in the critical path of encapsulation itself, where an implementation can not even use caching of reused key to avoid paying this cost. Note that this line of code will be called 2-3 times for every single (m)TLS connection that is getting established, meaning that an unnecessary hash call has a measurable economic and ecological impact.

While I love robust specs and implementations, I am not certain that hashing the output of a DRBG actually counts as robustness. It defends against one specific flaw in a random number generator that is pretty much confined to a single algorithm that is not in use anymore and was never all that popular, and even then the fact that most protocols will include parts of the DRBG output makes it rather meaningless as far as mitigations go.

[Blumenthal, Uri - 0553 - MITLL]

>> This discussion questioning the need to protect RNG output seems to

>> congeal into the argument between theoreticians and practitioners.

>
> I'm making my argument very much from the perspective of the practitioner.

Let me rephrase then: "an argument between idealists and realists". The former believe that the environment will be whatever they declare/require it to be (especially if it's desirable or makes sense for it to be that way), and the latter have learned better. __ __

[Markku-Juhani O. Saarinen]

(sorry for double send again)

Hi All,

I guessed (but didn't know!) that some folks at Google or similar places might make this call and just remove Line 2.

Yeah, the distinction here is between people who have the privilege to understand and carefully control their crypto stack and those whose stack is, uh, chaotic ("my RNG might or might not be an LFSR.") The latter situation of course occurs frequently out there.

I understand Peter's security goal and the XOF random expansion thing is consistent in Kyber and Dilithium and elegant in its way. However many practitioners will inevitably view the direct hashing of RBG output as an instance of someone's  "superhash(x)=SHA3(SHA2(x))" -- because that sort of thing is de facto happening here -- and just cut it out. That's their job as that will prolong the battery life of phones or make the data centre just a little cooler etc, with no impact in security.

I think the "Line 2" hash would look a bit like "superhash" above if it appears in a FIPS standard. Little ad hoc, inelegant, and weird -- given that Kyber is extremely carefully designed overall, with very few superfluous parts.

Anyway, these things are never ideal, but at least we have discussed this particular hash in detail.

Cheers,

Markku

--
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.

[Daniel Apon]

"SHA3(SHA2(x))"

*vomit*

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.

[Rafael Misoczki]

Defense-in-depth is indeed an important strategy to address unforeseen risks in systems in general but not sure applying it at the cryptographic primitive design level is the right thing to do. If we start challenging what each cryptographic primitive building block effectively delivers, we will navigate through a gray zone where it will be pretty hard to reason about security as a whole.

The proposed additional hashing for example, besides leading to a significant compound effect in systems deployed at scale (think of quadrillion hash calls because of this apparent negligible addition), only protects the cryptosystem against a certain type of flaw in the external PRNG. But if we decide to do so, should we not assume that the hash function building block itself (likely an external building block used to implement functions G and H) might also suffer from some unforeseen issues and therefore may benefit from another layer of protection as well? As we can see, this will quickly drag us into a rabbit hole discussion.

I'm usually on the theoreticians' side, fighting against countless requests from SW/HW engineers to optimize/remove that “apparently unnecessary step” in crypto implementations, but here I feel their pain and still don't see clear (or consistent) counter arguments.
 
Given the above, my suggestion would be to remove line 2 of Kyber's encapsulation algorithm.

Best regards, 

Rafael Misoczki

[Blumenthal, Uri - 0553 - MITLL]

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.

[Sophie Schmieg]

Hashing a DRBG does not fix underlying issues with it. In fact this hashing step, just like any deterministic function call, decreases the entropy the DRBG provides (negligibly, but still technically less entropy), I want to make sure that we are on the same page about this, hashing does not produce entropy out of the thin air, and does not fix any flaws of a random number generator that are not related to specifically a backdoor that can be exploited by knowing unhashed outputs (i.e. DUAL_EC_DRBG). A DRBG with a low period will continue to have a low period when you hash its outputs, a DRBG with low entropy will have the exact same entropy when hashed etc. Hashing does not fix generic flaws with a random number generator. I do agree that a TRNG should be hashed (or more accurately run through a DRBG) before usage, but that is not what the Kyber spec calls for, it calls for system randomness, i.e. usually the output of a DRBG seeded with a TRNG.

Note that as long as Kyber_CPA_encrypt is indeed CPA secure with security level l, and the system randomness is a random variable X with codomain {0,1}^256 and entropy S(X) (X not necessarily being uniformly distributed this gives you S(X) <= 256), the security level of the full FO transformed Kyber is min(l, S(X)), hashing changes this to min(l, S(H(X)) <= min(l, S(X)), since the security guarantees of the FO transform do not depend on the input randomness X being uniform, it just will reduce the security level to the entropy of this input distribution.

As for the spec calling for hashing the system rng, that is exactly why I'm writing emails here, before an actual standard exists, so that we change the spec to not waste all this computing power on meaningless hash calculations, Kyber isn't the blockchain, after all.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/C5E1D4A9-BFC3-465E-B5F3-3ED813A1D79D%40ll.mit.edu.

[Peter Schwabe]

"'dustin...@nist.gov' via pqc-forum" <pqc-...@list.nist.gov> wrote:
> All,

Dear Dustin, dear all,

> NIST is planning to incorporate the CRYSTAL-Kyber team's suggestion of
> tweaking the FO transform into the draft standard, as described in Peter
> Schwabe's earlier post

> <https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/WFRDl8DqYQ4/m/54var7dfAQAJ>.

> Any comments or feedback are welcome.

I'm sorry that we didn't notice this earlier: In order to derive the
rejection key from z and c, I propose to use SHAKE256 instead of
SHA3-512. In the proof, this derivation of the rejection key is modelled
as a PRF and not as the same RO that is used to derive the real key, so
it is natural to use a different function here.

Using SHA3-512 would result in a considerable slowdown (compared to
using SHAKE256 and also compared to the round-3 specification), because
of the much smaller rate of SHA3-512 and the fact that the whole
ciphertext (and not just the hash of the ciphertext) is now fed into
this function.

All the best,

Peter

[Kampanakis, Panos]

Just to add a little more data, my colleague Dusan Kostic measured the software performance impact of removing the hash in encaps, but the email alias has not been kind to him, so I am sending the results on his behalf. This is for the official Kyber implementation (not in hardware) with its optimizations in https://github.com/pq-crystals/kyber.

On m5 AWS EC2 instance with Intel(R) Xeon(R) Platinum 8175M CPU @ 2.50GHz, the AVX2 implementation of Kyber encaps takes:

• Kyber512 with hashing 31673, without hashing 30642 cycles. Diff: -3.2%
• Kyber768 with hashing 47415, without hashing 46220 cycles. Diff: -2.5%
• Kyber1024 with hashing 64726, without hashing 63197 cycles. Diff: -2.3%

On a c7g AWS EC2 instance with Graviton 3 CPU, the reference implementation of Kyber encaps takes:

• Kyber512 with hashing 35005, without hashing 34714 cycles. Diff: -0.8%
• Kyber768 with hashing 55146, without hashing 54832 cycles. Diff: -0.6%
• Kyber1024 with hashing 80942, without hashing 80733 cycles. Diff: -0.3%

 

In my opinion, 300-1500 cycles are negligible for most use-cases. Even 5% for a well-performing algorithm like Kyber is insignificant. Personally I think that keeping the hash in the spec is probably worth it as a defense-in-depth mechanism as mentioned previously in this thread.

 

Implementations that consider it important to shave a little more from encapsulation could chose to omit the hash by taking into consideration the theoretical concerns (laid out in this thread). Maybe this could even be documented in the spec.

 

 

 

 

From: 'Bas Westerbaan' via pqc-forum <pqc-...@list.nist.gov>
Sent: Saturday, April 29, 2023 11:09 AM
To: Markku-Juhani O. Saarinen <mjos....@gmail.com>
Cc: Andreas Hülsing <ie...@huelsing.net>; Peter Schwabe <pe...@cryptojedi.org>; dustin...@nist.gov <dustin...@nist.gov>; pqc-forum <pqc-...@list.nist.gov>
Subject: RE: [EXTERNAL][pqc-forum] Discussion about Kyber's tweaked FO transform

 

CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you can confirm the sender and know the content is safe.

 

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.

 

We will not remove that hash, and prefer it not to be removed from the standard.

 

Bas

 

 

--

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/CAMjbhoV-RUxNnWX%3DBZfdEcU2%2B3C2g8gej-WbCrPAeSLLNHPQ_g%40mail.gmail.com.

[Blumenthal, Uri - 0553 - MITLL]

I completely agree with Panos here. Given the data he presented, it doesn’t make sense to keep arguing.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/4667dbd7e5604d2e8afdedbdf2f16c01%40amazon.com.

[Markku-Juhani O. Saarinen]

On Mon, May 8, 2023 at 3:48 PM 'Kampanakis, Panos' via pqc-forum <pqc-...@list.nist.gov> wrote:

(..)

Implementations that consider it important to shave a little more from encapsulation could chose to omit the hash by taking into consideration the theoretical concerns (laid out in this thread). Maybe this could even be documented in the spec.

Hi,

This hash is not doing much harm so I don't want get too stuck on this. But to clarify some things:

It has now become clear that the existence of this hash is actually a form of subtle protest -- it is an expression of mistrust. This is arguably well-deserved, given that highly suspicious RBGs such as MS_DRBG still exist in standards such as ISO 18031.

The Line 2 hash is now even commented as "hash of shame" in the official implementation too (the recently updated "standard" branch): https://github.com/pq-crystals/kyber/blob/a440ac9901e16564d426be9df009a9e3ae05bbf7/ref/kem.c#L85

So I doubt that NIST will want to document what the Line 2 hash is actually is about. There is no theoretical concern, except "I worry that there's <an intelligence agency> in my RBG implementation, and also at the other end of the communication, receiving information from my backdoored up RBG via Decapsulation."🤷 

For defence-in depth: Using a secure RBG -- and strictly enforcing this policy via technical means -- gives broader security benefits than hashing all outputs from a backdoored random number generator (you would need to do that for consistency.) The AES and SHA2 based DRBGs in current NIST standards are fine (Revision 1 of SP 800-90A removed Dual_EC_DRBG in June 2015.)

[Dang, Quynh H. (Fed)]

Hi all,

We appreciate the discussion about Kyber's tweaked FO transform.  While there are arguments that can be made for either including or not including the hash of m during Encaps, NIST is not planning to include this step in the upcoming draft standard for Kyber.

The upcoming standard focuses on FIPS-certifiable implementations, which includes auxiliary functions such as the RGB. In the case of a standardized version of Kyber being deployed in a non-FIPS-certified setting, it is possible than an attacker can back-door the RBG to learn all future outputs.  In this case, NIST believes that adding an extra hash to Kyber will not do much to mitigate the potential harms faced by the jeopardized system.

Regards,

Quynh.

---

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of Markku-Juhani O. Saarinen <mjos....@gmail.com>
Sent: Monday, May 8, 2023 11:33 AM
To: Kampanakis, Panos <kpa...@amazon.com>
Cc: pqc-forum <pqc-...@list.nist.gov>; Moody, Dustin (Fed) <dustin...@nist.gov>
Subject: Re: [pqc-forum] Discussion about Kyber's tweaked FO transform

 

--

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/CA%2BiU_q%3Du9WW4dHcC0_eL4sGMnC9-mEH%2ByUF31taKizxFR6jFBA%40mail.gmail.com.