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

Andy Lutomirski <luto@amacapital.net> Tue, 13 September 2016 15:32 UTC

Return-Path: <luto@amacapital.net>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 0332B12B4D4 for <cfrg@ietfa.amsl.com>; Tue, 13 Sep 2016 08:32:07 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.6
X-Spam-Level:
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: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=amacapital-net.20150623.gappssmtp.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id T7QMm6sz5baz for <cfrg@ietfa.amsl.com>; Tue, 13 Sep 2016 08:32:01 -0700 (PDT)
Received: from mail-vk0-x230.google.com (mail-vk0-x230.google.com [IPv6:2607:f8b0:400c:c05::230]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 9208012B4ED for <cfrg@irtf.org>; Tue, 13 Sep 2016 07:59:06 -0700 (PDT)
Received: by mail-vk0-x230.google.com with SMTP id m62so128064132vkd.3 for <cfrg@irtf.org>; Tue, 13 Sep 2016 07:59:06 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amacapital-net.20150623.gappssmtp.com; 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; d=1e100.net; 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 10.31.165.136 with SMTP id o130mr1175080vke.9.1473778745577; Tue, 13 Sep 2016 07:59:05 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.103.51.23 with HTTP; Tue, 13 Sep 2016 07:59:04 -0700 (PDT)
Received: by 10.103.51.23 with HTTP; Tue, 13 Sep 2016 07:59:04 -0700 (PDT)
In-Reply-To: <e8864929-45f2-0767-8ecc-dc7c2da8d066@lounge.org>
References: <147367129321.14577.4302361405783294005.idtracker@ietfa.amsl.com> <3e9341e6-d826-a028-df40-a4e0dff98635@lounge.org> <CALCETrXo3AQNJGzvVQ-O3YtGhPOu45Y6S13u3WUJO8PjkU6EJQ@mail.gmail.com> <e0fe2661-7012-ca38-de81-5941d64a0ec2@lounge.org> <CALCETrUoQKN3Pw+aNej5sXaTY_d-tbbA4Qjx32KhL0kPa9XFfQ@mail.gmail.com> <e8864929-45f2-0767-8ecc-dc7c2da8d066@lounge.org>
From: Andy Lutomirski <luto@amacapital.net>
Date: Tue, 13 Sep 2016 07:59:04 -0700
Message-ID: <CALCETrXFD1gDVJ7GVX9cxhpiQty2C4WpzHLFX=7QesQMn-mOWw@mail.gmail.com>
To: Dan Harkins <dharkins@lounge.org>
Content-Type: multipart/alternative; boundary=001a11416cc49baaa2053c64dacb
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/6p8TvS-2VJA9HNw4wzf2d1Z3HzY>
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] Fwd: New Version Notification for draft-harkins-pkex-00.txt
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 13 Sep 2016 15:32:07 -0000

On Sep 13, 2016 12:39 AM, "Dan Harkins" <dharkins@lounge.org> wrote:
>
>
>
> On 9/12/16 2:43 PM, Andy Lutomirski wrote:
>>
>> On Mon, Sep 12, 2016 at 1:19 PM, Dan Harkins <dharkins@lounge.org> 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
802.11
>>> DPP drafts.  It was terminally insecure then and it appears to be just
as
>>> terminally insecure now.  If it's really necessary for some reason, I
can
>>> 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?

--Andy