Subject: [Cfrg] PKEX Update and Summary

From: Paul Lambert <[email-masked]>
Date: Mon, 19 Sep 2016 21:52:54 +0000

I¹ve posted a summary of the ³PKEX² protocol and it¹s background:

	https://mentor.ieee.org/802.11/dcn/16/11-16-1142-02-00ai-cryptographic-rev
iew-and-pkex.ppt

The presentation provides an overview of the protocol and details of the
O(sqrt(N)) off-line attack and the MiTM attack.

Any productive comments and would be greatly appreciated. Please do let me
know me know if you identify significant errors or omissions.

Note - the PKEX protocol was removed from IEEE 802.11ai last week.

Regards,

Paul

---

From: Dan Harkins <[email-masked]>
Date: Mon, 19 Sep 2016 16:07:05 -0700

Hi Paul,

> know me know if you identify significant errors or omissions.

   I do not think you and Andy represent "a 'good' PAKE" properly vis-a-vis
off-line dictionary attacks on slide 9 of your presentation. The 
definition of
a dictionary attack is one where the adversary gains an advantage through
_computation_ and not _interaction_.

   For "a 'good' PAKE" an off-line dictionary attack is not possible. 
It's not,
as you claim, that it takes O(sqrt(q)), it's that it's not possible at all.

   Given resistance to dictionary attack, the best an attacker can do is
repeated active attacks learning one thing with each attack: whether a 
single
guess of the password is correct. The work order of this type of attack is
based on the size of the pool from which the password is drawn (the pool
being known to the adversary).

   So your comment that an attack against "a 'good' PAKE" using curve 
P256 "for
any passphrase...is of order 2^127" is also incorrect. The order of the
curve does not matter in this sort of repeated active guessing attack,
merely the size of the pool from which the password was drawn.

> Note - the PKEX protocol was removed from IEEE 802.11ai last week.

   If you are going to make summaries of "PKEX" then you should be
complete and point out that the attacks described in your presentation
are not possible against the protocol called PKEX as described in
draft-harkins-pkex. Please correct the record.

   regards,

   Dan.

---

From: Paul Lambert <[email-masked]>
Date: Tue, 20 Sep 2016 21:50:48 +0000

Dan,

>as you claim, that it takes O(sqrt(q)), it's that it's not possible at

Yes - that text was attempting to give a comparison of the level of
difficulty of the attack. I was attempting to show that the search space
for a brute-force attack on a ‘good PAKE’ is related to the order of the
group and not (as in PKEX) the order of the passphrase space.

I’ve republished and made the description simpler:
https://mentor.ieee.org/802.11/dcn/16/11-16-1142-03-00ai-cryptographic-revi
ew-and-pkex.ppt

I assume this also means that you acknowledge that your characterization
of the brute-force and MiTM attacks are incorrect in:
	https://mentor.ieee.org/802.11/dcn/16/11-16-1151-07-00ai-kdf-prf-pkex.docx

>merely the size of the pool from which the password was drawn.

I disagree … the value of a PAKE is in extending the entropy of the search
space. Off-line brute-force attacks are related to the order of the group.

PKEX is broken because the first message: Ca = Pa + m_a*Pwe

The ‘Pa’ in PKEX is a static long term key and replaced the usage in
SPAKE2 of an ephemeral key.

Brute force attacks on SPAKE2 require guessing the passphrase and
ephemeral values. The ephemeral values are of order ‘q’ (order of curve).

Brute force attacks may be attempted on both PKEX and SPAKE2. Such an
attack on SPAKE2 is infeasible because of the size of the search space,
which is what I was trying to illustrate.

>draft-harkins-pkex. Please correct the record.

?
Please correct the title of the more recent draft since the source of the
confusion comes from the author of the drafts choice of naming. As
recommended before, the draft could be PKEX 2.0, PKEX 3.0 or some new
acronym.

Paul