Re: [Cfrg] Status of DragonFly

"Dan Harkins" <dharkins@lounge.org> Mon, 17 December 2012 22:54 UTC

Return-Path: <dharkins@lounge.org>
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 <cfrg@ietfa.amsl.com>; 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 <cfrg@ietfa.amsl.com>; 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 <cfrg@irtf.org>; 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: <e1de21414feb021d4b0a22c78340eeb4.squirrel@www.trepanning.net>
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" <dharkins@lounge.org>
To: "Igoe, Kevin M." <kmigoe@nsa.gov>
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 <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: 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.