Re: [lamps] Side-channel attack on multi-level trees and key generation of LMS.
Jim Schaad <ietf@augustcellars.com> Tue, 26 March 2019 15:29 UTC
Return-Path: <ietf@augustcellars.com>
X-Original-To: spasm@ietfa.amsl.com
Delivered-To: spasm@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 9A84912047E for <spasm@ietfa.amsl.com>; Tue, 26 Mar 2019 08:29:56 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.09
X-Spam-Level:
X-Spam-Status: No, score=0.09 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, HTTPS_HTTP_MISMATCH=1.989, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id pxdf0HUBx7z9 for <spasm@ietfa.amsl.com>; Tue, 26 Mar 2019 08:29:54 -0700 (PDT)
Received: from mail2.augustcellars.com (augustcellars.com [50.45.239.150]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 13351120447 for <spasm@ietf.org>; Tue, 26 Mar 2019 08:29:53 -0700 (PDT)
Received: from Jude (31.133.136.100) by mail2.augustcellars.com (192.168.0.56) with Microsoft SMTP Server (TLS) id 15.0.1395.4; Tue, 26 Mar 2019 08:29:45 -0700
From: Jim Schaad <ietf@augustcellars.com>
To: "'Dang, Quynh (Fed)'" <quynh.dang@nist.gov>, "'Scott Fluhrer (sfluhrer)'" <sfluhrer@cisco.com>, 'SPASM' <spasm@ietf.org>
References: <BN6PR14MB1106140408FFB08553DEAE98835F0@BN6PR14MB1106.namprd14.prod.outlook.com>, <D6AB5830-C69A-44CA-BD63-9B64F92C032E@vigilsec.com> <BN8PR09MB3604C9C7C8609430A58FD99EF35F0@BN8PR09MB3604.namprd09.prod.outlook.com>, <afb437b0d9e14a8097947a25d8422286@XCH-RTP-006.cisco.com> <BN8PR09MB3604324EF9D5BF4E9061F1B4F35F0@BN8PR09MB3604.namprd09.prod.outlook.com>, <048d01d4e3e6$625b4980$2711dc80$@augustcellars.com> <BN8PR09MB36040F0DFA1A6C8D4D80B8F0F35F0@BN8PR09MB3604.namprd09.prod.outlook.com>
In-Reply-To: <BN8PR09MB36040F0DFA1A6C8D4D80B8F0F35F0@BN8PR09MB3604.namprd09.prod.outlook.com>
Date: Tue, 26 Mar 2019 16:29:41 +0100
Message-ID: <04a801d4e3e8$bd2f79b0$378e6d10$@augustcellars.com>
MIME-Version: 1.0
Content-Type: multipart/alternative; boundary="----=_NextPart_000_04A9_01D4E3F1.1EF4F320"
X-Mailer: Microsoft Outlook 16.0
Thread-Index: AQGxeOKNdKozrHAci8pAAx4ahTvmlgIxG3TbAT4B+M8A3xuK/AH0U3JhASTbB3oCpWkHaaYUeOtQ
Content-Language: en-us
X-Originating-IP: [31.133.136.100]
Archived-At: <https://mailarchive.ietf.org/arch/msg/spasm/gLJ4vHfzC0aZVCuuUAbOoEbpkl0>
Subject: Re: [lamps] Side-channel attack on multi-level trees and key generation of LMS.
X-BeenThere: spasm@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "This is a venue for discussion of doing Some Pkix And SMime \(spasm\) work." <spasm.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/spasm>, <mailto:spasm-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/spasm/>
List-Post: <mailto:spasm@ietf.org>
List-Help: <mailto:spasm-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/spasm>, <mailto:spasm-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 26 Mar 2019 15:30:00 -0000
From: Dang, Quynh (Fed) <quynh.dang@nist.gov> Sent: Tuesday, March 26, 2019 4:21 PM To: Jim Schaad <ietf@augustcellars.com>; 'Scott Fluhrer (sfluhrer)' <sfluhrer@cisco.com>; 'SPASM' <spasm@ietf.org> Subject: Re: [lamps] Side-channel attack on multi-level trees and key generation of LMS. _____ From: Jim Schaad <ietf@augustcellars.com <mailto:ietf@augustcellars.com> > 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 <spasm-bounces@ietf.org <mailto:spasm-bounces@ietf.org> > On Behalf Of Dang, Quynh (Fed) Sent: Tuesday, March 26, 2019 3:04 PM To: Scott Fluhrer (sfluhrer) <sfluhrer@cisco.com <mailto:sfluhrer@cisco.com> >; SPASM <spasm@ietf.org <mailto:spasm@ietf.org> > 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) <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.ia cr.org%2F2018%2F674%2F20180713%3A140821&data=02%7C01%7Cquynh.dang%40nist.gov %7C8d6a1d790ec0480aafe408d6b1fd9160%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7 C0%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.
- [lamps] Call for adoption of draft-nir-saag-star Tim Hollebeek
- Re: [lamps] Call for adoption of draft-nir-saag-s… Melinda Shore
- Re: [lamps] Call for adoption of draft-nir-saag-s… Ryan Sleevi
- Re: [lamps] Call for adoption of draft-nir-saag-s… Dr. Pala
- Re: [lamps] Call for adoption of draft-nir-saag-s… Daniel Migault
- Re: [lamps] Call for adoption of draft-nir-saag-s… Russ Housley
- [lamps] discuss: empty OSCP (as: Re: Call for ado… Toerless Eckert
- Re: [lamps] Call for adoption of draft-nir-saag-s… Dr. Pala
- [lamps] Call for adoption of draft-vangeest-x509-… Russ Housley
- Re: [lamps] Call for adoption of draft-vangeest-x… Salz, Rich
- Re: [lamps] Call for adoption of draft-vangeest-x… Scott Fluhrer (sfluhrer)
- [lamps] Side-channel attack on multi-level trees … Dang, Quynh (Fed)
- Re: [lamps] Side-channel attack on multi-level tr… Scott Fluhrer (sfluhrer)
- Re: [lamps] Side-channel attack on multi-level tr… Dang, Quynh (Fed)
- Re: [lamps] Side-channel attack on multi-level tr… Jim Schaad
- Re: [lamps] Side-channel attack on multi-level tr… Jim Schaad
- Re: [lamps] Side-channel attack on multi-level tr… Dang, Quynh (Fed)
- Re: [lamps] Side-channel attack on multi-level tr… Scott Fluhrer (sfluhrer)
- Re: [lamps] Side-channel attack on multi-level tr… Tim Hollebeek
- Re: [lamps] Side-channel attack on multi-level tr… Dang, Quynh (Fed)
- Re: [lamps] Side-channel attack on multi-level tr… Jim Schaad
- Re: [lamps] Side-channel attack on multi-level tr… Dang, Quynh (Fed)
- Re: [lamps] Side-channel attack on multi-level tr… Tim Hollebeek
- Re: [lamps] Side-channel attack on multi-level tr… Dang, Quynh (Fed)
- Re: [lamps] Side-channel attack on multi-level tr… Dang, Quynh (Fed)
- Re: [lamps] Side-channel attack on multi-level tr… Russ Housley
- Re: [lamps] Side-channel attack on multi-level tr… Russ Housley
- Re: [lamps] Side-channel attack on multi-level tr… Dang, Quynh (Fed)
- Re: [lamps] Side-channel attack on multi-level tr… Scott Fluhrer (sfluhrer)
- Re: [lamps] Side-channel attack on multi-level tr… Daniel Van Geest
- Re: [lamps] Side-channel attack on multi-level tr… Dang, Quynh (Fed)
- Re: [lamps] Side-channel attack on multi-level tr… Russ Housley
- Re: [lamps] Side-channel attack on multi-level tr… Panos Kampanakis (pkampana)
- Re: [lamps] Call for adoption of draft-vangeest-x… Ryan Sleevi
- Re: [lamps] Call for adoption of draft-vangeest-x… Russ Housley
- Re: [lamps] Call for adoption of draft-vangeest-x… Adam Langley
- Re: [lamps] Call for adoption of draft-vangeest-x… Jonathan Hammell
- Re: [lamps] Side-channel attack on multi-level tr… Tim Hollebeek
- Re: [lamps] Call for adoption of draft-vangeest-x… Tim Hollebeek
- Re: [lamps] Call for adoption of draft-vangeest-x… Jim Schaad
- Re: [lamps] Call for adoption of draft-vangeest-x… Russ Housley
- Re: [lamps] Call for adoption of draft-vangeest-x… Russ Housley