Re: [Cfrg] Wack-A-Mole and PKEX 3.0 -> Re: Fwd: New Version Notification for draft-harkins-pkex-00.txt

Andy Lutomirski <> Tue, 13 September 2016 19:57 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id A38A612B04D for <>; Tue, 13 Sep 2016 12:57:57 -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, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 2zNpvKjv_-pE for <>; Tue, 13 Sep 2016 12:57:55 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4002:c05::22a]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 75B7C126FDC for <>; Tue, 13 Sep 2016 12:57:55 -0700 (PDT)
Received: by with SMTP id i129so40354129ywb.0 for <>; Tue, 13 Sep 2016 12:57:55 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=FYZ2Z9wbHz9X5R2DGL+07CsYWCJPYlLQriDq1mdQovY=; b=oJUUAFDsMNSmbpRkpzwZBGqJ5NEFp6zCy3ERg9SN4dxiNK/EW/RHeicSYRUMVNaPLY c+KCfOJiOkzYpvRTNHOXif4qugu/DcQzYx6UPUUmeCy/qa9Vxqsp87Pq20hB0Y/8zWY3 1IEcKrz/2+n6zDEUaA9E2607u3PfAmH0Cm68thKGoW/+2w0b5gov+l3tzF9in8b3E8zz GXJqcD9RKPA5HA825g8nPLAUJ8P0EJ8DUkvEXTi201x6EM8dPJIUDg/++V02kV51LDJu sm3Itr2X2Ebq8x4Kz2/cwriSpmJlLcsrZpiHhgG6cp/qdxZIcZ8xvUWVwe2epAhJjrHV sefQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=FYZ2Z9wbHz9X5R2DGL+07CsYWCJPYlLQriDq1mdQovY=; b=E6eOnfQRymApYyYww6Dg7HjpYVMzuQrogPmcyMj9cIS1TP6S2TXdAMXI+jlsDj69YG P8ar0+WoSIIHxkUVDieLjN8hEbqFSCXIcd+cJWjPpqUizRX4GeZC+oWKtB81i/HlwZBh XaNUT7ZPczlbJuVdVOIp4/aoU29VLlhCv0zt5v1GNH8k9Qsjxlm1fiG0OALsALkv+7HE NH493Gn1QwdYHd2N1wWhphOl9CYbTk1f3TrDh8MTj/OBAwU783OEnB2aZLP7uwCXs+/X OXJA5oj4UYC2LRrr6MLFi+h3WsB5JwRKVact6Bk0tHmExaHZZpJds7dxbnV7s5T+pG8d H/fQ==
X-Gm-Message-State: AE9vXwMKrj2Xcie7QsNG32Ou0k/XpoS/IlDLWmY4AhU8HuJxC3BO/Bt4qnWEufRpNP3h2IZdyDCbIu7tScw+sJIF
X-Received: by with SMTP id p83mr2681334ywb.148.1473796674627; Tue, 13 Sep 2016 12:57:54 -0700 (PDT)
MIME-Version: 1.0
Received: by with HTTP; Tue, 13 Sep 2016 12:57:34 -0700 (PDT)
In-Reply-To: <>
References: <> <> <> <> <> <> <>
From: Andy Lutomirski <>
Date: Tue, 13 Sep 2016 12:57:34 -0700
Message-ID: <>
To: Dan Harkins <>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Archived-At: <>
Cc: "Adrangi, Farid" <>, "" <>
Subject: Re: [Cfrg] Wack-A-Mole and PKEX 3.0 -> Re: Fwd: New Version Notification for draft-harkins-pkex-00.txt
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, 13 Sep 2016 19:57:57 -0000

On Tue, Sep 13, 2016 at 12:24 PM, Dan Harkins <> wrote:
> On 9/13/16 9:51 AM, Andy Lutomirski wrote:
>> On Tue, Sep 13, 2016 at 7:36 AM, Paul Lambert <> wrote:
>>> With enough tries … PKEX 3.0 or PKEX n.0 could be deemed secure.
>>> Including
>>> the validated exchange of public keys in a PAKE exchange is a very
>>> interesting mechanism. Usage constraints of such a protocol still may
>>> make
>>> it inappropriate for particular applications.
>> Can we take a step back and ponder *why* a protocol that exchanges
>> public keys and proves possession of the corresponding private keys is
>> useful?
>> Here's roughly what PKEX tries to achieve (I think):  Alice and Bob
>> each know a password, and Alice and Bob are assumed to be the only
>> parties that know that password.  Alice can run PKEX and, if the
>> protocol succeeds, she knows that (1) a public key B, (2) that Bob
>> claims that the holder of the private key b is Bob and (3) that Bob
>> actually has the ability to perform private key operations using b.
>> Bob learns the same things about Alice and her keys.  There are whole
>> bunch of properties about offline attack that the protocol ought to
>> have.
>   Yes, that's a good list and let me add that Alice also knows that
> b is the private analog to the public key B. Also an important feature.

What does that mean?  Alice doesn't know b.  She knows that there
exists a number b such that B = b*G, but that's not interesting.  She
does not, and cannot, know that Bob actually knows b unless Bob tells
it to her (which would be a terrible idea) because b might reside on
an HSM.

>   If there are any other "properties about offline attacks that the protocol
> ought to have" that are not already listed in PKEX I'd like to hear about
> them. Thank you in advance.

A strong concept of what various parties (Alice, Bob, and any
potential MITM) can and cannot do to attack a weak password, online
and offline, even if Alice and Bob go and leak the entire output of
the protocol along with a and b afterwards.  The literature on PAKEs
should contain something usable here.

>> For the purpose of pairing two devices that intend to communicate
>> using public-key crypto, property (1) is obviously critical.  In my
>> mind, property (2) should be sufficient.  I'm asking why property (3)
>> is useful.
>   PKEX is, as the intro states, intended to provide trust to public keys
> so they can be used in a different exchange that uses "raw" public keys
> like TLS and IKEv2.

This doesn't mean anything to me.  I don't trust public keys.  I trust
certain things about the people who are able to use those keys in the

>   Now both TLS and IKEv2 offer security guarantees about the authenticated
> state of a successful run of the protocol and these are based, in part, on
> the assurances placed in the public keys used in authentication. For
> instance,
> that the certificate was not issued to someone who could not prove ownership
> of
> the public key.

Please elaborate.  What exactly breaks in TLS if I somehow obtain an
apparently valid certificate for that lists
Google's private key?  I certainly can't get any browser to identify
me as using such a certificate because I have no
ability to perform private key operations.  I sure hope that none of
the TLS variants are subject to identity misbinding attacks.

>> Here's an example of a bad protocol where you need property (3).
>> Suppose that Bob writes a message that says "Please send me $100" and
>> signs it using b.  Alice receives that message with appropriate
>> assurances from someone she trusts that she should pay $100.  She
>> further learns via an *unauthenticated* channel that the money should
>> go to Bob.  She looks up Bob's public key B, checks the signature,
>> decides that only Bob could have sent the message, and sends Bob $100.
>> This protocol requires property (3).  But it's insecure in general
>> anyway because digital signatures don't provide the guarantee that
>> Alice is relying on: in many digital signature protocols, Charlie can
>> take a signed message and generate a brand new key pair that appears
>> to have also signed that message.
>> But this protocol is just silly and shouldn't need property (3) at
>> all.  Bob should sign the message "Pay me, Bob, $100 to this account"
>> and Alice should look up the key that Bob says is safe to use to
>> identify him (property (2)) and check the signature.  Problem solved
>> (and it's now using digital signatures correctly, too).
>   Instead of addressing this ridiculous straw man of a protocol let me
> refer you to the seminal work of Hugo Krawczyk: "SIGMA: The SIGn-and-MAc
> Approach to Authenticated Diffie-Hellman and its Use in the IKE
> Protocols." I strongly suggest you read the whole thing very closely but
> pay special attention to the "identity mis-binding" attack he describes
> against STS "when parties can register public keys without proving knowledge
> of the corresponding signature key."

Do you mean this bit, quoted directly from the paper?

> Thus, for the STS to be secure one must assume that a secure external mechanism for proof of possession of signature keys is enforced. As we will see both the ISO protocol discussed in Section 4 and the SIGMA protocols presented here do not require such a mechanism.

A large part of that paper is about developing a protocol that does
*not* require property (3).

>> So what is DPP doing that makes property (3) useful in pairing?
>   Who cares? The property is not only useful it's critical!

It's only critical if DPP is poorly designed.  See above.

There's a good reason not to provide property (3), though: unless you
provide a genuine zero-knowledge proof of knowledge of the private
key, you are now at risk from cross-protocol attacks and the overall
protocol that uses your primitive needs to be checked for
cross-protocol attacks.  For example, here's a proof of possession of
a private key that is exceedingly dangerous:

Alice -> Bob (encrypted, authenticated, etc): N_a
Bob -> Alice (encrypted, authenticated, etc.): b * N_a

Bob has just proved knowledge of b very convincingly to Alice.  But
Alice can use this protocol as an oracle to sign arbitrary messages
from Bob.

Another problem with proving knowledge of the private key as a
built-in part of the protocol is that it ties the protocol to the
public-key cryptosystem.  If Bob is merely transmitting a bit string B
(with property (2) -- Alice trusts that Bob intended to send that bit
string), then B could be an encryption-only key, it could be on any
group, it could be a key of different underlying type entirely (e.g. a
hash-based signature key or a lattice key), etc.  If you prove
possession of b, then your protocol depends on the cryptosystem.  It
also may rule out restrictive HSMs -- suppose that Bob stores b on an
HSM that can *only* do ECDSA.  (This is probably a good idea in many
cases.)  Bob can't run your protocol.