[Cfrg] Review of Dragonfly PAKE

Trevor Perrin <trevp@trevp.net> Tue, 10 December 2013 22:30 UTC

Return-Path: <trevp@trevp.net>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 2053C1AE226 for <cfrg@ietfa.amsl.com>; Tue, 10 Dec 2013 14:30:58 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.977
X-Spam-Level:
X-Spam-Status: No, score=-1.977 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FM_FORGED_GMAIL=0.622, LOTS_OF_MONEY=0.001, RCVD_IN_DNSWL_LOW=-0.7] autolearn=unavailable
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id EJ5Jg_hZiQBK for <cfrg@ietfa.amsl.com>; Tue, 10 Dec 2013 14:30:54 -0800 (PST)
Received: from mail-wg0-f43.google.com (mail-wg0-f43.google.com [74.125.82.43]) by ietfa.amsl.com (Postfix) with ESMTP id 8C1C81AE154 for <cfrg@ietf.org>; Tue, 10 Dec 2013 14:30:54 -0800 (PST)
Received: by mail-wg0-f43.google.com with SMTP id k14so5669619wgh.10 for <cfrg@ietf.org>; Tue, 10 Dec 2013 14:30:48 -0800 (PST)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:date:message-id:subject:from:to:cc :content-type; bh=um4+UYNy4sTsPv13IiAF31cKsele6iIz0Ibye3eRC7c=; b=j4Zrn39G3Ehcf8aUwI0b6PjQst33GejalCt0+J/xJaoHe3afEBaRZPJlyfokXVmiMv uKKIMjfHCGGg5CU0S2xyDhPvzIlt6b/RLmn47scibJUQUwdLx34tp59qfK3bEQuGL/d5 CL7Tf28wSa08UISbKIPe5qURJts7TFCpNsZdxKbpJ+HFdkLAexcRWr45rULWxO1N9Fig JT35DdKxcEDS9+4nh+Q5VguAxD7Y4m0VPllePwYzLi8LB5fUqOiCOqe2Z8a7004VsKdJ gF7T1JRIhvCO2G5+Wg1dWmvQ4DgWhLeDfDrSeJkRo/oMXmy61cTr3JnGFhmWl+hGux55 8z/w==
X-Gm-Message-State: ALoCoQkJJcsSn2+c1VK9oUsAKpUD96gMC5lO51xJdtZtF1VTH7ZR4D0zb6R3WckuATJO2zQP4S6M
MIME-Version: 1.0
X-Received: by 10.180.73.6 with SMTP id h6mr145087wiv.20.1386714648580; Tue, 10 Dec 2013 14:30:48 -0800 (PST)
Received: by 10.216.214.134 with HTTP; Tue, 10 Dec 2013 14:30:48 -0800 (PST)
X-Originating-IP: [199.83.223.81]
Date: Tue, 10 Dec 2013 14:30:48 -0800
Message-ID: <CAGZ8ZG0+LBsSiub9JDpXpn3NA366a8_9DqiA-HERMpmyWjq0kw@mail.gmail.com>
From: Trevor Perrin <trevp@trevp.net>
To: cfrg@ietf.org
Content-Type: text/plain; charset="ISO-8859-1"
Cc: "tls@ietf.org" <tls@ietf.org>
Subject: [Cfrg] Review of Dragonfly PAKE
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
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, 10 Dec 2013 22:30:58 -0000

Dear CFRG (cc: TLS),

Here's a review of the Dragonfly Password-Authenticated Key Exchange (PAKE) from
draft-irtf-cfrg-dragonfly-02 [CFRGDRAFT].

Overview
----
The Dragonfly PAKE is built on SPEKE with an "obfuscation" applied to
the exchange of Diffie-Hellman values.  The obfuscation lacks formal
analysis and serves no obvious purpose, but may be an attempt to avoid
the SPEKE patent [IPSEC].  Dragonfly has security weaknesses due to
use of a variable-time algorithm to map a password to an EC point
[STRUIK], and lack of "augmented" PAKE properties.

Obfuscating the SPEKE DH exchange
----
SPEKE is an old and well-known PAKE [JABLON].  In SPEKE each party
uses a shared password to derive a Diffie-Hellman generator.  The
generator is then used for a Diffie-Hellman exchange.

SPEKE is patented until 2017 [SPEKEPATENT].  Alternatives without
current patents incude [DH-EKE] and [J-PAKE].  Alternatives with
royalty-free terms include [SRP] and [AUGPAKE].

Dragonfly uses the SPEKE approach but obfuscates the exchange of DH
values.  In particular, given:

  g : DH generator (calculated by hashing the password)
  a : Alice's DH private key

