Re: [Cfrg] Review of Dragonfly PAKE

[Trevor Perrin <[e-mail]>]

On Tue, Dec 10, 2013 at 5:35 PM, Dan Harkins <[e-mail]> wrote:
>
>   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.

It makes little sense to use a 1024-bit FFC group in any circumstances
because (pardon me, Kevin) - fuck the NSA.

Having server-side password-data be flexible to different DH groups
seems of little value.  For a typical password auth performed over an
existing encrypted session, the PAKE DH group is already decoupled
from the session's DH group.

I prefer the security benefit of an augmented PAKE.


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

I think augmented PAKEs are preferable.  But if you really want a
balanced PAKE, there are many better than Dragonfly (e.g. DH-EKE,
SPAKE2, J-PAKE).


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

The AugPAKE IPR declaration is not a license, it's a declaration that
the AugPAKE patent holders will make a royalty-free license available
*if* the IETF adopts AugPAKE on the standard track.

I hope the AugPAKE inventors have seen enough IETF incompetence to
rethink tying AugPAKE's future to the IETF.  I would certainly prefer
a royalty-free license without such restrictions.

But I see no basis for questioning the honesty of the AugPAKE IPR declaration.


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

Yes.  You added a gimmick to SPEKE, hoping to avoid its IPR.


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

That thread develops your theory about how the SPEKE patent only
applies to a "known technique of unauthenticated key distribution",
and how your gimmick transforms DH into something unknown, thus
avoiding it.

I'm not qualified to assess this argument, but it seems dubious.  The
primary innovation in SPEKE is mapping a password to a DH base point,
which is used in Dragonfly.  Adding innovations onto an existing
patented work does not free you from the earlier patent.

Perhaps I'm wrong.  But the patent situation in the rest of the PAKE
world seems much clearer.  The last Lucent EKE patent expired a few
months ago.  As that was from the inventors of the PAKE concept, it
cast a bit of a pall over the whole area.  But now that's gone.

I'm particularly leery of the SPEKE patents, as the patent holder used
to aggressively pursue licensing.

So while I support steering clear of difficult IPR, I think there are
easier ways of doing it.


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

To me, it looks like Diffie-Hellman with a silly gimmick.


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

Except that sidechannel attacks use statistics, so injecting noise
just increases the number of measurements required.

Modern crypto practice is to prefer constant-time algorithms when
remote timing attacks are possible, as in this case.


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

Yes, I see people like Rene Struik recommended not mixing the nonces
in multiple times [1,2].

Even Kevin Igoe - a fount of bad advice, generally - mentioned this
once, before agreeing that just looping a shit-ton of times was an
"elegant change" [3,4].


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

I won't support this draft even with the gratuitous sidechannel problem fixed.

I think it's a bad PAKE and there are many better ones (DH-EKE,
SPAKE2, J-PAKE, SRP, AugPAKE, and probably others).


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

1 and 2 are true.  I don't understand why CFRG is reviewing this, or
why the TLS WG is considering TLS-PWD.

According to chair Kevin Igoe, Dragonfly "fills a real need" [5].
Perhaps he can explain.

(I'm not a cheerleader for AugPAKE.  It's one of many protocols that
are better than Dragonfly).


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

I'd prefer to use PAKEs which steer clear of the SPEKE approach entirely.


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

I don't support this draft.  I think it's a bad PAKE and there are better ones.


Trevor


[1] http://www.ietf.org/mail-archive/web/cfrg/current/msg03489.html
[2] http://www.ietf.org/mail-archive/web/cfrg/current/msg03527.html
[3] http://www.ietf.org/mail-archive/web/cfrg/current/msg03258.html
[4] http://www.ietf.org/mail-archive/web/cfrg/current/msg03262.html
[5] http://www.ietf.org/mail-archive/web/cfrg/current/msg03383.html