From ietf@augustcellars.com Thu Dec 6 21:23:20 2012 Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 3EC4411E80E0 for ; Thu, 6 Dec 2012 21:23:20 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -3.599 X-Spam-Level: X-Spam-Status: No, score=-3.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, RCVD_IN_DNSWL_LOW=-1] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id TtC95YcOqllG for ; Thu, 6 Dec 2012 21:23:19 -0800 (PST) Received: from smtp3.pacifier.net (smtp3.pacifier.net [64.255.237.177]) by ietfa.amsl.com (Postfix) with ESMTP id CE82D11E80D2 for ; Thu, 6 Dec 2012 21:23:19 -0800 (PST) Received: from Philemon (mail.augustcellars.com [50.34.17.238]) (using TLSv1 with cipher AES128-SHA (128/128 bits)) (No client certificate requested) (Authenticated sender: jimsch@nwlink.com) by smtp3.pacifier.net (Postfix) with ESMTPSA id 1908638E6A for ; Thu, 6 Dec 2012 21:23:19 -0800 (PST) From: "Jim Schaad" To: Date: Thu, 6 Dec 2012 21:23:08 -0800 Message-ID: <015c01cdd43a$f18f3b60$d4adb220$@augustcellars.com> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Mailer: Microsoft Outlook 14.0 Thread-Index: Ac3UOkozciLafGFZSP6gO4lpsIWbxA== Content-Language: en-us Subject: [Cfrg] KCipher-2 X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 07 Dec 2012 05:23:20 -0000 The ISE is debating the publication of the document http://tools.ietf.org/html/draft-kiyomoto-kcipher2-07 which describes the KCipher2 algorithm. I would like to get more eyes to look at the draft and provide comments on the following issues: 1. Does anybody know any reason why we should not publish this document? 2. In section 2.4.2 of the document, a procedure is given to determine the values of a0, a1, a2 and a3. In appendix A, a simple lookup table is provided which allows the normal program to not care about what the values of a0, a1, a2 and a3 are as they can do the required multiplication step by table lookup. Is there any reason to require that actual values be provided for a0, a1, a2 and a3 so that somebody who is not well up on the math (for example me) could actually check that the values are both correct according to what they have said is the method of deriving them and that the lookup tables are correct. Thanks for any and all input, Jim Schaad From mcgrew@cisco.com Fri Dec 7 10:23:14 2012 Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id CBAC821F8798 for ; Fri, 7 Dec 2012 10:23:14 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -110.599 X-Spam-Level: X-Spam-Status: No, score=-110.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, RCVD_IN_DNSWL_HI=-8, USER_IN_WHITELIST=-100] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id mPFnunMgo8nX for ; Fri, 7 Dec 2012 10:23:13 -0800 (PST) Received: from rcdn-iport-7.cisco.com (rcdn-iport-7.cisco.com [173.37.86.78]) by ietfa.amsl.com (Postfix) with ESMTP id B573B21F85E1 for ; Fri, 7 Dec 2012 10:23:13 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=2792; q=dns/txt; s=iport; t=1354904593; x=1356114193; h=from:to:subject:date:message-id:in-reply-to:content-id: content-transfer-encoding:mime-version; bh=/LIucKslh4QgJT6Wx3oNfxIr4Z89oCjR4rzX8IUwg4I=; b=Ykxw6v5HjuCLKAcK1JexQk+2s/Tuf5EnSiKXcnOAWx2Hrf0viq15zVbj FlWJE9y8in/D8q6cS7/eFCAEGPwvZYzx0fX3A/j/OJbdQdxeUvYrBS0s4 B1Xqm3suDKnnkvJWyslO7WNvSSorWhAbfNE037ZN/9rnl5sjaHjiNcCTI s=; X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Av8EAPUywlCtJXG9/2dsb2JhbABEvjoWc4IgAQQBAQE3NB0BCA4UFDcLJQEBBAESCAGICAzCIZAhYQOXIY8sgnOCIg X-IronPort-AV: E=McAfee;i="5400,1158,6919"; a="150583235" Received: from rcdn-core2-2.cisco.com ([173.37.113.189]) by rcdn-iport-7.cisco.com with ESMTP; 07 Dec 2012 18:23:13 +0000 Received: from xhc-rcd-x06.cisco.com (xhc-rcd-x06.cisco.com [173.37.183.80]) by rcdn-core2-2.cisco.com (8.14.5/8.14.5) with ESMTP id qB7INDpp004773 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=FAIL); Fri, 7 Dec 2012 18:23:13 GMT Received: from xmb-rcd-x04.cisco.com ([169.254.8.56]) by xhc-rcd-x06.cisco.com ([173.37.183.80]) with mapi id 14.02.0318.001; Fri, 7 Dec 2012 12:23:12 -0600 From: "David McGrew (mcgrew)" To: Jim Schaad , "cfrg@irtf.org" Thread-Topic: [Cfrg] KCipher-2 Thread-Index: Ac3UOkozciLafGFZSP6gO4lpsIWbxAAdgC4A Date: Fri, 7 Dec 2012 18:23:12 +0000 Message-ID: <747787E65E3FBD4E93F0EB2F14DB556B0F566DA0@xmb-rcd-x04.cisco.com> In-Reply-To: <015c01cdd43a$f18f3b60$d4adb220$@augustcellars.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: user-agent: Microsoft-MacOutlook/14.2.1.120420 x-originating-ip: [10.117.10.227] Content-Type: text/plain; charset="us-ascii" Content-ID: Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Subject: Re: [Cfrg] KCipher-2 X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 07 Dec 2012 18:23:14 -0000 Hi Jim, On 12/7/12 12:23 AM, "Jim Schaad" wrote: >The ISE is debating the publication of the document >http://tools.ietf.org/html/draft-kiyomoto-kcipher2-07 >which describes the KCipher2 algorithm. I would like to get more eyes to >look at the draft and provide comments on the following issues: > >1. Does anybody know any reason why we should not publish this document? I think it is appropriate for the document to be published by ISE. It seems like sound work and a well written document. My comments are: * it appears that only one independent security analysis has been done. This is OK, but not great. If other analyses have been done, I suggest the authors cite them directly. * the document should state what the requirements on the IV are; is it intended to be distinct (as with counter mode), or does it need to be random or pseudorandom (as with CBC mode)? Also, the security considerations should describe what security properties go away when the IV is poorly chosen. * the security considerations should note the absence of authentication, and the importance of that security service. "Kcipher2 does not provide data origin authentication, and thus it SHOULD be used in conjunction with a message authentication code of comparable cryptographic strength", or something like that. * it would be good to verify that there have been multiple independent implementations. Perhaps this requirement could slide because there is reference code in the draft. A nit: I noticed a stray comma in the line " , where GF_mult_by_2 and GF_mult_by_3 are multiplication functions" > >2. In section 2.4.2 of the document, a procedure is given to determine >the >values of a0, a1, a2 and a3. In appendix A, a simple lookup table is >provided which allows the normal program to not care about what the values >of a0, a1, a2 and a3 are as they can do the required multiplication step >by >table lookup. Is there any reason to require that actual values be >provided >for a0, a1, a2 and a3 so that somebody who is not well up on the math (for >example me) could actually check that the values are both correct >according >to what they have said is the method of deriving them and that the lookup >tables are correct. I think it is reasonable to ask for more information on the field representation and what the elements of the table mean. The authors should be able to provide this with little trouble. But I wouldn't rate it as critical, it seems possible to figure it out. Regards, David > > >Thanks for any and all input, > >Jim Schaad > > >_______________________________________________ >Cfrg mailing list >Cfrg@irtf.org >http://www.irtf.org/mailman/listinfo/cfrg From jon@callas.org Fri Dec 7 11:00:39 2012 Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 80AD421F875E for ; Fri, 7 Dec 2012 11:00:39 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.599 X-Spam-Level: X-Spam-Status: No, score=-2.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id VilvpQr04NOa for ; Fri, 7 Dec 2012 11:00:38 -0800 (PST) Received: from mail.merrymeet.com (merrymeet.com [173.164.244.100]) by ietfa.amsl.com (Postfix) with ESMTP id C7EDE21F86AA for ; Fri, 7 Dec 2012 11:00:38 -0800 (PST) Received: from localhost (localhost [127.0.0.1]) by mail.merrymeet.com (Postfix) with ESMTP id C7E10143D6E3 for ; Fri, 7 Dec 2012 11:00:37 -0800 (PST) X-Virus-Scanned: amavisd-new at merrymeet.com Received: from mail.merrymeet.com ([127.0.0.1]) by localhost (localhost [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id BlwExoGV7KUi for ; Fri, 7 Dec 2012 11:00:37 -0800 (PST) Received: from keys.merrymeet.com (keys.merrymeet.com [173.164.244.97]) by mail.merrymeet.com (Postfix) with ESMTPSA id 9486A143D6D8 for ; Fri, 7 Dec 2012 11:00:37 -0800 (PST) Received: from [192.168.4.75] ([70.102.71.225]) by keys.merrymeet.com (PGP Universal service); Fri, 07 Dec 2012 11:00:37 -0800 X-PGP-Universal: processed; by keys.merrymeet.com on Fri, 07 Dec 2012 11:00:37 -0800 Mime-Version: 1.0 (Apple Message framework v1283) From: Jon Callas In-Reply-To: <015c01cdd43a$f18f3b60$d4adb220$@augustcellars.com> Date: Fri, 7 Dec 2012 11:00:30 -0800 Message-Id: <612879CA-AB3A-46AE-AD66-808EF4B4C57F@callas.org> References: <015c01cdd43a$f18f3b60$d4adb220$@augustcellars.com> To: "Jim Schaad" X-Mailer: Apple Mail (2.1283) X-PGP-Encoding-Format: Partitioned X-PGP-Encoding-Version: 2.0.2 X-Content-PGP-Universal-Saved-Content-Transfer-Encoding: quoted-printable X-Content-PGP-Universal-Saved-Content-Type: text/plain; charset=us-ascii Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: QUOTED-PRINTABLE Cc: cfrg@irtf.org, Jon Callas Subject: Re: [Cfrg] KCipher-2 X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 07 Dec 2012 19:00:39 -0000 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 My answers: No, and yes. Publish the document. It's an *informational* RFC. In general, I think that= an informational RFC should default against editorializing. For a cipher, = yes, you don't want to document something that is bad. We all know and agre= e that. We all also know the dangers of too many options. But we also know = the dangers of monoculture. Providing information is different than interpr= eting it. I think KCipher-2 meets a bar on that.=20 Yes, put the table in. It's a long-standing frustration of mine that crypto= documents seem to think that part of the fun is to guess about implementat= ion until you finally get it right. A sort of gameification, I suppose, tha= t makes a spec a choose-your-own adventure. This gets boring, fast. The vas= t majority of us implementors want to get it done, fast and accurate. Anyth= ing that helps that is a Good Thing. Jon -----BEGIN PGP SIGNATURE----- Version: PGP Universal 3.2.0 (Build 1672) Charset: us-ascii wj8DBQFQwjzVsTedWZOD3gYRAiKsAJ9uwclJKU5IGDAfo1D0+oBR693xwACgqSXa D5QBJprFkRvn2xOoAYqqibQ=3D =3Dbog0 -----END PGP SIGNATURE----- From rstruik.ext@gmail.com Wed Dec 12 06:17:24 2012 Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 3F48821F861D for ; Wed, 12 Dec 2012 06:17:24 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -3.599 X-Spam-Level: X-Spam-Status: No, score=-3.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, RCVD_IN_DNSWL_LOW=-1] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id bOMT1cKAHnLU for ; Wed, 12 Dec 2012 06:17:23 -0800 (PST) Received: from mail-ia0-f173.google.com (mail-ia0-f173.google.com [209.85.210.173]) by ietfa.amsl.com (Postfix) with ESMTP id 10C1F21F8A38 for ; Wed, 12 Dec 2012 06:17:23 -0800 (PST) Received: by mail-ia0-f173.google.com with SMTP id w21so929241iac.32 for ; Wed, 12 Dec 2012 06:17:22 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type:content-transfer-encoding; bh=L2ncPzH57WVqzbmXY/27Cbx1PZyk6WS0u39QrRgUeRw=; b=wNBuFaenznZLOcgOUfzM6U2GaSoe4XcuiokJtSC0hUdCnn3+lPwdoLGi8ymOjOfp6y d5yCT6yqhC7bqsKVelCbX500Y3w4FrXV9qr2LQ230lgz84CT53WQEtfYHWJa9d2Xg/rT mlggK40tuOeL2r7SQ8dwbCgHu3OFuCOuhsLypn345V21VEFg2xn5y8Dwrva2y7jKyhFX B7AGwXtu/foiefMA+1FcpcA/Zmc92cPf7t6nEKzHaPJksveUopC8K6rkJfW5DHY6YPMG ubN2Gi9XuElu60GcRG1yMl5exfAGCEmTMOWOV9A4tPO2JbxEdIazoRgAYs4zLB1HZxVc HNZw== Received: by 10.50.33.147 with SMTP id r19mr13461385igi.73.1355321842136; Wed, 12 Dec 2012 06:17:22 -0800 (PST) Received: from [192.168.1.103] (CPE0013100e2c51-CM001cea35caa6.cpe.net.cable.rogers.com. [99.231.4.27]) by mx.google.com with ESMTPS id wg2sm1853537igb.13.2012.12.12.06.17.21 (version=TLSv1/SSLv3 cipher=OTHER); Wed, 12 Dec 2012 06:17:21 -0800 (PST) Message-ID: <50C891E7.4000009@gmail.com> Date: Wed, 12 Dec 2012 09:17:11 -0500 From: Rene Struik User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/17.0 Thunderbird/17.0 MIME-Version: 1.0 To: Andrey Jivsov References: <50C7C3AC.7010405@brainhub.org> In-Reply-To: <50C7C3AC.7010405@brainhub.org> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Cc: cfrg@irtf.org, saag@ietf.org, Peter Gutmann Subject: Re: [Cfrg] [saag] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 12 Dec 2012 14:17:24 -0000 Hi Andrey: One can already implement the x-coordinate only representation of an elliptic curve point simply by converting the affine representation into compressed representation and randomizing the compression "bit". The reverse operation then yields the point or its inverse (which have the same x-coordinate). To my knowledge, this does not require any changes to data formatting (nor additional bytes). Best regards, Rene On 12/11/2012 6:37 PM, Andrey Jivsov wrote: > On 12/11/2012 03:15 PM, Peter Gutmann wrote: >> Andrey Jivsov writes: >> >>> I thought that it would be useful for the Internet community to have >>> an IETF >>> document that describes how to encode an ECC point. >> >> Maybe I'm missing something here, but wouldn't this just consist of: >> >> -- Snip -- >> >> See [1]. >> >> [1] X9.62-2005, "Public Key Cryptography for the Financial Services >> Industry: >> The Elliptic Curve Digital Signature Standard (ECDSA)", November, 2005. >> >> -- Snip -- >> >> That's what every existing RFC that uses ECC seems to be using. >> >> Peter. >> > > Hello Peter. > > "X9.62-2005" in the search engine lends me on a page that asks for > $100. I think http://www.secg.org/collateral/sec1_final.pdf [SEC1] is > more popular as a reference (assuming they are identical regarding the > point compression method). > > I claim that what I submitted is better in many respects than SEC1. > > Let me expand on one of the benefits not covered in the spec. It's > very likely that an employee of a commercial company thinking about > using [SEC1] compression with any ECC method would get an order from > the legal department to stay away from compression. The fact that > somebody on the Internet posted something to the contrary has little > weight for them. My contribution is an attempt towards a compact > representation that is actually usable in practice. It's the most > direct extension to the 1985 idea by [Miller] (see my document for > details). > > Thank you. > > _______________________________________________ > saag mailing list > saag@ietf.org > https://www.ietf.org/mailman/listinfo/saag -- email: rstruik.ext@gmail.com | Skype: rstruik cell: +1 (647) 867-5658 | US: +1 (415) 690-7363 From sfluhrer@cisco.com Wed Dec 12 08:52:32 2012 Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id C901121F850D for ; Wed, 12 Dec 2012 08:52:32 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -10.599 X-Spam-Level: X-Spam-Status: No, score=-10.599 tagged_above=-999 required=5 tests=[AWL=0.000, BAYES_00=-2.599, RCVD_IN_DNSWL_HI=-8] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id sWv6BY17Sxq2 for ; Wed, 12 Dec 2012 08:52:30 -0800 (PST) Received: from rcdn-iport-5.cisco.com (rcdn-iport-5.cisco.com [173.37.86.76]) by ietfa.amsl.com (Postfix) with ESMTP id 9C3F721F845B for ; Wed, 12 Dec 2012 08:52:30 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=3153; q=dns/txt; s=iport; t=1355331150; x=1356540750; h=from:to:cc:subject:date:message-id:references: in-reply-to:content-transfer-encoding:mime-version; bh=+iPAqO5DXLAMkCnZWZkrUdUsgSlmM72zUu8qZddzMAQ=; b=G3HJCXvwX28diybaeCDJXLBv5eVUJuW8dRgSUe+O7vVZEeTiKXpLbDhd /yPJaBNIfts97Z7HTb0ngfjvMK5NfmcUUNlqh3YumMZ/D1IoZ2U++qOhw /l5BRkZKECpo2+h4fIAkWlUpoNChqFTwrzCvx/rW+TXn3TevDHxGoMhtv o=; X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgEFAOG1yFCtJV2a/2dsb2JhbABCA78VFnOCHgEBAQIBAQEBATc0CwwEAgEIDgMEAQEBChQFBAchBgsUCQgCBAENBQgBC4drAwkGDLQIDYlVi2JpC4EKgk1hA4pRiAWBXY0NhRGCc4FtNQ X-IronPort-AV: E=Sophos;i="4.84,267,1355097600"; d="scan'208";a="152169284" Received: from rcdn-core-3.cisco.com ([173.37.93.154]) by rcdn-iport-5.cisco.com with ESMTP; 12 Dec 2012 16:52:04 +0000 Received: from xhc-rcd-x14.cisco.com (xhc-rcd-x14.cisco.com [173.37.183.88]) by rcdn-core-3.cisco.com (8.14.5/8.14.5) with ESMTP id qBCGq4Mv012857 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=FAIL); Wed, 12 Dec 2012 16:52:04 GMT Received: from xmb-rcd-x04.cisco.com ([169.254.8.29]) by xhc-rcd-x14.cisco.com ([173.37.183.88]) with mapi id 14.02.0318.004; Wed, 12 Dec 2012 10:52:03 -0600 From: "Scott Fluhrer (sfluhrer)" To: Rene Struik , Andrey Jivsov Thread-Topic: [Cfrg] [saag] A proposal for compact representation of an elliptic curve point (ECC point compression) Thread-Index: AQHN2HN1n0mZdiOeF06/Mfx4iUhUp5gVYE2g Date: Wed, 12 Dec 2012 16:52:03 +0000 Message-ID: References: <50C7C3AC.7010405@brainhub.org> <50C891E7.4000009@gmail.com> In-Reply-To: <50C891E7.4000009@gmail.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [10.32.244.86] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Cc: "cfrg@irtf.org" , "saag@ietf.org" , Peter Gutmann Subject: Re: [Cfrg] [saag] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 12 Dec 2012 16:52:32 -0000 > -----Original Message----- > From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf Of > Rene Struik > Sent: Wednesday, December 12, 2012 9:17 AM > To: Andrey Jivsov > Cc: cfrg@irtf.org; saag@ietf.org; Peter Gutmann > Subject: Re: [Cfrg] [saag] A proposal for compact representation of an > elliptic curve point (ECC point compression) >=20 > Hi Andrey: >=20 > One can already implement the x-coordinate only representation of an > elliptic curve point simply by converting the affine representation into > compressed representation and randomizing the compression "bit". The > reverse operation then yields the point or its inverse (which have the sa= me > x-coordinate). >=20 > To my knowledge, this does not require any changes to data formatting (no= r > additional bytes). That randomization of the y-component works fine for ECDH (at least, if you= use only the x-component of the shared secret); however, it doesn't work f= or ECDSA public keys. >=20 > Best regards, >=20 > Rene >=20 > On 12/11/2012 6:37 PM, Andrey Jivsov wrote: > > On 12/11/2012 03:15 PM, Peter Gutmann wrote: > >> Andrey Jivsov writes: > >> > >>> I thought that it would be useful for the Internet community to have > >>> an IETF document that describes how to encode an ECC point. > >> > >> Maybe I'm missing something here, but wouldn't this just consist of: > >> > >> -- Snip -- > >> > >> See [1]. > >> > >> [1] X9.62-2005, "Public Key Cryptography for the Financial Services > >> Industry: > >> The Elliptic Curve Digital Signature Standard (ECDSA)", November, 2005= . > >> > >> -- Snip -- > >> > >> That's what every existing RFC that uses ECC seems to be using. > >> > >> Peter. > >> > > > > Hello Peter. > > > > "X9.62-2005" in the search engine lends me on a page that asks for > > $100. I think http://www.secg.org/collateral/sec1_final.pdf [SEC1] is > > more popular as a reference (assuming they are identical regarding the > > point compression method). > > > > I claim that what I submitted is better in many respects than SEC1. > > > > Let me expand on one of the benefits not covered in the spec. It's > > very likely that an employee of a commercial company thinking about > > using [SEC1] compression with any ECC method would get an order from > > the legal department to stay away from compression. The fact that > > somebody on the Internet posted something to the contrary has little > > weight for them. My contribution is an attempt towards a compact > > representation that is actually usable in practice. It's the most > > direct extension to the 1985 idea by [Miller] (see my document for > > details). > > > > Thank you. > > > > _______________________________________________ > > saag mailing list > > saag@ietf.org > > https://www.ietf.org/mailman/listinfo/saag >=20 >=20 > -- > email: rstruik.ext@gmail.com | Skype: rstruik > cell: +1 (647) 867-5658 | US: +1 (415) 690-7363 >=20 > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > http://www.irtf.org/mailman/listinfo/cfrg From prvs=9693c77741=dbrown@certicom.com Wed Dec 12 10:41:05 2012 Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id CF5601F0CDC for ; Wed, 12 Dec 2012 10:41:05 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -5.053 X-Spam-Level: X-Spam-Status: No, score=-5.053 tagged_above=-999 required=5 tests=[AWL=0.150, BAYES_00=-2.599, MIME_QP_LONG_LINE=1.396, RCVD_IN_DNSWL_MED=-4] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id LNC5umwAzq9C for ; Wed, 12 Dec 2012 10:41:04 -0800 (PST) Received: from mhs060cnc.rim.net (mhs060cnc.rim.net [208.65.73.34]) by ietfa.amsl.com (Postfix) with ESMTP id 199C01F0CDA for ; Wed, 12 Dec 2012 10:41:03 -0800 (PST) X-AuditID: 0a41282f-b7fea6d000001d56-c0-50c8cfb13308 Received: from XCT106CNC.rim.net (xct106cnc.rim.net [10.65.161.206]) by mhs060cnc.rim.net (SBG) with SMTP id 6D.59.07510.1BFC8C05; Wed, 12 Dec 2012 12:40:49 -0600 (CST) Received: from XCT111CNC.rim.net (10.65.161.211) by XCT106CNC.rim.net (10.65.161.206) with Microsoft SMTP Server (TLS) id 14.2.318.1; Wed, 12 Dec 2012 13:40:49 -0500 Received: from XMB111CNC.rim.net ([fe80::fcd6:cc6c:9e0b:25bc]) by XCT111CNC.rim.net ([::1]) with mapi id 14.02.0318.001; Wed, 12 Dec 2012 13:40:48 -0500 From: Dan Brown To: 'Andrey Jivsov' , "saag@ietf.org" , "cfrg@irtf.org" Thread-Topic: [saag] A proposal for compact representation of an elliptic curve point (ECC point compression) Thread-Index: AQHN1+JKYfEillVVT0CYN/ZbTZXZi5gVcVkg Date: Wed, 12 Dec 2012 18:40:48 +0000 Message-ID: <810C31990B57ED40B2062BA10D43FBF50ECB6A@XMB111CNC.rim.net> References: <50C79E2A.9040100@brainhub.org> In-Reply-To: <50C79E2A.9040100@brainhub.org> Accept-Language: en-CA, en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [10.65.160.245] Content-Type: text/plain; charset="us-ascii" content-transfer-encoding: quoted-printable MIME-Version: 1.0 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFrrOKsWRmVeSWpSXmKPExsXC5bjwnO7G8ycCDJZP07To/nGQyeJ11y8m iyn9nUwOzB63px9m81iy5CeTx+SNh9kCmKMaGG2SEkvKgjPT8/TtbBLz8vJLEktSFVJSi5Nt lXxS0xNzFAKKMssSkysVXDKLk3MSM3NTi5QUMlNslUyUFApyEpNTc1PzSmyVEgsKUvNSlOy4 FDCADVBZZp5Cal5yfkpmXrqtkmewv66FhamlrqGSnW5CJ0/GlOO3WAqmKlfMb3jI2MB4QKaL kYNDQsBE4kWTdhcjJ5ApJnHh3nq2LkYuDiGBVYwSs/uWM0E4Kxklbi4/C+XMYZQ42NvICNLC JqAqcf/oOWaQSSICeRL/tteBhIWBzO7La9hAbBGBfInN+9dD2UYSLbt62UFsFqDW1vlHmEBs XgE3ieX/14CNFBLQlnja/gasnlNAR+LSuyfMIDajgKzE7rPXweqZBcQlbj2ZzwRxtYDEkj3n mSFsUYmXj/+xQtiKEqtf3WKDqNeRWLD7E5StLbFs4WtmiL2CEidnPmGB2KsgceX6PpYJjOKz kKyYhaR9FpL2WUjaFzCyrGIUzM0oNjAzSM5L1ivKzNXLSy3ZxAhOKRr6Oxjfvrc4xCjAwajE wztxx4kAIdbEsuLK3EOMEhzMSiK8bgeAQrwpiZVVqUX58UWlOanFhxhdgSE0kVmKOzkfmO7y SuKNDQxwc5TEeZWZDwYICaQDk1V2ampBahHMHCYOTpA9XFIixcCUk1qUWFqSEQ9KjPHFwNQo 1cCY8tIgWk3/1eqLvz8kbDmXdsF1r+2Lk2cvZ7RZHmN3OfegwUf2U2fs1n9L1nbM4b7PL2vc sEFhcsBFhgu9Dsfzu3qCHy32O2fgaVvx66I5h8fL8jSTx15pRl9THDy/3/q2KsSAb6Zs2DfO sDvmxxrffFh+NHe9ypyVHgof/WIm85yYmzxN4dMvJZbijERDLeai4kQA4ER++WoDAAA= Subject: Re: [Cfrg] [saag] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 12 Dec 2012 18:41:05 -0000 Hi Andrey, Some quibbles. The SEC1 EC point format profiles the ANSI X9.62 and IEEE 1363 formats. My belief is that octet strings, rather than integers, were chosen (long bef= ore I was involved) for these formats because (at least partly, and perhaps= mainly) these standards also allowed other finite fields (binary and odd ch= aracteristic extension fields), which are not naturally represented by integ= ers. The SEC1 format also has the property of being a prefix-free encoding (for a= given elliptic curve), which I think was intentional. My limited understan= ding of networking theory is that prefix-free encoding helps to avoid misint= erpretations of streams. Well, at least DER encoding of ASN.1 seems (to me)= to be prefix-free. Certainly, the SEC1 format prefix-free property is redu= ndant when inside an ASN.1 wrapper, but otherwise, if used outside of ASN.1,= the prefix-free property of SEC1 may be a little helpful. Your ID mentions power-of-two byte alignment. I understand alignment to be= quite important for storage, but how important is it for networking? (Octe= t string formats help networking interoperability; for local storage, an imp= lementation can really use any format.) Because your format specifies integers, it can fit into an ASN.1 type. The= current ASN.1 types for ECC public keys (and generators in domain parameter= s) expect ASN.1 octet string types. These ASN.1 ECC public key formats wou= ld need to be changed. Some formats use two's complement, which assumes signed integers. I think t= hat BER and DER use it for integers. This forces a sign bit, which could ad= d a byte. Section 6 of your ID says a P-256 point will never exceed 32 byte= s, but it might need an extra byte if DER encoded. (Please correct me if I= am wrong, which is likely, since I am not an ASN.1 expert.) The extra sign= byte would have value zero, which slightly conflicts with the SEC1 format f= or the point-at-infinity. Also, since DER encodings are variable length, th= e power-of-two alignment might suffer. Best regards, Daniel Brown Research In Motion Limited > -----Original Message----- > From: saag-bounces@ietf.org [mailto:saag-bounces@ietf.org] On Behalf Of > Andrey Jivsov > Sent: Tuesday, December 11, 2012 3:57 PM > To: saag@ietf.org; cfrg@irtf.org > Subject: [saag] A proposal for compact representation of an elliptic > curve point (ECC point compression) > > Greetings. > > > I thought that it would be useful for the Internet community to have an > IETF document that describes how to encode an ECC point. I will focus > on the elliptic curves over the prime fields here. > > http://datatracker.ietf.org/doc/draft-jivsov-ecc-compact > > > Cryptographic protocols defined in IETF most often work with large > integers, such as the modulus of an RSA key, which they encode with > some applicable protocol-specific method. > > Unfortunately, the default representation of an ECC point is not just a > "large integer". It is either a pair of integers of x,y, or x with > optional information about y. Additional metadata tagged to x,y is > common. The encoding of an ECC point needs further definition, plus the > additional complexity is present due to the decisions to make ECC point > compression optional (I suspect on the ground of IPR concerns). > > In the ideal world the situation would be the following: there is an > RFC for ECC point definition; it uses compact representation; the > representation is just a large integer; it's free of patents; secure; > and that's the default mandatory method in every IETF standard. > > I am proposing here a format that in my opinion comes the closest to > the ideal features outlined above. Getting to the ideal world is > another story, but the first step on this journey is a working method > that I am pleased to present here. At the very least, the new protocols > can take advantage of the proposal; otherwise the new submissions will > likely to gravitate towards the SEC1 format, at least on the practical > grounds because the SEC1 is the only popular format that is searchable > and publicly available. I would like to offer an alternative / useful > point of reference to future standards. > > Thank you. > > _______________________________________________ > saag mailing list > saag@ietf.org > https://www.ietf.org/mailman/listinfo/saag --------------------------------------------------------------------- This transmission (including any attachments) may contain confidential infor= mation, privileged material (including material protected by the solicitor-c= lient or other applicable privileges), or constitute non-public information.= Any use of this information by anyone other than the intended recipient is= prohibited. If you have received this transmission in error, please immedia= tely reply to the sender and delete this information from your system. Use,= dissemination, distribution, or reproduction of this transmission by uninte= nded recipients is not authorized and may be unlawful. From housley@vigilsec.com Wed Dec 12 10:43:42 2012 Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 93FF321F87C9 for ; Wed, 12 Dec 2012 10:43:42 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -102.565 X-Spam-Level: X-Spam-Status: No, score=-102.565 tagged_above=-999 required=5 tests=[AWL=0.034, BAYES_00=-2.599, USER_IN_WHITELIST=-100] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id tOkNjFZdy37h for ; Wed, 12 Dec 2012 10:43:41 -0800 (PST) Received: from odin.smetech.net (mail.smetech.net [208.254.26.82]) by ietfa.amsl.com (Postfix) with ESMTP id 9693721F87EE for ; Wed, 12 Dec 2012 10:43:41 -0800 (PST) Received: from localhost (unknown [208.254.26.81]) by odin.smetech.net (Postfix) with ESMTP id 9B6039A4023; Wed, 12 Dec 2012 13:43:50 -0500 (EST) X-Virus-Scanned: amavisd-new at smetech.net Received: from odin.smetech.net ([208.254.26.82]) by localhost (ronin.smetech.net [208.254.26.81]) (amavisd-new, port 10024) with ESMTP id lOVl++H6dLy7; Wed, 12 Dec 2012 13:43:27 -0500 (EST) Received: from [192.168.2.100] (pool-96-255-37-162.washdc.fios.verizon.net [96.255.37.162]) (using TLSv1 with cipher AES128-SHA (128/128 bits)) (No client certificate requested) by odin.smetech.net (Postfix) with ESMTP id DB52E9A401E; Wed, 12 Dec 2012 13:43:49 -0500 (EST) Mime-Version: 1.0 (Apple Message framework v1085) Content-Type: text/plain; charset=us-ascii From: Russ Housley In-Reply-To: <810C31990B57ED40B2062BA10D43FBF50ECB6A@XMB111CNC.rim.net> Date: Wed, 12 Dec 2012 13:43:39 -0500 Content-Transfer-Encoding: quoted-printable Message-Id: <5B13CF7D-9D78-40DF-B3E9-C20EAE5AE03C@vigilsec.com> References: <50C79E2A.9040100@brainhub.org> <810C31990B57ED40B2062BA10D43FBF50ECB6A@XMB111CNC.rim.net> To: Dan Brown X-Mailer: Apple Mail (2.1085) Cc: 'Andrey Jivsov' , "cfrg@irtf.org" , "saag@ietf.org" Subject: Re: [Cfrg] [saag] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 12 Dec 2012 18:43:42 -0000 Dan: OCTET STRING was chosen to avoid the need to carry an extra byte to make = the sign bit a zero. Russ On Dec 12, 2012, at 1:40 PM, Dan Brown wrote: > My belief is that octet strings, rather than integers, were chosen = (long before I was involved) for these formats because (at least partly, = and perhaps mainly) these standards also allowed other finite fields = (binary and odd characteristic extension fields), which are not = naturally represented by integers. =20 From rstruik.ext@gmail.com Wed Dec 12 11:23:23 2012 Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 8D3A221E804E for ; Wed, 12 Dec 2012 11:23:22 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -3.599 X-Spam-Level: X-Spam-Status: No, score=-3.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, RCVD_IN_DNSWL_LOW=-1] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id PgbmhhRVnIZe for ; Wed, 12 Dec 2012 11:23:21 -0800 (PST) Received: from mail-ia0-f182.google.com (mail-ia0-f182.google.com [209.85.210.182]) by ietfa.amsl.com (Postfix) with ESMTP id E9C9621F8754 for ; Wed, 12 Dec 2012 11:23:16 -0800 (PST) Received: by mail-ia0-f182.google.com with SMTP id x2so1272124iad.13 for ; Wed, 12 Dec 2012 11:23:07 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type:content-transfer-encoding; bh=bLF5wp8re59uYAV9+TpJcAsa8fmxN8q1+e2rAMoDcE8=; b=s9jA1GLmGpWEwgCdT3Gn0HnjXlLF5v3jM9wbMGyF2YYTyHrhXIj4+B70oSPyc8AN8g hP+OEJ0mizMoLxeHJR8BMQ/KAFEHItSpjdoWBeLZwDzygNEVmjm3jZD3ncyepJ8+sEOl ElqV6KvywgroNhkyXXYYHrUtHGXh3vl2U255SueG1d/gCqbEdX213bc6kAZNboLbiHnm ePtBc4ziKa9AnG+CvHi2PczZeYK+jtcGiCNiYrY6v7WDrsrT5ZnAUTNU5UpHNftubLY+ C+aHfjAu4sYAw0Y5WPS4+o8iErKayNxt5Poi7614k3ORGuAtgn8I5TTcBzIThwDZKTpB Zx9w== Received: by 10.43.130.131 with SMTP id hm3mr1728001icc.25.1355340187690; Wed, 12 Dec 2012 11:23:07 -0800 (PST) Received: from [192.168.1.103] (CPE0013100e2c51-CM001cea35caa6.cpe.net.cable.rogers.com. [99.231.4.27]) by mx.google.com with ESMTPS id gz10sm12808741igc.9.2012.12.12.11.23.06 (version=TLSv1/SSLv3 cipher=OTHER); Wed, 12 Dec 2012 11:23:07 -0800 (PST) Message-ID: <50C8D991.5080809@gmail.com> Date: Wed, 12 Dec 2012 14:22:57 -0500 From: Rene Struik User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/17.0 Thunderbird/17.0 MIME-Version: 1.0 To: Andrey Jivsov References: <50C7C3AC.7010405@brainhub.org> <50C891E7.4000009@gmail.com> <50C8D4D1.8050805@brainhub.org> In-Reply-To: <50C8D4D1.8050805@brainhub.org> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Cc: Peter Gutmann , "cfrg@irtf.org" , "saag@ietf.org" , "Scott Fluhrer \(sfluhrer\)" Subject: Re: [Cfrg] [saag] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 12 Dec 2012 19:23:23 -0000 Hi Andrey: I just wanted to understand the problem one tries to solve. My simple suggestion was aimed at realizing the same effect. [I had a short offline exchange with Scott Fluhrer on this, including on the ECDSA verification angle - summarized by the sentence below] In most common implementations, ECDSA signature verification cost is roughly the same, no matter whether one know the y-coordinate of the signature verification key or not. Given this, it seems that for ECDSA signature verification and ECDH the argument for yet another construct seems to be somewhat weak: my simple suggestion would also work, does not require new formatting, or transition periods (and, to my knowledge, does not read on any "nontechnical issues"). I hope this helps. Best regards, Rene On 12/12/2012 2:02 PM, Andrey Jivsov wrote: > I have the same comment as Scott, but I am not sure exactly what Rene > means. > > I will assume that Rene says that because there are two y for each x, > one can calculate the corresponding y or p-y and choose one at random. > > The format I proposed indeed fits very well with the feature of the > ECDH-based protocol that Scott refers to (which covers ECC encryption > and key agreement). As the draft shows, one simply drops the y > coordinate to obtain the compact representation, while there are no > extra steps for ECDH key generation (because ECDH keys are not > sensitive to maintaining the "right" y). > > The extra key generation step is only needed for ECDSA keys. > > On 12/12/2012 08:52 AM, Scott Fluhrer (sfluhrer) wrote: >> >> >>> -----Original Message----- >>> From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf Of >>> Rene Struik >>> Sent: Wednesday, December 12, 2012 9:17 AM >>> To: Andrey Jivsov >>> Cc: cfrg@irtf.org; saag@ietf.org; Peter Gutmann >>> Subject: Re: [Cfrg] [saag] A proposal for compact representation of an >>> elliptic curve point (ECC point compression) >>> >>> Hi Andrey: >>> >>> One can already implement the x-coordinate only representation of an >>> elliptic curve point simply by converting the affine representation >>> into >>> compressed representation and randomizing the compression "bit". The >>> reverse operation then yields the point or its inverse (which have >>> the same >>> x-coordinate). >>> >>> To my knowledge, this does not require any changes to data >>> formatting (nor >>> additional bytes). >> >> That randomization of the y-component works fine for ECDH (at least, >> if you use only the x-component of the shared secret); however, it >> doesn't work for ECDSA public keys. >> >>> >>> Best regards, >>> >>> Rene >>> >>> On 12/11/2012 6:37 PM, Andrey Jivsov wrote: >>>> On 12/11/2012 03:15 PM, Peter Gutmann wrote: >>>>> Andrey Jivsov writes: >>>>> >>>>>> I thought that it would be useful for the Internet community to have >>>>>> an IETF document that describes how to encode an ECC point. >>>>> >>>>> Maybe I'm missing something here, but wouldn't this just consist of: >>>>> >>>>> -- Snip -- >>>>> >>>>> See [1]. >>>>> >>>>> [1] X9.62-2005, "Public Key Cryptography for the Financial Services >>>>> Industry: >>>>> The Elliptic Curve Digital Signature Standard (ECDSA)", November, >>>>> 2005. >>>>> >>>>> -- Snip -- >>>>> >>>>> That's what every existing RFC that uses ECC seems to be using. >>>>> >>>>> Peter. >>>>> >>>> >>>> Hello Peter. >>>> >>>> "X9.62-2005" in the search engine lends me on a page that asks for >>>> $100. I think http://www.secg.org/collateral/sec1_final.pdf [SEC1] is >>>> more popular as a reference (assuming they are identical regarding the >>>> point compression method). >>>> >>>> I claim that what I submitted is better in many respects than SEC1. >>>> >>>> Let me expand on one of the benefits not covered in the spec. It's >>>> very likely that an employee of a commercial company thinking about >>>> using [SEC1] compression with any ECC method would get an order from >>>> the legal department to stay away from compression. The fact that >>>> somebody on the Internet posted something to the contrary has little >>>> weight for them. My contribution is an attempt towards a compact >>>> representation that is actually usable in practice. It's the most >>>> direct extension to the 1985 idea by [Miller] (see my document for >>>> details). >>>> >>>> Thank you. >>>> >>>> _______________________________________________ >>>> saag mailing list >>>> saag@ietf.org >>>> https://www.ietf.org/mailman/listinfo/saag >>> >>> >>> -- >>> email: rstruik.ext@gmail.com | Skype: rstruik >>> cell: +1 (647) 867-5658 | US: +1 (415) 690-7363 >>> >>> _______________________________________________ >>> Cfrg mailing list >>> Cfrg@irtf.org >>> http://www.irtf.org/mailman/listinfo/cfrg > -- email: rstruik.ext@gmail.com | Skype: rstruik cell: +1 (647) 867-5658 | US: +1 (415) 690-7363 From sfluhrer@cisco.com Wed Dec 12 12:10:56 2012 Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 2556911E80E4 for ; Wed, 12 Dec 2012 12:10:56 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -10.599 X-Spam-Level: X-Spam-Status: No, score=-10.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, RCVD_IN_DNSWL_HI=-8] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id tGmMmWbqRZ-n for ; Wed, 12 Dec 2012 12:10:55 -0800 (PST) Received: from rcdn-iport-5.cisco.com (rcdn-iport-5.cisco.com [173.37.86.76]) by ietfa.amsl.com (Postfix) with ESMTP id 17D8911E80DC for ; Wed, 12 Dec 2012 12:10:55 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=5125; q=dns/txt; s=iport; t=1355343055; x=1356552655; h=from:to:cc:subject:date:message-id:references: in-reply-to:content-transfer-encoding:mime-version; bh=4NIuTZ3/j2mG1xF6w3EEnf7Q7xPNR/DU6IqzU2TehnY=; b=Sjqrk1vszWhl+T5q+gdCacU9Lf1P46PvEP/sqmnDq/ci6xzv7gr/hMYi lr4hOGjqW6RVJuJOFxYIK76Idu1Ge4ylWvqjPxwskgs5EN+lSprskt0l/ uUfieELlVdDJgbJ9hhlr8iNSbluT4xGBCM5T/frKfqYrp+nCF2Tl9zw8r g=; X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgEFAP/jyFCtJXG9/2dsb2JhbABCA78YFnOCHgEBAQIBAQEBATc0CwwEAgEIDgMEAQEBChQFBAchBgsUCQgCBA4FCAELh2sDCQYMtAsNiVWLYmkLgQqCTWEDilGIBYFdjQ2FEYJzgW01 X-IronPort-AV: E=Sophos;i="4.84,268,1355097600"; d="scan'208";a="152269685" Received: from rcdn-core2-2.cisco.com ([173.37.113.189]) by rcdn-iport-5.cisco.com with ESMTP; 12 Dec 2012 20:10:54 +0000 Received: from xhc-aln-x04.cisco.com (xhc-aln-x04.cisco.com [173.36.12.78]) by rcdn-core2-2.cisco.com (8.14.5/8.14.5) with ESMTP id qBCKAs09029605 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=FAIL); Wed, 12 Dec 2012 20:10:54 GMT Received: from xmb-rcd-x04.cisco.com ([169.254.8.29]) by xhc-aln-x04.cisco.com ([173.36.12.78]) with mapi id 14.02.0318.004; Wed, 12 Dec 2012 14:10:54 -0600 From: "Scott Fluhrer (sfluhrer)" To: Andrey Jivsov Thread-Topic: [Cfrg] [saag] A proposal for compact representation of an elliptic curve point (ECC point compression) Thread-Index: AQHN2HN1n0mZdiOeF06/Mfx4iUhUp5gVYE2ggACJ5oD//6zskA== Date: Wed, 12 Dec 2012 20:10:53 +0000 Message-ID: References: <50C7C3AC.7010405@brainhub.org> <50C891E7.4000009@gmail.com> <50C8D4D1.8050805@brainhub.org> In-Reply-To: <50C8D4D1.8050805@brainhub.org> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [10.32.244.86] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Cc: Peter Gutmann , "cfrg@irtf.org" , "saag@ietf.org" Subject: Re: [Cfrg] [saag] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 12 Dec 2012 20:10:56 -0000 > -----Original Message----- > From: Andrey Jivsov [mailto:openpgp@brainhub.org] > Sent: Wednesday, December 12, 2012 2:03 PM > To: Scott Fluhrer (sfluhrer) > Cc: Rene Struik; cfrg@irtf.org; saag@ietf.org; Peter Gutmann > Subject: Re: [Cfrg] [saag] A proposal for compact representation of an > elliptic curve point (ECC point compression) >=20 > I have the same comment as Scott, but I am not sure exactly what Rene > means. >=20 > I will assume that Rene says that because there are two y for each x, one= can > calculate the corresponding y or p-y and choose one at random. >=20 > The format I proposed indeed fits very well with the feature of the ECDH- > based protocol that Scott refers to (which covers ECC encryption and key > agreement). As the draft shows, one simply drops the y coordinate to obta= in > the compact representation, while there are no extra steps for ECDH key > generation (because ECDH keys are not sensitive to maintaining the "right= " > y). >=20 > The extra key generation step is only needed for ECDSA keys. Actually, as Rene pointed out to me privately, it isn't much more for ECDSA= , at least with the standard algorithm. The ECDSA verification is a check whether r =3D (uG + vQ)_x, where Q is the= public key. If you are given only the x coordinate of Q, what you do is t= o pick a corresponding y coordinate (so you get a point S where either S=3D= Q or S=3D-Q, where Q is the original public key), and check if one of these= two holds: r =3D (uG + vS)_x r =3D (uG - vS)_x If either does, the signature verifies. This adds the cost of a single poi= nt addition (and the cost of generating the y coordinate of S); fairly smal= l. >=20 > On 12/12/2012 08:52 AM, Scott Fluhrer (sfluhrer) wrote: > > > > > >> -----Original Message----- > >> From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf > >> Of Rene Struik > >> Sent: Wednesday, December 12, 2012 9:17 AM > >> To: Andrey Jivsov > >> Cc: cfrg@irtf.org; saag@ietf.org; Peter Gutmann > >> Subject: Re: [Cfrg] [saag] A proposal for compact representation of > >> an elliptic curve point (ECC point compression) > >> > >> Hi Andrey: > >> > >> One can already implement the x-coordinate only representation of an > >> elliptic curve point simply by converting the affine representation > >> into compressed representation and randomizing the compression "bit". > >> The reverse operation then yields the point or its inverse (which > >> have the same x-coordinate). > >> > >> To my knowledge, this does not require any changes to data formatting > >> (nor additional bytes). > > > > That randomization of the y-component works fine for ECDH (at least, if > you use only the x-component of the shared secret); however, it doesn't > work for ECDSA public keys. > > > >> > >> Best regards, > >> > >> Rene > >> > >> On 12/11/2012 6:37 PM, Andrey Jivsov wrote: > >>> On 12/11/2012 03:15 PM, Peter Gutmann wrote: > >>>> Andrey Jivsov writes: > >>>> > >>>>> I thought that it would be useful for the Internet community to > >>>>> have an IETF document that describes how to encode an ECC point. > >>>> > >>>> Maybe I'm missing something here, but wouldn't this just consist of: > >>>> > >>>> -- Snip -- > >>>> > >>>> See [1]. > >>>> > >>>> [1] X9.62-2005, "Public Key Cryptography for the Financial Services > >>>> Industry: > >>>> The Elliptic Curve Digital Signature Standard (ECDSA)", November, > 2005. > >>>> > >>>> -- Snip -- > >>>> > >>>> That's what every existing RFC that uses ECC seems to be using. > >>>> > >>>> Peter. > >>>> > >>> > >>> Hello Peter. > >>> > >>> "X9.62-2005" in the search engine lends me on a page that asks for > >>> $100. I think http://www.secg.org/collateral/sec1_final.pdf [SEC1] > >>> is more popular as a reference (assuming they are identical > >>> regarding the point compression method). > >>> > >>> I claim that what I submitted is better in many respects than SEC1. > >>> > >>> Let me expand on one of the benefits not covered in the spec. It's > >>> very likely that an employee of a commercial company thinking about > >>> using [SEC1] compression with any ECC method would get an order from > >>> the legal department to stay away from compression. The fact that > >>> somebody on the Internet posted something to the contrary has little > >>> weight for them. My contribution is an attempt towards a compact > >>> representation that is actually usable in practice. It's the most > >>> direct extension to the 1985 idea by [Miller] (see my document for > >>> details). > >>> > >>> Thank you. > >>> > >>> _______________________________________________ > >>> saag mailing list > >>> saag@ietf.org > >>> https://www.ietf.org/mailman/listinfo/saag > >> > >> > >> -- > >> email: rstruik.ext@gmail.com | Skype: rstruik > >> cell: +1 (647) 867-5658 | US: +1 (415) 690-7363 > >> > >> _______________________________________________ > >> Cfrg mailing list > >> Cfrg@irtf.org > >> http://www.irtf.org/mailman/listinfo/cfrg From vf@unity.net Thu Dec 13 03:21:26 2012 Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 8C3FC21F8945; Thu, 13 Dec 2012 03:21:25 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.599 X-Spam-Level: X-Spam-Status: No, score=-2.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id hP6wexnLH3Pm; Thu, 13 Dec 2012 03:21:25 -0800 (PST) Received: from vc.unity.net (140-242.trifle.net [195.24.140.242]) by ietfa.amsl.com (Postfix) with ESMTP id D6C7021F8A4D; Thu, 13 Dec 2012 03:21:24 -0800 (PST) Received: from vf by vc.unity.net with local (Exim 4.72) (envelope-from ) id 1Tj6qn-0002ac-V3; Thu, 13 Dec 2012 13:21:13 +0200 Date: Thu, 13 Dec 2012 13:21:13 +0200 From: Vadym Fedyukovych To: "Scott Fluhrer (sfluhrer)" Message-ID: <20121213112113.GJ17472@unity.net> References: <50C7C3AC.7010405@brainhub.org> <50C891E7.4000009@gmail.com> <50C8D4D1.8050805@brainhub.org> MIME-Version: 1.0 Content-Type: text/plain; charset=koi8-r Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.20 (2009-06-14) Cc: Andrey Jivsov , "cfrg@irtf.org" , "saag@ietf.org" , Peter Gutmann Subject: Re: [Cfrg] [saag] A proposal for compact representation of an elliptic curve point (ECC point compression) X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 13 Dec 2012 11:21:27 -0000 On Wed, Dec 12, 2012 at 08:10:53PM +0000, Scott Fluhrer (sfluhrer) wrote: > > > -----Original Message----- > > From: Andrey Jivsov [mailto:openpgp@brainhub.org] > > Sent: Wednesday, December 12, 2012 2:03 PM > > > [...] > > I will assume that Rene says that because there are two y for each x, one can > > calculate the corresponding y or p-y and choose one at random. > [...] > Actually, as Rene pointed out to me privately, it isn't much more for ECDSA, at least with the standard algorithm. > > The ECDSA verification is a check whether r = (uG + vQ)_x, where Q is the public key. If you are given only the x coordinate of Q, what you do is to pick a corresponding y coordinate (so you get a point S where either S=Q or S=-Q, where Q is the original public key), and check if one of these two holds: > > r = (uG + vS)_x > r = (uG - vS)_x > > If either does, the signature verifies. This adds the cost of a single point addition (and the cost of generating the y coordinate of S); fairly small. This looks like a non-trivial change of threat model to me. There may be two different messages signed with such a signature. To be practical, one would consider generating (well, calculating) a key to fit any two pre-selected messages later. "IOY amount/10" could be an example for a nice article in game theory. > > On 12/12/2012 08:52 AM, Scott Fluhrer (sfluhrer) wrote: > > > > > > > > >> -----Original Message----- > > >> From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf > > >> Of Rene Struik > > >> Sent: Wednesday, December 12, 2012 9:17 AM > [...] From kmigoe@nsa.gov Thu Dec 13 10:42:59 2012 Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id BCCD421F88D8 for ; Thu, 13 Dec 2012 10:42:59 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -10.598 X-Spam-Level: X-Spam-Status: No, score=-10.598 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_HI=-8] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 0OWTW7HL50O1 for ; Thu, 13 Dec 2012 10:42:57 -0800 (PST) Received: from nsa.gov (emvm-gh1-uea08.nsa.gov [63.239.67.9]) by ietfa.amsl.com (Postfix) with ESMTP id 23E2421F88CE for ; Thu, 13 Dec 2012 10:42:56 -0800 (PST) X-TM-IMSS-Message-ID: <18cfab8c00039ea3@nsa.gov> Received: from MSHT-GH1-UEA02.corp.nsa.gov ([10.215.227.181]) by nsa.gov ([63.239.67.9]) with ESMTP (TREND IMSS SMTP Service 7.1; TLSv1/SSLv3 AES128-SHA (128/128)) id 18cfab8c00039ea3 ; Thu, 13 Dec 2012 13:42:56 -0500 Received: from MSMR-GH1-UEA02.corp.nsa.gov (10.215.227.180) by MSHT-GH1-UEA02.corp.nsa.gov (10.215.227.181) with Microsoft SMTP Server (TLS) id 14.1.289.1; Thu, 13 Dec 2012 13:42:55 -0500 Received: from MSMR-GH1-UEA03.corp.nsa.gov ([10.215.224.3]) by MSMR-GH1-UEA02.corp.nsa.gov ([10.215.227.180]) with mapi id 14.01.0289.001; Thu, 13 Dec 2012 13:42:55 -0500 From: "Igoe, Kevin M." To: "cfrg@irtf.org" Thread-Topic: Status of DragonFly Thread-Index: Ac3YlStNhI1Pb7rLTAC7Nu690xzU7Q== Date: Thu, 13 Dec 2012 18:42:54 +0000 Message-ID: <3C4AAD4B5304AB44A6BA85173B4675CA49672A1B@MSMR-GH1-UEA03.corp.nsa.gov> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [10.215.254.27] Content-Type: multipart/alternative; boundary="_000_3C4AAD4B5304AB44A6BA85173B4675CA49672A1BMSMRGH1UEA03cor_" MIME-Version: 1.0 Cc: Dan Harkins Subject: [Cfrg] Status of DragonFly X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 13 Dec 2012 18:42:59 -0000 --_000_3C4AAD4B5304AB44A6BA85173B4675CA49672A1BMSMRGH1UEA03cor_ Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable I'd like the reading list's input on DragonFly (hereafter called DF), Dan H= arkins' Password Authenticated Key Exchange design (draft-irtf-cfrg-dragonfly-00). I'd like to point out = that draft-harkins-tls-pwd-03 is a proposal to use DF in TLS that differs slightly from the CFRG draft. Here is where I believe we stand: 1) Confidentiality: The proof that the confidentiality of the key gene= rated by the DF protocol is reducible to the standard Diffie-Hellmann problem is quit= e straight forward, so the resulting shared secret value is at least as secure a= s with standard DH/ECDH. 2) Authentication: Obviously the system can be no more secure than the= password being used. I believe the most viable attack is to guess a password, = use this password to initiate the DF protocol with the endpoint being attacked, and se= e if it works. Monitoring the system logs should easily detect such an attack. 3) Timing: I'm particularly concerned about the method used to generat= e the PE (password dependent base point) in the ECDH case. Inside a while loop, several parame= ters, including the identities of the two endpoints, the shared password, and a = counter are passed to a KDF to produce an n-bit output, where the curve is mod an n-bit= prime p. The resulting n-bit value X is checked to see if 0 <=3D X < p and X^3+a*X+b= is a quadratic residue mod p (an event of probability =BD). If both these tests are passe= d, the while loop is exited and X is used as the x-coordinate of our PE. The problem I see with (3) is that the number of times through the loop giv= es an opponent a check on any putative value for the password. E.g. if their current gues= s for the password takes many passes through the while loop to generate the PE, but they obser= ve that the DF response time is inconsistent with that, they have eliminated that guess for the pa= ssword. When DF is applied to TLS in as described in draft-harkins-tls-pwd-03= , two nonces are used as inputs to the KDF, which has two consequences: a. the PE MUST be computed online b. each DF exchange gives an independent timing check on the password. The opponent can passively sit back, monitoring the timing of DF exch= anges on various links until they stumble across one where the timings match up with the timings a= ssociated with one of the passwords they are testing. They've now are able to bypass the authen= tication provided by DF. A possible fix is to use the KDF to generate a random X, 1 | of thinking we used when we create= d them." | - Albert Einstein - ----------------+-------------------------------------------------- --_000_3C4AAD4B5304AB44A6BA85173B4675CA49672A1BMSMRGH1UEA03cor_ Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable
I’d like the reading list’s input on DragonFly (hereafter = called DF), Dan Harkins’ Password Authenticated
Key Exchange design (draft-irtf-cfrg-dragonfly-00).  I’d like to= point out that draft-harkins-tls-pwd-03
is a proposal to use DF in  TLS that differs slightly f= rom the CFRG draft.
 
