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

["Panos Kampanakis (pkampana)" <[e-mail]>]

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 <[e-mail]> On Behalf Of Russ Housley
Sent: Friday, March 29, 2019 10:19 AM
To: Quynh Dang <[e-mail]>
Cc: SPASM <[e-mail]>; Daniel Van Geest <[e-mail]>; Jim Schaad <[e-mail]>; Scott Fluhrer (sfluhrer) <[e-mail]>
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) <[e-mail]<mailto:[e-mail]>> 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 <[e-mail]<mailto:[e-mail]>>
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)" <[e-mail]<mailto:[e-mail]> on behalf of [e-mail]<mailto:[e-mail]>> wrote:




From: Jim Schaad <[e-mail]<mailto:[e-mail]>>
Sent: Tuesday, March 26, 2019 12:14 PM
To: Scott Fluhrer (sfluhrer) <[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.


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://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>


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%7Cf6277e7102074843afe408d6b4321776%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C636894524568596697&sdata=krnCaCoGSCwG%2FXDYPPnijwnp6toouFB82F88Q20H158%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.iacr.org%2F2018%2F674%2F20180713%3A140821&data=02%7C01%7Cquynh.dang%40nist.gov%7Cf6277e7102074843afe408d6b4321776%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C636894524568596697&sdata=xsTRh1kObIT8W%2Bt8EWUSRZdEjIC9mDwWiJbdCRK5Zbk%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.






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