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

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=40nist.gov@dmarc.ietf.org> wrote:
> 
> 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) <sfluhrer@cisco.com <mailto:sfluhrer@cisco.com>>
> 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 <spasm-bounces@ietf.org <mailto:spasm-bounces@ietf.org>> On Behalf Of Dang, Quynh (Fed)
> Sent: Tuesday, March 26, 2019 9:11 AM
> To: SPASM <spasm@ietf.org <mailto:spasm@ietf.org>>
> 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%7C17afe62f6ae74a858cbf08d6b1edc737%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%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. 
>  
>  
>  
>  
> _______________________________________________
> Spasm mailing list
> Spasm@ietf.org <mailto:Spasm@ietf.org>
> https://www.ietf.org/mailman/listinfo/spasm <https://www.ietf.org/mailman/listinfo/spasm>