Stateful hash-based signatures

[Moody, Dustin (Fed)]

Everyone,

      The IETF has announced that the XMSS stateful hash-based signature scheme has been published as RFC 8391.  We hear that the LMS stateful hash-based signature scheme will likely be published as an RFC in the coming months as well.  As we stated in our FAQ:

 

NIST plans to coordinate with other standards organizations, such as the IETF, to develop standards for stateful hash-based signatures. As stateful hash-based signatures do not meet the API requested for signatures, this standardization effort will be a separate process from the one outlined in the call for proposals. It is expected that NIST will only approve a stateful hash-based signature standard for use in a limited range of signature applications, such as code signing, where most implementations will be able to securely deal with the requirement to keep state.

 

      We would like some feedback.  Should NIST start moving forward now with XMSS?  Should we wait until the RFC for LMS is finished?  Is anybody aware of industry using stateful hash-based signatures at this time? 

 

Please let us know, either by replying to the forum, or sending us a message at pqc-co...@nist.gov.

 

Thanks,

 

Dustin Moody

NIST

[Paul Hoffman]

On Jun 13, 2018, at 6:49 AM, Moody, Dustin (Fed) <dustin...@nist.gov> wrote:
> The IETF has announced that the XMSS stateful hash-based signature scheme has been published as RFC 8391. We hear that the LMS stateful hash-based signature scheme will likely be published as an RFC in the coming months as well. As we stated in our FAQ:
>
> NIST plans to coordinate with other standards organizations, such as the IETF, to develop standards for stateful hash-based signatures. As stateful hash-based signatures do not meet the API requested for signatures, this standardization effort will be a separate process from the one outlined in the call for proposals. It is expected that NIST will only approve a stateful hash-based signature standard for use in a limited range of signature applications, such as code signing, where most implementations will be able to securely deal with the requirement to keep state.
>
> We would like some feedback. Should NIST start moving forward now with XMSS? Should we wait until the RFC for LMS is finished? Is anybody aware of industry using stateful hash-based signatures at this time?

On a process note, the IETF did not standardize XMSS, nor is it standardizing LMS. Informational RFCs are explicitly not standards in the IETF sense. They are publications that, in these cases, have been heavily vetted by a group associated with, but not part of, the IETF process, namely the CFRG, which is part of the IRTF.

Informational RFCs are often updated when errors are found or new operational considerations are brought up. It is much easier to update an RFC than, say, a NIST spec. The real question is what value having a parallel NIST specification for XMSS or LMS would be to the community. NIST could just publish documents that reference the RFCs and add NIST's point of view on some topics, add NIST identifiers, and so on.

--Paul Hoffman

[Panos Kampanakis (pkampana)]

Hi Dustin,

 

LDWM (the earlier version of the LMS draft) signatures are used in some Cisco chips for FPGA firmware signing. We also have heard interest in software package signing with stateful schemes.

 

We would like to see LMS and XMSS approved by NIST for some usecases. We tried to compare the two schemes for potential adopters in https://eprint.iacr.org/2017/349 Personally, I would prefer for NIST to evaluate them together after they are both IETF RFCs. FWIW, there might be usecases of stateful schemes that have not been realized yet. For example in PKI, smaller size trees could be used as the Offline Root CA signing scheme given that the Root CA is offline and does not sign live. Such a usecase would assume different stateless schemes are used at the leaves of the cert chain of course.

 

Rgs,

Panos

--
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.
Visit this group at https://groups.google.com/a/list.nist.gov/group/pqc-forum/.

[Mike Gardiner]

Hi Dustin,

I'm aware of some partners in progress with implementing LMS for PKI / Code Signing use but I cannot disclose the names.    

[Sarah McCarthy]

Hello,

I am currently out of office until 18th June (provided I don’t get eaten by a bear), with limited access to email.

Best wishes,
Sarah

[Sarah McCarthy]

Hello,

I am currently out of office until 18th June (provided I don’t get eaten by a bear), with limited access to email.