Here is where I believe we stand:
 
  1. Confidentiality: The proof that the confidentiality of the key generate= d by the DF
    protocol is reducible to the standard Diffie-Hellmann problem is quite stra= ight
    forward, so the resulting shared secret value is at least as secure as with=   standard DH/ECDH.
  2. Authentication: Obviously the system can be no more secure than th= e password
    being used. I believe the most viable attack is to guess a password, use th= is password
    to initiate the  DF protocol with the endpoint being attacked, and see= if it works.
    Monitoring the system logs should easily detect such an attack.
  3. Timing: I’m particularly concerned about the method used to = generate the PE (password
    dependent base point) in the ECDH case. Inside a while loop, several parame= ters,
     including the identities of the two endpoints, the shared password, a= nd a counter are
    passed to a KDF to produce an n-bit output, where the curve is mod an n-bit= prime p.
    The resulting n-bit value X is checked to see if 0 <=3D X < p and X^3= +a*X+b is a quadratic
    residue mod p (an event of probability =BD).  If both these tests are = passed, the while
    loop is exited and X is used as the x-coordinate of our PE.

    The problem I see with (3) is that the number of times through the loop giv= es an opponent a
    check  on any putative value for the password.  E.g.  if the= ir current guess for the password
    takes many passes through the while loop to generate the PE, but they obser= ve that the DF response
     time is inconsistent with that, they have eliminated that guess for t= he password. 
 
