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

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:

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

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

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

inputs to the KDF, which has two consequences:

- the PE MUST be computed online
- 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

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

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

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

&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

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

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

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

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

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-03is a proposal to use DF in TLS that differs slightly from the CFRG draft.Here is where I believe we stand:

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

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

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

- the PE MUST be computed online
- 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 cryptographicsubgroup 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 theKDF 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 theDF based Diffie-Hellmann exchange.----------------+--------------------------------------------------Kevin M. Igoe | "We can't solve problems by using the same kindkmigoe@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:

**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:

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.

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. =
;

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

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

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

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