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

["Dang, Quynh (Fed)" <[e-mail]>]

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







From: Dang, Quynh (Fed) <[e-mail]<mailto:[e-mail]>>
Sent: Tuesday, March 26, 2019 4:21 PM
To: Jim Schaad <[e-mail]<mailto:[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.







________________________________

From: Jim Schaad <[e-mail]<mailto:[e-mail]>>
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 <[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.iacr.org%2F2018%2F674%2F20180713%3A140821&data=02%7C01%7Cquynh.dang%40nist.gov%7C8d6a1d790ec0480aafe408d6b1fd9160%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C636892099954210337&sdata=2VcGnAW6UEsdbDbU5wcB5tBSI4gL7H3%2F1xVeXzIW39w%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.