When DF is applied to TLS in as described= in draft-harkins-tls-pwd-03, two nonces are used as
inputs to the KDF, which has two consequences:
  1. the PE MUST be computed online
  2. each DF exchange gives an indepe= ndent timing check on the password.
The opponent can passively sit back, moni= toring the timing of DF exchanges on various links until
they stumble across one where the timings match up with the timings associa= ted with one of the
passwords they are testing. They’ve now are able to bypass the authen= tication provided by DF.

A possible fix is to use the KDF to generate a random X, 1<X<q, where= q is the size of the cryptographic
subgroup of the curve, and take PE =3D X*= G, where G is the generator of the cryptographic subgroup.  For
most cryptographic curves,  q  is very, very close to 2^n, so it = is VERY unlikely that more than 1 call to the
KDF will be needed.
 
Another fix would be to require PE genera= tion be done offline, which would eliminate any possibility of
using nonces in the DF protocol.  One could, however, mix the nonces i= n after the completion to the
DF based Diffie-Hellmann exchange.  =
 
 
 
 
----------------+------------------------------------= --------------
Kevin M. Igoe   | "We can't solve problems= by using the same kind
kmigoe@nsa.gov  | of thinking we used when we created them."
         &nb= sp;      |      &nbs= p;       - Albert Einstein -
