Re: [TLS] [Cfrg] Review of Dragonfly PAKE

  Hi Trevor,

On Tue, December 10, 2013 2:30 pm, Trevor Perrin wrote:
> 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.

  I disagree with this over-simplification.

>                                                             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.

  What is a "weakness" from the point of view of an augmented PAKE
scheme is a benefit from the point of view of a balanced PAKE scheme.
Augmented PAKE schemes bind the password to a single domain
parameter set while balanced PAKE schemes allow for the domain
parameter set to be negotiated. This allows, for example, a domain
parameter set to be agreed upon that provides commensurate
security to the rest of the cipher suite with which it can be used.

  It makes little sense to negotiate a 256-bit or even a 128-bit
cipher or a hash algorithm with a 256-bit or 512-bit digest size
when the domain parameter set is fixed to a 1024-bit FFC group.
What makes sense is to allow for negotiation of a 4096-bit FFC
group or a 256-bit ECC group along with your AES-GCM-128
with key derivation using HMAC-256.

  Of course, you may disagree (in fact, I'll bet money on it). But
I hope you do not feel that your opinion is the only valid one. I
respect your opinion on the matter, I just don't know why you
fail to respect the opinion of anyone who has a different evaluation
of that cost-benefit equation.

  A balanced PAKE scheme in addition to the existing augmented
PAKE scheme offers choice. You want to restrict and prohibit
choice.

> 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].

  AugPAKE has particularly nasty terms as the license explicitly
states that the "royalty-free" license does not cover all the claims
in the patent yet it does not spell out exactly which ones are or
are not covered. If your legal council advises you accept such a
license I'd advise you get new legal council.

> 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.

  Apparently much is not clear to you. I will tell you that I do not believe
that sending (a+m, g^-m) with a password-derived g has any security
benefits over sending g^a with a password-derived g. Does that clear
anything up?

> 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.

  That is truly a content-free statement, especially given the subject matter
(IPR). The reference you give goes to some lengths to explain the rationale
behind that statement. Sadly your response does not address any points
made in that reference, and, in fact, contributes nothing. Maybe this too is
not clear to you so let me give a brief attempt to make it more obvious:

  - if you replace the password-derived generator from SPEKE with the
     generator from the domain parameter set what do you have? You have
     the Diffie-Hellman key exchange, a "known technique of unauthenticated
     key distribution."

  - if you replace the password-derived generator from dragonfly with
     the generator from the domain parameter set what do you have? Well,
     whatever it is it is certainly not a "known technique of unauthenticated
     key distribution." I had never seen this technique of unauthenticated
     key distribution. If you have, please provide me with a reference from
     before 2007 or so.

>                                                      Particularly given
expiry of the
> Lucent EKE/DH-EKE patents [LUCENT], the Dragonfly IPR situation seems
> less clear than some alternatives.

  The existence of "alternatives" is really irrelevant to the subject of
your email-- a review of dragonfly. Yes there are numerous ways to skin
a cat. So what?

> 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:

  This has been discussed on both the TLS and CFRG lists already.

>  * 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.

  Except that the amount of time is hidden by a constant number of
loops through the hunting-and-pecking loop. Given that randomness
replaces the base once PE is obtained, it makes it all the more difficult
for the attacker to use any recorded time from a run of the protocol
or to make any prediction on the amount of time it would take.

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

  Which given the additional randomness will not correlate in a
way that allows the attacker to reduce the size of the pool from
which the password was chosen.

> 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]).

  It also adds randomness into the loop once PE is found, which
will be with probability 1 - (q/2p)^n, after n loops (where q is the
order of the domain parameter set and p is the prime).

  And that's why it continues to loop through a fixed number of times,
in order to hide the number of times it took to find the solution.

> 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.

  The current "hunting-and-pecking" text in draft-ietf-tls-pwd is
the result of a discussion with numerous people on a long thread on
the TLS list from an earlier version of the draft. Given that you have
obviously spent a considerable amount of time scouring through
numerous email lists that should be known to you. I'm not really sure
why you have waited until now to comment on it but I'm glad you have,
so let me ask:

  - what change would you like to see in the text and why? And,

  - if I accommodated your change would you support this draft?

> 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.

  This is well-known and mentioned in the Security Considerations.
As mentioned above, the benefit to this cost is that the domain
parameter set is not fixed to a password. And, as I mentioned, while
you may not view that benefit as outweighing the cost, your opinion
is not the ultimate truth on the subject, other people may evaluate
that equation differently and just because they do does not mean
they're wrong.

  As I mentioned above, having a balanced PAKE protocol (dragonfly)
as well as an augmented PAKE protocol (SRP) allows for freedom of
choice. What you are advocating for is less choice, and in fact,
restricting everyone to what you would choose. That is a somewhat
arrogant position.

  I'm also not sure why you have become a cheerleader for AugPAKE,
especially given your previous statements about: 1) how nobody
wants any PAKE solution in TLS; 2) that we have SRP and that can
address the few people (in your mind) who want it; and, 3) how you
would be against any additional PAKE scheme in TLS. It's especially
bizarre given that AugPAKE offers nothing on top of what SRP already
offers.

> 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

  It is extremely clear; it's not patented. Would you would like me to give
you a "royalty-free" license to use an unpatented protocol? Would you like
it to include all of the claims in a patent that does not exist or would you
be OK with it if it excluded some claims in a patent that does not exist?

>  * High computation cost due to "hunting-and-pecking" and "DH obfuscation"
>  * Side-channel risks due to "hunting-and-pecking"
>  * Non-augmented properties

  Aside from the last one, which is your personal preference which has
really no bearing on the personal preferences of anyone else, what would
you like to see change in the draft?

  regards,

  Dan.

> 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
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>