Preferred hash-based signature algorithm
John Mattsson
Hi,
We appreciate that NIST prioritized standardization of SLH-DSA and that it will be published at the same time as ML-KEM and ML-DSA. If I remember correctly, NIST was previously planning to standardize SLH-DSA later together with NL-DSA.
While ML-DSA will likely be the default algorithm for most use cases, it is good to have the more conservative SLH-DSA standardized. For example, for software and firmware updates.
It would be interesting to hear NISTs and NSAs thoughts on hash-based signatures now that SLH-DSA has been prioritized up. Due to the current mandate in SP 800-208 to not allow the secret keying material to be exported, it is impossible to use LMS and XMSS in many use cases. Especially for firmware update.
Is NSA planning to include SLH-DSA in CNSA 2.0? If so, it would be good if NSA announced that as soon as possible before vendors starts implementing LMS or XMSS. It seems to me like the stateless SLH-DSA should be preferred over the stateful LMS and XMSS.
Cheers,
John Preuß Mattsson
Expert Cryptographic Algorithms and Security Protocols, Ericsson
Daniel Apon
I'm neither a NIST nor NSA employee, but I'm relatively familiar with 800-208..
I've heard this type of concern (i.e. "Due to the current mandate in SP 800-208 to not allow the secret keying material to be exported, it is impossible to use LMS and XMSS in many use cases. Especially for firmware update.") stated elsewhere before in various ways.
My understanding of the non-export requirement in 800-208 is to attempt to ensure the protection of highly sensitive non-cryptographic state of LMS, XMSS, and similar algorithms. Specifically, the monotonically increasing counter.
A simple "nightmare scenario" for accidental mis-use of LMS/XMSS would be for these algorithms' secret-key materials to be stored 'securely' in a virtual machine, and then for this virtual machine to be (naively) cloned by a process that is non-cryptographic in nature; e.g. by a hypervisor or VM-master-controller. With a cloned counter, two VMs might continue issuing digital signatures - from the same counter-state - and immediately break security of the overall system.
That said, in my view, it would certainly be very unfortunate if practitioners felt there was no choice but to abandon LMS/XMSS (for the applications best-suited for their use) in favor of SPHINCS+, due to the massive increase in memory/size/timing costs. It would be much better for LMS/XMSS to be widely adopted for software/firmware update signing than SPHINCS+.
It's not my intent to raise debate whether NIST would consider reviewing 800-208 and issuing an update to ensure that the stateless LMS/XMSS can be conveniently used in the places for which they are intended.
However, it might help serve NIST'ers if you would make a very clear proposal for how, where, and why to allow which secret keying material to be exported.
Is it possible to ensure & retain proper guidance aimed to prevent accidental mis-use of LMS/XMSS while lifting the seemingly burdensome restriction for firmware update applications?
Leaving it up to you; cheers,
--Daniel
--
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/GVXPR07MB9678A0FC5D7B44F88C4F182289F1A%40GVXPR07MB9678.eurprd07.prod.outlook.com.
D. J. Bernstein
> It seems to me like the stateless SLH-DSA should be preferred over the
> stateful LMS and XMSS.
of application integration for a stateless interface, as in SPHINCS+,
than for a stateful interface, as in LMS and XMSS.
Internally, the LMS/XMSS structure is relatively easy to review compared
to SPHINCS+, reducing a different type of security risk, but this isn't
a long-term advantage: all of the structures are going to be completely
computer-verified, the worst-case possibility being that some bug has to
be fixed first. Part of the verification has been done in
https://eprint.iacr.org/2023/408
and the rest is within sight.
The remaining risk is that the hash function isn't good enough. For this
risk, XMSS and SPHINCS+-robust have a reviewability advantage over LMS
and SPHINCS+simple respectively, since they decompose the hash-function
requirements into simpler cryptanalyst-friendly questions rather than
modeling hash functions as random oracles. Given that analyses of
(1) the number of rounds that H needs for collision resistance and
(2) the number of rounds that H needs for preimage resistance
typically come up with different answers, we should expect that
(3) the number of rounds that H needs for signature system S
will have its own answer; XMSS and SPHINCS+-robust are laying out a
path for analyzing this. In the absence of an S-specific analysis for
#3, a reasonable way to control risks is to maximize security margins
for #1 and #2, which means taking SHAKE256 rather than SHA-2.
To summarize, I recommend taking SPHINCS+-robust with SHAKE256 by
default, monitoring progress in verification, and monitoring progress in
hash-function cryptanalysis. If it's necessary to comply with a standard
that can't handle SPHINCS+-robust then I'd recommend SPHINCS+-simple
instead, again with SHAKE256.
For the corner case of an application that really can't afford SPHINCS+
but can afford something smaller, I recommend using XMSS and carefully
checking application integration. People will get this wrong sometimes,
but this foot-cannon is a smaller security risk than Dilithium.
Whichever choice is made, I categorically recommend deploying it as an
extra layer on top of existing cryptography (rather than throwing away
the existing cryptography), so that it's easy for auditors to see that
security isn't getting worse. I don't recommend making exceptions for
well-studied systems, even with full formal verification of software:
such exceptions make the auditor's job more difficult and will end up
adding further delays to post-quantum deployment.
---D. J. Bernstein (speaking for myself)
Jim Goodman
Hello everyone,
There has been a lot of similar sentiments shared by
numerous companies and HSM vendors regarding the
difficulties associated with using stateful HBS schemes
given the constraints of SP800-208.
These concerns motivated a group of us to organize our
thoughts and arrange a meeting with NIST to see what could
be done to make SP800-208 more amenable to allow us to build
systems complying with the requirements and timelines of
CNSA 2.0. That meeting was held on August 14th in Maryland
at NIST's NCCoE facilities, and I've attached a copy of the
slide deck that was presented by the industry consortium.
NIST has taken those thoughts, and the feedback voiced
during the meeting, and is currently considering what, if
anything they can do, to address them. NIST plans to share
their thoughts on the matter at the upcoming ICMC in
Ottawa on Wednesday, September 20th @ 12:00 EDT in an
informal sidebar meeting that Crypto4A will be hosting at
the Shaw Centre where ICMC is being held. The meeting will
also be accessible via Webex for those who can’t attend in
person.
I’m the lucky guy handling the logistics so please feel free
to reach out to me directly (ji...@crypto4a.com) if you are
interested in attending either in person or remotely. We
have limited space in the room so it will be a first-come,
first-served sort of admittance. We plan to distribute the
Webex link to those who indicate they wish to attend
remotely.
Take care.
Jim
========================================================
Jim Goodman, Ph.D. (V) 1-613-454-2222
Crypto4a Inc. (C) 1-613-668-4894
1550A Laperriere Avenue
Ottawa, ON K1Z 7T2
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAPxHsSJG_zDst5GmVCniqA3jkbf6MqTCYv-zBXmTa81B33bEtQ%40mail.gmail.com.
Daniel Apon
"Whichever choice is made, I categorically recommend deploying it as an
extra layer on top of existing cryptography (rather than throwing away
the existing cryptography), so that it's easy for auditors to see that
security isn't getting worse."
Best regards,
--Daniel
--
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/20230914161707.15102.qmail%40cr.yp.to.
D. J. Bernstein
> Whichever choice is made, I categorically recommend deploying it as an
> extra layer on top of existing cryptography (rather than throwing away
> the existing cryptography), so that it's easy for auditors to see that
> security isn't getting worse. I don't recommend making exceptions for
> well-studied systems, even with full formal verification of software:
> such exceptions make the auditor's job more difficult and will end up
> adding further delays to post-quantum deployment.
> I'm sorry for my personal confusion here, I just want to be clear (for
> myself) that I understand what you're advocating -- you're recommending to
> where LMS/XMSS seem useful?
What I wrote is not specific to particular cryptosystems. It is a
simple, easy to audit, categorical recommendation. It applies to all
applications upgrading from existing cryptography to post-quantum
cryptography. It applies to all post-quantum KEMs and all post-quantum
signature systems. It applies to whichever encryption and signature
systems were already in place. It says that the post-quantum system is
added as an extra layer (e.g., keep signing with the existing system
_and_ sign with the new system, of course making sure to verify both
signatures), rather than as a replacement for the existing layer.
Giving auditors the choice between the old P and the new P+Q makes it as
easy as possible to see that the upgrade doesn't hurt security. Giving
auditors the choice between the old P and the new Q creates unnecessary
slowdowns: people worry that Q is going to be broken, and spend time
figuring out how to deal with this risk.
It's reasonable for people to worry. Half of the submissions to NISTPQC
were shown not to meet their stated security goals. For Compact LWE
(lattices) and qTESLA-s (lattices) and Rainbow-I (MQ) and Round2
(lattices) and SIKE (isogenies) and a dozen other submissions, the
attacks ran in a weekend on a laptop. Some of the attacks didn't appear
until years after the submissions.
There's a reasonable counterargument saying that SPHINCS+ is in a
different position. But auditors who have dealt with one cryptographic
failure after another will remember that they heard overconfident
arguments for many of those broken systems. How are they supposed to
distinguish those arguments from the arguments for SPHINCS+?
There are ways to answer this question---but getting into the details is
missing the basic procedural point here. When people are worried about
the risk that switching from P to Q will lose security, spending time
trying to convince them that they shouldn't be worried is delaying
deployment compared to cutting this out of the critical path and simply
recommending P+Q.
Daniel Apon
--
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/20230915013724.27510.qmail%40cr.yp.to.
Iluminada Baturone
Dear all,
if anyone is interested, we were faced with the problem of state management in constrained IoT devices using stateful HBS for device attestation and, as has been commented on this forum, we thought that SPHINCS+ was too heavy for certain devices. We finally came to the conclusion that it would be interesting to play with one-time HBS as well. A solution for this is suggested in:
Roberto Román, Rosario Arjona and Iluminada Baturone. "A lightweight remote attestation using PUFs and hash-based signatures for low-end IoT devices". Future Generation Computer Systems (2023). https://doi.org/10.1016/j.future.2023.06.008
Our solution includes the use of a Physically Unclonable Function (PUF) as well.
Best regards,
Iluminada.