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

Andy Lutomirski <> Tue, 13 September 2016 15:32 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 0332B12B4D4 for <>; Tue, 13 Sep 2016 08:32:07 -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 T7QMm6sz5baz for <>; Tue, 13 Sep 2016 08:32:01 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:400c:c05::230]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 9208012B4ED for <>; Tue, 13 Sep 2016 07:59:06 -0700 (PDT)
Received: by with SMTP id m62so128064132vkd.3 for <>; Tue, 13 Sep 2016 07:59:06 -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=A9c9ENUGFrlHdpwC/nV84P2ZiuVsC0S8w/+d5LWc5KY=; b=afkySP9SDmyFFF/kqD6XBBHowkLAahA43zRFo9VxbF/jzrHg70TA35uUx1AdQU1MTL sB1hrdIK60G7rHBJDg7oI+5cF/wUfHvKKvdBcRZogSKTjKF8YRlrUDX+pXno9Gc/TnSW WQ3nEhmQGbcp9fOAbe0dJ/O0KehjXAmrXj5+AjMa3dslo6MS1DeKwJSR1+pOLkMTYWAT x+OXw1nm8cpxDFKxjPHS/EN5ADs8r+d1vtYDOILL1jepSmaRAvLrAkA7M242oCLN5ulT 8uD3y3XU2O0Ben9TNLMQQYjlaAc2feCdNYWcgsOnN0GWMCA2D6kY+vxqhE/tV8Ja9ygC I0JQ==
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=A9c9ENUGFrlHdpwC/nV84P2ZiuVsC0S8w/+d5LWc5KY=; b=Z7rLu6UXXnA4sBz0h+N0Tc/+gtbJkeHCNpKwS4kdZJue0jPGw50XueSGtqdXkTvgy3 G6hMc7bMzRBdqwAv6kCLEPPQaCuaTINWJfPqr7090gJYw5UJqym0h2qxfOqJqNbbyWj4 V5pneby9ZFKQihk0q0LLkiYNJzfeC3nNE63NEvneF9LvEMRDvRJYHrMZp6rMdf/pQMVZ CPjDvrLQ5cTz3NrfCQkU+NUYsTRZ038OAnO4OI+jaGY/VVFsF0WM1ufV2K4CJGFVyDWb QKH9TvAnc0wuuCdkNTItHrq8n4NiDrC+GEmZa1LfaBvzhtfPnjmxMxaQwKbavQsxtHmt 1JHA==
X-Gm-Message-State: AE9vXwNLxgsK3wz+6YkX7s9AxrvPAZNLwknUespnm21fDshvxuKeeKJf+dahxAx9Qp8vC3hbvYmThTCG0O3qeemn
X-Received: by with SMTP id o130mr1175080vke.9.1473778745577; Tue, 13 Sep 2016 07:59:05 -0700 (PDT)
MIME-Version: 1.0
Received: by with HTTP; Tue, 13 Sep 2016 07:59:04 -0700 (PDT)
Received: by with HTTP; Tue, 13 Sep 2016 07:59:04 -0700 (PDT)
In-Reply-To: <>
References: <> <> <> <> <> <>
From: Andy Lutomirski <>
Date: Tue, 13 Sep 2016 07:59:04 -0700
Message-ID: <>
To: Dan Harkins <>
Content-Type: multipart/alternative; boundary=001a11416cc49baaa2053c64dacb
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 15:32:07 -0000

On Sep 13, 2016 12:39 AM, "Dan Harkins" <> wrote:
> On 9/12/16 2:43 PM, Andy Lutomirski wrote:
>> On Mon, Sep 12, 2016 at 1:19 PM, Dan Harkins <> wrote:
>>>    Hi Andy,
>>> On 9/12/16 8:20 AM, Andy Lutomirski wrote:
>>> This appears to be more or less the same protocol described in the
>>> DPP drafts.  It was terminally insecure then and it appears to be just
>>> terminally insecure now.  If it's really necessary for some reason, I
>>> reiterate the multiple ways I found to break it after half an hour of
>>> thinking.
>>> Yes please do show the multiple ways to break this.
>> It's hard in this particular case because the draft does not define
>> its symbols.  In particular, I'm guessing that (X, x) is Alice's key.
>> So here's one break:
>   The draft clearly says "Alice's public key she wants to share with Bob
> is A and her private key is a, while Bob's public key he wants to share
> with Alice is B and his private key is b." x/X is Alice's ephemeral share.
>> 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.

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.

>>> This protocol needs to be replaced, starting from scratch.  By "from
>>> scratch", I mean that a real PAKE should be used, in its intended
form.  The
>>> result will not even need to mention "groups", because there is no
reason at
>>> all for the tiny bit of protocol layered above the PAKE to care that the
>>> exchanged keys are anything other than opaque strings.
>>>    I am honestly soliciting constructive comments. If you have some
>>> please provide them.
>> Sure.
>> 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?