Best wishes,
Sarah

On 14 Jun 2018, at 03:51, 'Panos Kampanakis (pkampana)' via pqc-forum <pqc-...@list.nist.gov> wrote:

[Rafael Misoczki]

Dear All,

 

We believe there is an industry wide benefit in accelerating NIST endorsement for Hash-Based Signatures (HBS).

 

Intel is researching/experimenting with HBS schemes and we would be inclined to bring sharper focus on schemes that do get formally endorsed by NIST.

 

Since XMSS is already a published RFC scheme, we see significant benefits in starting its NIST approval process now.

 

Best Regards,

Rafael Misoczki

Research Scientist

Intel Labs

[Sheehe, Charles J. (GRC-LCN0)]

Hi

I would like NIST to address the Stateful hash-based signatures.
Address specific use cases where they would be allowed, especially for government organizations.
And recommended parameters.

This is my opinion and does not reflect the position of my agency.

Thanks
Chuck


Charles J. Sheehe III
Computer Engineer
Glenn Research Center
21000 Brookpark Rd
Cleveland, OH 44135
Charles....@NASA.GOV
Office: 216-433-5179

“Omnia vero”

Please let us know, either by replying to the forum, or sending us a message at pqc-co...@nist.gov <javascript:> .

[David Hua]

To my knowledge, this is an "Informational RFC". Any one can create an informational RFC and publish it in IETF as RFC. Informational RFC does not mean that it has been standardized by IETF. The similar scenario is that any one can publish a technical report in ArXiv or ePrint. One can interpret Information RFC as a technical report in ePrint or ArXiv.

thanks!

Hua

----

Everyone,

      The IETF has announced that the XMSS stateful hash-based signature scheme has been published as RFC 8391.  We hear that the LMS stateful hash-based signature scheme will likely be published as an RFC in the coming months as well.  As we stated in our FAQ:

 

NIST plans to coordinate with other standards organizations, such as the IETF, to develop standards for stateful hash-based signatures. As stateful hash-based signatures do not meet the API requested for signatures, this standardization effort will be a separate process from the one outlined in the call for proposals. It is expected that NIST will only approve a stateful hash-based signature standard for use in a limited range of signature applications, such as code signing, where most implementations will be able to securely deal with the requirement to keep state.

 

      We would like some feedback.  Should NIST start moving forward now with XMSS?  Should we wait until the RFC for LMS is finished?  Is anybody aware of industry using stateful hash-based signatures at this time? 

 

Please let us know, either by replying to the forum, or sending us a message at pqc-co...@nist.gov.

 

Thanks,

 

Dustin Moody

NIST

[Dave Finlay]

I think you are selling short the RFC Informational Category in general, and egregiously so when it comes to the publication process. Even the IRTF fast track (RFC 5743) used for RFC 8391 resulted in a 3 year iteration cycle. Independent Submissions, such as the Draft JSON Schema RFP, go through an even more arduous process. Having never published, maybe my comprehension of the relative effort between an RFC and a publication on arVix is lacking here. 

For further review:

  RFC Publication Process: https://www.rfc-editor.org/pubprocess/

  arXiv Publication Process: https://arxiv.org/help/submit

Many Informational RFCs also have a large impact, even though the IETF did not Standards Track them. RFC 1591 comes to mind.

Apologies for tangential rant, just wanted to clarify a perceived misconception.

Dave Finlay

Principal Architect

Everyone Counts, Inc.

Phone: 1.858.361.7627

Email: dave....@everyonecounts.com

Web:   www.everyonecounts.com

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.

To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+unsubscribe@list.nist.gov.

[Russ Housley]

Dustin:

This paper describes the difference between the HSS/LMS and XMSS:  https://eprint.iacr.org/2017/349.pdf

I suspect that you already know about the paper, but others may find it useful.

I am an advocate of the HSS/LMS hash-based algorithm, mostly because it is more straightforward. There is some speed improvement for the additional complexity in XMSS at the cost of a larger signature value.  In my opinion, the speed improvement is not big enough to justify the larger signature size.

