Subject: [TLS] The PAKE question and PSK

From: Watson Ladd <[email-masked]>
Date: Tue, 1 Apr 2014 21:28:40 -0700

Dear all,

I'm afraid that several important points and quite a bit of history
has been missing from the recent exchange concerning Dragonfly in TLS.

Dragonfly is a modified SPEKE. SPEKE was introduced in 2001. SPEKE has
a patent that expires in 2016, and a security proof in the ROM under a
DH style assumption and a reasonable ideal/real attack model.
Dragonfly was created by Dan Harkins, and adopted in IEEE 802.11s to
authenticate nodes in a mesh network. It has no security proof despite
efforts to try and find one.

The intended usecase is provisioning of constrained devices. While one
could include a 128 bit key on each device and have users type it in
(as they do for Xbox Live and Windows verification: 25 letters and
numbers from a 32 bit alphabet) it was felt that this was a bit much.
PSK will not work with anything that isn't a key, because offline
attack works beautifully. Nico's concerns about key database
compromise, etc, are ignoring the realities of this setting: the
password is the least valuable thing on the device, and since it was
not entered by the user (as the device has no user interaction
capability) unlikely to be reused.

Dragonfly was presented at IETF 83. AugPAKE was proven secure in 2010.
There is currently a draft for AugPAKE in TLS. Unfortunately AugPAKE
is not specified on ECC groups, but this is easy to fix. (It's also
ugly to shoehorn into TLS, but the draft seems to do it) PAKEs are not
on the agenda because of a rather heated controversy about how
Dragonfly got (seeming) CFRG approval, but there is a good case for
including them. On the web we have more of a problem due to the UI
issues that made client certificates a nonstarter.

Sincerely,
Watson Ladd

---

From: Hannes Tschofenig <[email-masked]>
Date: Wed, 02 Apr 2014 09:29:00 +0200

Hi Watson,

I believe there are several aspects that need to be untangled here:

a) Is there a problem where a strong password-based authentication and
key exchange protocol can help?

b) Since there are various protocol variants available, which one is the
best for the job?

Item (a) is about use cases and clearly the Web is not the use case.
There are use cases documented in
http://tools.ietf.org/html/draft-ietf-tls-pwd-04#section-1.1 but I
personally don't quite buy them.

The constrained device use case is, however, one that I ran into myself
as well. It requires a bit more description since constrained device are
used in various different ways. There are at least three different cases
I have seen:

1) Device talks to the cloud infrastructure. For this case it is not a
problem to use long symmetric keys since the is nothing for the user to
type.

2) Device talks to another device. There are two variants to this:

 2a) Pairing / Imprinting

Here the pairing protocol typically runs a Diffie-Hellman and then you
might have to confirm the initial set-up to avoid MITM attacks (via an
out-of-band channel, such as a human entering something).

There are obviously many ways to do this pairing procedures and I am
sure you have used many of them already yourself.

Ekr provided a good overview for a workshop:
http://www.lix.polytechnique.fr/hipercom/SmartObjectSecurity/papers/EricRescorla.pdf

 2b) Key printed on the device itself

I believe that this is the case you are talking about where you want to
avoid having users enter too many numbers. Today, user's are often only
required to scan a QR code instead of entering something but maybe there
is something to standardize here.

Regarding item (b) about the protocol choice. Given the use cases
previously described I doubt that the "database leaking secrets" is a
bit concern here in these environments. The database in most cases
contains a single key (or a small number of them).

A few years ago Yaron, Glen, Scott and myself co-authored EAP-EKE (RFC
6124) and we picked EKE because the publications reached their 20 year
anniversary.

Just something to think about.

Ciao
Hannes

On 04/02/2014 06:28 AM, Watson Ladd wrote:
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: Nico Williams <[email-masked]>
Date: Wed, 2 Apr 2014 11:12:11 -0500

> capability) unlikely to be reused.

Ah, thanks for clarifying the context.  I agree that in this context a
ZKPP, unaugmented, is just fine.  If I had to build one today I'd use
EKE with a DJB cuve and Elligator: no patents apply and none are
likely to apply (EKE's patent is expired, and it seems exceedingly
unlikely that any patent covers the rest).

Nico
--

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 2 Apr 2014 09:38:59 -0700 (PDT)

Hi Hannes,

> problem to use long symmetric keys since the is nothing for the user to

  From what authenticated source does this long symmetric key come?

> out-of-band channel, such as a human entering something).

  The "something" the user enters is a simple, low-entropy, easy-to-enter
key. That key authenticates a PAKE exchange.

> http://www.lix.polytechnique.fr/hipercom/SmartObjectSecurity/papers/EricRescorla.pdf

  And the use of PAKEs is mentioned there. The downside to PAKEs, according
to Eric, is use of public key cryptography with a constrained device that is
assumed to have limited CPU power. And that's why ECC support in a PAKE
is so crucial.

> is something to standardize here.

  Putting a symmetric key in a QR code is a bad idea. Anybody who
