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

From: Rene Struik <[email-masked]>
Date: Fri, 29 Nov 2013 15:46:22 -0500

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.

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 
symbol);
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)

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

---

From: Basil Dolmatov <[email-masked]>
Date: Sat, 30 Nov 2013 16:48:22 +0400

Dear colleagues,

I think  that this can be of interest for list participants:

PROVISION
on the Open Research Paper Competition on Hash-Function GOST R 34.11-2012 

...
There are 16 tasks, publications about which will be accepted. Submissions to the competition can be made up to 28 February 2014

For more details, please refer to www.streebog.info (choose ENG as a language) or specifically to http://www.streebog.info/upload/documents/polozhenie_full_eng.pdf

I hope that someone can find these tasks interesting. Please fell free to distribute this information to anyone who could be interested in participation.

dol@

---

From: Feng Hao <[email-masked]>
Date: Sat, 30 Nov 2013 21:03:21 +0000

Dear Rene and members on the list,

I am new to this list, so please pardon me for my unfamiliarity with how things work in CFRG.

Regarding the comment on a lack of cryptanalysis on the dragonfly protocol, there is a paper (in press) to be published by IET Information Security.

A preprint of the paper can be found at:

http://homepages.cs.ncl.ac.uk/feng.hao/files/Dragonfly_final.pdf

The attack is caused by a lack of public key validation in the protocol (dragonfly-00). We communicated the attack to Dan in private emails (and we thank Dan for quick feedback). As I understand it, addressing the attack is one of the major changes in the later versions of the draft.

On the subject of PAKE, besides considering dragonfly, I would suggest people on the list to spare a moment to consider J-PAKE as another potential candidate.

The J-PAKE protocol was designed by Peter Ryan and myself in 2008. From the day the paper was presented at SPW'08, we decided to write a blog and be fully open to any comments, questions and critiques from anyone over the Internet. You can find the full track of discussions and developments of J-PAKE in the blog below:

http://www.lightbluetouchpaper.org/2008/05/29/j-pake/

After 5 years of public scrutiny with no attacks found,  I feel now may be a good time to recommend J-PAKE for more general use. In fact, J-PAKE has already been used in real-world applications at a relatively large scale. Note that by design, J-PAKE is naturally fit for elliptic curve implementation without change in the protocol - more specifically, it doesn't require any mapping–to–curve function as in dragonfly or SPEKE. More details about J–PAKE can be found in the Internet draft below:

J-PAKE Internet-draft: http://datatracker.ietf.org/doc/draft-hao-jpake/

I am happy to answer any questions if anyone on the list is interested.

Best regards,
Feng

From: Rene Struik <[email-masked]<mailto:[email-masked]>>
Date: Fri, 29 Nov 2013 15:46:22 -0500
To: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: [Cfrg] review of draft-irtf-dragonfly-02 (triggered by [TLS] Working Group Last Call for draft-ietf-tls-pwd)

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.

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

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]><mailto:[email-masked]>
To:     <[email-masked]><mailto:[email-masked]> <[email-masked]><mailto:[email-masked]>

- Joe
(For the TLS chairs)
_______________________________________________
TLS mailing list
[email-masked]<mailto:[email-masked]>https://www.ietf.org/mailman/listinfo/tls

_______________________________________________ Cfrg mailing list [email-masked]<mailto:[email-masked]>http://www.irtf.org/mailman/listinfo/cfrg