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

[Andy Lutomirski <[e-mail]>]

On Mon, Sep 12, 2016 at 1:19 PM, Dan Harkins <[e-mail]> 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:

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.

Now the attacker computes Z = (F(pw1) - F(pw2)) * Pi starts
brute-forcing password pairs (pw_guess1, pw2_guess) and, for each
pair, checks whether they recover the value Z.  If the passwords are
short, then this will run quickly and will, with high probability,
recover the actual values pw1 and pw2.



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

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.

Optionally, if Bob wants Alice to prove possession of the
corresponding private key, Alice proves possession.  If the key is a
*signing* key, then she could sign her message from step 3, being
careful to avoid cross-protocol attacks.  If it's a Curve25519 ECDH
secret, she could do a Curve25519 exchange using it, for example.


But IMO even that protocol is a bit silly, because I think the use
case is contrived.  Suppose that Alice has a display and Bob has a
keyboard.  Here's a stab at an even better protocol:

Step 1: Alice and Bob generate random strings Na and Nb.  Alice sends
Bob a commitment to Na (e.g. H(R || Na) for random R).  Bob sends
Alice Nb.  Once Bob has sent Nb, Bob MUST NOT retry the protocol until
he has actually prompted the user for the password in step 3.

Step 2: Alice calculates a password P = F(H(Na || Nb)) where H is a
cryptographic hash and F is some public function that derives a short
password.

Step 3: Alice displays P.  The user types P into Bob's keyboard.

Step 4: Alice and Bob run a balanced PAKE using P as the password.
Both parties MUST NOT attempt the PAKE more than once without starting
over from scratch.  Future messages are sent using authenticated
encryption with replay protection, etc, keyed by the output of the
PAKE.

Step 5: Alice sends Bob the "reveal" part of her Na commitment.  (If
using the variant above, Alice would send R.)  Bob checks it and
re-derives P and checks that it's the correct value.

Now Alice and Bob proceed as in the earlier variant.

It has a really nice security property: even a lazy implementation on
Alice or Bob's part won't compromise the protocol.  For example, we
won't see Bluetooth-like pairing keys of "0000".  Alice cannot control
control P at all.  Bob could be lazy and skip the verification in step
4, but he doesn't gain any usability improvement by doing so, and a
conformance test could easily check this by requiring that Bob's
implementation fail if Alice (a) uses the wrong password or (b) sends
an invalid "reveal" message.

Note that nothing about this is specific to using it to exchange
long-term keys.  It could be used to establish a long-term pairwise
symmetric key or even just to transfer a single file.

This probably deserves a security proof and a search for a similar
protocol that doesn't need a PAKE.