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

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

Irom: Spasm <[e-mail]> On Behalf Of Dang, Quynh (Fed)
Sent: Tuesday, March 26, 2019 9:11 AM
To: SPASM <[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.



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.