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

Rene Struik <rstruik.ext@gmail.com> Fri, 29 November 2013 20:46 UTC

Return-Path: <rstruik.ext@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com []) by ietfa.amsl.com (Postfix) with ESMTP id BD3581ADE7C for <cfrg@ietfa.amsl.com>; Fri, 29 Nov 2013 12:46:44 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Status: No, score=-1.999 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, HTML_MESSAGE=0.001, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id j66zNOqVqBcI for <cfrg@ietfa.amsl.com>; Fri, 29 Nov 2013 12:46:41 -0800 (PST)
Received: from mail-ie0-x230.google.com (mail-ie0-x230.google.com [IPv6:2607:f8b0:4001:c03::230]) by ietfa.amsl.com (Postfix) with ESMTP id 1A8F91ADDAC for <cfrg@irtf.org>; Fri, 29 Nov 2013 12:46:41 -0800 (PST)
Received: by mail-ie0-f176.google.com with SMTP id at1so16540428iec.21 for <cfrg@irtf.org>; Fri, 29 Nov 2013 12:46:39 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:date:from:user-agent:mime-version:to:subject:references :in-reply-to:content-type; bh=1ZPcmCwonJJ7gL8J2rN56Omtf1TkZnjHXZXlprbCv8A=; b=ZGyvIrRZrKybyrtnO/6OK1Omix/rldiLbD46AsIRMcJHso4oKJkHT4Or8ldRNCdWps BuXP1irQLLA7kWUs2H9W6h4NTqK+KgJd2fWgP3GzIXt49HUdUWD6tA01vwtIImPFXsKW TOfxJNe2HbWBmfrwptahmQAb/LHUoC2U1iYdbiO5SHO+iWWOSR6omNWOdkA3dVlBq+KA azQSLif3Dbe4Z36DQmo4muOy3RgL8uOBLQZV0yXxhUAGIPrliVSn+YAtFsUBHEec7DsK tZ1XJyyuSIvUy3fkU02AwM1YSkrhi5foexfc94u+OGFCu7QROaPA94xA0QN5Ogdv+5sa jtVw==
X-Received: by with SMTP id kq12mr3103120icc.55.1385757999668; Fri, 29 Nov 2013 12:46:39 -0800 (PST)
Received: from [] (CPE0013100e2c51-CM001cea35caa6.cpe.net.cable.rogers.com. []) by mx.google.com with ESMTPSA id s4sm15406788ige.0.2013. for <cfrg@irtf.org> (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Fri, 29 Nov 2013 12:46:38 -0800 (PST)
Message-ID: <5298FD1E.6020307@gmail.com>
Date: Fri, 29 Nov 2013 15:46:22 -0500
From: Rene Struik <rstruik.ext@gmail.com>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.1.1
MIME-Version: 1.0
To: "cfrg@irtf.org" <cfrg@irtf.org>
References: <3065D910-832C-47B6-9E0B-2F8DCD2657D2@cisco.com>
In-Reply-To: <3065D910-832C-47B6-9E0B-2F8DCD2657D2@cisco.com>
X-Forwarded-Message-Id: <3065D910-832C-47B6-9E0B-2F8DCD2657D2@cisco.com>
Content-Type: multipart/alternative; boundary="------------000305020200090508050407"
Subject: [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: Fri, 29 Nov 2013 20:46:44 -0000

Dear colleagues:

Please find below my review of the Dragonfly protocol 

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.

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.

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.
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.
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 
c-2) Implementation of modular reduction temp variable (derivation of 
seed value);
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))
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.
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.

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

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)

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

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