Subject: Re: [lamps] Call for adoption of draft-vangeest-x509-hash-sigs-03

From: Ryan Sleevi <[email-masked]>
Date: Tue, 2 Apr 2019 15:22:42 +0900

Opposed.

It does not seem the concerns raised in the November thread - e.g.
https://mailarchive.ietf.org/arch/msg/spasm/4EP3bX2adJBCmTjBMYazAKQJFU0 -
have been addressed.

Much like we should be careful about introducing CBC or other non-AEAD
constructions in TLS, we should be very careful in introducing algorithms
with critical system failures in the presence of issues widespread in
existing PKIs. Moving from a stateful signature algorithm to a stateless
one seems the best way to achieve the goals stated in the draft, and
without such (significant) risks.

On Tue, Mar 26, 2019 at 9:56 PM Russ Housley <[email-masked]> wrote:

> We talked about the "Algorithm Identifiers for HSS and XMSS for Use in the
> Internet X.509 Public Key Infrastructure" <
> https://www.ietf.org/id/draft-vangeest-x509-hash-sigs-03.txt> document
> today dat the face-to-face meeting session.  It was suggested that the
> document is read for WG adoption.  Please voice your support or concerns on
> the list.
>
> Russ
>
> _______________________________________________
> Spasm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/spasm
>

---

From: Russ Housley <[email-masked]>
Date: Thu, 11 Apr 2019 14:31:49 -0400

Only three people have spoken so fare (2 support; 1 oppose).  We need more participation to make a consensus call.

Russ

> On Mar 26, 2019, at 8:56 AM, Russ Housley <[email-masked]> wrote:
> 
> We talked about the "Algorithm Identifiers for HSS and XMSS for Use in the Internet X.509 Public Key Infrastructure" <https://www.ietf.org/id/draft-vangeest-x509-hash-sigs-03.txt <https://www.ietf.org/id/draft-vangeest-x509-hash-sigs-03.txt>> document today dat the face-to-face meeting session.  It was suggested that the document is read for WG adoption.  Please voice your support or concerns on the list.
> 
> Russ
>

---

From: Adam Langley <[email-masked]>
Date: Thu, 11 Apr 2019 12:00:18 -0700

On Thu, Apr 11, 2019 at 11:31 AM Russ Housley <[email-masked]> wrote:
> We talked about the "Algorithm Identifiers for HSS and XMSS for Use in the Internet X.509 Public Key Infrastructure" <https://www.ietf.org/id/draft-vangeest-x509-hash-sigs-03.txt> document today dat the face-to-face meeting session.  It was suggested that the document is read for WG adoption.  Please voice your support or concerns on the list.

Since you're asking, my worries remain the same as outlined in
November[1] and thus I guess I'm "opposed", although that's a stronger
word that I would select.

There are firmware-signing contexts where size and verification speed
seem to preclude stateless signatures. There one may have to try and
invest in lots of infrastructure to manage the state. But such
contexts are also not using X.509 because of the same size concerns.

