Re: [Cfrg] Status of DragonFly

"Igoe, Kevin M." <kmigoe@nsa.gov> Tue, 18 December 2012 14:20 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 1B4CE21F87AC for <cfrg@ietfa.amsl.com>; 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 <cfrg@ietfa.amsl.com>; 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 <cfrg@irtf.org>; 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." <kmigoe@nsa.gov>
To: 'Dan Harkins' <dharkins@lounge.org>
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> <e1de21414feb021d4b0a22c78340eeb4.squirrel@www.trepanning.net>
In-Reply-To: <e1de21414feb021d4b0a22c78340eeb4.squirrel@www.trepanning.net>
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 <dharkins@arubanetworks.com>, "cfrg@irtf.org" <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 <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: 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 
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.  

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 
in place, Eve would just sit back and wait until one of the listening posts 
reported back with an overflow event and the associated metadata.  Eve 
would then stand a good chance of recovering this user's password and 
raiding their account. 

Our goal is to set the loop size so that Eve rarely, if ever, observes an 
overflow. 

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 = 2^-10 of the traffic 
        => Eve's network of listening posts see 2^60 bytes/year.
	- Assume that 2^-10 of this consists of DF exchanges => 2^50 bytes/year 
        of DF exchange data. 
	- Finally assume each DF exchange takes about 2^10 bytes.  This mean 
        Eve's listening post will see about 2^40 DF exchanges per year. 
 
Hence if a 40 long for-loop is used,  Eve expects to get 1 overflow per year. 
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
> 
> 
>   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.
>