Re: [Cfrg] Status of DragonFly

"Igoe, Kevin M." <kmigoe@nsa.gov> Mon, 17 December 2012 21:10 UTC

Return-Path: <kmigoe@nsa.gov>
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 <cfrg@ietfa.amsl.com>; 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 <cfrg@ietfa.amsl.com>; 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 <cfrg@irtf.org>; 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." <kmigoe@nsa.gov>
To: "cfrg@irtf.org" <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 <dharkins@arubanetworks.com>
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 <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Mon, 17 Dec 2012 21:10:23 -0000

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.



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 made them.



From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] 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 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 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:
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 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<mailto:kmigoe@nsa.gov>  | of thinking we used when we created them."
                |              - Albert Einstein -
----------------+--------------------------------------------------






_______________________________________________

Cfrg mailing list

Cfrg@irtf.org<mailto:Cfrg@irtf.org>

http://www.irtf.org/mailman/listinfo/cfrg



--

email: rstruik.ext@gmail.com<mailto:rstruik.ext@gmail.com> | Skype: rstruik

cell: +1 (647) 867-5658 | US: +1 (415) 690-7363