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
--Derek Atkins
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.
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.
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.
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.
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
Hi Markku,
Thanks for the elaboration: indeed the instance should be SHA-512 and not SHA-256.
Kind regards,
Joost
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>
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)?
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.
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 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.
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
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 email you cited (https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBurXr58Rs/m/xHojUDCaBAAJ), speaks for itself. NIST continues to be interested in people's opinions on whether or not our current plan to standardize Kyber512 is a good one. While reviewers are free, as a fun exercise, to attempt to "disprove what NIST _appears_ to be claiming about the security margin," the results of this exercise would not be particularly useful to the standardization process. NIST's prior assertion