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_--