[Cfrg] Review of Dragonfly PAKE

[Trevor Perrin <[e-mail]>]

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