SPHINCS isn't an RFC, but it's perfectly sound as a basis for a
stateless signature scheme. (There are several, good, marginal
improvements in NIST submissions but they're not critical if rushing.)
I would go that route rather than throw a stateful primitive at
code-signing CAs and wishing them good luck.

[1] https://mailarchive.ietf.org/arch/msg/spasm/4EP3bX2adJBCmTjBMYazAKQJFU0

Cheers

AGL

--
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: Tim Hollebeek <[email-masked]>
Date: Fri, 12 Apr 2019 19:37:57 +0000

I agree with Russ.

-Tim

From: Spasm <[email-masked]> On Behalf Of Russ Housley
Sent: Friday, March 29, 2019 10:19 AM
To: Quynh Dang <[email-masked]>
Cc: SPASM <[email-masked]>; Daniel Van Geest <[email-masked]>; Jim Schaad <[email-masked]>; Scott Fluhrer <[email-masked]>
Subject: Re: [lamps] Side-channel attack on multi-level trees and key generation of LMS.

I do not agree that this fault-injection attack leads to a SHOULD for single-level trees.

Russ 

On Mar 29, 2019, at 7:04 AM, Dang, Quynh (Fed) <[email-masked] <mailto:[email-masked]> > wrote:

Hi all,

I suggest to add that "When key generation time is not a problem for a single-level tree which provides the desired number of OTS private keys a user has, then the single-tree HBS is a preferred option over the alternative multi-level tree HBSs which provide the same (or close ) number as the desired number of the OTS private keys. 

Multi-level tree HBSs are insecure under fault-injection attack, see "reference to the paper".  Therefore, single-level tree HBSs should be used."

Some text guidance for defenses against the attack is needed. I am not a right person to provide such text.

Regards,

Quynh. 

  _____  

From: Daniel Van Geest < <mailto:[email-masked]> [email-masked]>
Sent: Friday, March 29, 2019 6:34:00 AM
To: Scott Fluhrer (sfluhrer); Jim Schaad; Dang, Quynh (Fed); 'SPASM'
Subject: Re: [lamps] Side-channel attack on multi-level trees and key generation of LMS.

This is an interesting discussion.  Is there anything anyone would like added to draft-vangeest-x509-hash-sigs as a result?  Also note that anything that could be added here would also apply to cms-hash-sigs since HSS supports multiple level trees.

Daniel

On 2019-03-27, 7:00 AM, "Spasm on behalf of Scott Fluhrer (sfluhrer)" < <mailto:[email-masked]> [email-masked] on behalf of  <mailto:[email-masked]> [email-masked]> wrote:

From: Jim Schaad < <mailto:[email-masked]> [email-masked]> 
Sent: Tuesday, March 26, 2019 12:14 PM
To: Scott Fluhrer (sfluhrer) < <mailto:[email-masked]> [email-masked]>; 'Dang, Quynh (Fed)' < <mailto:quynh.dang=[email-masked]> quynh.dang=[email-masked]>; 'SPASM' < <mailto:[email-masked]> [email-masked]>
Subject: RE: [lamps] Side-channel attack on multi-level trees and key generation of LMS.

I understand that, but again there are some trade-offs of memory vs time.  All of the simple tree saving algorithms I have thought of can occasionally require the generation of a large portion of the tree depending on what boundaries one is crossing in the tree, this means that the signing time is not constant.  One can also make gains by doing some pre-computation of expected trees as one goes along.  When you have a tree of trees, one can get lots of speed up by saving the signature for all but the bottom most tree so that only that tree needs to have portions regenerated until you move to a new sub-tree.

Again, there are better algorithms known; as an example to the fractal method I gave a link to before, if we have a H=25 tree (circa 32 million leaf nodes), we can perform a walk by storing a maximum of 158 Merkle node values, and for each signature, performing 6 leaf public key recomputations per signature (not counting the OTS signature generation and a handful of hash computations while we combine Merkle nodes).  For this algorithm, it always has the current authentication path entirely in memory; the entire computation done is performing pre-computation so we’re set up for the next authentication path.

The BDS algorithm works even better if you have minimal storage for internal Merkle nodes; see  <https://gcc01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww-old.cdc.informatik.tu-darmstadt.de%2Freports%2Freports%2FBDS08.pdf&data=02%7C01%7Cquynh.dang%40nist.gov%7Cf6277e7102074843afe408d6b4321776%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C636894524568586678&sdata=cFt0M7zVFWiJbwQCZXbNEBC0ds1SK6zo2uglvXcviHY%3D&reserved=0> https://www-old.cdc.informatik.tu-darmstadt.de/reports/reports/BDS08.pdf              

All of these are space/time trade-offs and one needs to understand what the extremes are on both ends before one says that a huge single tree is better or worse than a lot of small trees, even if the number of levels that are created are the same.

Jim

From: Scott Fluhrer (sfluhrer) < <mailto:[email-masked]> [email-masked]> 
Sent: Tuesday, March 26, 2019 4:28 PM
To: Jim Schaad < <mailto:[email-masked]> [email-masked]>; 'Dang, Quynh (Fed)' < <mailto:quynh.dang=[email-masked]> quynh.dang=[email-masked]>; 'SPASM' < <mailto:[email-masked]> [email-masked]>
Subject: RE: [lamps] Side-channel attack on multi-level trees and key generation of LMS.

Actually, there are algorithms that are able to generate the next authentication path by storing a comparatively small part of the tree, and using only a relatively small number of leaf node evaluations..  For example,  <https://gcc01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.szydlo.com%2Ffractal-jmls.pdf&data=02%7C01%7Cquynh.dang%40nist.gov%7Cf6277e7102074843afe408d6b4321776%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C636894524568596697&sdata=krnCaCoGSCwG%2FXDYPPnijwnp6toouFB82F88Q20H158%3D&reserved=0> http://www.szydlo.com/fractal-jmls.pdf

From: Jim Schaad < <mailto:[email-masked]> [email-masked]> 
Sent: Tuesday, March 26, 2019 11:13 AM
To: 'Dang, Quynh (Fed)' < <mailto:quynh.dang=[email-masked]> quynh.dang=[email-masked]>; Scott Fluhrer (sfluhrer) < <mailto:[email-masked]> [email-masked]>; 'SPASM' < <mailto:[email-masked]> [email-masked]>
Subject: RE: [lamps] Side-channel attack on multi-level trees and key generation of LMS.

There is one other factor to compare in terms of how big the tree is.  For a very large tree, if you do not have the resources to keep the entire private key set (or a large subset of it) then you get into the situation where you regenerate the entire private key tree for each and every signature.  This is part of the trade off between small key size and fast signature generation/usage of time.

Jim

From: Spasm < <mailto:[email-masked]> [email-masked]> On Behalf Of Dang, Quynh (Fed)
Sent: Tuesday, March 26, 2019 3:04 PM
To: Scott Fluhrer (sfluhrer) < <mailto:[email-masked]> [email-masked]>; SPASM < <mailto:[email-masked]> [email-masked]>
Subject: Re: [lamps] Side-channel attack on multi-level trees and key generation of LMS.

The only downside of 1 level tree is its key generation time comparing to multi-level trees. In situations ( such as a code signing application) where 1, 2 or 3 etc... hours of a key generation time is not a problem, then using a big 1 level tree seems better than using a multi-level tree. 

Therefore,  some bigger height numbers for 1-level tree may be desired.

Quynh. 

  _____  

From: Scott Fluhrer (sfluhrer) < <mailto:[email-masked]> [email-masked]>
Sent: Tuesday, March 26, 2019 9:20:05 AM
To: Dang, Quynh (Fed); SPASM
Subject: RE: [lamps] Side-channel attack on multi-level trees and key generation of LMS.

Irom: Spasm < <mailto:[email-masked]> [email-masked]> On Behalf Of Dang, Quynh (Fed)
Sent: Tuesday, March 26, 2019 9:11 AM
To: SPASM < <mailto:[email-masked]> [email-masked]>
Subject: [lamps] Side-channel attack on multi-level trees and key generation of LMS.

Hi all,

Here is the attack I mentioned at the meeting today:  <https://gcc01.safelinks.protection.outlook.com/?url=https%3A%2F%2Feprint.iacr.org%2F2018%2F674%2F20180713%3A140821&data=02%7C01%7Cquynh.dang%40nist.gov%7Cf6277e7102074843afe408d6b4321776%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C636894524568596697&sdata=xsTRh1kObIT8W%2Bt8EWUSRZdEjIC9mDwWiJbdCRK5Zbk%3D&reserved=0> https://eprint.iacr.org/2018/674/20180713:140821.

This is a fault attack (that is, you try to make the signer miscompute something, and then use the miscomputed signature); a signer implementation could implement protections against this (of course, those protections are not free).

I just looked at the LMS's draft, the single tree with height 25 ( 2^25 signatures)  takes only 1..5 hours.

Clarification on this:

*         The test used 15 cores (and so it used a total of circa 1 core-day)

*         This was done with a W=8 parameter set.  This makes the signature shorter (1936 bytes in this case), however it does increase the key generation time; a W=4 parameter set would approximately double the signature size, while decreasing the key generation time by circa a factor of 8.

Regards,

Quynh. 

 

_______________________________________________
Spasm mailing list
 <mailto:[email-masked]> [email-masked]
 <https://www.ietf.org/mailman/listinfo/spasm> https://www.ietf.org/mailman/listinfo/spasm

---

From: Tim Hollebeek <[email-masked]>
Date: Fri, 12 Apr 2019 19:44:02 +0000

We support this work and would implement it.  While there are some
legitimate concerns about state management, we think a standard that
articulates the proper procedures for addressing those concerns is the best
way to resolve that.

Hash-based signatures are an important and well-understood tool for
providing security against attacks based on quantum computing, and failing
to adopt drafts describing the right way of using them will increase the
risks they are implemented unsafely, instead of reducing the risk.

-Tim

From: Spasm <[email-masked]> On Behalf Of Russ Housley
Sent: Thursday, April 11, 2019 2:32 PM
To: SPASM <[email-masked]>
Subject: Re: [lamps] Call for adoption of draft-vangeest-x509-hash-sigs-03

Only three people have spoken so fare (2 support; 1 oppose).  We need more
participation to make a consensus call.

Russ

On Mar 26, 2019, at 8:56 AM, Russ Housley <[email-masked]
<mailto:[email-masked]> > wrote:

We talked about the "Algorithm Identifiers for HSS and XMSS for Use in the
Internet X.509 Public Key Infrastructure"
<https://www.ietf.org/id/draft-vangeest-x509-hash-sigs-03.txt> document
today dat the face-to-face meeting session.  It was suggested that the
document is read for WG adoption.  Please voice your support or concerns on
the list.

Russ

---

From: Jim Schaad <[email-masked]>
Date: Mon, 15 Apr 2019 17:52:50 -0700

I am completely indifferent to the adoption of this draft.  I don't have any
cases where I would use the results of this document.

Jim

From: Spasm <[email-masked]> On Behalf Of Russ Housley
Sent: Thursday, April 11, 2019 11:32 AM
To: SPASM <[email-masked]>
Subject: Re: [lamps] Call for adoption of draft-vangeest-x509-hash-sigs-03

Russ

Russ

---

From: Russ Housley <[email-masked]>
Date: Tue, 23 Apr 2019 16:06:59 -0400

I do not see consensus to adopt this document.  This is the tally:

	Support adoption:  3 people
	Oppose adoption:  2 people
	Indifferent:  1 person

I do not think that this work has a better home in the IETF, but the proponents have not gathered enough support at this time.

We can make some time at the WG session in Montreal for the proponents to try and convince others or offer a different way forward.

Russ

---

From: Russ Housley <[email-masked]>
Date: Tue, 23 Apr 2019 16:08:28 -0400

{Correcting typo in my earlier message}

	Support adoption:  4 people
	Oppose adoption:  2 people
	Indifferent:  1 person

Russ

> On Mar 26, 2019, at 8:56 AM, Russ Housley <[email-masked] <mailto:[email-masked]>> wrote:
>