In addition, Dave McGrew and his co-authors were very careful to use techniques that are at least 20 years old in the HSS/LMS specification.  This provides a great deal of confidence that there are no lurking patent concerns.  On the other hand, XMSS depends on some techniques that were published as recently as 2016.  I believe that the open source community will embrace the conservative approach taken in the HSS/LMS specification.

For these reasons, I would like to see NIST progress HSS/LMS and XMSS at the same time.

Russ

[Scott Fluhrer (sfluhrer)]

From: Russ Housley <hou...@vigilsec.com>
Sent: Friday, July 06, 2018 11:18 AM
To: Moody, Dustin (Fed) <dustin...@nist.gov>
Cc: pqc-...@list.nist.gov; pqc-co...@nist.gov
Subject: Re: [pqc-forum] Stateful hash-based signatures

 

Dustin:

 

This paper describes the difference between the HSS/LMS and XMSS:  https://eprint.iacr.org/2017/349.pdf

 

I suspect that you already know about the paper, but others may find it useful.

 

I am an advocate of the HSS/LMS hash-based algorithm, mostly because it is more straightforward.

 

Thank you.

 

There is some speed improvement for the additional complexity in XMSS at the cost of a larger signature value.

 

I’m not sure if I understand this, though.  For equivalent parameter sets, the signature sizes of HSS/LMS and XMSS are fairly close; XMSS tends to win on slightly deeper tree hierarchies, but that isn’t large; see table 3 of the paper.

 

As for the speed, LMS/HSS is consistently several times (3x-5x) faster than XMSS for equivalent parameter sets; this is because most of the time for both is spent computing hashes, and XMSS uses 3-5 times as many hashes (actually, hash compression computations) compared to LMS/HSS.

 

One place where you might say that LMS is slower and has a smaller signature is that the currently supported parameter sets in LMS allows that as an option; it allows W=256 (I’m using the XMSS terminology for the Winternitz parameter), and this approximately halves the signature size over W=16, while slowing things down by a factor of 8.

 

However:

-          This is an option; LMS supports W=16 parameter sets as well

-          There is no reason why XMSS couldn’t be extended to support W=256 parameter sets

 

 In my opinion, the speed improvement is not big enough to justify the larger signature size.

 

In addition, Dave McGrew and his co-authors were very careful to use techniques that are at least 20 years old in the HSS/LMS specification.  This provides a great deal of confidence that there are no lurking patent concerns.  On the other hand, XMSS depends on some techniques that were published as recently as 2016.  I believe that the open source community will embrace the conservative approach taken in the HSS/LMS specification.

 

For these reasons, I would like to see NIST progress HSS/LMS and XMSS at the same time.

 

Russ

 

 

On Jun 13, 2018, at 9:49 AM, Moody, Dustin (Fed) <dustin...@nist.gov> wrote:

 

Everyone,

      The IETF has announced that the XMSS stateful hash-based signature scheme has been published as RFC 8391.  We hear that the LMS stateful hash-based signature scheme will likely be published as an RFC in the coming months as well.  As we stated in our FAQ:

 

NIST plans to coordinate with other standards organizations, such as the IETF, to develop standards for stateful hash-based signatures. As stateful hash-based signatures do not meet the API requested for signatures, this standardization effort will be a separate process from the one outlined in the call for proposals. It is expected that NIST will only approve a stateful hash-based signature standard for use in a limited range of signature applications, such as code signing, where most implementations will be able to securely deal with the requirement to keep state.

 

      We would like some feedback.  Should NIST start moving forward now with XMSS?  Should we wait until the RFC for LMS is finished?  Is anybody aware of industry using stateful hash-based signatures at this time? 

 

Please let us know, either by replying to the forum, or sending us a message at pqc-co...@nist.gov.

 

Thanks,

 

Dustin Moody

NIST

 

--

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.