Re: [Cfrg] review of draft-irtf-dragonfly-02 (triggered by [TLS] Working Group Last Call for draft-ietf-tls-pwd)
Watson Ladd <watsonbladd@gmail.com> Wed, 04 December 2013 03:29 UTC
Return-Path: <watsonbladd@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id AEEAA1AE02A for <cfrg@ietfa.amsl.com>; Tue, 3 Dec 2013 19:29:08 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] 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 DEXCsO0vfE8R for <cfrg@ietfa.amsl.com>; Tue, 3 Dec 2013 19:29:05 -0800 (PST)
Received: from mail-wg0-x22c.google.com (mail-wg0-x22c.google.com [IPv6:2a00:1450:400c:c00::22c]) by ietfa.amsl.com (Postfix) with ESMTP id CDC061ADFF5 for <cfrg@irtf.org>; Tue, 3 Dec 2013 19:29:04 -0800 (PST)
Received: by mail-wg0-f44.google.com with SMTP id a1so12590963wgh.23 for <cfrg@irtf.org>; Tue, 03 Dec 2013 19:29:01 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=Htu9jizhDaTNJKHeX+i48tz8KWwBgEXXcAq5o6XunYc=; b=TsmAZPL5npK1J85SHXZNex6FpSXs+DvAJ5Ya01bF8lgtw3uQvyke8wl7CbYdgoa66R pEmSuZpjja1VJ0AL9ycBFLVUYXSIGIjElD0hVH7Zy4oPcqOIszppRvskaY1/SYw41MYS lMQWPygl3eG0nzUjwELhVguwl5YXs7Y83t3dG0ppYEiLkT0cOYjxunZXSOdn2spf70zL 5lQnFWo4Sgcx7Ds43fAy6lMrnO3znkVauCFwVAjbW7nAUSQ4GrdFaAVboiccYI3M1+70 Wx1QBrTDqhgIyAFY+MhIVn1L/AAwQfy6hcekSrMg+eTM8v9jWgGxlvUlwBNynS8GtDR2 4M0g==
MIME-Version: 1.0
X-Received: by 10.194.48.115 with SMTP id k19mr10111482wjn.47.1386127741419; Tue, 03 Dec 2013 19:29:01 -0800 (PST)
Received: by 10.194.242.131 with HTTP; Tue, 3 Dec 2013 19:29:01 -0800 (PST)
In-Reply-To: <92ae96995bb83441df86933581cb5eed.squirrel@www.trepanning.net>
References: <3065D910-832C-47B6-9E0B-2F8DCD2657D2@cisco.com> <5298FD1E.6020307@gmail.com> <92ae96995bb83441df86933581cb5eed.squirrel@www.trepanning.net>
Date: Tue, 03 Dec 2013 19:29:01 -0800
Message-ID: <CACsn0cmuTM-HwwNOhSC=J=fZqH1okKyZ+WWKmdgE=K8hDt538Q@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Dan Harkins <dharkins@lounge.org>
Content-Type: text/plain; charset="UTF-8"
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] review of draft-irtf-dragonfly-02 (triggered by [TLS] Working Group Last Call for draft-ietf-tls-pwd)
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 04 Dec 2013 03:29:08 -0000
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 <dharkins@lounge.org> 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) <jsalowey@cisco.com> >> To: <tls@ietf.org> <tls@ietf.org> >> >> >> >> 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 >> TLS@ietf.org >> https://www.ietf.org/mailman/listinfo/tls >> >> >> >> _______________________________________________ >> Cfrg mailing list >> Cfrg@irtf.org >> http://www.irtf.org/mailman/listinfo/cfrg >> > > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > 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
- [Cfrg] review of draft-irtf-dragonfly-02 (trigger… Rene Struik
- [Cfrg] Open competition for GOST 34.11.2012 hash … Basil Dolmatov
- Re: [Cfrg] review of draft-irtf-dragonfly-02 (tri… Feng Hao
- Re: [Cfrg] review of draft-irtf-dragonfly-02 (tri… Dan Harkins
- Re: [Cfrg] review of draft-irtf-dragonfly-02 (tri… Watson Ladd