Re: [lamps] Side-channel attack on multi-level trees and key generation of LMS.

[Tim Hollebeek <[e-mail]>]

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 <[e-mail]> On Behalf Of Dang, Quynh (Fed)
Sent: Tuesday, March 26, 2019 5:21 PM
To: Jim Schaad <[e-mail]>; 'Scott Fluhrer (sfluhrer)'
<[e-mail]>; 'Dang, Quynh (Fed)'
<quynh.dang=[e-mail]>; 'SPASM' <[e-mail]>
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 <[e-mail] <mailto:[e-mail]> > on
behalf of Jim Schaad <[e-mail] <mailto:[e-mail]>
>
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) <[e-mail]
<mailto:[e-mail]> > 
Sent: Tuesday, March 26, 2019 4:28 PM
To: Jim Schaad <[e-mail] <mailto:[e-mail]> >;
'Dang, Quynh (Fed)' <quynh.dang=[e-mail]
<mailto:quynh.dang=[e-mail]> >; 'SPASM' <[e-mail]
<mailto:[e-mail]> >
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>  

 

From: Jim Schaad <[e-mail] <mailto:[e-mail]> > 
Sent: Tuesday, March 26, 2019 11:13 AM
To: 'Dang, Quynh (Fed)' <quynh.dang=[e-mail]
<mailto:quynh.dang=[e-mail]> >; Scott Fluhrer (sfluhrer)
<[e-mail] <mailto:[e-mail]> >; 'SPASM' <[e-mail]
<mailto:[e-mail]> >
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 <[e-mail] <mailto:[e-mail]> > On
Behalf Of Dang, Quynh (Fed)
Sent: Tuesday, March 26, 2019 3:04 PM
To: Scott Fluhrer (sfluhrer) <[e-mail] <mailto:[e-mail]>
>; SPASM <[e-mail] <mailto:[e-mail]> >
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) <[e-mail]
<mailto:[e-mail]> >
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 <[e-mail] <mailto:[e-mail]> > On
Behalf Of Dang, Quynh (Fed)
Sent: Tuesday, March 26, 2019 9:11 AM
To: SPASM <[e-mail] <mailto:[e-mail]> >
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
%7Cdff17ae48c7244b4d0be08d6b2060b46%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7
C0%7C636892136357866162&sdata=MQDZ%2F6NEXUCdvUivnHwRVH0bXgIQb4D5GbCTNovZ3cg%
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.