Parameter selection for the selected algorithms
Moody, Dustin (Fed)
Dear all,
NIST has been thinking a lot about which parameter sets to include as part of the standards for the selected algorithms. We wanted to share our current view.
Dilithium
We are planning to include parameter sets corresponding to security categories 2, 3, and 5. We are not planning to include the AES variant.
Falcon
We are planning to include parameter sets corresponding to security categories 1 and 5.
SPHINCS+
We plan to include parameter sets for security categories 1, 3, and 5. We plan to include the simple (and NOT the robust) version. We also plan to include both the fast and small versions. Allowed hash functions will be SHAKE and SHA-2 (SHA-256 for category 1 and a mix of SHA-512 and SHA-256 for categories 3 and 5).
Kyber
We are planning on including parameter sets for categories 1, 3, and 5, though we would highly recommend the category 3 parameter set as the default option. We are not planning on including the 90s variant.
The decision for the category 1 parameter set has been more difficult. There have been extensive discussions if and in what metrics this parameter set achieves the same security as AES-128. It is clear that in the gate-count metric it is a very close call and that in this metric the pre-quantum security of Kyber-512 may be a few bits below the one of AES-128. However, the best known attacks against Kyber-512 require huge amounts of memory and the real attack cost will need to take the cost of (access to) memory into account. This cost is not easy to calculate, as it depends on the memory access patterns of the lattice algorithms used for cryptanalysis, as well as the physical properties of the memory hardware. Nonetheless, barring major improvements in cryptanalysis, it seems unlikely that the cost of memory access will ever become small enough to cause Kyber-512 to fall below category 1 security, in realistic models of security that take these costs into account. We acknowledge there can be different views on our current view to include Kyber-512.
As
a point of clarification: in this email, we refer to parameter sets based on the claimed security strength category where those parameter sets are most recently specified, irrespective of whether those parameter sets actually meet their claimed security level.
That said, our current assessment is that, when realistic memory access costs of known attacks are taken into account, all the parameter sets we plan to standardize do, in fact, meet their claimed security strength categories.
NIST PQC team
Moody, Dustin (Fed)
Sent: Wednesday, November 30, 2022 11:13 AM
To: Moody, Dustin (Fed) <dustin...@nist.gov>
Cc: pqc-forum <pqc-...@list.nist.gov>
Subject: Re: [pqc-forum] Parameter selection for the selected algorithms
Thank you for this update. Quoting from page 18 of the third round
report, which covers potential adoption challenges posed by third-party
patents: 'NIST expects to execute the various agreements prior to
publishing the standard. If the agreements are not executed by the end
of 2022, NIST may consider selecting NTRU instead of KYBER.' Are there
any updates on this front?
Regards,
Arne
D. J. Bernstein
questions at the conference: "It's great to see the progress in opening
things up for free worldwide use. I have two questions: (1) Suppose
someone deploys the current version of Kyber-768 (the round-3 version),
and then in 2024 NIST standardizes a tweaked version of Kyber-768 (maybe
different hash functions or prefix hashing). Am I correctly
understanding the first license to say that the license is only for the
tweaked version, not today's version, so the patent holder can sue for
infringement regarding the deployment? (2) Are these two agreements the
end of NIST's patent negotiations regarding Kyber---i.e., NIST has no
negotiations underway regarding any of the other patent families listed
in https://ntruprime.cr.yp.to/faq.html?"
The NIST representative said he would have to check with NIST's legal
team before answering. I'm looking forward to seeing the answers here.
Various people have also pointed out a further clarification question
that's important to answer: (3) _When_ exactly do the licenses permit
Kyber deployment under those two patent families? Consider, for example,
the following scenario:
* NIST announces at some point in 2023 something like "We're putting
an end to the Kyber modifications, and the final Kyber to be
standardized as NIST MLWE-KEM is as follows." This handles #1.
* Other patent threats also turn out to have been resolved by then
(through buyouts, or through sufficient analysis for the public to
be sure that the patents don't apply). This handles #2.
* A company then asks whether it can safely deploy that version of
Kyber in 2023, or whether it has to wait until the standard is
issued in 2024.
The text posted by NIST says "any time on or after the EFFECTIVE DATE"
but the definition of "EFFECTIVE DATE" seems to have been omitted. The
text is labeled as "relevant language (with modifications for
readability) from the licenses" but doesn't seem to have _all_ relevant
language. Even if the "EFFECTIVE DATE" is in the past, isn't the company
infringing the patent in 2023 since at that point there's no "standard
prescribed by NIST"? It's not clear to me from the existing text how the
issuance of a standard could retroactively remove earlier infringement.
As a procedural matter, back in July, Scott Fluhrer wrote "until we get
the text of the licenses (both the one signed with CNRS and the one to
be signed with Algo Consulting), Cisco cannot use Kyber". It's hard to
imagine a corporate lawyer viewing edited excerpts as an adequate
substitute for the full, unedited license text; hidden contract
provisions can override other provisions. There also seems to be some
confusion regarding the overall status of the license text (e.g., the
NIST representative writing "I'm pretty sure what is posted is verbatim
text" while the NIST text says "modifications for readability"), and
lawyers tend to go on high alert when they see such inconsistencies.
---D. J. Bernstein
P.S. The first time I sent this message, Google bounced it, saying
"The group pqc-...@list.nist.gov has exceeded its quota for total
number of external recipients." So I'm trying again now. Meanwhile it
seems that a message from h...@arnepadmos.com wasn't delivered to the
list.
D. J. Bernstein
> Nonetheless, barring major improvements in cryptanalysis, it seems
> unlikely that the cost of memory access will ever become small enough
> to cause Kyber-512 to fall below category 1 security, in realistic
> models of security that take these costs into account.
(A) In reality, because of the costs of memory _relative to
computation_, all published Kyber-512 attack algorithms are much
more expensive than single-target AES-128 key search.
(B) It seems unlikely for the real costs of memory relative to
computation to improve much.
(C) Ergo, in reality, breaking Kyber-512 more cheaply than
single-target AES-128 key search would require much better attack
algorithms than what has been published.
My current guess is that NIST is _not_ making the following statement, a
statement very different from B:
(D) It seems unlikely that there are much better attack algorithms
against Kyber-512.
But perhaps the scope of "unlikely" was meant not to refer not merely to
the real costs of memory but also to the "barring" hypothesis. Also,
perhaps I'm misunderstanding what "small enough" was meant to indicate.
Clarification would be useful for cryptanalysts and for decisionmakers
interested in long-term security.
---D. J. Bernstein
Derek Atkins
--Derek Atkins
Chief Technology Officer
Office: 203.227.3151 x1343
Direct: 617.623.3745
Mobile: 617.290.5355
Email: DAt...@Veridify.com
This email message may contain confidential, proprietary and / or legally privileged information and intended only for the use of the intended recipient(s) and others specifically authorized. Any disclosure, dissemination, copying, distribution or use of the information contained in this email message, including any attachments, to or by anyone other than the intended recipient is strictly prohibited. If you received this in error, please immediately advise the sender by reply email or at the telephone number above, and then delete, shred, or otherwise dispose of this message.
D. J. Bernstein
> I don't think any clarification is required. I think it is quite
> obvious that NIST is claiming A, B, and C, and is not claiming D, just
> as you "guess"ed.
what A says; and readers who aren't sticking to literal interpretations
could easily understand the "barring ... unlikely" part to indicate D. I
think A+B+C-not-D is a reasonable interpretation, but I'm not at all
sure that this is what NIST meant. NIST should clarify.
---D. J. Bernstein
John Mattsson
I think this seems like a good plan. I assume the suggested changes to the algorithms like the excellent TurboSHAKE idea will be discussed in a separate thread.
>Kyber-512 may be a few bits below the one of AES-128.
I don't think this is a problem in practice. The same is true for Curve25519. I think "realistic models of security" are the only one NIST should consider when making decisions. I think NIST should standardize Kyber-512 and label Kyber-512 as Level I. The public keys and encapsulations in Kyber-768 is a whopping 400 bytes larger which will decrease performance.
BTW, when will we get any news on FIPS 186-5 and SP 800-186? These are very important specifications. RSA and ECC will continue being used for decades, both standalone and as part of hybrid solutions. I would like to see them published yesterday. It seems obvious that the specifications has met some opposition in the publication process. Is NIST planning to give any updates on the situation?
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://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/SA1PR09MB86694461EA7AA74FC0A5A4A5E5159%40SA1PR09MB8669.namprd09.prod.outlook.com.
dustin...@nist.gov
What we meant was: There are various possible improvements in cryptanalysis, including: (i) optimization of lattice algorithms to improve the locality of memory access, (ii) building memory hardware that reduces the cost of non-local memory access, and (iii) other (more fundamental) improvements in the attacks. It seems unlikely that (i) and (ii) alone will be sufficient to cause Kyber-512 to fall below category 1 security, in realistic models of security that take these costs into account.
D. J. Bernstein
> What we meant was: There are various possible improvements in
> cryptanalysis, including: (i) optimization of lattice algorithms to improve
> the locality of memory access, (ii) building memory hardware that reduces
> the cost of non-local memory access, and (iii) other (more fundamental)
> improvements in the attacks. It seems unlikely that (i) and (ii) alone will
> be sufficient to cause Kyber-512 to fall below category 1 security, in
> realistic models of security that take these costs into account.
In the interests of transparency and falsifiability, can NIST please
explain how it arrived at the above likelihood assessment? The pieces
sound like
(1) thinking that known Kyber-512 attacks haven't dropped far below
single-target AES-128 key search (2^143) in gate counts,
(2) thinking that the costs of memory gain many more bits of security
against those Kyber-512 attacks,
(3) thinking that improvements in algorithmic memory locality are
unlikely to reduce Kyber-512's security level by much, and
(4) thinking that improvements in physical memory hardware (compared
to computation) are unlikely to reduce Kyber-512's security level
by much,
but I don't see any documentation of how NIST arrived at any of these
individual conclusions, never mind evaluating the likelihood of error in
the overall conclusion.
Of course, I checked the latest Kyber document from the Kyber team:
https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf
This document addresses #1 but is obviously outdated, estimating 151
where typical estimates today are in the 130s. Which of the newer
attacks and analyses is NIST taking into account? Is NIST's evaluation
of #1 accounting for "known unknowns", and, if so, how?
As for the costs of memory, the 2021 Kyber document makes a brief,
unquantified claim that 135 wouldn't be "catastrophic, in particular
given the massive memory requirements that are ignored in the gate-count
metric". Is this somehow the basis of NIST arriving at #2 or #3 or #4?
---D. J. Bernstein
peter...@gmail.com
Dilithium
We are planning to include parameter sets corresponding to security categories 2, 3, and 5. We are not planning to include the AES variant.
Perlner, Ray A. (Fed)
We can elaborate a little bit further on our reasoning leading to our current assessment that Kyber512 likely meets NIST category I (similar considerations apply to the other parameter sets we plan to standardize for lattice-based schemes.) That said, beyond this message, we don’t think further elaboration of our current position will be helpful. While we did consult among ourselves and with the Kyber team, it’s basically just our considered opinion based on the same publicly available information everyone else has access to. The point of this thread is to seek a broader range of perspectives on whether our current plan to standardize Kyber512 is a good one, and a long back and forth between us and a single researcher does not serve that purpose.
Here's how we see the situation:
In April this year, “Report on the Security of LWE” was published by MATZOV (https://zenodo.org/record/6412487#.Y4-V53bMKUk), describing an attack, assessed in the RAM model to bring some parameter sets, including Kyber512, slightly below their claimed security strength categories. In particular, the report estimates the cost of attacking Kyber512 using a classical lattice attack to be 2^137 bit operations, which is less than the approximately 2^143 bit operations required to classically attack AES-128. However, like previous lattice attacks, the MATZOV attack is based on sieving techniques, which require a large amount of (apparently unstructured) access to a very large memory. The RAM model ignores the cost of this memory access, and while the science of comparing the cost of memory access to other costs involved in a large cryptanalytic attack is not as mature as we would like, it seems overwhelmingly likely that, in any realistic accounting of memory access costs, these will significantly exceed the costs that are assessed by the RAM model for lattice sieving.
The largest practical implementation of sieving techniques we know of, described in detail in “Advanced Lattice Sieving on GPUs, with Tensor Cores” by Ducas, Stevens, and van Woerden (https://eprint.iacr.org/2021/141), was forced by memory access limitations, to adopt settings for bucket size, that would be suboptimal according to the RAM model. It should be noted that, increasing the scale of the instances being attacked to near cryptographic scale would probably require extensive hardware optimization, e.g. by using special purpose ASICs, and these techniques, being generally acknowledged to be less effective against memory-intensive tasks, would likely make memory access even more of a bottleneck.
Additionally, While the Kyber, Dilithium, and Falcon teams did not give a quantitative assessment of the practical cost of memory access during sieving against cryptographic parameters, assessments by the NTRU and NTRUprime teams gave estimates that would suggest the cost of sieving against category 1 parameters, in models that account for the cost of memory access, is something like 20 to 40 bits of security more than would be suggested by the RAM model. (For NTRU’s estimates see section 6.3 of the round 3 specification document available at https://ntru.org/index.shtml . For NTRUprime’s estimates see section 6.11 of https://ntruprime.cr.yp.to/nist/ntruprime-20201007.pdf . The Kyber spec (available at https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf) discusses, but does not quantify, memory access costs in section 5.3 (Q6))
Taking Matzov's estimates of the attack cost to be accurate, only 6 bits of security from memory access costs are required for Kyber512 to meet category 1, so in this case Kyber512 would meet category 1 even if the NTRU and NTRUprime submission significantly overestimate the cost of memory access in lattice sieving algorithms. Further, since about 5 of the 14 claimed bits of security by Matzov involved speedups to local computations in AllPairSearch (as described by section 6 of the MATZOV paper), it is likely that Kyber512 would not be brought below category 1 by the MATZOV attack, as long as state of the art lattice cryptanalyses prior to the MATZOV paper were bottlenecked by memory at all. However, we acknowledge there is some additional uncertainty in the exact complexity of the MATZOV attack (and all other sieving-based lattice attacks) due to the known-unknowns Dan alludes to (described with quantitative estimates in section 5.3 of the Kyber spec.) Nonetheless, even taking the most paranoid values for these known-unknowns (16 bits of security loss), the cost of memory access and/or algorithmically making memory access local, would still need to be less than what both the NTRU and NTRUPrime submissions assume. The low end estimate of approximately 20 bits (from the NTRU submission) is based on a conjecture by Ducas that a fully local implementation of the BGJ1 sieving algorithm is possible. So, in the case that all known-unknowns take on the most paranoid values, this would either require a sieving algorithm with local memory access that is much better than any such published algorithm, and in fact better than any that has been conjectured (at least as far as we are aware), or it would require the approximately 40 bits of additional security quoted as the "real cost of memory access" by the NTRUprime submission to be a massive overestimate. In any event, a lot of things would have to go wrong simultaneously to push the real-world classical cost of known attacks against Kyber512 below category 1, which is why we don't think it's terribly likely.
As a final note, known quantum speedups for lattice sieving are much less effective than Grover’s algorithm for brute force key search, so in the likely scenario where the limiting attack on AES128 is Grover’s algorithm, this would further increase the security margin of Kyber512 over AES128 in practice.
Ray Perlner (NIST PQC)
-----Original Message-----
From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of D. J. Bernstein
Sent: Saturday, December 3, 2022 11:11 AM
To: pqc-forum <pqc-...@list.nist.gov>
Subject: Re: [pqc-forum] Parameter selection for the selected algorithms
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.
D. J. Bernstein
> We can elaborate a little bit further on our reasoning leading to our
> current assessment that Kyber512 likely meets NIST category I
question to make sure I understand the underlying calculations. Within
the space of scenarios reviewed, if we take the particular scenario of
(1) assuming accuracy of 2^137 from the most recent attack paper
taken into account (Matzov) regarding the number of "gates",
(2) assuming this isn't affected by the "known unknowns", and
(3) assuming accuracy of the RAM-cost model in the NTRU Prime
documentation,
then am I correctly gathering that you're calculating the Kyber-512
security level as 2^177 (i.e., 34 bits of security margin compared to
2^143 for AES-128), where this 177 comes from the above 137 plus 40,
where 40 comes from 169 minus 129 on page 103 of the NTRU Prime
documentation, specifically "real" minus "free" for pre-quantum sieving
for sntrup653?
---D. J. Bernstein
Joost Renes
Hi Dustin,
We would like to put forward the option of allowing SHA-2 for the Dilithium message hash mu = H(tr || M).
We are generally in favor of allowing NIST primitives which are already widely deployed and have seen wide adoption in (embedded) systems, such as AES and SHA-2.
While we agree that the simplicity of a single symmetric primitive (SHAKE) is preferable from a design perspective, the decision of a user for adoption and migration towards PQC ultimately is determined by the impact on their system.
There can be a significant difference in performance between HW-accelerated AES and SHA-2, and SHAKE which is mostly not yet available in HW.
Indeed this is a problem that would resolve itself in the medium to long term, but we believe many systems will significantly benefit from using a SHA-2 / AES version where it might make the difference between PQC being feasible or not.
Having that said, we would like to particularly emphasize the message hash itself.
In most performance benchmarks of Dilithium this is barely taken into account: e.g., the specification benchmarks 64-byte messages for AVX2 [1] while pqm4 uses 59-byte messages [2].
However, for many applications the message hash may be a significant part of the performance.
Our investigations for PQC enabled secure boot on one of NXP’s automotive platforms led to the conclusion that with SHA-3 in software the hash of a 128 KiB image takes ~150ms while the remainder only requires ~16.7ms [3, Table 1].
Realistic images for automotive applications can even be megabytes large, making the message hash the dominant cost by far.
For comparison: with HW-accelerated SHA-2 the 128 KiB message hash takes only 0.2ms.
This is not an isolated case; SHA-2 is much more widely adopted in hardware than SHA-3.
Again, to push for PQC adoption it is very helpful to allow this improvement in performance.
This is a very similar argument as for allowing SHA-2 as a parameter set for SPHINCS+.
Finally, this only involves the digest creation which is often done external to the signing/verification (as also discussed in the past on this mailing list) so would have little impact on the complexity of Dilithium itself.
We look forward to hearing your thoughts (and anyone else’s!).
Kind regards,
NXP PQC team
[1] https://github.com/pq-crystals/dilithium/blob/master/ref/test/test_speed.c
[2] https://github.com/mupq/mupq/blob/3b48fa5aff6f5921df5b3444450281daca6d21d1/crypto_sign/speed.c
[3] https://eprint.iacr.org/2022/635.pdf
From: 'Moody, Dustin (Fed)' via pqc-forum <pqc-...@list.nist.gov>
Sent: Wednesday, November 30, 2022 1:26 PM
To: pqc-forum <pqc-...@list.nist.gov>
Subject: [EXT] [pqc-forum] Parameter selection for the selected algorithms
Caution: EXT Email
--
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/SA1PR09MB8669BA6FE29FFC5D68C04E3CE5159%40SA1PR09MB8669.namprd09.prod.outlook.com.
Kampanakis, Panos
Hi Joost,
I think you are suggesting to support a mu calculation in Dilithium based on SHA-256 instead of SHAKE-256 because it will be much faster for bigger messages. A similar argument is made for SPHINCS+’s SHA256 versions. You are also suggesting that SHA-256 should still be supported as a message digest function in the digest-then-sign usecases like the automotive image signing because of the performance benefits. But if you digest the message beforehand, then the hash function used in calculating mu in Dilithium or Hmsg in SPHINCS+ will not make much difference because the message input to the signature is very small.
I want to clarify. Are you saying that if SHA-256 is used in the mu or Hmsg calculations, then these usecases could stop using digest-then-sign? Or are you suggesting to add SHA-256 support for the mu calculation in Dilithium for the general case where the message can be relatively big?
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/AM9PR04MB8161AD39A8403821E0C79400FFE29%40AM9PR04MB8161.eurprd04.prod.outlook.com.
Joost Renes
Hi Panos,
Indeed digest-then-sign is a solution, as we also explored in [3].
But since using SHA2 will be beneficial on such a wide variety of system, we rather prefer it to be included in the standard rather than built on top in an ad hoc fashion.
In particular because Dilithium does consider the digest computation part of the specification: Instead of double-digest computations, we would prefer the option of explicitly allowing SHA2.
Kind regards,
Joost
Markku-Juhani O. Saarinen
> We would like to put forward the option of allowing SHA-2 for the Dilithium message hash mu = H(tr || M).
> I think you are suggesting to support a mu calculation in Dilithium based on SHA-256 instead of SHAKE-256 because it will be much faster for bigger messages.
What was suggested was the computation of mu as "mu = H(tr || M)." with SHA-2. I support this option (and it should be an option), but the instance of H should be SHA-512, not SHA-256.
Rationale: SHA-2 algorithms are widely available and fast (there are effectively two distinct SHA-2 algorithms; "32-bit" SHA-224/256 and "64-bit" SHA-384/512 -- the latter is faster on PCs), and it is good to be able to use an "external" SHA-2 hashing engine in hardware use cases.
- Recall that mu is 512 bits; currently 64 bytes from SHAKE256. The "256" in SHAKE256 refers to the "256-bit" security level; it's an XOF that can produce an output sequence of arbitrary length. Internally SHAKE256 has a 512-bit chaining capacity (just like SHA-512).
- For internal hash/XOF operations, I would prefer to stick to Keccak-based procedures. Otherwise, hardware modules (especially side-channel secure ones) will become much more complex to implement as they would need to support many internal options ("mu" is effectively external to the signature generation and verification logic). A masked Keccak is relatively large but has many redeeming qualities when compared to masked versions of SHA-2.
- Also, we should stay with a single definition of "tr," which is a 256-bit SHAKE256 hash of the public key tr=H(rho || t1). It is also a part of the secret key as Dilithium doesn't need the full public key to perform the private key operation, just the "tr" prefix.
On Monday, December 12, 2022 at 10:17:16 PM UTC+1 joost.renes wrote:
> In particular because Dilithium does consider the digest computation part of the specification: Instead of double-digest computations, we would prefer the option of explicitly allowing SHA2.
Cheers,
- markku
Dr. Markku-Juhani O. Saarinen <mj...@iki.fi>
Joost Renes
Hi Markku,
Thanks for the elaboration: indeed the instance should be SHA-512 and not SHA-256.
Kind regards,
Joost
Peter Schwabe
> Hi Dustin,
Hi Joost,
> We would like to put forward the option of allowing SHA-2 for the Dilithium
> message hash mu = H(tr || M).
"HashedDilithium", i.e., a version that takes the message M, first
computes M' = H(M) with any FIPS-certifiable hash function H at suitable
security level and then run Dilithium.Sign(M',sk)?
All the best,
Peter
Blumenthal, Uri - 0553 - MITLL
Thanks
--
V/R,
Uri
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.
Joost Renes
That would alleviate the performance concerns, so yes we would be in favor
of having such a version in the standard.
Could you elaborate on why this is preferable over allowing this instance of
H to be a FIPS-certifiable function itself?
It seems to me more natural than chaining the digests as would be done in
hashedDilithium.
Kind regards,
Joost
-----Original Message-----
From: Peter Schwabe <pe...@cryptojedi.org>
Sent: Tuesday, December 13, 2022 3:01 PM
To: Joost Renes <joost...@nxp.com>
Cc: pqc-forum <pqc-...@list.nist.gov>; Moody, Dustin (Fed)
<dustin...@nist.gov>
algorithms
Caution: EXT Email
Markku-Juhani O. Saarinen
> We would like to put forward the option of allowing SHA-2 for the
> Dilithium message hash mu = H(tr || M).
> Would it alternatively work for you to standardize also
> "HashedDilithium", i.e., a version that takes the message M, first
> computes M' = H(M) with any FIPS-certifiable hash function H at suitable
> security level and then run Dilithium.Sign(M',sk)?
- Plain (un-prefixed) H(M) with SHA3-512 might be good enough for PQC Level 5 (SHA3 does not have a 256-bit classical attack design upper bound like SHA2), but additional quantum security analysis would be needed. Note that SHA3-512 requires 89% more permutations to process M than SHAKE256; hence it runs at almost half the speed (per kilobyte of data signed/verified) compared to the current Dilithium5 v3.1 design.
Joost Renes
Hi Markku,
Would this not be solved by setting M’ = H(tr||M) and running Dilithium.Sign(M’,sk) as proposed by Peter?
That would have negligible overhead since tr is computed anyway.
(Though I am not convinced yet it is necessary, see questions/comments below.)
“Arguments can be made that the quantum security level could be less, and hence H(M) with SHA2-512 would not meet PQ Security Level 5.”
I don’t really understand this point: it might have lower quantum security, but the same can be argued about AES256.
The definition of the NIST security levels says SHA256 (L2) > AES128 (L1) and SHA384 (L4) > AES192 (L3).
What is special about SHA512 that we do not have SHA512 > AES256 (L5)?
I am not trying to get into a deep technical argument here on quantum algorithms.
But if these are the levels defined by NIST, it would be strange to deviate from them now.
KR,
Joost
From: Markku-Juhani O. Saarinen <mjos....@gmail.com>
Sent: Tuesday, December 13, 2022 7:45 PM
To: pqc-forum <pqc-...@list.nist.gov>
Markku-Juhani O. Saarinen
Hi Markku,
Would this not be solved by setting M’ = H(tr||M) and running Dilithium.Sign(M’,sk) as proposed by Peter?
That would have negligible overhead since tr is computed anyway.
(Though I am not convinced yet it is necessary, see questions/comments below.)
“Arguments can be made that the quantum security level could be less, and hence H(M) with SHA2-512 would not meet PQ Security Level 5.”
I don’t really understand this point: it might have lower quantum security, but the same can be argued about AES256. The definition of the NIST security levels says SHA256 (L2) > AES128 (L1) and SHA384 (L4) > AES192 (L3). What is special about SHA512 that we do not have SHA512 > AES256 (L5)?
Kampanakis, Panos
Another argument against the spec including a prehash version is history. Defining PureEdDSA and PrehashEdDSA didn't help interop and in the end only PureEdDSA got used in most use-cases (eg. TLS, IKEv2, SSH, X509, CMS).
If a use-case needs to prehash the message, it can do so. PKCS#11, for example, offers a PrehashEdDSA mechanism for cases where the message is so big that it can't be cached in the signer or the verifier. Specifically for Dilithium, this is not even necessary because H(tr || M) can be calculated by the signer/verifier without a problem by using the PKCS#11 incremental API (C_SignUpdate/ C_VerifyUpdate).
From: pqc-...@list.nist.gov <pqc-...@list.nist.gov>
On Behalf Of Markku-Juhani O. Saarinen
Sent: Tuesday, December 13, 2022 6:16 PM
To: pqc-forum <pqc-...@list.nist.gov>
Cc: joost.renes <joost...@nxp.com>; pqc-forum <pqc-...@list.nist.gov>; dustin...@nist.gov <dustin...@nist.gov>; Peter Schwabe <pe...@cryptojedi.org>; Markku-Juhani O. Saarinen <mjos....@gmail.com>
Subject: RE: [EXTERNAL][EXT] [pqc-forum] Parameter selection for the selected algorithms
|
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. |
--
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/a0917aa3-1ceb-44be-bcf4-14426cec350dn%40list.nist.gov.
John Mattsson
Hi,
I agree. I think there is a lot to learn from the EdDSA standardization:
- Specifying PureEdDSA and PrehashEdDSA has so far just led to confusion. My preference would be to only have one version.
- Specifying only SHA-512 in Ed25519 was likely also a bad choice. EdDSA has not seen any use in Web Servers. It has also not been used in constrained IoT where the increased performance would have been very welcome. Many older devices only have hardware acceleration
for SHA-256, and many newer IoT systems is looking at using Keccak only. For new algorithms, I think it make sense to go for Keccak only.
https://datatracker.ietf.org/meeting/100/materials/slides-100-t2trg-small-crypto-for-small-iot
- Only specifying a deterministic mode made EdDSA more or less unusable on IoT devices due to side-channel attacks. A purely randomized version works on some devices but not on many others. In general hedged signatures are needed (unless deterministic can be
implemented in side-channel secure way).
Cheers,
John
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/8b5c4a5467944530bf9cd6b77ceefc35%40amazon.com.
Peter Schwabe
> Hi,
Dear all,
> I agree. I think there is a lot to learn from the EdDSA
> standardization:
>
> - Specifying PureEdDSA and PrehashEdDSA has so far just led to
> confusion. My preference would be to only have one version.
>
> - Specifying only SHA-512 in Ed25519 was likely also a bad choice.
> EdDSA has not seen any use in Web Servers. It has also not been used
> in constrained IoT where the increased performance would have been
> very welcome. Many older devices only have hardware acceleration for
> SHA-256, and many newer IoT systems is looking at using Keccak only.
> For new algorithms, I think it make sense to go for Keccak only.
I very much agree with this last argument: I believe that there
shouldn't be different versions of Dilithium with different hash
functions. Going for Keccak only is the obvious choice and the clean
solution that avoids long-term incompatibilies.
However, from Joost's comment and earlier discussions I understand that
there are applications that are bottlenecked by the message hash, and
currently have hardware acceleration only for SHA2. Giving these
legacy applications some way to use the accelerator for the message hash
would ease short-term migration.
The obvious solution is to use fast SHA2 to hash the message and then
sign that hash with clean, purely Keccak-based Dilithium. I don't know
exactly what is required in terms of phrasing in standards to allow this
short-term solution. Somehow supporting such "pre-hashing", at least for
legacy devices, seems better to me than the alternatives, namely
specifying Dilithium with different options for hash functions, or not
migrating those legacy devices to PQC signatures at all.
All the best,
Peter
D. J. Bernstein
Nicolai Brown maintains a list of "Things that use Ed25519":
https://ianix.com/pub/ed25519-deployment.html
---D. J. Bernstein
John Mattsson
Peter Schwabe wrote:
> there are applications that are bottlenecked by the message hash, and
currently
> have hardware acceleration only for SHA2.
My experience from working a lot with constrained device developers is that that a lot of current devices have acceleration of SHA-256 only, i.e., not SHA2 in general.
John
From:
pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of Peter Schwabe <pe...@cryptojedi.org>
Date: Wednesday, 14 December 2022 at 09:46
To: John Mattsson <john.m...@ericsson.com>
Cc: Kampanakis, Panos <kpa...@amazon.com>, Markku-Juhani O. Saarinen <mjos....@gmail.com>, pqc-forum <pqc-...@list.nist.gov>, joost.renes <joost...@nxp.com>, dustin...@nist.gov <dustin...@nist.gov>, Peter Schwabe <pe...@cryptojedi.org>
Subject: Re: [EXT] [pqc-forum] Parameter selection for the selected algorithms
--
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.
Joost Renes
Hi John,
Of course I cannot speak for your or others’ experiences.
Our experience with migrating towards PQC is that the optional SHA2-512 support would significantly help in many situations (e.g., the S32 series processor I mentioned before), which is why we brought up the topic.
Having a standardized way to do this is preferable over an ad hoc method.
Let’s also not completely dismiss SHA-256, since this would provide sufficient security for Dilithium2.
Newer models of many of our systems do have support for SHA3, but the current and previous generations are very much in use and will remain to be used for many years.
If the PQC algorithms are much slower than existing PKC and domain-specific targets cannot be met (e.g., max boot time) then migration is much more complex or even not feasible at all.
Kind regards,
Joost
D. J. Bernstein
for "category 1", i.e., is as hard to break as AES-128, the minimum
security level allowed in NISTPQC.
("Figure 1 shows [performance] for Kyber ... for security categories 1
and 3"; Figure 1 lists Kyber-512 and Kyber-768.)
When NIST started this thread in November 2022, it announced plans to
standardize Kyber-512, and claimed that Kyber-512 is "likely" as hard to
break as AES-128 in "in realistic models of security" that account for
the costs of memory, assuming no "major improvements in cryptanalysis".
NIST's email dated 7 Dec 2022 22:38:45 +0000 _sounds_ like it includes
the components of NIST's calculations of security margins (or deficits)
for Kyber-512 in a particular space of scenarios. (NIST says that the
scenarios with deficits are unlikely.)
However, NIST didn't give any clear end-to-end statements that Kyber-512
has N bits of security margin in scenario X for clearly specified (N,X).
In the absence of such clarity, reviewers have to worry that putting
NIST's stated components together in what _seems_ to be the obvious way,
and then doing the work to disprove what NIST _appears_ to be claiming
about the security margin, will lead to a response claiming that, no,
NIST meant something else. It's natural to ask for clarification.
So I picked a simple scenario that's extremely favorable to Kyber-512,
and asked (see quote below) whether I was correctly gathering that NIST
was claiming 34 bits of security margin for Kyber-512 in that scenario.
I went through exactly which NIST scenario I was picking and what NIST
seemed to be calculating in that scenario.
I was hoping for a prompt "Yes, that's correct" answer. But NIST still
hasn't replied.
I've again gone through NIST's 7 December email, and again concluded
that for this scenario NIST is claiming 34 bits in the way spelled out
below. Is there any way I could be missing something here? Does anyone
see another way to interpret NIST's calculations?
---D. J. Bernstein
> Subject: Re: [pqc-forum] Parameter selection for the selected algorithms
> To: pqc-...@list.nist.gov
> Message-ID: <2022120802100...@cr.yp.to>
David A. Cooper
NIST claimed in its round-3 report in July 2022 that Kyber-512 qualifies
for "category 1", i.e., is as hard to break as AES-128, the minimum
security level allowed in NISTPQC.
("Figure 1 shows [performance] for Kyber ... for security categories 1
and 3"; Figure 1 lists Kyber-512 and Kyber-768.)
As the primary author of Section 2.2.2 of NISTIR 8413, I would like to clarify that everything written in that section was based on the submitters' claimed security categories of each of the parameter sets for each of the schemes. It was not my intention (nor of anyone who helped in writing that section) to make any assertions about whether or not the parameter sets actually provided the claimed level of security. I apologize if my failure to note this in the text caused any confusion.
When NIST started this thread in November 2022, it announced plans to standardize Kyber-512, and claimed that Kyber-512 is "likely" as hard to break as AES-128 in "in realistic models of security" that account for the costs of memory, assuming no "major improvements in cryptanalysis". NIST's email dated 7 Dec 2022 22:38:45 +0000 _sounds_ like it includes the components of NIST's calculations of security margins (or deficits) for Kyber-512 in a particular space of scenarios. (NIST says that the scenarios with deficits are unlikely.) However, NIST didn't give any clear end-to-end statements that Kyber-512 has N bits of security margin in scenario X for clearly specified (N,X). In the absence of such clarity, reviewers have to worry that putting NIST's stated components together in what _seems_ to be the obvious way, and then doing the work to disprove what NIST _appears_ to be claiming about the security margin, will lead to a response claiming that, no, NIST meant something else. It's natural to ask for clarification.
The emai