sees the QR code can determine the secret. As Eric said in the paper
you referred to above, "The primary concern with a secret value system
is that the value must be kept secret or an attacker can impersonate the
base station to the device and vice versa." Indeed.

  Putting a public key in a QR code is a much better idea (and, again,
ECC support is crucial because the x-coordinate of a point on a 256-bit
curve produces a usable QR code while a 4096-bit RSA key does not-- too
big, too dense, hard-to-impossible to scan). For many devices, though, this
only provides one way authentication (not mutual) because the device that
scanned the QR code knows definitely it is talking to the device whose QR
code was scanned, but the device with the QR code has no idea who it is
communicating with. Using a short, easy-to-enter key with a PAKE
provides good mutual authentication.

  Also not every constrained device has a camera interface to scan QR
codes with, while many of them do have some limited UI from which
the user can enter a short key.

> contains a single key (or a small number of them).

  Yes, that is correct. A large password database is not envisioned by
this use case. In fact, as The whole benefit of an augmented PAKE--
a protected password database-- is not applicable to this use case.

> 6124) and we picked EKE because the publications reached their 20 year

  I remember it well. I wrote EAP-pwd (dragonfly) and Yaron followed
with EAP-EKE, I proposed a dragonfly exchange in IKE and Yaron followed
with an EKE exchange (which was later abandoned).

  One of the problems with EKE is that using it with ECC opens the
exchange up to a partitioning attack.

  regards,

  Dan.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 2 Apr 2014 09:45:52 -0700

>   From what authenticated source does this long symmetric key come?

The manufacturer.
> exchange up to a partitioning attack.

Not if you use a uniform representation like Elligator.

---

From: Nico Williams <[email-masked]>
Date: Wed, 2 Apr 2014 11:46:25 -0500

> exchange up to a partitioning attack.