In SPEKE, Alice sends g^a.

In Dragonfly, Alice generates a mask m, and sends (a+m, g^-m).  Bob
uses these values and g to reconstruct g^a.  [ g^a = g^(a+m) * g^-m ]

This obfuscation adds computation and bandwidth costs.  It's not clear
whether it adds any security benefit.  It's not clear how Dragonfly's
security relates to SPEKE; whether the SPEKE security proof from
[MACKENZIE] still applies; or whether another security proof could be
created.

The Dragonfly author argues that the SPEKE patent only covers use of a
"password-based parameter" with a "known technique of unauthenticated
key distribution" [IPSEC], and thus does not apply to Dragonfly.

It's not obvious that this is true.  Particularly given expiry of the
Lucent EKE/DH-EKE patents [LUCENT], the Dragonfly IPR situation seems
less clear than some alternatives.


Sidechannel attack on mapping password to EC point
----
Mapping a password onto a Diffie-Hellman generator is easy for
Diffie-Hellman with safe primes, which are typically used with SPEKE.
For ECDH, the naive "try-and-increment" algorithm for mapping to a
point leaks timing information about its input ([BONEH], [ICART]).

Nonetheless, this algorithm might be acceptable provided its input is
fixed for a given password.  Unfortunately, Dragonfly recommends
mixing nonces with the password prior to "hunting-and-pecking".  This
enables a timing attack:

 * The attacker initiates many protocol runs, recording the time taken
by the server to produce each Commit message.  (Alternatively, the
attacker passively observes many protocol runs.)

 * Afterwards, for each offline password guess, the attacker predicts
how long the "hunting-and-pecking" algorithm would have taken for each
run.

 * For a successful guess, the predictions will be correlated with
recorded times.

Dragonfly attempts to reduce this timing leak by performing the
"hunting-and-pecking" loop a fixed number of times (at least 40 is
recommended).  Yet within each loop are conditional branches and
Legendre symbol / square-root algorithms, which are hard to implement
efficiently in constant time ([STRUIK], [ICART], [FIPS186-4]).

This attack is easily avoided by omitting nonces from the input to the
"hunting-and-pecking" loop.  However, variants of the attack may be
possible (e.g. using salt to attack the client).  Difficulties of this
sort are why PAKE schemes often avoid the EC setting.


Non-augmented protocol
-----
Unlike [SRP] and [AUGPAKE], Dragonfly is a "balanced" PAKE, not an
"augmented" one.  This means that a Dragonfly server stores values
that can be used directly to authenticate to that server.  In
contrast, an SRP or AugPAKE server stores verifiers which would have
to be attacked by password-cracking.


Conclusions
------------
The Dragonfly approach seems inferior to existing PAKE schemes due to:
 * Lack of formal security proofs or extensive cryptanalysis
 * An unclear IPR situation compared to alternatives
 * High computation cost due to "hunting-and-pecking" and "DH obfuscation"
 * Side-channel risks due to "hunting-and-pecking"
 * Non-augmented properties


Trevor


[CFRGDRAFT] http://tools.ietf.org/html/draft-irtf-cfrg-dragonfly-02
[IPSEC] http://www.ietf.org/mail-archive/web/ipsec/current/msg06323.html
[STRUIK]
  http://www.ietf.org/mail-archive/web/cfrg/current/msg03259.html
  http://www.ietf.org/mail-archive/web/cfrg/current/msg03489.html
  http://www.ietf.org/mail-archive/web/cfrg/current/msg03527.html
[JABLON]
  http://www.jablon.org/jab96.pdf
  http://www.jablon.org/jab97.pdf
[SPEKEPATENT]
  https://www.google.com/patents/US6226383
  https://www.google.com/patents/US6792533
[DH-EKE]
  http://www.cs.columbia.edu/~smb/papers/neke.ps
  http://eprint.iacr.org/2000/014.pdf
[J-PAKE] http://eprint.iacr.org/2010/190.pdf
[SRP]
  http://tools.ietf.org/html/rfc5054
  http://srp.stanford.edu/design.html
[AUGPAKE] https://eprint.iacr.org/2010/334.pdf
[MACKENZIE] https://eprint.iacr.org/2001/057.pdf
[LUCENT] http://www.ietf.org/mail-archive/web/tls/current/msg08191.html
[BONEH] http://cseweb.ucsd.edu/~hovav/dist/sigs.pdf
[ICART] http://www.iacr.org/archive/crypto2009/56770300/56770300.pdf
[FIPS186-4] http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf