Re: [Cfrg] Fwd: New Version Notification for draft-harkins-pkex-00.txt

Andy Lutomirski <> Tue, 13 September 2016 16:25 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 41A7F12B45E for <>; Tue, 13 Sep 2016 09:25:37 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.6
X-Spam-Status: No, score=-2.6 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, 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 KSauxkH3efci for <>; Tue, 13 Sep 2016 09:25:34 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:400c:c05::22a]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 9C5C612B45C for <>; Tue, 13 Sep 2016 09:15:15 -0700 (PDT)
Received: by with SMTP id 16so166038770vko.2 for <>; Tue, 13 Sep 2016 09:15:15 -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; bh=wpJkGp62ONd6MrORP5yGJs8YzuiugCkmhvw7KH0tn/k=; b=R8MDh+Nomoq4RL8jKVL7FRK5kUj+DoxMFg2zH4ksJ2IhHJgp+da2BZ1USB2Hy0S6Jp cPqEzRXzAl4MCCFD0PR/UuLC0LwgjQ8BJ3lzWXOntaAaiMLZZzKlWlxMvoxSrHpB9Arc fqbbeolzuZjGyVy+4OEQQeiuav38pP6tIHF+zTPWXMMrd/xMIEjMsT1e7N4OXCg661cR XW1Mf8w/V9uY6Vg47aSlhG4sXWrSOqkD3CZYOPCs0eKHMVxosoWTX/rsjeLhNZVzzCkH vM3RUeXieTZMXJ834KymEb1ihR3FOEoM8mImHWccJp6ttNSYCdr3ZXk4uctrY4pVnoZ4 FgLQ==
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; bh=wpJkGp62ONd6MrORP5yGJs8YzuiugCkmhvw7KH0tn/k=; b=LQIEVeFzVdCCqp6MPECU07u8i4dna/Q+xC0kbpwa8Vp3se0N0eQ56EE0xZHBFXAROE hUEt4CaXaCi5W9rfRE2bS2SZsaT2jhdJtRMMu5WG4Pzm/sQa/awpNQ/VzM/RYLbZnAHC AU1G56PubQIuqxrNzwsSyGEJptGjvWQmFS4WJlEt02++tnvWHxZUg/nwUqCeh+vmoGkw 6Phmr2RrRRRIXYNA+0xP9OvrR1wg+tPvPf/ohD7bZmoCWtI5JdNtYURJ9PDQYHaiKNuK 2C43wRm7pvmdrpXFZ+YCCZxFQfH41Umi3HNzyVuAyRUsfjkFR/f7+26roo/4g7VubUQd rj4A==
X-Gm-Message-State: AE9vXwPkEHC/WLB9WELPnfCp/u/hem9wFUvID+/5dCbeRZM0kPvShk0woAnsapv+LeQ/2f99XfrrQtgTpp6lCrGn
X-Received: by with SMTP id i62mr1370787vkc.137.1473783314264; Tue, 13 Sep 2016 09:15:14 -0700 (PDT)
MIME-Version: 1.0
Received: by with HTTP; Tue, 13 Sep 2016 09:15:13 -0700 (PDT)
Received: by with HTTP; Tue, 13 Sep 2016 09:15:13 -0700 (PDT)
In-Reply-To: <>
References: <> <> <> <> <> <> <> <>
From: Andy Lutomirski <>
Date: Tue, 13 Sep 2016 09:15:13 -0700
Message-ID: <>
To: Dan Harkins <>
Content-Type: multipart/alternative; boundary=94eb2c096ef4ec4bee053c65ea1b
Archived-At: <>
Subject: Re: [Cfrg] 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 16:25:37 -0000

On Sep 13, 2016 8:59 AM, "Dan Harkins" <> wrote:
> On 9/13/16 7:59 AM, Andy Lutomirski wrote:
>> On Sep 13, 2016 12:39 AM, "Dan Harkins" <> wrote:
>> >
>> > On 9/12/16 2:43 PM, Andy Lutomirski wrote:
>> >> Alice and Bob start running the protocol with one password pw1.  Alice
>> >> sends X + Qa = X + F(pw1) * Pi where F is a function that an attacker
>> >> can compute.  The attacker interrupts the exchange and Alice and Bob
>> >> retry using a different pasword.  The draft *says* that the keys are
>> >> ephemeral, but that's really hard to believe because the whole stated
>> >> point is to establish a long-term key.  So Alice how sends X + F(pw2)
>> >> * Pi.
>> >
>> >
>> >   So your "attack" is based on the supposition that it's "really hard
>> > to believe" an ephemeral key is ephemeral? Hmmm.
>> >
>> >   What you have done is to look at the _very first_ of the Security
>> > Considerations, decided to ignore the statement that says you void
>> > the security of the exchange if you reuse ephemeral keys and then claim
>> > you have discovered an "attack" on the protocol?
>> No, I read a different version of the protocol that really did seem to
do this, and I didn't notice that this part changed.
>> But what's the point, then?  Why are you inventing a brand new PAKE that
doesn't have a security proof?  What benefit do you gain over using a real,
proven PAKE?
>> But you are still reusing the ephemeral keys yourself in the very same
protocol! Suppose Bob *doesn't* know the password but does know a.  (He
*shouldn't*, but still.)  Bob can run most of the protocol anyway by
sending random made-up values and Alice will send u.  Bob can now calculate
what Alice would have sent as u for any given pw value and thus brute-force
the password.
>   If Bob knows a then Bob knows the private key to Alice's long-term
> key. He can also trivially determine A. So he can impersonate Alice in
> or any other protocol using a trusted "raw" key for authentication. The
> of him attacking PKEX to determine an, essentially, one time use password

Back up a sec.  A real PAKE is secure if the password is reused because no
party in the entire exchange can brute-force it offline.  There is no
legitimate reason that a new protocol shouldn't provide the same property.

>   Granted, this does, I guess, technically violate one of the properties
> (active attack only learns whether one guess of the password was right or
> but as an attack is so contrived as to be pointless, as are most
"attacks" that
> begin, "Assuming I have the private key...."

Attacks only get worse.

>   I guess I could add some note in the assumptions that private keys are
> but I figured that went without saying. Thank you for your comment
though, it may
> result in a change to the draft.

Or you could fix the protocol.

>> For this type of protocol, you should be building on real primitives
with provable security, and you should use them as intended so the security
proof works.
>   It is possible to build something, as you suggest, that approximates
PKEX using
> some other PAKE plus an AEAD scheme plus some PKCS#10 blob but it has its
> security critical moving parts. And then you end up with something like
> authenticating EST, which is a tad heavyweight and not the kind of PAKE
usage that
> the PAKE requirements draft is referring to; PKEX is.
>> >> Step 1: define clearly what you're actually trying to do.  I'll guess
>> >> what you're trying to do: Alice and Bob are devices with keyboards,
>> >> and there's a user (an actual person) who will come up with a
>> >> temporary password to use to pair the devices.  Both devices have
>> >> keyboards.
>> >>
>> >> Step 1: User chooses a password and types it in to both devices.
>> >>
>> >> Step 2: Alice and Bob run a balanced PAKE (DH-EKE, SPAKE2, whatever)
>> >> using that password.  They do this the normal way, using fresh
>> >> ephemeral random numbers as prescribed by the PAKE in use, and they do
>> >> not keep any internal values around that they are supposed to discard.
>> >> The result is a shared secret.  They do this PAKE exchange exactly
>> >> once and they do not retry without explicit input from the user.
>> >
>> >
>> >   Interesting that now "fresh ephemeral random numbers as prescribed
>> > by the PAKE" are eminently believable yet you find such behavior
>> > "really hard to believe" for PKEX.
>> >
>> >
>> >>
>> >> This has the usual balanced PAKE security property: an attacker gets
>> >> exactly one guess with which to try cracking the password, and no
>> >> off-line attack against the password is possible.
>> >>
>> >> Step 3: Alice uses her favorite authenticated encryption protocol,
>> >> keyed by the shared secret, to send Bob her public key.  Bob now knows
>> >> that whoever sent this key knows the password or got extremely lucky
>> >> on their one and only chance to guess the password.
>> >
>> >
>> >   And this provides absolutely no proof-of-possession. Bob got a public
>> > key and he knows that Alice sent it to him but there is nothing that
>> > Alice does to prove that she holds the corresponding private key.
>> Did you read the very next sentence of my email?
>   Yes. Merely signing your public key does not provide proof of ownership.
> To demonstrate ownership you need to additionally sign something that
> your statement to the authenticated state already established (which is
> PKEX does). It's tricky to do right and you don't seem to understand that
> which demonstrates the kind of dangerous hubris you seem to be accusing me
> of having.

Of course it's tricky.  You need to define what exactly you're trying to
prove and then prove that.  If you want to prove that whoever did the PAKE
knew the private key at the time (or colluded with someone who knew the
private key), then derive a fresh key from the PAKE output and sign that.
But see the next email I'll send on this particular topic.

Your draft doesn't precisely state what security goals it actually tries to
achieve, so it's quite awkward to try to decide what exactly Bob should
believe at the end of the protocol run.

>   So you could perhaps build something that, if done right, did what PKEX
> but uses 3+ different crypto tools each with its own set of assumptions
> you better make sure you operate inside. Or you could just do PKEX.
>   Thank you again for your comment and suggestion.
>   Dan.