Re: [Cfrg] review of draft-irtf-dragonfly-02 (triggered by [TLS] Working Group Last Call for draft-ietf-tls-pwd)

[Watson Ladd <[e-mail]>]

There is a foundations-of-hashing style attack that after one active
intervention can break a password offline with 2^40 work, by
reduction to the discrete logarithm with choices from a short list.
It requires a list of 2^40 magic numbers to function, but this implies
that there is *no* security proof, and in particular we do not
understand what security would mean for this protocol.

On Tue, Dec 3, 2013 at 10:46 AM, Dan Harkins <[e-mail]> wrote:
>
>   Dear Rene,
>
> On Fri, November 29, 2013 12:46 pm, Rene Struik wrote:
>> Dear colleagues:
>>
>> Please find below my review of the Dragonfly protocol
>> (draft-irtf-cfrg-dragonfly-02).
>>
>> This review was triggered by the IETF LC that was recently initiated in
>> the TLS WG on the related draft draft-ietf-tls-pwd-01. However, review
>> comments below *strictly* apply to the latest CFRG draft only; the
>> related TLS draft will be dealt with separately. (Contrary to the
>> suggestion in the IETF LC, the cryptographic constructs underlying the
>> TLS draft and the CFRG draft cannot be mapped to each other.)
>>
>> Note: To my knowledge, current status CFRG draft is unknown. Last
>> mailing list discussion of December 12, 2012 [3] primarily focused on
>> potential side channel attacks on the password-to-base point mapping,
>> which triggered some changes in the draft (draft reviewed below was
>> posted Aug 27, 2013). To my knowledge, contrary to implicit message in
>> TLS WG LC, no "blessing" by CFRG was received.
>
>   The status of any draft can be determined from the tracker, specifically:
>
>       https://datatracker.ietf.org/doc/draft-irtf-cfrg-dragonfly/
>
> It has an IRTF state and an IESG state.
>
>> One-line summary: While the proposed protocol could probably be made to
>> work, it would require more work to get there, including removal of
>> security weaknesses (see analysis below).
>>
>> Review notes:
>>
>> 1) Abstract.
>> This draft proposes a password-based key agreement scheme (including key
>> confirmation), based on knowledge by either party of a shared
>> low-entropy password. The scheme resembles the ephemeral Diffie-Hellman
>> key agreement scheme, where the generator of the DH group used is
>> derived from the shared password.
>>
>> 2) General comments.
>> a) Security evidence. The protocol would benefit from detailed
>> cryptanalysis, which is currently lacking. While the document
>> cross-references other standards that have implemented (a variant of)
>> the protocol, this should not be seen as substitute for the need to
>> provide technical evidence.
>> b) Protocol rationale. It is unclear what makes this protocol special
>> compared to other contenders: there are quite a few password-based
>> protocols out there, of which one could focus on ones with similar or
>> better performance and with detailed cryptanalysis.
>
>   There is no claim of "specialness" being made in the draft.
>
>   And nothing is stopping you from doing work to focus on protocols that
> pique your interest.
>
>> 3) Security comments (require fixing).
>> a) The protocol succumbs to a simple reflection attack, an elementary
>> protocol attack (see [1, Section 12.9.1]), where the responding party
>> simply bounces back messages sent by the initiator of the protocol. This
>> follows immediately from the way the key confirmation exchange messages
>> re structured (Section 3.4, p. 12). While it seems quite easy to fix the
>> protocol thereby thwarting this attack, it is quite serious that this
>> attack occurs in the first place (and has not been discovered yet). This
>> re-emphasizes the need to have protocols accompanied by detailed
>> technical rationale.
>
>   Actually this was mentioned in other instantiations of dragonfly,
> namely RFC 5931 and IEEE Std 802.11-2012. My bad for not mentioning
> it here. Thanks for reminding me!
>
>> b) The protocol is claimed to be secure against passive and active
>> attackers (see the Abstract). While it is easy to show that the
>> Diffie-Hellman key exchange is indeed secure against passive attacks
>> (see, e.g., the  informal argument on Slide 11 of [2]), security in
>> context of active adversaries is unknown, contrary to what is claimed.
>> In fact, Slide 12 of [2] suggests that this will be hard to prove. While
>> provability also has limitations, suffice it to say that unjustified
>> claims should not be made.
>
>   I'm sorry but I disagree with this being something that will "require
> fixing".
>
>> c) The hunting and pecking procedure (Section 3.2) has changed from one
>> version of the draft to the next, primarily to thwart potential side
>> channel attacks (see also discussion in [3]). Unfortunately, there are
>> still many opportunities to derive password-dependent information if one
>> is not *extremely careful* to implement steps correctly (in all these
>> cases, this leads to a password space partitioning attack):
>> {Discussion relative to Section 3.2.1}
>> c-1) Implementation of quadratic residue test (computation of Legendre
>> symbol);
>
>   There is already a test that (x^3 + ax + b) is a quadratic residue. If
> it's not then PE is not found and hunting-and-pecking continues.
>
>> c-2) Implementation of modular reduction temp variable (derivation of
>> seed value);
>
>   There is a typo there-- "seed' and "temp" are mixed up. Thanks for
> pointing that out.
>
>> c-3) Implementation of choice of +/- PE  (leakage of password info via
>> base value, esp. lethal if one includes nonces in the base computation
>> (as recommended in Section 3.2, p. 10, last para))
>
>   I do not see the lethality when one includes nonces in H(). Please
> explain this lethalness to me.
>
>> c-4) Implementation of the loop with not sufficiently many rounds k (the
>> draft does not provide any guidance). Mailing list discussion [3]
>> resulted in recommendation to pick k:=40.
>
>   That is already mentioned in the draft.
>
>> c-5) The password element PE resulting from the loop is the one with
>> highest counter value. This may result in implementers (or compilers)
>> taking shortcuts and looping backwards, so as to avoids seemingly
>> unnecessary (seemingly, since discounting implementation attacks)
>> overhead. The mailing list discussion [3] resulted in the recommendation
>> to pick as password element PE the middle pick, rather than the last
>> pick, so as to protect implementers against their own vices.
>
>   I think it would be better to choose the first. I will make that change.
>
>> 4) Smaller comments (require fixing).
>> a) Section 3.2: The hunting and pecking procedure has changed from one
>> version of the draft to the next. Unfortunately, the last changes still
>> has bugs, thereby suggesting the draft to be unstable: a-1) In Section
>> 3.2.1, the temp variable should be expressed in terms of base in
>> kdf-n(base,...), and not in terms of uninitiated variable seed in
>> kdf-n(seed, ...); a-2) Similar remark as in #a above, but now w.r.t.
>> Finite Field groups.
>
>   Yes, you mentioned that already. There's a typo; I'll fix it.
>
>> b) Section 3.1, Assumption 2: The function F (point-to-x-coordinate
>> mapping in case of elliptic curves) is not an injection: after all,
>> point Q and -Q have the same x-coordinate.
>
>   Hmmm, good point (no pun intended). I'll address that.
>
>> c) Section 3.1, Assumption 4: the security of the protocol depends on
>> the intractability of the Diffie-Hellman problem, not on that of the
>> discrete log problem (it is not always known whether the former is as
>> hard as the latter).
>
>   Actually I don't agree. This isn't really a Diffie-Hellman exchange.
>
>> d) Section 3.2, p. 9, last sentence: this is an example where "64 more
>> bits than needed" is false, since obviously needed to counter potential
>> bias of modular reduction if the modulus p is not close to a power of two.
>
>   It notes that the reason is to counter potential bias. It really is
> stretched
> to 64 bits more than is needed because 64 is added to the length that
> is needed. What _specifically_ do you want me to change in that sentence?
>
>> e) Section 3.2, p. 10, last sentence: mixing-in nonces with the PE
>> procedure yields a set of pairs {(r,Q(pwd,r)}, which may be exploited
>> via side channel analysis.
>
>   Please explain this attack.
>
>> f) Section 3.2.2, p. 11: The title suggests MODP groups, whereas any
>> subgroup, not just the ones of safe-prime groups, is -- I presume --
>> meant.
>
>   There is no suggestion made in the draft that "MODP" is exclusively
> "safe-prime groups".
>
>> g) Section 3.3, p. 12, first para: it is not clear why the private key
>> and mask should be in range [2,q-1]; in passive attack case, one only
>> needs that private key is in [1,q-1]; mask can be any value.
>
>   You mention above your desire for conservativeness in design-- i.e.
> to be "*extremely careful* to implement steps correctly"-- yet you
> now seem to suggest a dangerous relaxing. I think it's best to keep
> strict bounds on things like this that have no apparent benefit to
> relaxation but have some potential downsides (some lazy person
> will make a mask that's 20 bits).
>
>> h) Section 3.3, p. 12: the mechanism by which kck and mk are derived is
>> ambiguous (any split of the concatenated string will do right now).
>
>   What is the ambiguity? Keying material of length n = len(p) * 2 is
> derived and the first len(p) bits are kck and the next len(p) bits
> are mk.
>
>> i) Section 6, p. 14, second para: on-the-fly generation of groups with
>> random domain parameters is so dangerous that it should be forbidden
>> outright (not just recommended).
>
>   Yes, it is dangerous but protocols that could use dragonfly (like TLS)
> allow them and I don't want to expressly disallow dragonfly in TLS
> simply because it allows for on-the-fly agreement of domain parameters.
>
>> j) Section 2.1, p. 5, 6th para: scalar operation is addition (not
>> multiplication) of a point to itself. Later on in the same para: is
>> added (x-1)-times to itself...
>
>   You're right. Thanks for finding that, I'll fix it.
>
>> 5) Typos, etc.
>> a) Abstract: fix cryptogprahy
>> b) Section 2: fix Discete log crypto;
>> c) Section 3.2: fix Derviation.
>> d) Throughout: fix dragonfly (capitalize).
>> etc. (many more)
>
>   I'll check into these. Thanks for such a detailed read of my draft!
>
>   regards,
>
>   Dan.
>
>> Ref:
>> [1] A. Menezes, P. van Oorschot, S. Vanstone, "Handbook of Applied
>> Cryptography", CRC Press: 1995.
>> [2] presentation at CFRG meeting during IETF-83, Paris, France, March
>> 26-30, 2012:
>> http://www.ietf.org/proceedings/83/slides/slides-83-cfrg-0.pdf
>> [3] CFRG mailing list discussion, see, e.g., December 12, 2012
>> discussion by Kevin Igoe et al:
>> http://www.ietf.org/mail-archive/web/cfrg/current/msg03258.html
>>
>>
>>
>>
>> -------- Original Message --------
>> Subject:      [TLS] Working Group Last Call for draft-ietf-tls-pwd
>> Date:         Fri, 8 Nov 2013 01:11:39 +0000
>> From:         Joseph Salowey (jsalowey) <[e-mail]>
>> To:   <[e-mail]> <[e-mail]>
>>
>>
>>
>> This is the beginning of the working group last call for
>> draft-ietf-tls-pwd-01.
>> The underlying cryptographic protocol for TLS-PWD has been reviewed by the
>> IRTF CFRG
>> group with satisfactory results.  The document needs particular attention
>> paid to the
>> integration of this mechanism into the TLS protocol.
>> Please send comments to the TLS list by December 2, 2013.
>>
>> - Joe
>> (For the TLS chairs)
>> _______________________________________________
>> TLS mailing list
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/tls
>>
>>
>>
>> _______________________________________________
>> Cfrg mailing list
>> [e-mail]
>> http://www.irtf.org/mailman/listinfo/cfrg
>>
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin