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

From: Russ Housley <[email-masked]>
Date: Tue, 26 Mar 2019 08:56:40 -0400

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: "Salz, Rich" <[email-masked]>
Date: Tue, 26 Mar 2019 12:59:21 +0000

Yes to adoption

From: Russ Housley <[email-masked]>
Date: Tuesday, March 26, 2019 at 1:56 PM
To: "[email-masked]" <[email-masked]>
Subject: [lamps] Call for adoption of draft-vangeest-x509-hash-sigs-03

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: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 26 Mar 2019 12:59:44 +0000

Support

From: Spasm <[email-masked]> On Behalf Of Russ Housley
Sent: Tuesday, March 26, 2019 8:57 AM
To: SPASM <[email-masked]>
Subject: [lamps] Call for adoption of draft-vangeest-x509-hash-sigs-03

Russ

---

From: "Dang, Quynh (Fed)" <[email-masked]>
Date: Tue, 26 Mar 2019 13:10:38 +0000

Hi all,

Here is the attack I mentioned at the meeting today: https://eprint.iacr.org/2018/674/20180713:140821.

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

Regards,

Quynh.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 26 Mar 2019 13:20:05 +0000

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

Hi all,

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).

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.

---

From: "Dang, Quynh (Fed)" <[email-masked]>
Date: Tue, 26 Mar 2019 14:03:56 +0000

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) <[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.

Hi all,

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

Clarification on this:

Regards,

Quynh.

---

From: Jim Schaad <[email-masked]>
Date: Tue, 26 Mar 2019 16:12:50 +0100

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 <[email-masked]> On Behalf Of Dang, Quynh (Fed)
Sent: Tuesday, March 26, 2019 3:04 PM
To: Scott Fluhrer (sfluhrer) <[email-masked]>; SPASM <[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. 

Quynh. 

  _____  

From: Scott Fluhrer (sfluhrer) <[email-masked]
<mailto:[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 <[email-masked] <mailto:[email-masked]> > On
Behalf Of Dang, Quynh (Fed)
Sent: Tuesday, March 26, 2019 9:11 AM
To: SPASM <[email-masked] <mailto:[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://eprint.iacr.org/2018/674/20180713:140821
<https://gcc01.safelinks.protection.outlook.com/?url=https%3A%2F%2Feprint.ia
cr.org%2F2018%2F674%2F20180713%3A140821&data=02%7C01%7Cquynh.dang%40nist.gov
%7C17afe62f6ae74a858cbf08d6b1edc737%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7
C0%7C636892032138187826&sdata=9u3pPjSd5ErMGIiBVoyV%2BjwwRyreeZJm4U7ONsQPU5w%
3D&reserved=0> .

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.

---

From: "Dang, Quynh (Fed)" <[email-masked]>
Date: Tue, 26 Mar 2019 15:21:18 +0000

________________________________
From: Jim Schaad <[email-masked]>
Sent: Tuesday, March 26, 2019 11:12 AM
To: Dang, Quynh (Fed); 'Scott Fluhrer (sfluhrer)'; 'SPASM'
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.

Quynh: You generate a OTS private key whenever you need it from a SEED: this is the same with multi-level tree.

Quynh.

This is part of the trade off between small key size and fast signature generation/usage of time.

Jim

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

Quynh.

From: Scott Fluhrer (sfluhrer) <[email-masked]<mailto:[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 <[email-masked]<mailto:[email-masked]>> On Behalf Of Dang, Quynh (Fed)
Sent: Tuesday, March 26, 2019 9:11 AM
To: SPASM <[email-masked]<mailto:[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://eprint.iacr..org/2018/674/20180713:140821<https://gcc01.safelinks.protection.outlook.com/?url=https%3A%2F%2Feprint.iacr.org%2F2018%2F674%2F20180713%3A140821&data=02%7C01%7Cquynh.dang%40nist.gov%7C8d6a1d790ec0480aafe408d6b1fd9160%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C636892099954210337&sdata=2VcGnAW6UEsdbDbU5wcB5tBSI4gL7H3%2F1xVeXzIW39w%3D&reserved=0>.

Clarification on this:

Regards,

Quynh.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 26 Mar 2019 15:27:40 +0000

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, http://www.szydlo.com/fractal-jmls.pdf

From: Jim Schaad <[email-masked]>
Sent: Tuesday, March 26, 2019 11:13 AM
To: 'Dang, Quynh (Fed)' <quynh.dang=[email-masked]>; Scott Fluhrer (sfluhrer) <[email-masked]>; 'SPASM' <[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 <[email-masked]<mailto:[email-masked]>> On Behalf Of Dang, Quynh (Fed)
Sent: Tuesday, March 26, 2019 3:04 PM
To: Scott Fluhrer (sfluhrer) <[email-masked]<mailto:[email-masked]>>; SPASM <[email-masked]<mailto:[email-masked]>>
Subject: Re: [lamps] Side-channel attack on multi-level trees and key generation of LMS.

Quynh.

Hi all,

Clarification on this:

Regards,

Quynh.

---

From: Jim Schaad <[email-masked]>
Date: Tue, 26 Mar 2019 16:29:41 +0100

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

  _____  

From: Jim Schaad <[email-masked] <mailto:[email-masked]> >
Sent: Tuesday, March 26, 2019 11:12 AM
To: Dang, Quynh (Fed); 'Scott Fluhrer (sfluhrer)'; 'SPASM'
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. 

Quynh: You generate a OTS private key whenever you need it from a SEED: this
is the same with multi-level tree.  

Jim: You also need to generate the path from the leaf to the root.  Since
this path changes for every message you sign, you also need to do some
regeneration of the path if you don't keep all (or a large set) of the leaf
OTS public keys.

Quynh. 

This is part of the trade off between small key size and fast signature
generation/usage of time.

Jim

From: Spasm <[email-masked] <mailto:[email-masked]> > On
Behalf Of Dang, Quynh (Fed)
Sent: Tuesday, March 26, 2019 3:04 PM
To: Scott Fluhrer (sfluhrer) <[email-masked] <mailto:[email-masked]>
>; SPASM <[email-masked] <mailto:[email-masked]> >

Quynh. 

  _____  

Hi all,

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

Clarification on this:

 

Regards,

Quynh.

---

From: Tim Hollebeek <[email-masked]>
Date: Tue, 26 Mar 2019 15:45:33 +0000

(chair hat off)

There are implementations that try to only hold the expanded private key in
HSM memory and never outside the HSM.  So there are space concerns as well
as CPU time concerns that may limit total tree size.  Remember that for some
use-cases, it is desirable to be able to use relatively small and
underpowered HSMs, especially for relatively rare operations like
code-signing.

And as I mentioned this afternoon, "only two hours" already pushes the
boundaries of what is feasible as part of a key generation ceremony.

I can appreciate the desire to use single-level trees in some use cases, but
there are other practical use cases where multi-level trees have some very
desirable characteristics.  In fact, single-level trees may be completely
infeasible.

This is already a concern with some of the implementations we have played
with today.  Undoubtably even more use cases will come up in the future.

The flexibility that multi-level trees allow is very important.  We just
need to make sure that we provide the appropriate advice to make sure that
they are being used in a secure way.

-Tim

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

From: Dang, Quynh (Fed) <[email-masked] <mailto:[email-masked]> > 
Sent: Tuesday, March 26, 2019 4:21 PM
To: Jim Schaad <[email-masked] <mailto:[email-masked]> >;
'Scott Fluhrer (sfluhrer)' <[email-masked] <mailto:[email-masked]>
>; 'SPASM' <[email-masked] <mailto:[email-masked]> >

  _____  

Quynh. 

Jim

Quynh. 

  _____  

Hi all,

Clarification on this:

 

Regards,

Quynh.

---

From: "Dang, Quynh (Fed)" <[email-masked]>
Date: Tue, 26 Mar 2019 16:02:58 +0000

A HSM holds the LMS private key (the full LMS private key) of a small signing leaf tree is the same with the HSM holds the equivalent number of OTS private keys from a 1-level tree.

So, the situation is the same for both cases.

Quynh.

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

(chair hat off)

There are implementations that try to only hold the expanded private key in HSM memory and never outside the HSM.  So there are space concerns as well as CPU time concerns that may limit total tree size.  Remember that for some use-cases, it is desirable to be able to use relatively small and underpowered HSMs, especially for relatively rare operations like code-signing.

And as I mentioned this afternoon, “only two hours” already pushes the boundaries of what is feasible as part of a key generation ceremony.

I can appreciate the desire to use single-level trees in some use cases, but there are other practical use cases where multi-level trees have some very desirable characteristics.  In fact, single-level trees may be completely infeasible.

This is already a concern with some of the implementations we have played with today.  Undoubtably even more use cases will come up in the future.

The flexibility that multi-level trees allow is very important.  We just need to make sure that we provide the appropriate advice to make sure that they are being used in a secure way.

-Tim

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

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

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

Jim: You also need to generate the path from the leaf to the root.  Since this path changes for every message you sign, you also need to do some regeneration of the path if you don’t keep all (or a large set) of the leaf OTS public keys.

Quynh.

Jim

Quynh.

Hi all,

Clarification on this:

Regards,

Quynh.

---

From: Jim Schaad <[email-masked]>
Date: Tue, 26 Mar 2019 17:13:30 +0100

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.

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) <[email-masked]> 
Sent: Tuesday, March 26, 2019 4:28 PM
To: Jim Schaad <[email-masked]>; 'Dang, Quynh (Fed)'
<quynh.dang=[email-masked]>; 'SPASM' <[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,
http://www.szydlo.com/fractal-jmls.pdf 

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

Jim

Quynh. 

  _____  

Hi all,

Clarification on this:

 

Regards,

Quynh.

---

From: "Dang, Quynh (Fed)" <[email-masked]>
Date: Tue, 26 Mar 2019 16:21:23 +0000

time and memory trade-offs are applicable to both cases. Think the multi-level tree is a tree, like a big 1-level tree.

Quynh.

________________________________
From: Spasm <[email-masked]> on behalf of Jim Schaad <[email-masked]>
Sent: Tuesday, March 26, 2019 12:13:30 PM
To: 'Scott Fluhrer (sfluhrer)'; 'Dang, Quynh (Fed)'; 'SPASM'
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.

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) <[email-masked]>
Sent: Tuesday, March 26, 2019 4:28 PM
To: Jim Schaad <[email-masked]>; 'Dang, Quynh (Fed)' <quynh.dang=[email-masked]>; 'SPASM' <[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, http://www.szydlo.com/fractal-jmls.pdf<https://gcc01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.szydlo.com%2Ffractal-jmls.pdf&data=02%7C01%7Cquynh.dang%40nist.gov%7Cdff17ae48c7244b4d0be08d6b2060b46%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C636892136357856166&sdata=EfECdJowp9SvSbwh7RtHD1OHVA2dBU7I3DF%2FK%2FI7J%2BU%3D&reserved=0>

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

Jim

Quynh.

Hi all,

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

Clarification on this:

Regards,

Quynh.

---

From: Tim Hollebeek <[email-masked]>
Date: Wed, 27 Mar 2019 09:08:31 +0000

Except that a two level tree is not like a big one level tree.

For an N node one level tree, you can typically reduce the number of nodes
that need to be managed at a time to 2 x sqrt(N), by using two level trees
and only keeping one subtree around at a time.

You also don't have to generate all the subtrees in advance.

-Tim

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

time and memory trade-offs are applicable to both cases. Think the
multi-level tree is a tree, like a big 1-level tree. 

Quynh. 

  _____  

From: Spasm <[email-masked] <mailto:[email-masked]> > on
behalf of Jim Schaad <[email-masked] <mailto:[email-masked]>

Jim

From: Scott Fluhrer (sfluhrer) <[email-masked]
<mailto:[email-masked]> > 
Sent: Tuesday, March 26, 2019 4:28 PM
To: Jim Schaad <[email-masked] <mailto:[email-masked]> >;
'Dang, Quynh (Fed)' <quynh.dang=[email-masked]
<mailto:quynh.dang=[email-masked]> >; 'SPASM' <[email-masked]
<mailto:[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,
http://www.szydlo.com/fractal-jmls.pdf
<https://gcc01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.szydlo
.com%2Ffractal-jmls.pdf&data=02%7C01%7Cquynh.dang%40nist..gov%7Cdff17ae48c72
44b4d0be08d6b2060b46%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C6368921363
57856166&sdata=EfECdJowp9SvSbwh7RtHD1OHVA2dBU7I3DF%2FK%2FI7J%2BU%3D&reserved
=0>  

Jim

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. 

Quynh. 

  _____  

Hi all,

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

Clarification on this:

 

Regards,

Quynh.

---

From: "Dang, Quynh (Fed)" <[email-masked]>
Date: Wed, 27 Mar 2019 09:18:22 +0000

________________________________
From: Tim Hollebeek <[email-masked]>
Sent: Wednesday, March 27, 2019 5:08 AM
To: Dang, Quynh (Fed); Jim Schaad; 'Scott Fluhrer (sfluhrer)'; 'SPASM'
Subject: RE: [lamps] Side-channel attack on multi-level trees and key generation of LMS.

For an N node one level tree, you can typically reduce the number of nodes that need to be managed at a time to 2 x sqrt(N), by using two level trees and only keeping one subtree around at a time.

Hi Tim, can you clarify what you are saying here ?

You also don’t have to generate all the subtrees in advance.

That has been said before: the downside of a big-level tree is key generation time comparing to the multi-level trees.

Quynh.

-Tim

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

Quynh.

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

Jim

From: Scott Fluhrer (sfluhrer) <[email-masked]<mailto:[email-masked]>>
Sent: Tuesday, March 26, 2019 4:28 PM
To: Jim Schaad <[email-masked]<mailto:[email-masked]>>; 'Dang, Quynh (Fed)' <quynh.dang=[email-masked]<mailto:quynh.dang=[email-masked]>>; 'SPASM' <[email-masked]<mailto:[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, http://www.szydlo.com/fractal-jmls.pdf<https://gcc01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.szydlo.com%2Ffractal-jmls.pdf&data=02%7C01%7Cquynh.dang%40nist..gov%7Cdff17ae48c7244b4d0be08d6b2060b46%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C636892136357856166&sdata=EfECdJowp9SvSbwh7RtHD1OHVA2dBU7I3DF%2FK%2FI7J%2BU%3D&reserved=0>

Jim

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.

Quynh.

Hi all,

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

Clarification on this:

Regards,

Quynh.

---

From: "Dang, Quynh (Fed)" <[email-masked]>
Date: Wed, 27 Mar 2019 09:23:35 +0000

The trick of memory and time (computation) trade-offs is that either you keep a hash value(the parent node) of its child nodes or you compute the parent node on the fly from the child nodes and that is the same for a small sub-tree or a big tree.

Quynh.

Sent: Wednesday, March 27, 2019 5:08:31 AM

-Tim

Quynh.

Jim

Jim

Quynh.

Hi all,

Clarification on this:

Regards,

Quynh.

---

From: Russ Housley <[email-masked]>
Date: Wed, 27 Mar 2019 05:44:20 -0400

This was discussed briefly in the SUIT WG today, and it was observed that a small tree of providing 32 signatures is acceptable in many cases, and the last update can be reserved for installing a new trust anchor for a new tree.

Russ

> On Mar 26, 2019, at 10:03 AM, Dang, Quynh (Fed) <quynh.dang=[email-masked]> wrote:
> 
> From: Scott Fluhrer (sfluhrer) <[email-masked] <mailto:[email-masked]>>
> Irom: Spasm <[email-masked] <mailto:[email-masked]>> On Behalf Of Dang, Quynh (Fed)
> To: SPASM <[email-masked] <mailto:[email-masked]>>
> Here is the attack I mentioned at the meeting today: https://eprint.iacr.org/2018/674/20180713:140821 <https://gcc01.safelinks.protection.outlook.com/?url=https%3A%2F%2Feprint.iacr.org%2F2018%2F674%2F20180713%3A140821&data=02%7C01%7Cquynh.dang%40nist.gov%7C17afe62f6ae74a858cbf08d6b1edc737%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C636892032138187826&sdata=9u3pPjSd5ErMGIiBVoyV%2BjwwRyreeZJm4U7ONsQPU5w%3D&reserved=0>.
>  
> 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
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/spasm <https://www.ietf.org/mailman/listinfo/spasm>

---

From: Russ Housley <[email-masked]>
Date: Wed, 27 Mar 2019 05:54:56 -0400

Quynh:

That is not correct. In one big tree, all of the nodes need to be populated to generate the public key.  In a tree of trees, the top-most tree must be populated and then one of the subordinate trees, then a leaf on the top-most tree is used to sign the public key of the subordinate tree.  One does not have to populate the second subordinate tree until the first one is consumed.

Russ

> On Mar 26, 2019, at 12:21 PM, Dang, Quynh (Fed) <[email-masked]> wrote:
> 
> From: Spasm <[email-masked] <mailto:[email-masked]>> on behalf of Jim Schaad <[email-masked] <mailto:[email-masked]>>
> To: Jim Schaad <[email-masked] <mailto:[email-masked]>>; 'Dang, Quynh (Fed)' <quynh.dang=[email-masked] <mailto:quynh.dang=[email-masked]>>; 'SPASM' <[email-masked] <mailto:[email-masked]>>
> 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,http://www.szydlo.com/fractal-jmls.pdf <https://gcc01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.szydlo.com%2Ffractal-jmls.pdf&data=02%7C01%7Cquynh.dang%40nist..gov%7Cdff17ae48c7244b4d0be08d6b2060b46%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C636892136357856166&sdata=EfECdJowp9SvSbwh7RtHD1OHVA2dBU7I3DF%2FK%2FI7J%2BU%3D&reserved=0>
>  
> From: Jim Schaad <[email-masked] <mailto:[email-masked]>> 
> To: 'Dang, Quynh (Fed)' <quynh.dang=[email-masked] <mailto:quynh.dang=[email-masked]>>; Scott Fluhrer (sfluhrer) <[email-masked] <mailto:[email-masked]>>; 'SPASM' <[email-masked] <mailto:[email-masked]>>
> From: Spasm <[email-masked] <mailto:[email-masked]>> On Behalf Of Dang, Quynh (Fed)
> To: Scott Fluhrer (sfluhrer) <[email-masked] <mailto:[email-masked]>>; SPASM <[email-masked] <mailto:[email-masked]>>
> Here is the attack I mentioned at the meeting today: https://eprint.iacr..org/2018/674/20180713:140821 <https://gcc01.safelinks.protection.outlook.com/?url=https%3A%2F%2Feprint.iacr.org%2F2018%2F674%2F20180713%3A140821&data=02%7C01%7Cquynh.dang%40nist.gov%7Cdff17ae48c7244b4d0be08d6b2060b46%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C636892136357866162&sdata=MQDZ%2F6NEXUCdvUivnHwRVH0bXgIQb4D5GbCTNovZ3cg%3D&reserved=0>.
>

---

From: "Dang, Quynh (Fed)" <[email-masked]>
Date: Wed, 27 Mar 2019 10:20:51 +0000

Hi Russ,

That is not the time and memory trade offs that has  been discussed. Time and memory trade-offs are different ways to perform/build validation paths.

That is the downside of 1-level tree: key generation time: the whole big tree must be generated.

Quynh,

________________________________
From: Russ Housley <[email-masked]>
Sent: Wednesday, March 27, 2019 5:54 AM
To: Dang, Quynh (Fed)
Cc: SPASM
Subject: Re: [lamps] Side-channel attack on multi-level trees and key generation of LMS.

Quynh:

Russ

On Mar 26, 2019, at 12:21 PM, Dang, Quynh (Fed) <[email-masked]<mailto:[email-masked]>> wrote:

Quynh.

Jim

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,http://www.szydlo.com/fractal-jmls.pdf<https://gcc01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.szydlo.com%2Ffractal-jmls.pdf&data=02%7C01%7Cquynh.dang%40nist..gov%7Cdff17ae48c7244b4d0be08d6b2060b46%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C636892136357856166&sdata=EfECdJowp9SvSbwh7RtHD1OHVA2dBU7I3DF%2FK%2FI7J%2BU%3D&reserved=0>

Jim

Quynh.

Hi all,

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

Clarification on this:

Regards,
Quynh.

_______________________________________________
Spasm mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/spasm<https://gcc01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Fmailman%2Flistinfo%2Fspasm&data=02%7C01%7Cquynh.dang%40nist.gov%7Cfb3f52679da440d9f14e08d6b29a4b0a%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C636892773087924754&sdata=ov%2BJjShHxgP5ErZxuLNtgsRTLuOL2mYVX%2BDcrd%2FfEB8%3D&reserved=0>

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 27 Mar 2019 10:59:55 +0000

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

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://www-old.cdc.informatik.tu-darmstadt.de/reports/reports/BDS08.pdf

Jim

Jim

Quynh.

Hi all,

Clarification on this:

Regards,

Quynh.

---

From: Daniel Van Geest <[email-masked]>
Date: Fri, 29 Mar 2019 10:34:00 +0000

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)" <[email-masked]<mailto:[email-masked]> on behalf of [email-masked]<mailto:[email-masked]>> wrote:

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://www-old.cdc.informatik.tu-darmstadt.de/reports/reports/BDS08.pdf

Jim

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, http://www.szydlo.com/fractal-jmls.pdf

Jim

Quynh.

Hi all,

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.

---

From: "Dang, Quynh (Fed)" <[email-masked]>
Date: Fri, 29 Mar 2019 11:04:14 +0000

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 <[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.

Daniel

The BDS algorithm works even better if you have minimal storage for internal Merkle nodes; see https://www-old.cdc.informatik.tu-darmstadt.de/reports/reports/BDS08.pdf<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>

Jim

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, http://www.szydlo.com/fractal-jmls.pdf<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>

Jim

Quynh.

Hi all,

Here is the attack I mentioned at the meeting today: https://eprint.iacr.org/2018/674/20180713:140821<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>.

Clarification on this:

Regards,

Quynh.

---

From: Russ Housley <[email-masked]>
Date: Fri, 29 Mar 2019 10:19:08 -0400

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]> wrote:
> 
> Hi all,
> 
> From: Daniel Van Geest <[email-masked] <mailto:[email-masked]>>
> On 2019-03-27, 7:00 AM, "Spasm on behalf of Scott Fluhrer (sfluhrer)" <[email-masked] <mailto:[email-masked]> on behalf of [email-masked] <mailto:[email-masked]>> wrote:
>  
>  
> To: Scott Fluhrer (sfluhrer) <[email-masked] <mailto:[email-masked]>>; 'Dang, Quynh (Fed)' <quynh.dang=[email-masked] <mailto:quynh.dang=[email-masked]>>; 'SPASM' <[email-masked] <mailto:[email-masked]>>
> The BDS algorithm works even better if you have minimal storage for internal Merkle nodes; see https://www-old.cdc.informatik.tu-darmstadt.de/reports/reports/BDS08.pdf <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>              
>  
> 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, http://www.szydlo.com/fractal-jmls.pdf <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>
>  
> Here is the attack I mentioned at the meeting today: https://eprint.iacr.org/2018/674/20180713:140821 <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>.
>

---

From: "Panos Kampanakis (pkampana)" <[email-masked]>
Date: Sat, 30 Mar 2019 04:55:00 +0000

Indeed there are protections against multilevel tree fault attacks. Single level trees are not the only solution. As stated in section 4 of the paper Quynh referenced, the protection is to cache the OTS of the layers so you can check against them if recomputing. That way someone could not inject a fault for the same message and private key and then use it to graft his own subtree. Something like that with an informative reference could be added in the Security Considerations.

Fault attacks against Lattice schemes and HBS had been brought up in the NIST PQ forum  too [1,2] where some countermeasures were discussed. Simple ideas like running the computation twice and comparing values were proposed there. [3] is a good reference of SW countermeasures.

[1] https://groups.google.com/a/list.nist.gov/forum/#!searchin/pqc-forum/%22fault$20attacks%22%7Csort:date/pqc-forum/c9CnPcx1eQc/74sVbH_3CAAJ
[2] https://groups.google.com/a/list.nist.gov/forum/#!searchin/pqc-forum/%22fault$20attacks%22%7Csort:date/pqc-forum/WjF2ZTUAJiA/zEEAjWSmBwAJ
[3] https://eprint.iacr.org/2017/1082.pdf

Rgs,
Panos

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 (sfluhrer) <[email-masked]>
Subject: Re: [lamps] Side-channel attack on multi-level trees and key generation of LMS.

Russ

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

Hi all,

Regards,
Quynh.
From: Daniel Van Geest <[email-masked]<mailto:[email-masked]>>

Daniel

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

Jim

Jim

Quynh.

Hi all,

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
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/spasm