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

From: "Dan Harkins" <[email-masked]>
Date: Tue, 3 Dec 2013 10:46:09 -0800 (PST)

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) <[email-masked]>
> To: 	<[email-masked]> <[email-masked]>
>
>
>
> 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
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>
>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Watson Ladd <[email-masked]>
Date: Tue, 3 Dec 2013 19:29:01 -0800

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.

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