Re: [Cfrg] PKEX Update and Summary

Paul Lambert <> Tue, 20 September 2016 21:50 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 6776312B4EA for <>; Tue, 20 Sep 2016 14:50:56 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.601
X-Spam-Status: No, score=-2.601 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id BFuslj1eHDDQ for <>; Tue, 20 Sep 2016 14:50:54 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id E36B512B4DC for <>; Tue, 20 Sep 2016 14:50:54 -0700 (PDT)
Received: from pps.filterd ( []) by ( with SMTP id u8KLoUlw007155; Tue, 20 Sep 2016 14:50:54 -0700
Received: from ([]) by with ESMTP id 25h36knjv7-8 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT); Tue, 20 Sep 2016 14:50:52 -0700
Received: from ( by ( with Microsoft SMTP Server (TLS) id 15.0.1104.5; Tue, 20 Sep 2016 14:50:48 -0700
Received: from ([fe80::6cb0:4dfa:f3f3:b8b6]) by ([fe80::6cb0:4dfa:f3f3:b8b6%21]) with mapi id 15.00.1104.000; Tue, 20 Sep 2016 14:50:48 -0700
From: Paul Lambert <>
To: Dan Harkins <>, "" <>
Thread-Topic: PKEX Update and Summary
Thread-Index: AQHSEsAsOQ6XQjC40kuDkuS1YdP37qCB5OuAgAEHqgA=
Date: Tue, 20 Sep 2016 21:50:48 +0000
Message-ID: <>
References: <> <>
In-Reply-To: <>
Accept-Language: en-US
Content-Language: en-US
user-agent: Microsoft-MacOutlook/
x-ms-exchange-messagesentrepresentingtype: 1
x-ms-exchange-transport-fromentityheader: Hosted
x-originating-ip: []
Content-Type: text/plain; charset="euc-kr"
Content-ID: <>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:, , definitions=2016-09-20_08:, , signatures=0
X-Proofpoint-Details: rule=outbound_notspam policy=outbound score=0 priorityscore=1501 malwarescore=0 suspectscore=0 phishscore=0 bulkscore=0 spamscore=0 clxscore=1015 lowpriorityscore=0 impostorscore=0 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1609020000 definitions=main-1609200278
Archived-At: <>
Subject: Re: [Cfrg] PKEX Update and Summary
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 20 Sep 2016 21:50:56 -0000


>On 9/19/16 2:52 PM, Paul Lambert wrote:
>> I¹ve posted a summary of the ³PKEX² protocol and it¹s background:
>> 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
>> know me know if you identify significant errors or omissions.
>   I do not think you and Andy represent "a 'good' PAKE" properly
>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

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:

I assume this also means that you acknowledge that your characterization
of the brute-force and MiTM attacks are incorrect in:

>   Given resistance to dictionary attack, the best an attacker can do is
>repeated active attacks learning one thing with each attack: whether a
>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 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.

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.

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

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


>   regards,
>   Dan.