Very much so.  For example, EKE with curve25519 allows eavesdroppers
to eliminate 7/8ths of possible passwords for each exchange observed
(that's a different 7/8ths of possible passwords in each exchange).
After a few exchanges the attacker can recover the password with very
high confidence.

For some ECC curves the solution is Elligator.  This is quite
convenient because EKE w/ ECC and Elligator is to a very high
likelihood not subject to any patents whatsoever.

Nico
--

---

From: Hannes Tschofenig <[email-masked]>
Date: Wed, 02 Apr 2014 18:38:42 +0200

Hi Dan,

comments inline.

>   From what authenticated source does this long symmetric key come?

This secret is pre-provisioned by the manufacturer of the device.
If you buy any IoT device today this is most likely the model they are
using.

> key. That key authenticates a PAKE exchange.

Nope, this is not necessarily PAKE and the if you, fo rexample, use
Bluetooth it is not PAKE.

> assumed to have limited CPU power. And that's why ECC support in a PAKE

+ patents on ECC and patents on PAKE to worry about...

> sees the QR code can determine the secret.

This is the model that many embedded devices use. Look at your embedded
router, for example. I doubt that someone breaks into your home and then
has nothing better to do than to read the secret from your home router...

> As Eric said in the paper

Understand that argument but nothing of it can be found in your draft.

> a protected password database-- is not applicable to this use case.

Yes.

> exchange up to a partitioning attack.
Given that this initial exchange happens very infrequently additional
delay with RSA does not matter that much (+ you don't have to worry
about the IPRs).

Ciao
Hannes

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 2 Apr 2014 10:18:27 -0700 (PDT)

Hi Hannes,

> If you buy any IoT device today this is most likely the model they are

  It's the symmetric equivalent of a manufacturing certificate. This has
its place but that place is not here.

> Bluetooth it is not PAKE.

  Bluetooth is not secure. What I am proposing is to use a secure PAKE,
not something insecure.

> + patents on ECC and patents on PAKE to worry about...

  FUD. There are no patents to worry about with TLS-pwd.

> has nothing better to do than to read the secret from your home router...

  They wouldn't need to since the protocol that uses that symmetric key
on my home router is horribly broken.

  You keep bringing up broken uses of symmetric keys (bluetooth, WPS) as
alternatives to doing it right. I'm having a hard time understanding what is
motivating you here.

> Understand that argument but nothing of it can be found in your draft.

  I didn't think an expansive explanation of use cases was appropriate for
a draft that defines a protocol. I can provide a bit more introductory text
as well as an "applicability statement" if it will help.

  (I am currently rethinking my opinions on use case documents since
people really seem to not understand the motivation for TLS-pwd. I have
done a very poor job on that front).

> delay with RSA does not matter that much (+ you don't have to worry

  EKE doesn't do RSA. And, as Nico pointed out, observing a single exchange
can eliminate a large majority of the potential passwords. Even an infrequent
use can give an adversary a high probability of successfully determining
the secret.

  Again, the IPR issue is FUD.

  regards,

  Dan.

---

From: Nico Williams <[email-masked]>
Date: Wed, 2 Apr 2014 12:26:31 -0500

> use can give an adversary a high probability of successfully determining

But if you use Elligator then that problem goes away.  That's the key point.

---

From: Nico Williams <[email-masked]>
Date: Wed, 2 Apr 2014 12:35:29 -0500

With Elligator the eavesdropper goes from being able to eliminate
7/8ths of possible passwords with each exchange to being able to
eliminate only 19/2^256 possible passwords (in the curve25519 case;
the exact number varies by curve for which Elligator is available).
Therefore EKE with ECC + Elligator is safe.

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 2 Apr 2014 10:55:18 -0700 (PDT)

> But if you use Elligator then that problem goes away.  That's the key

  Yes, as I mentioned back in December on this list, EKE with Elligator
would make a very good alternative to TLS-pwd. And if there was a mature
draft ready for publication that specified such a scheme it would be worth
considering. But there isn't. And we're 2+ years away from having such a
thing. Probably more since we have not identified a stuckee willing to
edit it.

  As Cullen mentioned, the IETF is a volunteer organization and telling
people that they should go write a draft specifying your alternative to
their draft is not really productive.

  I have received and resolved comments on the draft dealing with
protection of the username from passive observers and on mitigating
side channel attacks. There is no technical problem with TLS-pwd and it
solves real problems right now. I see no reason why it should not ease
away from the curb (and out of its parked position).

  regards,

  Dan.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 2 Apr 2014 11:15:42 -0700

> away from the curb (and out of its parked position).

What about the complete absence of any positive security analysis? You've
known this was going to be an issue since you invented Dragonfly. I feel
completely uncompelled to be 'productive' at the expense of security.

Quit fussing and whining about how hard it is to write drafts. You could
have started with something provably secure and avoided wasting your
efforts.

Failing that, make AugPAKE work on ECC by grabbing the draft and fixing it,
then submit that instead.

Sincerely,
Watson Ladd

---

From: Nico Williams <[email-masked]>
Date: Wed, 2 Apr 2014 13:27:56 -0500

On Wed, Apr 2, 2014 at 1:15 PM, Watson Ladd <[email-masked]> wrote:

To be fair it's not just about I-Ds.  I've written quite a few myself
-- it's easy.   It's also about running code.

Nico
--

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 2 Apr 2014 11:38:26 -0700 (PDT)

> -- it's easy.   It's also about running code.

  Check out Appendix A of draft-ietf-tls-pwd-04. Do you know of
any running code that implements TLS ciphersuites that perform EKE
with Elligator curves?

  Dan.

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 2 Apr 2014 11:52:26 -0700 (PDT)

> completely uncompelled to be 'productive' at the expense of security.

  You're overstating things a bit. There is no formal proof but that doesn't
mean there is a complete absence of any positive security analysis.

  Being uncompelled and upset at the lack of a formal proof are not
technical comments, they are just whines.

> have started with something provably secure and avoided wasting your

  "Quit fussing and whining" works both ways. You've been fussing and
whining since you joined this list and it might be a good time to quit.

  To be clear, I have not said that it is hard to write a draft, I said it
is time
consuming. And I already have a draft (and running code) that solves the
problems I have identified. I have no reason to volunteer to write another
draft to do something that you want and I don't think you can afford my
consulting rate.

> Failing that, make AugPAKE work on ECC by grabbing the draft and fixing
> it, then submit that instead.

  You should stop telling people to do things you are unwilling to do
yourself.

  Dan.

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Wed, 2 Apr 2014 15:00:20 -0400

Could you please remind me - is Elligator limited to a certain group/class
of curves, or is it usable with any, e.g.,  E(Fp)?

Thanks!

---

From: Nico Williams <[email-masked]>
Date: Wed, 2 Apr 2014 14:37:20 -0500

> any running code that implements TLS ciphersuites that perform EKE

And in constant time.  Still, we're inching closer to having all the
pieces.  I did find one liberally-licensed C implementation of
Elligator just now, and an unlicensed implementation in Go.  We may
soon well have enough Elligator implementations to permit interop
testing and widespread implementation of EKE w/ Elligator.  And, of
course, one can always write one's own implementation.

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Wed, 2 Apr 2014 14:38:17 -0500

> of curves, or is it usable with any, e.g.,  E(Fp)?

http://elligator.cr.yp.to/elligator-20130828.pdf

---

From: SeongHan Shin <[email-masked]>
Date: Wed, 9 Apr 2014 13:07:15 +0900

Dear all,

>  You should stop telling people to do things you are unwilling to do

In the next version, I would include ECC version of AugPAKE.

Best regards,
Shin

-- 
------------------------------------------------------------------
SeongHan Shin
Research Institute for Secure Systems (RISEC),
National Institute of Advanced Industrial Science and Technology (AIST),
Central 2, 1-1-1, Umezono, Tsukuba City, Ibaraki 305-8568 Japan
Tel : +81-29-861-2670/5284
Fax : +81-29-861-5285
E-mail : [email-masked]
------------------------------------------------------------------