----------------+------------------------------------= --------------
 
 
 
 --_000_3C4AAD4B5304AB44A6BA85173B4675CA49672A1BMSMRGH1UEA03cor_-- From rstruik.ext@gmail.com Thu Dec 13 11:12:15 2012 Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 86E0421F880F for ; Thu, 13 Dec 2012 11:12:15 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -3.599 X-Spam-Level: X-Spam-Status: No, score=-3.599 tagged_above=-999 required=5 tests=[AWL=-0.001, BAYES_00=-2.599, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-1] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 4jzn3V0n+wTK for ; Thu, 13 Dec 2012 11:12:00 -0800 (PST) Received: from mail-ia0-f182.google.com (mail-ia0-f182.google.com [209.85.210.182]) by ietfa.amsl.com (Postfix) with ESMTP id 5746E21F871D for ; Thu, 13 Dec 2012 11:12:00 -0800 (PST) Received: by mail-ia0-f182.google.com with SMTP id x2so2370620iad.13 for ; Thu, 13 Dec 2012 11:12:00 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type; bh=tXPjjasxVTOrEvQkIidRPcex6XIJqSGQY4QoWHj3DwY=; b=m+QDVe3mPQYyiNbhsxidaq+dj7VUzoI7Aj9xcmxO7acISJ1PqreQwjF2KNs+guwD0U 1UySYiTBwJr5kg01emzK8nL+dr5hEg5vBUp9CAI9e9JhOPM3iS2GhmnE+EZ6WErVLP5x HzyIE7QAaWAmU+Mv0b04+0k0dkFHx5X0Stf6qV2+4lwoc9npPM3ST9jPPdkLKRzVJaWk tAJOsO8retUS+z3TrhKJdaZ/EX5dsB8pfjqgSlBnVnraI1GO3W6zCiSDseOaBmBJNbbA g2F3xIrc1EINXjJhawzJa4FFau525bmAM8m5M+zFnfslijAGFP9OCHHKnlO77/gPxJrr 2L1A== Received: by 10.50.213.7 with SMTP id no7mr2820986igc.18.1355425919871; Thu, 13 Dec 2012 11:11:59 -0800 (PST) Received: from [192.168.1.103] (CPE0013100e2c51-CM001cea35caa6.cpe.net.cable.rogers.com. [99.231.4.27]) by mx.google.com with ESMTPS id yf6sm1958347igb.0.2012.12.13.11.11.58 (version=TLSv1/SSLv3 cipher=OTHER); Thu, 13 Dec 2012 11:11:59 -0800 (PST) Message-ID: <50CA2873.1090509@gmail.com> Date: Thu, 13 Dec 2012 14:11:47 -0500 From: Rene Struik User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/17.0 Thunderbird/17.0 MIME-Version: 1.0 To: "Igoe, Kevin M." References: <3C4AAD4B5304AB44A6BA85173B4675CA49672A1B@MSMR-GH1-UEA03.corp.nsa.gov> In-Reply-To: <3C4AAD4B5304AB44A6BA85173B4675CA49672A1B@MSMR-GH1-UEA03.corp.nsa.gov> Content-Type: multipart/alternative; boundary="------------030500070005090701000905" Cc: Dan Harkins , "cfrg@irtf.org" Subject: Re: [Cfrg] Status of DragonFly X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 13 Dec 2012 19:12:15 -0000 This is a multi-part message in MIME format. --------------030500070005090701000905 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit Hi Kevin: I do share some of your timing attack concerns. Unless I missed something here, your suggested fix does not seem to work, however: Suppose A and B use ECDH with as generator the point G(p):= pG, where p:=kdf(..) {I use small-case p ("password") rather than capital-case X below (so as to separate scalars and elliptic curve points)}. Now, suppose A and B exchange X:=xG(p) where p is the correct password and where Y:= y G(p'), where p' is any guess for p by B (or just takes p":=1). Then A (the legitimate party holding password p) computes Ka:= (xy) G(p')= (xy p') G and B computes Kb:=(yx) G(p)= (yxp) G. In other words, Ka:= p' K, Kb:= p K, where K:= (xy)G. So, Ka:= (p'/p) Kb. Now, once A sends B a key confirmation message, B can just cycle through the password space, compute a candidate key that A could have computed and check the validity of his guess via verification of the key confirmation message just received. As to implementing Dragonfly, one has to be careful in case of active attacks: as an example, if one uses multiple-point multiplications, one may end up at the point of infinity as intermediate point in the computation, thus forcing implementations to use exception handling routines for point addition/doubling along the entire computational path (Note: if one hits the point at infinity, this exposes the password used, thus leaking the entire password in an observable way). If one does not use multiple-point multiplications, this attack seems much harder but requires two full scalar multiplications (rather than one scalar multiplication as, e.g., SPEKE requires). Best regards, Rene == A possible fix is to use the KDF to generate a random X, 1 I'd like the reading list's input on DragonFly (hereafter called DF), > Dan Harkins' Password Authenticated > Key Exchange design (draft-irtf-cfrg-dragonfly-00). I'd like to point > out that draft-harkins-tls-pwd-03 > is a proposal to useDF in TLS that differs slightly from the CFRG draft. > Here is where I believe we stand: > > 1. Confidentiality: The proof that the confidentiality of the key > generated by the DF > protocol is reducible to the standard Diffie-Hellmann problem is > quite straight > forward, so the resulting shared secret value is at least as > secure as with standard DH/ECDH. > 2. Authentication: Obviously the system can be no more secure than > the password > being used. I believe the most viable attack is to guess a > password, use this password > to initiate the DF protocol with the endpoint being attacked, and > see if it works. > Monitoring the system logs should easily detect such an attack. > 3. Timing: I'm particularly concerned about the method used to > generate the PE (password > dependent base point) in the ECDH case. Inside a while loop, > several parameters, > including the identities of the two endpoints, the shared > password, and a counter are > passed to a KDF to produce an n-bit output, where the curve is mod > an n-bit prime p. > The resulting n-bit value X is checked to see if 0 <= X < p and > X^3+a*X+b is a quadratic > residue mod p (an event of probability ½). If both these tests > are passed, the while > loop is exited and X is used as the x-coordinate of our PE. > > The problem I see with (3) is that the number of times through the > loop gives an opponent a > check on any putative value for the password. E.g. if their > current guess for the password > takes many passes through the while loop to generate the PE, but > they observe that the DF response > time is inconsistent with that, they have eliminated that guess > for the password. > > When DF is applied to TLS in as described in draft-harkins-tls-pwd-03, > two nonces are used as > inputs to the KDF, which has two consequences: > > 1. the PE MUST be computed online > 2. each DF exchange gives an independent timing check on the password. > > The opponent can passively sit back, monitoring the timing of DF > exchanges on various links until > they stumble across one where the timings match up with the timings > associated with one of the > passwords they are testing. They've now are able to bypass the > authentication provided by DF. > > A possible fix is to use the KDF to generate a random X, 1 q is the size of the cryptographic > subgroup of the curve, and take PE = X*G, where G is the generator of > the cryptographic subgroup. For > most cryptographic curves, q is very, very close to 2^n, so it is > VERY unlikely that more than 1 call to the > KDF will be needed. > Another fix would be to require PE generation be done offline, which > would eliminate any possibility of > using nonces in the DF protocol. One could, however, mix the nonces > in after the completion to the > DF based Diffie-Hellmann exchange. > ----------------+-------------------------------------------------- > Kevin M. Igoe | "We can't solve problems by using the same kind > _kmigoe@nsa.gov_ | of thinking we used when > we created them." > | - Albert Einstein - > ----------------+-------------------------------------------------- > > > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > http://www.irtf.org/mailman/listinfo/cfrg -- email: rstruik.ext@gmail.com | Skype: rstruik cell: +1 (647) 867-5658 | US: +1 (415) 690-7363 --------------030500070005090701000905 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit
Hi Kevin:

I do share some of your timing attack concerns. Unless I missed something here, your suggested fix does not seem to work, however:

Suppose A and B use ECDH with as generator the point G(p):= pG, where p:=kdf(..) {I use small-case p ("password") rather than capital-case X below (so as to separate scalars and elliptic curve points)}. Now, suppose A and B exchange X:=xG(p) where p is the correct password and where Y:= y G(p'), where p' is any guess for p by B (or just takes p":=1). Then A (the legitimate party holding password p) computes Ka:= (xy) G(p')= (xy p') G and B computes Kb:=(yx) G(p)= (yxp) G. In other words, Ka:= p' K, Kb:= p K, where K:= (xy)G. So, Ka:= (p'/p) Kb. Now, once A sends B a key confirmation message, B can just cycle through the password space, compute a candidate key that A could have computed and check the validity of his guess via verification of the key confirmation message just received.

As to implementing Dragonfly, one has to be careful in case of active attacks: as an example, if one uses multiple-point multiplications, one may end up at the point of infinity as intermediate point in the computation, thus forcing implementations to use exception handling routines for point addition/doubling along the entire computational path (Note: if one hits the point at infinity, this exposes the password used, thus leaking the entire password in an observable way). If one does not use multiple-point multiplications, this attack seems much harder but requires two full scalar multiplications (rather than one scalar multiplication as, e.g., SPEKE requires).

Best regards, Rene

==
A possible fix is to use the KDF to generate a random X, 1<X<q, where q is the size of the cryptographic
subgroup of the curve, and take PE = X*G, where G is the generator of the cryptographic subgroup.  For
most cryptographic curves,  q  is very, very close to 2^n, so it is VERY unlikely that more than 1 call to the
KDF will be needed.


On 12/13/2012 1:42 PM, Igoe, Kevin M. wrote:
I’d like the reading list’s input on DragonFly (hereafter called DF), Dan Harkins’ Password Authenticated
Key Exchange design (draft-irtf-cfrg-dragonfly-00).  I’d like to point out that draft-harkins-tls-pwd-03
is a proposal to use DF in  TLS that differs slightly from the CFRG draft.
 
Here is where I believe we stand:
 
  1. Confidentiality: The proof that the confidentiality of the key generated by the DF
    protocol is reducible to the standard Diffie-Hellmann problem is quite straight
    forward, so the resulting shared secret value is at least as secure as with  standard DH/ECDH.
  2. Authentication: Obviously the system can be no more secure than the password
    being used. I believe the most viable attack is to guess a password, use this password
    to initiate the  DF protocol with the endpoint being attacked, and see if it works.
    Monitoring the system logs should easily detect such an attack.
  3. Timing: I’m particularly concerned about the method used to generate the PE (password
    dependent base point) in the ECDH case. Inside a while loop, several parameters,
     including the identities of the two endpoints, the shared password, and a counter are
    passed to a KDF to produce an n-bit output, where the curve is mod an n-bit prime p.
    The resulting n-bit value X is checked to see if 0 <= X < p and X^3+a*X+b is a quadratic
    residue mod p (an event of probability ½).  If both these tests are passed, the while
    loop is exited and X is used as the x-coordinate of our PE.

    The problem I see with (3) is that the number of times through the loop gives an opponent a
    check  on any putative value for the password.  E.g.  if their current guess for the password
    takes many passes through the while loop to generate the PE, but they observe that the DF response
     time is inconsistent with that, they have eliminated that guess for the password. 
 
When DF is applied to TLS in as described in draft-harkins-tls-pwd-03, two nonces are used as
inputs to the KDF, which has two consequences:
  1. the PE MUST be computed online
  2. each DF exchange gives an independent timing check on the password.
The opponent can passively sit back, monitoring the timing of DF exchanges on various links until
they stumble across one where the timings match up with the timings associated with one of the
passwords they are testing. They’ve now are able to bypass the authentication provided by DF.

A possible fix is to use the KDF to generate a random X, 1<X<q, where q is the size of the cryptographic
subgroup of the curve, and take PE = X*G, where G is the generator of the cryptographic subgroup.  For
most cryptographic curves,  q  is very, very close to 2^n, so it is VERY unlikely that more than 1 call to the
KDF will be needed.
 
Another fix would be to require PE generation be done offline, which would eliminate any possibility of
using nonces in the DF protocol.  One could, however, mix the nonces in after the completion to the
DF based Diffie-Hellmann exchange. 
 
 
 
 
----------------+--------------------------------------------------
Kevin M. Igoe   | "We can't solve problems by using the same kind
kmigoe@nsa.gov  | of thinking we used when we created them."
                |              - Albert Einstein -
----------------+--------------------------------------------------
 
 
 
 

_______________________________________________
Cfrg mailing list
Cfrg@irtf.org
http://www.irtf.org/mailman/listinfo/cfrg



-- 
email: rstruik.ext@gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
--------------030500070005090701000905-- From sfluhrer@cisco.com Thu Dec 13 11:22:28 2012 Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id D401821F898D for ; Thu, 13 Dec 2012 11:22:28 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -10.598 X-Spam-Level: X-Spam-Status: No, score=-10.598 tagged_above=-999 required=5 tests=[AWL=-0.000, BAYES_00=-2.599, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_HI=-8] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id M0RMHLYyasrT for ; Thu, 13 Dec 2012 11:22:25 -0800 (PST) Received: from rcdn-iport-4.cisco.com (rcdn-iport-4.cisco.com [173.37.86.75]) by ietfa.amsl.com (Postfix) with ESMTP id 7A08D21F897E for ; Thu, 13 Dec 2012 11:22:25 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=22335; q=dns/txt; s=iport; t=1355426545; x=1356636145; h=from:to:cc:subject:date:message-id:references: in-reply-to:mime-version; bh=Gk0FuYoI3x1GW5aXRLUaujQ+RJteICQdedbWxWDJaS4=; b=d9UndiXbxZELfUFZyf9Hub/hNa6QNurRK8oBrLgMRT47+UQCseB7ABXI pfMuf1BtLRYAMPd+sQYmclO1/aXiH/pbW+X0poQ0EaJWqSYo3BAs6LbQD fNfosESEtf4B1Wt8fSRP8eNBzmxFaZjVKLr1RggtsmNrsfHMGvm0TxcrT 4=; X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgEFAL8pylCtJXG8/2dsb2JhbABFgkm8JxZzgh4BAQEELUwQAgEIEQQBAQsOCAcHMhQJCAEBBAENBQiIC7xvjFeBHIJGYQOIK4ork3uCc4Ii X-IronPort-AV: E=Sophos;i="4.84,275,1355097600"; d="scan'208,217";a="152729348" Received: from rcdn-core2-1.cisco.com ([173.37.113.188]) by rcdn-iport-4.cisco.com with ESMTP; 13 Dec 2012 19:22:24 +0000 Received: from xhc-rcd-x05.cisco.com (xhc-rcd-x05.cisco.com [173.37.183.79]) by rcdn-core2-1.cisco.com (8.14.5/8.14.5) with ESMTP id qBDJMLdI002246 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=FAIL); Thu, 13 Dec 2012 19:22:24 GMT Received: from xmb-rcd-x04.cisco.com ([169.254.8.29]) by xhc-rcd-x05.cisco.com ([173.37.183.79]) with mapi id 14.02.0318.004; Thu, 13 Dec 2012 13:14:13 -0600 From: "Scott Fluhrer (sfluhrer)" To: "Igoe, Kevin M." , "cfrg@irtf.org" Thread-Topic: Status of DragonFly Thread-Index: Ac3YlStNhI1Pb7rLTAC7Nu690xzU7QAzgKEg Date: Thu, 13 Dec 2012 19:14:12 +0000 Message-ID: References: <3C4AAD4B5304AB44A6BA85173B4675CA49672A1B@MSMR-GH1-UEA03.corp.nsa.gov> In-Reply-To: <3C4AAD4B5304AB44A6BA85173B4675CA49672A1B@MSMR-GH1-UEA03.corp.nsa.gov> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [10.32.244.86] Content-Type: multipart/alternative; boundary="_000_A113ACFD9DF8B04F96395BDEACB340421E74A3xmbrcdx04ciscocom_" MIME-Version: 1.0 Cc: Dan Harkins Subject: Re: [Cfrg] Status of DragonFly X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 13 Dec 2012 19:22:29 -0000 --_000_A113ACFD9DF8B04F96395BDEACB340421E74A3xmbrcdx04ciscocom_ Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf Of Igo= e, Kevin M. Sent: Thursday, December 13, 2012 1:43 PM To: cfrg@irtf.org Cc: Dan Harkins Subject: [Cfrg] Status of DragonFly I'd like the reading list's input on DragonFly (hereafter called DF), Dan H= arkins' Password Authenticated Key Exchange design (draft-irtf-cfrg-dragonfly-00). I'd like to point out = that draft-harkins-tls-pwd-03 is a proposal to use DF in TLS that differs slightly from the CFRG draft. Here is where I believe we stand: 1. Confidentiality: The proof that the confidentiality of the key gen= erated by the DF protocol is reducible to the standard Diffie-Hellmann problem is quite stra= ight forward, so the resulting shared secret value is at least as secure as with= standard DH/ECDH. 2. Authentication: Obviously the system can be no more secure than th= e password being used. I believe the most viable attack is to guess a password, use th= is password to initiate the DF protocol with the endpoint being attacked, and see if i= t works. Monitoring the system logs should easily detect such an attack. 3. Timing: I'm particularly concerned about the method used to genera= te the PE (password dependent base point) in the ECDH case. Inside a while loop, several parame= ters, including the identities of the two endpoints, the shared password, and a = counter are passed to a KDF to produce an n-bit output, where the curve is mod an n-bit= prime p. The resulting n-bit value X is checked to see if 0 <=3D X < p and X^3+a*X+b= is a quadratic residue mod p (an event of probability =BD). If both these tests are passe= d, the while loop is exited and X is used as the x-coordinate of our PE. The problem I see with (3) is that the number of times through the loop giv= es an opponent a check on any putative value for the password. E.g. if their current gues= s for the password takes many passes through the while loop to generate the PE, but they obser= ve that the DF response time is inconsistent with that, they have eliminated that guess for the pa= ssword. When DF is applied to TLS in as described in draft-harkins-tls-pwd-03, two = nonces are used as inputs to the KDF, which has two consequences: a. the PE MUST be computed online b. each DF exchange gives an independent timing check on the password. The opponent can passively sit back, monitoring the timing of DF exchanges = on various links until they stumble across one where the timings match up with the timings associa= ted with one of the passwords they are testing. They've now are able to bypass the authenticati= on provided by DF. A possible fix is to use the KDF to generate a random X, 1 | of thinking we used when we create= d them." | - Albert Einstein - ----------------+-------------------------------------------------- --_000_A113ACFD9DF8B04F96395BDEACB340421E74A3xmbrcdx04ciscocom_ Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

 <= /p>

 <= /p>

From: cfrg-bou= nces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf Of Igoe, Kevin M.
Sent: Thursday, December 13, 2012 1:43 PM
To: cfrg@irtf.org
Cc: Dan Harkins
Subject: [Cfrg] Status of DragonFly

 

I’d like the reading list’s= input on DragonFly (hereafter called DF), Dan Harkins’ Password Auth= enticated
Key Exchange design (draft-irtf-cfrg-dragonfly-00).  I’d like to= point out that draft-harkins-tls-pwd-03

is a proposal to use DF in  TLS that differs slightly from the CFRG dra= ft.

 

Here is where I believe we stand:<= /o:p>

 

1.    &nb= sp;  Confidentiality: The proof that= the confidentiality of the key generated by the DF
protocol is reducible to the standard Diffie-Hellmann problem is quite stra= ight
forward, so the resulting shared secret value is at least as secure as with=   standard DH/ECDH.

2.    &nb= sp;  Authentication: Obviously the s= ystem can be no more secure than the password
being used. I believe the most viable attack is to guess a password, use th= is password
to initiate the  DF protocol with the endpoint being attacked, and see= if it works.
Monitoring the system logs should easily detect such an attack. =

3.    &nb= sp;  Timing: I’m particularly = concerned about the method used to generate the PE (password
dependent base point) in the ECDH case. Inside a while loop, several parame= ters,
 including the identities of the two endpoints, the shared password, a= nd a counter are
passed to a KDF to produce an n-bit output, where the curve is mod an n-bit= prime p.
The resulting n-bit value X is checked to see if 0 <=3D X < p and X^3= +a*X+b is a quadratic
residue mod p (an event of probability =BD).  If both these tests are = passed, the while
loop is exited and X is used as the x-coordinate of our PE.

The problem I see with (3) is that the number of times through the loop giv= es an opponent a
check  on any putative value for the password.  E.g.  if the= ir current guess for the password
takes many passes through the while loop to generate the PE, but they obser= ve that the DF response
 time is inconsistent with that, they have eliminated that guess for t= he password. 

 

When DF is applied to TLS in as describ= ed in draft-harkins-tls-pwd-03, two nonces are used as
inputs to the KDF, which has two consequences:

a.    &nb= sp;  the PE MUST be computed online<= o:p>

b.    &nb= sp; each DF exchange gives an indep= endent timing check on the password.

The opponent can passively sit back, mo= nitoring the timing of DF exchanges on various links until
they stumble across one where the timings match up with the timings associa= ted with one of the
passwords they are testing. They’ve now are able to bypass the authen= tication provided by DF.

A possible fix is to use the KDF to generate a random X, 1<X<q, where= q is the size of the cryptographic

subgroup of the curve, and take PE =3D = X*G, where G is the generator of the cryptographic subgroup.  For
most cryptographic curves,  q  is very, very close to 2^n, so it = is VERY unlikely that more than 1 call to the

KDF will be needed.

 <= /p>

You sure?  I believe= this breaks the security property of the protocol.  That is, if the a= ttacker knows the order of potential points PE, he knows their relative order, and so is able to test multiple passwords by examining the results = of a single exchange.  With Dan’s approach, no one knows the rel= ative order of any PE.

 

Another fix would be to require PE gene= ration be done offline, which would eliminate any possibility of
using nonces in the DF protocol.  One could, however, mix the nonces i= n after the completion to the

DF based Diffie-Hellmann exchange. = ;

 <= /p>

The other possible fix is= to mandate that N (where N is perhaps 40) different x values are generated= and tested; only after all N are tested, we pick the middle one that succeeded (middle one so an engineer would not be tempted to skip= the tests after one passed :-); if all N failed, then we do some error han= dling (say, keep on generating x’s until we do find one that pass).&n= bsp; This takes mostly constant time, and if N=3D40, the error handling will be hardly ever run (one in a trillion key = exchanges).

 

 

 

 

----------------+-----------------------= ---------------------------

Kevin M. Igoe   | "We can't s= olve problems by using the same kind<= /p>

kmigoe@nsa.= gov  | of thinking we used when we created them."

       &n= bsp;        |    &nb= sp;         - Albert Einstein -

----------------+-----------------------= ---------------------------

 

 

 

--_000_A113ACFD9DF8B04F96395BDEACB340421E74A3xmbrcdx04ciscocom_-- From kmigoe@nsa.gov Thu Dec 13 12:19:35 2012 Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 7341A21F8A0F for ; Thu, 13 Dec 2012 12:19:35 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -10.598 X-Spam-Level: X-Spam-Status: No, score=-10.598 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_HI=-8] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 7VkWzzBV5T2d for ; Thu, 13 Dec 2012 12:19:31 -0800 (PST) Received: from nsa.gov (emvm-gh1-uea08.nsa.gov [63.239.67.9]) by ietfa.amsl.com (Postfix) with ESMTP id D28D821F89BE for ; Thu, 13 Dec 2012 12:19:30 -0800 (PST) X-TM-IMSS-Message-ID: <1928102a0003b794@nsa.gov> Received: from MSHT-GH1-UEA02.corp.nsa.gov ([10.215.227.181]) by nsa.gov ([63.239.67.9]) with ESMTP (TREND IMSS SMTP Service 7.1; TLSv1/SSLv3 AES128-SHA (128/128)) id 1928102a0003b794 ; Thu, 13 Dec 2012 15:19:29 -0500 Received: from MSMR-GH1-UEA02.corp.nsa.gov (10.215.227.180) by MSHT-GH1-UEA02.corp.nsa.gov (10.215.227.181) with Microsoft SMTP Server (TLS) id 14.1.289.1; Thu, 13 Dec 2012 15:19:28 -0500 Received: from MSMR-GH1-UEA03.corp.nsa.gov ([10.215.224.3]) by MSMR-GH1-UEA02.corp.nsa.gov ([10.215.227.180]) with mapi id 14.01.0289.001; Thu, 13 Dec 2012 15:19:28 -0500 From: "Igoe, Kevin M." To: 'Rene Struik' Thread-Topic: [Cfrg] Status of DragonFly Thread-Index: Ac3YlStNhI1Pb7rLTAC7Nu690xzU7QA+m/WAAAhk1JA= Date: Thu, 13 Dec 2012 20:19:27 +0000 Message-ID: <3C4AAD4B5304AB44A6BA85173B4675CA4AE0C72D@MSMR-GH1-UEA03.corp.nsa.gov> References: <3C4AAD4B5304AB44A6BA85173B4675CA49672A1B@MSMR-GH1-UEA03.corp.nsa.gov> <50CA2873.1090509@gmail.com> In-Reply-To: <50CA2873.1090509@gmail.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [10.215.254.27] Content-Type: multipart/alternative; boundary="_000_3C4AAD4B5304AB44A6BA85173B4675CA4AE0C72DMSMRGH1UEA03cor_" MIME-Version: 1.0 Cc: Dan Harkins , "cfrg@irtf.org" Subject: Re: [Cfrg] Status of DragonFly X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 13 Dec 2012 20:19:35 -0000 --_000_3C4AAD4B5304AB44A6BA85173B4675CA4AE0C72DMSMRGH1UEA03cor_ Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Thanks Rene. I agree with your analysis on my first proposed fix. Clearly= this needs some more thought. Pre-computing PE offline may well turn out to be the best option. From: Rene Struik [mailto:rstruik.ext@gmail.com] Sent: Thursday, December 13, 2012 2:12 PM To: Igoe, Kevin M. Cc: cfrg@irtf.org; Dan Harkins Subject: Re: [Cfrg] Status of DragonFly Hi Kevin: I do share some of your timing attack concerns. Unless I missed something h= ere, your suggested fix does not seem to work, however: Suppose A and B use ECDH with as generator the point G(p):=3D pG, where p:= =3Dkdf(..) {I use small-case p ("password") rather than capital-case X belo= w (so as to separate scalars and elliptic curve points)}. Now, suppose A an= d B exchange X:=3DxG(p) where p is the correct password and where Y:=3D y G= (p'), where p' is any guess for p by B (or just takes p":=3D1). Then A (the= legitimate party holding password p) computes Ka:=3D (xy) G(p')=3D (xy p')= G and B computes Kb:=3D(yx) G(p)=3D (yxp) G. In other words, Ka:=3D p' K, = Kb:=3D p K, where K:=3D (xy)G. So, Ka:=3D (p'/p) Kb. Now, once A sends B a = key confirmation message, B can just cycle through the password space, comp= ute a candidate key that A could have computed and check the validity of hi= s guess via verification of the key confirmation message just received. As to implementing Dragonfly, one has to be careful in case of active attac= ks: as an example, if one uses multiple-point multiplications, one may end = up at the point of infinity as intermediate point in the computation, thus = forcing implementations to use exception handling routines for point additi= on/doubling along the entire computational path (Note: if one hits the poin= t at infinity, this exposes the password used, thus leaking the entire pass= word in an observable way). If one does not use multiple-point multiplicati= ons, this attack seems much harder but requires two full scalar multiplicat= ions (rather than one scalar multiplication as, e.g., SPEKE requires). Best regards, Rene =3D=3D A possible fix is to use the KDF to generate a random X, 1 | of thinking we used when we create= d them." | - Albert Einstein - ----------------+-------------------------------------------------- _______________________________________________ Cfrg mailing list Cfrg@irtf.org http://www.irtf.org/mailman/listinfo/cfrg -- email: rstruik.ext@gmail.com | Skype: rstruik cell: +1 (647) 867-5658 | US: +1 (415) 690-7363 --_000_3C4AAD4B5304AB44A6BA85173B4675CA4AE0C72DMSMRGH1UEA03cor_ Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

Thanks Rene.  I agre= e with your analysis on my first proposed fix.  Clearly this needs som= e more thought.

Pre-computing PE offline = may well turn out to be the best option.

 <= /p>

From: Rene Struik [mailto:rstruik.ext@gmail.com]
Sent: Thursday, December 13, 2012 2:12 PM
To: Igoe, Kevin M.
Cc: cfrg@irtf.org; Dan Harkins
Subject: Re: [Cfrg] Status of DragonFly

 

Hi Kevin:

I do share some of your timing attack concerns. Unless I missed something h= ere, your suggested fix does not seem to work, however:

Suppose A and B use ECDH with as generator the point G(p):=3D pG, where p:= =3Dkdf(..) {I use small-case p ("password") rather than capital-c= ase X below (so as to separate scalars and elliptic curve points)}. Now, su= ppose A and B exchange X:=3DxG(p) where p is the correct password and where Y:=3D y G(p'), where p' is any guess for p by B= (or just takes p":=3D1). Then A (the legitimate party holding passwor= d p) computes Ka:=3D (xy) G(p')=3D (xy p') G and B computes Kb:=3D(yx) G(p)= =3D (yxp) G. In other words, Ka:=3D p' K, Kb:=3D p K, where K:=3D (xy)G. So, Ka:=3D (p'/p) Kb. Now, once A sends B a key confirm= ation message, B can just cycle through the password space, compute a candi= date key that A could have computed and check the validity of his guess via= verification of the key confirmation message just received.

As to implementing Dragonfly, one has to be careful in case of active attac= ks: as an example, if one uses multiple-point multiplications, one may end = up at the point of infinity as intermediate point in the computation, thus = forcing implementations to use exception handling routines for point addition/doubling along the entire computation= al path (Note: if one hits the point at infinity, this exposes the password= used, thus leaking the entire password in an observable way). If one does = not use multiple-point multiplications, this attack seems much harder but requires two full scalar multiplications= (rather than one scalar multiplication as, e.g., SPEKE requires).

Best regards, Rene

=3D=3D
A possible fix is to use the KDF to generate a random X, 1<X<q, where= q is the size of the cryptographic

subgroup of the cur= ve, and take PE =3D X*G, where G is the generator of the cryptographic subg= roup.  For
most cryptographic curves,  q  is very, very close to 2^n, so it = is VERY unlikely that more than 1 call to the

KDF will be needed.

On 12/13/2012 1:42 PM, Igoe, Kevin M. wrote:

I’d like the reading list’s= input on DragonFly (hereafter called DF), Dan Harkins’ Password Auth= enticated
Key Exchange design (draft-irtf-cfrg-dragonfly-00).  I’d like to= point out that draft-harkins-tls-pwd-03

is a proposal to use DF in  TLS that differs slightly from the CFRG dra= ft.

 

Here is where I believe we stand:<= /o:p>

 

1.   Confidentiality: The proof that= the confidentiality of the key generated by the DF
protocol is reducible to the standard Diffie-Hellmann problem is quite stra= ight
forward, so the resulting shared secret value is at least as secure as with=   standard DH/ECDH.

2.   Authentication: Obviously the s= ystem can be no more secure than the password
being used. I believe the most viable attack is to guess a password, use th= is password
to initiate the  DF protocol with the endpoint being attacked, and see= if it works.
Monitoring the system logs should easily detect such an attack. =

3.   Timing: I’m particularly = concerned about the method used to generate the PE (password
dependent base point) in the ECDH case. Inside a while loop, several parame= ters,
 including the identities of the two endpoints, the shared password, a= nd a counter are
passed to a KDF to produce an n-bit output, where the curve is mod an n-bit= prime p.
The resulting n-bit value X is checked to see if 0 <=3D X < p and X^3= +a*X+b is a quadratic
residue mod p (an event of probability =BD).  If both these tests are = passed, the while
loop is exited and X is used as the x-coordinate of our PE.

The problem I see with (3) is that the number of times through the loop giv= es an opponent a
check  on any putative value for the password.  E.g.  if the= ir current guess for the password
takes many passes through the while loop to generate the PE, but they obser= ve that the DF response
 time is inconsistent with that, they have eliminated that guess for t= he password. 

 

When DF is applied to TLS in as describ= ed in draft-harkins-tls-pwd-03, two nonces are used as
inputs to the KDF, which has two consequences:

a.   the PE MUST be computed online<= o:p>

b.   each DF exchange gives an indep= endent timing check on the password.

The opponent can passively sit back, mo= nitoring the timing of DF exchanges on various links until
they stumble across one where the timings match up with the timings associa= ted with one of the
passwords they are testing. They’ve now are able to bypass the authen= tication provided by DF.

A possible fix is to use the KDF to generate a random X, 1<X<q, where= q is the size of the cryptographic

subgroup of the curve, and take PE =3D = X*G, where G is the generator of the cryptographic subgroup.  For
most cryptographic curves,  q  is very, very close to 2^n, so it = is VERY unlikely that more than 1 call to the

KDF will be needed.

 

Another fix would be to require PE gene= ration be done offline, which would eliminate any possibility of
using nonces in the DF protocol.  One could, however, mix the nonces i= n after the completion to the

DF based Diffie-Hellmann exchange. = ;

 

 

 

 

----------------+-----------------------= ---------------------------

Kevin M. Igoe   | "We can't s= olve problems by using the same kind<= /p>

kmigoe@nsa.= gov  | of thinking we used when we created them."

       &n= bsp;        |    &nb= sp;         - Albert Einstein -

----------------+-----------------------= ---------------------------

 

 

 




_______________________________________________
Cfrg mailing list
Cfrg@irtf.org
http://www.irtf.=
org/mailman/listinfo/cfrg




-- 
email: rstruik.ext@gmail.com<=
/a> | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
--_000_3C4AAD4B5304AB44A6BA85173B4675CA4AE0C72DMSMRGH1UEA03cor_-- From kmigoe@nsa.gov Mon Dec 17 13:10:23 2012 Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id B097221F882A for ; Mon, 17 Dec 2012 13:10:23 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -10.598 X-Spam-Level: X-Spam-Status: No, score=-10.598 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_HI=-8] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id bMwZgBrceRSZ for ; Mon, 17 Dec 2012 13:10:17 -0800 (PST) Received: from nsa.gov (emvm-gh1-uea09.nsa.gov [63.239.67.10]) by ietfa.amsl.com (Postfix) with ESMTP id 8DA4021F86CB for ; Mon, 17 Dec 2012 13:10:06 -0800 (PST) X-TM-IMSS-Message-ID: <0a279c430002b220@nsa.gov> Received: from MSHT-GH1-UEA02.corp.nsa.gov ([10.215.227.181]) by nsa.gov ([63.239.67.10]) with ESMTP (TREND IMSS SMTP Service 7.1; TLSv1/SSLv3 AES128-SHA (128/128)) id 0a279c430002b220 ; Mon, 17 Dec 2012 16:09:48 -0500 Received: from MSMR-GH1-UEA01.corp.nsa.gov (10.215.225.4) by MSHT-GH1-UEA02.corp.nsa.gov (10.215.227.181) with Microsoft SMTP Server (TLS) id 14.1.289.1; Mon, 17 Dec 2012 16:10:04 -0500 Received: from MSMR-GH1-UEA03.corp.nsa.gov ([10.215.224.3]) by MSMR-GH1-UEA01.corp.nsa.gov ([10.215.225.4]) with mapi id 14.01.0289.001; Mon, 17 Dec 2012 16:10:04 -0500 From: "Igoe, Kevin M." To: "cfrg@irtf.org" Thread-Topic: [Cfrg] Status of DragonFly Thread-Index: Ac3YlStNhI1Pb7rLTAC7Nu690xzU7QA+m/WAAAhk1JAAt2SbYA== Date: Mon, 17 Dec 2012 21:10:02 +0000 Message-ID: <3C4AAD4B5304AB44A6BA85173B4675CA4C1BE47B@MSMR-GH1-UEA03.corp.nsa.gov> References: <3C4AAD4B5304AB44A6BA85173B4675CA49672A1B@MSMR-GH1-UEA03.corp.nsa.gov> <50CA2873.1090509@gmail.com> <3C4AAD4B5304AB44A6BA85173B4675CA4AE0C72D@MSMR-GH1-UEA03.corp.nsa.gov> In-Reply-To: <3C4AAD4B5304AB44A6BA85173B4675CA4AE0C72D@MSMR-GH1-UEA03.corp.nsa.gov> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [10.215.254.27] Content-Type: multipart/alternative; boundary="_000_3C4AAD4B5304AB44A6BA85173B4675CA4C1BE47BMSMRGH1UEA03cor_" MIME-Version: 1.0 Cc: Dan Harkins Subject: Re: [Cfrg] Status of DragonFly X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 17 Dec 2012 21:10:23 -0000 --_000_3C4AAD4B5304AB44A6BA85173B4675CA4C1BE47BMSMRGH1UEA03cor_ Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable OK folks, we are still on the hook to provide the TLS WG with our analysis = of DragonFly as it currently exists. Here's what I see: 1) The confidentiality provided by DragonFly is at least as good as Di= ffie-Hallmann. 2) Impersonation is a different matter. The nefarious Eve can run thro= ugh a list of likely passwords, attempting to run the DragonFly protocol once for each guess until she hits one where the DragonFly protocol runs to completion, meaning Eve has almost certainly found the correct password. Proper monitoring of the error logs should detect such an attack. In the EC case, the situation is a bit muddier. The use of the nonces in t= he generation of PE leads to a timing attack. Assuming the observer can dete= rmine precisely how many passes have been made through the while-loop, each obse= rved instance of the DragonFly protocol between Alice and Bob provides 2 bits of= information about their common password. If the adversary has a list of 2^M passwords = which is likely to contain the password in use, passively observing about M+8 or so = DragonFly exchanges betwixt Alice and Bob provides enough information to uniquely ide= ntify the password (if it is on the list) with high probability. This is not without= cost to the attacker, they need to test the putative passwords one at a time until they= find one that generates the observed pattern of number of passes through the while l= oop. It all comes down to how well the passwords are chosen, and we all know how good users are at picking passwords. Scott Fluhrer proposed an elegant change to DragonFly that fixes this. In = the EC case, replace the while-loop with a for-loop, say "for t =3D 1,,,,40". On each pass thr= ough this for-loop generate a possible x- coorodinate as in DragonFly, saving off the first x value wh= ich corresponds to a point on the curve. The only thing that can go wrong here is doing all 40-= iterations without finding a good x-coordinate. This is quite unlikely to occur (~ 10^-12), b= ut when it does occur it gives 40 bits of information about the password. In some VERY high volu= me applications it might be prudent to choose a value larger than 40. Many thanks to Rene Struik and Scott Fluhrer for their insightful comments.= Would anyone else on the list like to join in? We can't learn from our mistakes until we realize we've m= ade them. From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf Of Igo= e, Kevin M. Sent: Thursday, December 13, 2012 3:19 PM To: 'Rene Struik' Cc: Dan Harkins; cfrg@irtf.org Subject: Re: [Cfrg] Status of DragonFly Thanks Rene. I agree with your analysis on my first proposed fix. Clearly= this needs some more thought. Pre-computing PE offline may well turn out to be the best option. From: Rene Struik [mailto:rstruik.ext@gmail.com] Sent: Thursday, December 13, 2012 2:12 PM To: Igoe, Kevin M. Cc: cfrg@irtf.org; Dan Harkins Subject: Re: [Cfrg] Status of DragonFly Hi Kevin: I do share some of your timing attack concerns. Unless I missed something h= ere, your suggested fix does not seem to work, however: Suppose A and B use ECDH with as generator the point G(p):=3D pG, where p:= =3Dkdf(..) {I use small-case p ("password") rather than capital-case X belo= w (so as to separate scalars and elliptic curve points)}. Now, suppose A an= d B exchange X:=3DxG(p) where p is the correct password and where Y:=3D y G= (p'), where p' is any guess for p by B (or just takes p":=3D1). Then A (the= legitimate party holding password p) computes Ka:=3D (xy) G(p')=3D (xy p')= G and B computes Kb:=3D(yx) G(p)=3D (yxp) G. In other words, Ka:=3D p' K, = Kb:=3D p K, where K:=3D (xy)G. So, Ka:=3D (p'/p) Kb. Now, once A sends B a = key confirmation message, B can just cycle through the password space, comp= ute a candidate key that A could have computed and check the validity of hi= s guess via verification of the key confirmation message just received. As to implementing Dragonfly, one has to be careful in case of active attac= ks: as an example, if one uses multiple-point multiplications, one may end = up at the point of infinity as intermediate point in the computation, thus = forcing implementations to use exception handling routines for point additi= on/doubling along the entire computational path (Note: if one hits the poin= t at infinity, this exposes the password used, thus leaking the entire pass= word in an observable way). If one does not use multiple-point multiplicati= ons, this attack seems much harder but requires two full scalar multiplicat= ions (rather than one scalar multiplication as, e.g., SPEKE requires). Best regards, Rene =3D=3D A possible fix is to use the KDF to generate a random X, 1 | of thinking we used when we create= d them." | - Albert Einstein - ----------------+-------------------------------------------------- _______________________________________________ Cfrg mailing list Cfrg@irtf.org http://www.irtf.org/mailman/listinfo/cfrg -- email: rstruik.ext@gmail.com | Skype: rstruik cell: +1 (647) 867-5658 | US: +1 (415) 690-7363 --_000_3C4AAD4B5304AB44A6BA85173B4675CA4C1BE47BMSMRGH1UEA03cor_ Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

OK folks, we are still on= the hook to provide the TLS WG with our analysis of DragonFly

as it currently exists.&n= bsp; Here’s what I see:

 <= /p>

1)  &= nbsp;   The confidentiali= ty provided by DragonFly is at least as good as Diffie-Hallmann.

2)  &= nbsp;   Impersonation is = a different matter. The nefarious Eve can run through a list
of likely passwords, attempting to run the DragonFly protocol once for each=
guess until she hits one where the DragonFly protocol runs to completion, <= br> meaning Eve has almost certainly found the correct password.  Proper monitoring of the error logs should detect such an attack.

In the EC case, the situation is a bit muddier.  The use of = the nonces in the
generation of PE leads to a timing attack.   Assuming the observe= r can determine
precisely how many passes have been made through the  while-loop, each= observed
instance of the DragonFly protocol between Alice and Bob provides 2 bits of= information
about their common password.  If the adversary has a list of 2^M passw= ords which is
likely to contain the password in use, passively observing about M+8 or= so DragonFly
exchanges betwixt Alice and Bob provides enough information to uniquely ide= ntify the
password (if it is on the list) with high probability.  This is not wi= thout cost to the
attacker, they need to test the putative passwords one at a time until they= find one
that generates the observed pattern of number of passes through the while l= oop. It
all comes down to how well the passwords are chosen, and we all know how good users are at picking passwords. 

Scott Fluhrer proposed an elegant change to DragonFly that fixes this. = ; In the EC case, replace
 the while-loop with a for-loop, say “for t =3D 1,,,,40”.&= nbsp; On each pass through this for-loop generate
a possible x- coorodinate as in DragonFly,  saving off the first x val= ue which corresponds to a
point on the curve.  The only thing that can go wrong here is doing al= l 40-iterations without
finding a good x-coordinate.  This is quite unlikely to occur (~ 10^-1= 2), but when it does occur
it gives 40 bits of information about the password.  In some VERY high= volume applications it
might be prudent to choose a value larger than 40.

 

Many thanks to Rene Struik and Scott Fluhrer for their insightful c= omments.  Would anyone else on the list
like to join in?  We can’t learn from our mistakes until we real= ize we’ve made them.

 

 <= /p>

From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.o= rg] On Behalf Of Igoe, Kevin M.
Sent: Thursday, December 13, 2012 3:19 PM
To: 'Rene Struik'
Cc: Dan Harkins; cfrg@irtf.org
Subject: Re: [Cfrg] Status of DragonFly

 

Thanks Rene.  I agre= e with your analysis on my first proposed fix.  Clearly this needs som= e more thought.

Pre-computing PE offline = may well turn out to be the best option.

 <= /p>

From: Rene Struik [mailto:rstruik.ext@gmail.com]
Sent: Thursday, December 13, 2012 2:12 PM
To: Igoe, Kevin M.
Cc: cfrg@irtf.org; Dan Harkins
Subject: Re: [Cfrg] Status of DragonFly

 

Hi Kevin:

I do share some of your timing attack concerns. Unless I missed something h= ere, your suggested fix does not seem to work, however:

Suppose A and B use ECDH with as generator the point G(p):=3D pG, where p:= =3Dkdf(..) {I use small-case p ("password") rather than capital-c= ase X below (so as to separate scalars and elliptic curve points)}. Now, su= ppose A and B exchange X:=3DxG(p) where p is the correct password and where Y:=3D y G(p'), where p' is any guess for p by B= (or just takes p":=3D1). Then A (the legitimate party holding passwor= d p) computes Ka:=3D (xy) G(p')=3D (xy p') G and B computes Kb:=3D(yx) G(p)= =3D (yxp) G. In other words, Ka:=3D p' K, Kb:=3D p K, where K:=3D (xy)G. So, Ka:=3D (p'/p) Kb. Now, once A sends B a key confirm= ation message, B can just cycle through the password space, compute a candi= date key that A could have computed and check the validity of his guess via= verification of the key confirmation message just received.

As to implementing Dragonfly, one has to be careful in case of active attac= ks: as an example, if one uses multiple-point multiplications, one may end = up at the point of infinity as intermediate point in the computation, thus = forcing implementations to use exception handling routines for point addition/doubling along the entire computation= al path (Note: if one hits the point at infinity, this exposes the password= used, thus leaking the entire password in an observable way). If one does = not use multiple-point multiplications, this attack seems much harder but requires two full scalar multiplications= (rather than one scalar multiplication as, e.g., SPEKE requires).

Best regards, Rene

=3D=3D
A possible fix is to use the KDF to generate a random X, 1<X<q, where= q is the size of the cryptographic

subgroup of the cur= ve, and take PE =3D X*G, where G is the generator of the cryptographic subg= roup.  For
most cryptographic curves,  q  is very, very close to 2^n, so it = is VERY unlikely that more than 1 call to the

KDF will be needed.

On 12/13/2012 1:42 PM, Igoe, Kevin M. wrote:

I’d like the reading list’s= input on DragonFly (hereafter called DF), Dan Harkins’ Password Auth= enticated
Key Exchange design (draft-irtf-cfrg-dragonfly-00).  I’d like to= point out that draft-harkins-tls-pwd-03

is a proposal to use DF in  TLS that differs slightly from the CFRG dra= ft.

 

Here is where I believe we stand:<= /o:p>

 

1.    &nb= sp;  Confidentiality: The proof that= the confidentiality of the key generated by the DF
protocol is reducible to the standard Diffie-Hellmann problem is quite stra= ight
forward, so the resulting shared secret value is at least as secure as with=   standard DH/ECDH.

2.    &nb= sp;  Authentication: Obviously the s= ystem can be no more secure than the password
being used. I believe the most viable attack is to guess a password, use th= is password
to initiate the  DF protocol with the endpoint being attacked, and see= if it works.
Monitoring the system logs should easily detect such an attack. =

3.    &nb= sp;  Timing: I’m particularly = concerned about the method used to generate the PE (password
dependent base point) in the ECDH case. Inside a while loop, several parame= ters,
 including the identities of the two endpoints, the shared password, a= nd a counter are
passed to a KDF to produce an n-bit output, where the curve is mod an n-bit= prime p.
The resulting n-bit value X is checked to see if 0 <=3D X < p and X^3= +a*X+b is a quadratic
residue mod p (an event of probability =BD).  If both these tests are = passed, the while
loop is exited and X is used as the x-coordinate of our PE.

The problem I see with (3) is that the number of times through the loop giv= es an opponent a
check  on any putative value for the password.  E.g.  if the= ir current guess for the password
takes many passes through the while loop to generate the PE, but they obser= ve that the DF response
 time is inconsistent with that, they have eliminated that guess for t= he password. 

 

When DF is applied to TLS in as describ= ed in draft-harkins-tls-pwd-03, two nonces are used as
inputs to the KDF, which has two consequences:

a.    &nb= sp;  the PE MUST be computed online<= o:p>

b.    &nb= sp; each DF exchange gives an indep= endent timing check on the password.

The opponent can passively sit back, mo= nitoring the timing of DF exchanges on various links until
they stumble across one where the timings match up with the timings associa= ted with one of the
passwords they are testing. They’ve now are able to bypass the authen= tication provided by DF.

A possible fix is to use the KDF to generate a random X, 1<X<q, where= q is the size of the cryptographic

subgroup of the curve, and take PE =3D = X*G, where G is the generator of the cryptographic subgroup.  For
most cryptographic curves,  q  is very, very close to 2^n, so it = is VERY unlikely that more than 1 call to the

KDF will be needed.

 

Another fix would be to require PE gene= ration be done offline, which would eliminate any possibility of
using nonces in the DF protocol.  One could, however, mix the nonces i= n after the completion to the

DF based Diffie-Hellmann exchange. = ;

 

 

 

 

----------------+-----------------------= ---------------------------

Kevin M. Igoe   | "We can't s= olve problems by using the same kind<= /p>

kmigoe@nsa.= gov  | of thinking we used when we created them."

       &n= bsp;        |    &nb= sp;         - Albert Einstein -

----------------+-----------------------= ---------------------------

 

 

 



_______________________________________________
Cfrg mailing list
Cfrg@irtf.org
http://www.irtf.=
org/mailman/listinfo/cfrg



-- 
email: rstruik.ext@gmail.com<=
/a> | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
--_000_3C4AAD4B5304AB44A6BA85173B4675CA4C1BE47BMSMRGH1UEA03cor_-- From dharkins@lounge.org Mon Dec 17 14:54:02 2012 Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 5A33321F88E7 for ; Mon, 17 Dec 2012 14:54:02 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -6.198 X-Spam-Level: X-Spam-Status: No, score=-6.198 tagged_above=-999 required=5 tests=[AWL=0.067, BAYES_00=-2.599, IP_NOT_FRIENDLY=0.334, RCVD_IN_DNSWL_MED=-4] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 7Sl9C4iUHaxs for ; Mon, 17 Dec 2012 14:54:01 -0800 (PST) Received: from colo.trepanning.net (colo.trepanning.net [69.55.226.174]) by ietfa.amsl.com (Postfix) with ESMTP id C7C6D21F868F for ; Mon, 17 Dec 2012 14:54:01 -0800 (PST) Received: from www.trepanning.net (localhost [127.0.0.1]) by colo.trepanning.net (Postfix) with ESMTP id C8E151022404A; Mon, 17 Dec 2012 14:53:59 -0800 (PST) Received: from 69.12.173.8 (SquirrelMail authenticated user dharkins@lounge.org) by www.trepanning.net with HTTP; Mon, 17 Dec 2012 14:54:00 -0800 (PST) Message-ID: In-Reply-To: <3C4AAD4B5304AB44A6BA85173B4675CA4C1BE47B@MSMR-GH1-UEA03.corp.nsa.gov> References: <3C4AAD4B5304AB44A6BA85173B4675CA49672A1B@MSMR-GH1-UEA03.corp.nsa.gov> <50CA2873.1090509@gmail.com> <3C4AAD4B5304AB44A6BA85173B4675CA4AE0C72D@MSMR-GH1-UEA03.corp.nsa.gov> <3C4AAD4B5304AB44A6BA85173B4675CA4C1BE47B@MSMR-GH1-UEA03.corp.nsa.gov> Date: Mon, 17 Dec 2012 14:54:00 -0800 (PST) From: "Dan Harkins" To: "Igoe, Kevin M." User-Agent: SquirrelMail/1.4.14 [SVN] MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Priority: 3 (Normal) Importance: Normal Cc: Dan Harkins , "cfrg@irtf.org" Subject: Re: [Cfrg] Status of DragonFly X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 17 Dec 2012 22:54:02 -0000 Hi Kevin, On Mon, December 17, 2012 1:10 pm, Igoe, Kevin M. wrote: > OK folks, we are still on the hook to provide the TLS WG with our analysis > of DragonFly as it currently exists. Here's what I see: > > 1) The confidentiality provided by DragonFly is at least as good as > Diffie-Hallmann. > > 2) Impersonation is a different matter. The nefarious Eve can run > through a list > of likely passwords, attempting to run the DragonFly protocol once for > each > guess until she hits one where the DragonFly protocol runs to completion, > meaning Eve has almost certainly found the correct password. Proper > monitoring of the error logs should detect such an attack. > > In the EC case, the situation is a bit muddier. The use of the nonces in > the > generation of PE leads to a timing attack. Assuming the observer can > determine > precisely how many passes have been made through the while-loop, each > observed > instance of the DragonFly protocol between Alice and Bob provides 2 bits > of information > about their common password. If the adversary has a list of 2^M passwords > which is > likely to contain the password in use, passively observing about M+8 or so > DragonFly > exchanges betwixt Alice and Bob provides enough information to uniquely > identify the > password (if it is on the list) with high probability. This is not > without cost to the > attacker, they need to test the putative passwords one at a time until > they find one > that generates the observed pattern of number of passes through the while > loop. It > all comes down to how well the passwords are chosen, and we all know how > good users are at picking passwords. > > Scott Fluhrer proposed an elegant change to DragonFly that fixes this. In > the EC case, replace > the while-loop with a for-loop, say "for t = 1,,,,40". On each pass > through this for-loop generate > a possible x- coorodinate as in DragonFly, saving off the first x value > which corresponds to a > point on the curve. The only thing that can go wrong here is doing all > 40-iterations without > finding a good x-coordinate. This is quite unlikely to occur (~ 10^-12), > but when it does occur > it gives 40 bits of information about the password. In some VERY high > volume applications it > might be prudent to choose a value larger than 40. This technique is already used in draft-harkins-tls-pwd-03. There is an additional security parameter, k, that is used to ensure that k iterations of the loop are performed. There are no interoperability issues with any particular value of k and I do not recommend a value. But I do make this statement in the Security Considerations: "The probability that a password will require more than k iterations is roughly (q/2p)^k so it is possible to mitigate a side channel attack at the expense of a constant cost per connection attempt." where q is the order of the group formed by the generator and p is the prime. Is that statement correct and is it adequate? regards, Dan. From kmigoe@nsa.gov Tue Dec 18 06:20:45 2012 Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 1B4CE21F87AC for ; Tue, 18 Dec 2012 06:20:45 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -10.599 X-Spam-Level: X-Spam-Status: No, score=-10.599 tagged_above=-999 required=5 tests=[AWL=0.000, BAYES_00=-2.599, RCVD_IN_DNSWL_HI=-8] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id fDlDqpd1HBCU for ; Tue, 18 Dec 2012 06:20:44 -0800 (PST) Received: from nsa.gov (emvm-gh1-uea08.nsa.gov [63.239.67.9]) by ietfa.amsl.com (Postfix) with ESMTP id 3124C21F894F for ; Tue, 18 Dec 2012 06:20:43 -0800 (PST) X-TM-IMSS-Message-ID: <319f32a80005dcbd@nsa.gov> Received: from MSHT-GH1-UEA02.corp.nsa.gov ([10.215.227.181]) by nsa.gov ([63.239.67.9]) with ESMTP (TREND IMSS SMTP Service 7.1; TLSv1/SSLv3 AES128-SHA (128/128)) id 319f32a80005dcbd ; Tue, 18 Dec 2012 09:20:29 -0500 Received: from MSMR-GH1-UEA03.corp.nsa.gov ([10.215.224.3]) by MSHT-GH1-UEA02.corp.nsa.gov ([10.215.227.181]) with mapi id 14.01.0289.001; Tue, 18 Dec 2012 09:20:38 -0500 From: "Igoe, Kevin M." To: 'Dan Harkins' Thread-Topic: [Cfrg] Status of DragonFly Thread-Index: Ac3YlStNhI1Pb7rLTAC7Nu690xzU7QA+m/WAAAhk1JAAt2SbYAARI8EAABMUOXA= Date: Tue, 18 Dec 2012 14:20:38 +0000 Message-ID: <3C4AAD4B5304AB44A6BA85173B4675CA4C1CA53D@MSMR-GH1-UEA03.corp.nsa.gov> References: <3C4AAD4B5304AB44A6BA85173B4675CA49672A1B@MSMR-GH1-UEA03.corp.nsa.gov> <50CA2873.1090509@gmail.com> <3C4AAD4B5304AB44A6BA85173B4675CA4AE0C72D@MSMR-GH1-UEA03.corp.nsa.gov> <3C4AAD4B5304AB44A6BA85173B4675CA4C1BE47B@MSMR-GH1-UEA03.corp.nsa.gov> In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [10.215.254.27] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Cc: Dan Harkins , "cfrg@irtf.org" Subject: Re: [Cfrg] Status of DragonFly X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 18 Dec 2012 14:20:45 -0000 A friend of mine once claimed the central skill in cryptology is setting the parameters properly. I believe a 40-long for-loop=20 is good enough, but 32-long for-loop is a wee bit too small. Let me run through the "back of the envelope" calculation that led me to choose a 40-long for-loop. =20 Consider trying to attack bank logins that use DF. Eve would start by setting up a network of "listening posts" to monitor DF bank logins, looking for for-loop overflows. Once the network "listening posts" is=20 in place, Eve would just sit back and wait until one of the listening posts= =20 reported back with an overflow event and the associated metadata. Eve=20 would then stand a good chance of recovering this user's password and=20 raiding their account.=20 Our goal is to set the loop size so that Eve rarely, if ever, observes an=20 overflow.=20 Cisco forecasts there will be about 2^70 bytes/year of internet traffic in 2016. Let's make some conservative assumptions: - Assume Eve is able to monitor 1/1000 =3D 2^-10 of the traffic=20 =3D> Eve's network of listening posts see 2^60 bytes/year. - Assume that 2^-10 of this consists of DF exchanges =3D> 2^50 bytes/year= =20 of DF exchange data.=20 - Finally assume each DF exchange takes about 2^10 bytes. This mean=20 Eve's listening post will see about 2^40 DF exchanges per year.=20 =20 Hence if a 40 long for-loop is used, Eve expects to get 1 overflow per yea= r.=20 Tough to make a profit at that rate! > -----Original Message----- > From: Dan Harkins [mailto:dharkins@lounge.org] > Sent: Monday, December 17, 2012 5:54 PM > To: Igoe, Kevin M. > Cc: cfrg@irtf.org; Dan Harkins > Subject: Re: [Cfrg] Status of DragonFly >=20 >=20 > Hi Kevin, >=20 > On Mon, December 17, 2012 1:10 pm, Igoe, Kevin M. wrote: > > OK folks, we are still on the hook to provide the TLS WG with our > analysis > > of DragonFly as it currently exists. Here's what I see: > > > > 1) The confidentiality provided by DragonFly is at least as good > as > > Diffie-Hallmann. > > > > 2) Impersonation is a different matter. The nefarious Eve can > run > > through a list > > of likely passwords, attempting to run the DragonFly protocol once > for > > each > > guess until she hits one where the DragonFly protocol runs to > completion, > > meaning Eve has almost certainly found the correct password. Proper > > monitoring of the error logs should detect such an attack. > > > > In the EC case, the situation is a bit muddier. The use of the > nonces in > > the > > generation of PE leads to a timing attack. Assuming the observer > can > > determine > > precisely how many passes have been made through the while-loop, > each > > observed > > instance of the DragonFly protocol between Alice and Bob provides 2 > bits > > of information > > about their common password. If the adversary has a list of 2^M > passwords > > which is > > likely to contain the password in use, passively observing about M+8 > or so > > DragonFly > > exchanges betwixt Alice and Bob provides enough information to > uniquely > > identify the > > password (if it is on the list) with high probability. This is not > > without cost to the > > attacker, they need to test the putative passwords one at a time > until > > they find one > > that generates the observed pattern of number of passes through the > while > > loop. It > > all comes down to how well the passwords are chosen, and we all know > how > > good users are at picking passwords. > > > > Scott Fluhrer proposed an elegant change to DragonFly that fixes > this. In > > the EC case, replace > > the while-loop with a for-loop, say "for t =3D 1,,,,40". On each pass > > through this for-loop generate > > a possible x- coorodinate as in DragonFly, saving off the first x > value > > which corresponds to a > > point on the curve. The only thing that can go wrong here is doing > all > > 40-iterations without > > finding a good x-coordinate. This is quite unlikely to occur (~ 10^- > 12), > > but when it does occur > > it gives 40 bits of information about the password. In some VERY > high > > volume applications it > > might be prudent to choose a value larger than 40. >=20 > This technique is already used in draft-harkins-tls-pwd-03. There is > an > additional security parameter, k, that is used to ensure that k > iterations > of the loop are performed. There are no interoperability issues with > any > particular value of k and I do not recommend a value. But I do make > this statement in the Security Considerations: >=20 > "The probability that a password will require more than k > iterations is roughly (q/2p)^k so it is possible to mitigate a > side > channel attack at the expense of a constant cost per connection > attempt." >=20 > where q is the order of the group formed by the generator and p is the > prime. Is that statement correct and is it adequate? >=20 > regards, >=20 > Dan. >=20 From sfluhrer@cisco.com Tue Dec 18 07:49:28 2012 Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id E816D21F8AD6 for ; Tue, 18 Dec 2012 07:49:28 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -10.599 X-Spam-Level: X-Spam-Status: No, score=-10.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, RCVD_IN_DNSWL_HI=-8] Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 3flbPdZ6pUMM for ; Tue, 18 Dec 2012 07:49:28 -0800 (PST) Received: from rcdn-iport-3.cisco.com (rcdn-iport-3.cisco.com [173.37.86.74]) by ietfa.amsl.com (Postfix) with ESMTP id E47E121F8AD5 for ; Tue, 18 Dec 2012 07:49:27 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=7070; q=dns/txt; s=iport; t=1355845768; x=1357055368; h=from:to:cc:subject:date:message-id:references: in-reply-to:content-transfer-encoding:mime-version; bh=AQVgONYlUQhI+0DuV3RRCuF/KKvUvkhwdglq5pGa9xE=; b=YP5auWUSHflGRb2QiUMK4Gl7/on4ZAg1ZzJyD7XJJZ6hUfLbB7iPil3Z uf9fXAmKeRVQeS06IThQRJbjD30CLvR0o85Dl4zkOvano3wMc8mbTInjU 98xMrRChuW6MoULghexjJsHj+vvVt4zkA/E5WWgntNZK9sB5yZ7x84NUn 0=; X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgEFAGWP0FCtJXHA/2dsb2JhbAA6Cr4mFnOCHgEBAQMBAQEBNzQLBQcEAgEIDgMEAQEBCg4GCQcnCxQJCAEBBA4FCAGIBAYMqA+QRYxJEQuBAIJGYQOSV5N7gnOCIg X-IronPort-AV: E=Sophos;i="4.84,309,1355097600"; d="scan'208";a="154244332" Received: from rcdn-core2-5.cisco.com ([173.37.113.192]) by rcdn-iport-3.cisco.com with ESMTP; 18 Dec 2012 15:49:27 +0000 Received: from xhc-aln-x05.cisco.com (xhc-aln-x05.cisco.com [173.36.12.79]) by rcdn-core2-5.cisco.com (8.14.5/8.14.5) with ESMTP id qBIFnRdw010374 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=FAIL); Tue, 18 Dec 2012 15:49:27 GMT Received: from xmb-rcd-x04.cisco.com ([169.254.8.135]) by xhc-aln-x05.cisco.com ([173.36.12.79]) with mapi id 14.02.0318.004; Tue, 18 Dec 2012 09:49:26 -0600 From: "Scott Fluhrer (sfluhrer)" To: Dan Harkins , "Igoe, Kevin M." Thread-Topic: [Cfrg] Status of DragonFly Thread-Index: Ac3YlStNhI1Pb7rLTAC7Nu690xzU7QBAtGaAAAJc/YAAyu6qAAADoYkAABS1LUA= Date: Tue, 18 Dec 2012 15:49:25 +0000 Message-ID: References: <3C4AAD4B5304AB44A6BA85173B4675CA49672A1B@MSMR-GH1-UEA03.corp.nsa.gov> <50CA2873.1090509@gmail.com> <3C4AAD4B5304AB44A6BA85173B4675CA4AE0C72D@MSMR-GH1-UEA03.corp.nsa.gov> <3C4AAD4B5304AB44A6BA85173B4675CA4C1BE47B@MSMR-GH1-UEA03.corp.nsa.gov> In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [10.32.244.86] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Cc: Dan Harkins , "cfrg@irtf.org" Subject: Re: [Cfrg] Status of DragonFly X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 18 Dec 2012 15:49:29 -0000 > -----Original Message----- > From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf Of > Dan Harkins > Sent: Monday, December 17, 2012 5:54 PM > To: Igoe, Kevin M. > Cc: Dan Harkins; cfrg@irtf.org > Subject: Re: [Cfrg] Status of DragonFly >=20 >=20 > Hi Kevin, >=20 > On Mon, December 17, 2012 1:10 pm, Igoe, Kevin M. wrote: > > OK folks, we are still on the hook to provide the TLS WG with our > > analysis of DragonFly as it currently exists. Here's what I see: > > > > 1) The confidentiality provided by DragonFly is at least as good a= s > > Diffie-Hallmann. > > > > 2) Impersonation is a different matter. The nefarious Eve can run > > through a list > > of likely passwords, attempting to run the DragonFly protocol once for > > each guess until she hits one where the DragonFly protocol runs to > > completion, meaning Eve has almost certainly found the correct > > password. Proper monitoring of the error logs should detect such an > > attack. > > > > In the EC case, the situation is a bit muddier. The use of the nonces > > in the > > generation of PE leads to a timing attack. Assuming the observer can > > determine > > precisely how many passes have been made through the while-loop, each > > observed instance of the DragonFly protocol between Alice and Bob > > provides 2 bits of information about their common password. If the > > adversary has a list of 2^M passwords which is likely to contain the > > password in use, passively observing about M+8 or so DragonFly > > exchanges betwixt Alice and Bob provides enough information to > > uniquely identify the password (if it is on the list) with high > > probability. This is not without cost to the attacker, they need to > > test the putative passwords one at a time until they find one that > > generates the observed pattern of number of passes through the while > > loop. It all comes down to how well the passwords are chosen, and we > > all know how good users are at picking passwords. > > > > Scott Fluhrer proposed an elegant change to DragonFly that fixes this. > > In the EC case, replace the while-loop with a for-loop, say "for t =3D > > 1,,,,40". On each pass through this for-loop generate a possible x- > > coorodinate as in DragonFly, saving off the first x value which > > corresponds to a point on the curve. The only thing that can go wrong > > here is doing all 40-iterations without finding a good x-coordinate. > > This is quite unlikely to occur (~ 10^-12), but when it does occur it > > gives 40 bits of information about the password. In some VERY high > > volume applications it might be prudent to choose a value larger than > > 40. >=20 > This technique is already used in draft-harkins-tls-pwd-03. Hmmm, I see it in the ECC section, but not the MODP section. It would seem= appropriate for MODP groups as well, at least in the case where q =3D (p-1= )/2 (e.g. the standard IKE groups). I believe that either you need to proh= ibit such groups, or modify the algorithm to handle such groups (possibly m= aking a distinction between those groups, and the 'small subgroup' case; al= ternatively, just note that k=3D1 is fine in cases where q< There is an > additional security parameter, k, that is used to ensure that k iteration= s of > the loop are performed. There are no interoperability issues with any > particular value of k and I do not recommend a value. I do believe that you should (at least) offer a solid suggestion; after all= , that value will be chosen by people who will read this RFC and nothing el= se; they may not appreciate all the implications of the below statement. And, if someone does pick a value that's too low, they're in danger of expo= sing the secret on behalf of everyone who shares that secret; not just them= . > But I do make this > statement in the Security Considerations: >=20 > "The probability that a password will require more than k > iterations is roughly (q/2p)^k so it is possible to mitigate a sid= e > channel attack at the expense of a constant cost per connection > attempt." >=20 > where q is the order of the group formed by the generator and p is the > prime. Is that statement correct and is it adequate? Actually, for MODP groups, the probability that k modular-exponentiations i= s required is about (q/p)^k ; for ECC groups, your listed probability on th= e number of QR tests is correct, but it can be more easily stated as about = (1/2)^k However, your random 'hunt-and-peck' method for forming the pwd-value also = doesn't take constant time, at least for some groups. For primes p which a= re just under a power of 2 (standard IKE groups, NIST ECC curves), it's fin= e; however, other groups (IKE group 24, Brainpool curves), it'll take a var= iable number of iterations, and hence potentially leaking some information.= You might consider the algorithm in B.4.1 from FIPS 186-3 as an alternativ= e; this essentially generates a random number 64 bits larger than what you = need, and then modulo-reduce that into the range you want; that gives you a= n (almost) uniform random number in the range in pretty close to constant t= ime. Also, if you want to put in a potential optimization in the ECC side, you c= an note that attempting the compute the square-root is not always the most = efficient way to compute whether a number has a square root (aka "is a quad= ratic residue"); it would be adequate to compute the Legendre symbol (the n= umber is a quadratic residue if the symbol is 1); you would need to take th= e square root only on the pwd-value we would actually use. Since computing= the Legendre symbol is potentially cheaper than computing the square root = (and also does not modify the constant time aspect of the algorithm, at lea= st, no more than computing the square root), you may want to mention that a= s an acceptable alternative implementation. If you want a reference on how to compute the Legendre symbol, well, if we'= re pointing them to FIPS 186-3 anyways, a reference would be the algorithm = in C.5 (they call it the Jacobi symbol; it's the same algorithm). >=20 > regards, >=20 > Dan. >=20 >=20 > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > http://www.irtf.org/mailman/listinfo/cfrg