[TLS] Review of Dragonfly PAKE

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

Return-Path: <trevp@trevp.net>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 178071AE225 for <tls@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=ham
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 On1lq5InjP6j for <tls@ietfa.amsl.com>; Tue, 10 Dec 2013 14:30:54 -0800 (PST)
Received: from mail-we0-f173.google.com (mail-we0-f173.google.com [74.125.82.173]) by ietfa.amsl.com (Postfix) with ESMTP id 9A2E31AE1BB for <tls@ietf.org>; Tue, 10 Dec 2013 14:30:54 -0800 (PST)
Received: by mail-we0-f173.google.com with SMTP id u57so5656533wes.18 for <tls@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=fa+txElP6xnBZhmSHivrWkVIe/QUf4W0eOfe4M2vPZtHr0qf9a3W6ajh7w0o7wP8gZ JjUaLwWJdEfGbygOxTUppXhXAvMe0Um3MREOaG76UkC+Wm1HVNv9X8Y4/g6htCSxaE3G U6VN++sR58mge4fcra6ZM187rm885qZp+3Z8yWThgZAQia9v3XlUZKS1TiLo9G5mmTzS PxEKjuJpjNetThSec2QAV58yTLUmF3g29Y0q/pBJ2L/ui/VlJck0+LdVN9RounxkA/H9 40tatVLZKTgupohRxDDgx/y/Vun3/NgH/T7OYZR/HgP238+QmB8j+A6pDit6yygde7BZ he/g==
X-Gm-Message-State: ALoCoQmCkEmaSk8vftzy5JXRwBU242YfmMQkv7HMxGnof0QZxWQMw6fClEUvFEBW92J7fXnYEPML
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: [TLS] Review of Dragonfly PAKE
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/tls/>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.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