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

From: Dan Harkins <[email-masked]>
Date: Mon, 12 Sep 2016 02:19:00 -0700

Hello,

   In the current PAKE requirements draft there is an application
described for which we have no candidate protocols. Namely,

  "In addition to key retrieval from escrow, there is also the variant
   of two parties exchanging public keys using a PAKE in lieu of
   certificates.  In this variant, public keys can be encrypted using a
   password.  Authentication key distribution can be performed because
   each side knows the private key associated with its unencrypted
   public key and can also decrypt the peer's public key.  This
   technique can be used to transform a short, one-time code into a
   long-term public key."

So I have written an I-D that proposes just such a protocol. I
solicit review and criticism.

   regards,

   Dan.

-------- Forwarded Message --------
A new version of I-D, draft-harkins-pkex-00.txt

has been successfully submitted by Dan Harkins and posted to the
IETF repository.

Name:		draft-harkins-pkex
Revision:	00
Title:		PKEX
Document date:	2016-09-12
Group:		Individual Submission
Pages:		9
URL:            https://www.ietf.org/internet-drafts/draft-harkins-pkex-00.txt
Status:         https://datatracker.ietf.org/doc/draft-harkins-pkex/
Htmlized:       https://tools.ietf.org/html/draft-harkins-pkex-00

Abstract:
    This memo describes a password-authenticated protocol to allow two
    devices to exchange "raw" (uncertified) public keys and establish
    trust that the keys belong to their respective identities.

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

The IETF Secretariat

---

From: Andy Lutomirski <[email-masked]>
Date: Mon, 12 Sep 2016 08:20:22 -0700

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.

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.

--Andy

On Sep 12, 2016 2:19 AM, "Dan Harkins" <[email-masked]> wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>
>

---

From: Dan Harkins <[email-masked]>
Date: Mon, 12 Sep 2016 13:19:03 -0700

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.

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

   Dan.

> --Andy
>
>
> On Sep 12, 2016 2:19 AM, "Dan Harkins" <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>
>       Hello,
>
>     URL:https://www.ietf.org/internet-drafts/draft-harkins-pkex-00.txt
>     <https://www.ietf.org/internet-drafts/draft-harkins-pkex-00.txt>
>     Status:https://datatracker.ietf.org/doc/draft-harkins-pkex/
>     <https://datatracker.ietf.org/doc/draft-harkins-pkex/>
>     Htmlized:https://tools.ietf.org/html/draft-harkins-pkex-00
>     <https://tools.ietf.org/html/draft-harkins-pkex-00>
>
>
>     Abstract:
>     until the htmlized version and diff are available attools.ietf.org <http://tools.ietf.org>.
>
>     The IETF Secretariat
>
>     _______________________________________________ Cfrg mailing list
>     [email-masked] <mailto:[email-masked]>
>     <https://www.irtf.org/mailman/listinfo/cfrg> 
>

---

From: Dan Harkins <[email-masked]>
Date: Mon, 12 Sep 2016 13:59:54 -0700

One more thing...

> the PAKE to care that the exchanged keys are anything other than 

   You do not seem to understand the value of the owner of a trusted
public key providing proof-of-possession of the corresponding private key.
Have you ever wondered why CSRs get signed? Think about it. If the protocol
treated a public key the way it would treat the string "Hello World" then it
would be quite useless.

   That said, no one is stopping you from writing the protocol that you
think is necessary. In fact, I'd love to see it.

   Dan.

---

From: Andy Lutomirski <[email-masked]>
Date: Mon, 12 Sep 2016 14:43:58 -0700

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

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

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.

---

From: Dan Harkins <[email-masked]>
Date: Tue, 13 Sep 2016 00:39:03 -0700

> its symbols.  In particular, I'm guessing that (X, x) is Alice's key.

   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.

> point is to establish a long-term key.  So Alice how sends X + F(pw2)

   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?

   Did you spend the whole "half an hour of thinking" to come up with this?

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

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

   Proof-of-possession is an express property of PKEX (see section 2, 
Properties)
that you have not provided in your ad hoc construction. 
Proof-of-possession is
critical to obtain trust that a public key actually belongs to an identity.
If your ad hoc construction does not provide it then your ad hoc
construction does not solve the problem.

   Again, I solicit review and criticism but it would be nice if the 
criticism
was professional in tone and content.

   Dan.

---

From: Andy Lutomirski <[email-masked]>
Date: Tue, 13 Sep 2016 07:59:04 -0700

>>> This appears to be more or less the same protocol described in the
802.11
> 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.

>>> scratch", I mean that a real PAKE should be used, in its intended
form.  The
> Alice does to prove that she holds the corresponding private key.

Did you read the very next sentence of my email?

--Andy

---

From: Dan Harkins <[email-masked]>
Date: Tue, 13 Sep 2016 08:59:33 -0700

On 9/13/16 7:59 AM, Andy Lutomirski wrote:
>
> On Sep 13, 2016 12:39 AM, "Dan Harkins" <[email-masked] 
> 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?
>
> 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 
identity
key. He can also trivially determine A. So he can impersonate Alice in 
TLS/IKEv2
or any other protocol using a trusted "raw" key for authentication. The 
point
of him attacking PKEX to determine an, essentially, one time use 
password is....?

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

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

> 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 own
security critical moving parts. And then you end up with something like 
TLS-pwd
authenticating EST, which is a tad heavyweight and not the kind of PAKE 
usage that
the PAKE requirements draft is referring to; PKEX is.

> 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 binds
your statement to the authenticated state already established (which is what
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.

   So you could perhaps build something that, if done right, did what 
PKEX does
but uses 3+ different crypto tools each with its own set of assumptions that
you better make sure you operate inside. Or you could just do PKEX.

   Thank you again for your comment and suggestion.

   Dan.

---

From: Andy Lutomirski <[email-masked]>
Date: Tue, 13 Sep 2016 09:15:13 -0700

identity
TLS/IKEv2
point
> of him attacking PKEX to determine an, essentially, one time use password
is....?

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
of PKEX
> (active attack only learns whether one guess of the password was right or
wrong)
"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
private
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.
PKEX using
> some other PAKE plus an AEAD scheme plus some PKCS#10 blob but it has its
own
TLS-pwd
usage that
> which demonstrates the kind of dangerous hubris you seem to be accusing me

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
does