Subject: [TLS] draft on new TLS key exchange

From: "Dan Harkins" <[email-masked]>
Date: Tue, 4 Oct 2011 23:12:15 -0700 (PDT)

Hi,

  I just uploaded a -00 draft that defines a new key exchange
for TLS that does not require certificates-- authentication using
a simple password only. It can be found at:

         http://tools.ietf.org/html/draft-harkins-tls-pwd-00

  Please take a look. The authors solicit comments.

  regards,

  Dan.

---

From: Geoffrey Keating <[email-masked]>
Date: 05 Oct 2011 14:09:19 -0700

>   Please take a look. The authors solicit comments.

It would be helpful to have a comparison between this proposal and
RFC5054, since both protocols appear to have the same aim ("secure
authentication using only a simple, low-entropy, password").

Some features of RFC5054 I noticed that could be used to improve this
draft are:

- RFC5054 requires that the server store only the 'verifier', while
  this protocol appears to require storing the plaintext password.
  There doesn't seem to be any discussion on the risks of storing the
  plaintext password or any mitigations (for example, using a salted
  hash of the password instead of the password directly).

- RFC5054 already specifies an extension for the user name.  I would
  suggest using the same extension for this protocol rather than
  creating a new one.

- RFC5054 has test vectors, this draft doesn't.

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 5 Oct 2011 16:07:05 -0700 (PDT)

Hello,

> authentication using only a simple, low-entropy, password").

  TLS is rife with drafts and RFCs that have the same aim but go about
it differently.

>   hash of the password instead of the password directly).

  Yes, I got another comment to add something to the security
considerations regarding compromise of the client and server. This
draft does not propose any protection against server compromise
the way RFC 5054 does. On the other hand, with this scheme one is not
required to fix a particular domain parameter set to a user at password
provisioning time. This allows for the choice of domain parameter set
to be based on the particular ciphersuite the server is proposing
to use (and removes a security critical decision from someone-- the
person provisioning the password on the server-- who might not have
the competence to make that decision).

  We could add some protection against server compromise by salting the
password when it is provisioned and sending the salt in the
ServerKeyExchange. The drawback to this is that the salting technique
has to be determined at provisioning time, but that's probably not that
big of a deal as the technique has no bearing on the security of the
underlying key exchange.

  Thanks for the suggestion!

>   suggest using the same extension for this protocol rather than

  It's named "srp" though which makes it less desirable. We'll note your
suggestion but unless there is strong desire by the WG to change this
we'd like to keep it as is. There's 65k extensions available so exhaustion
of this resource is unlikely.

> - RFC5054 has test vectors, this draft doesn't.

  Another good suggestion. We'll add some.

  thanks,

  Dan.

---

From: Jean-Marc Desperrier <[email-masked]>
Date: Thu, 06 Oct 2011 02:39:09 +0200

On 06/10/2011 01:07, Dan Harkins wrote:
> it differently
Even if there might indeed be quite a few like that in the TLS case, 
it's still against IETF policy.

There should be at least some specific advantage to your approach over 
the other one (or enough existing usage to justify documenting it 
through an experimental RFC), which is far from being proved for now.

SRP has the advantage over the other PAKE to be covered by a defensive 
patent with a royalty free license, which makes it safer to use.

If needed, it's also actually very easy to use SRP in symmetric mode, 
regenerating the verifier from the password on the fly.
Nothing in RFC5054 says how the client sends the verifier to the server 
initially. If you really want to send the password instead, you just can.

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 06 Oct 2011 13:40:29 +1300

"Dan Harkins" <[email-masked]> writes:

>I just uploaded a -00 draft that defines a new key exchange for TLS that does
>not require certificates-- authentication using a simple password only. It can
>be found at:
>

Oooh, oooh, I have one!  It's:

  "What does this give us that TLS-PSK and TLS-SRP don't already do?".

Peter.

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 5 Oct 2011 18:30:27 -0700 (PDT)

>   "What does this give us that TLS-PSK and TLS-SRP don't already do?".

  TLS-PSK: resistance to dictionary attack
  TLS-SRP: elliptic curve support, divorcing domain parameter set from
     the password

 I'm curious why you are not asking the authors of the SEED, Camellia,
and Clefia drafts what those drafts give us that the AES ciphersuites
don't already do.

  Dan.

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 06 Oct 2011 14:49:45 +1300

>  TLS-SRP: elliptic curve support, divorcing domain parameter set from

So it's a proposal that adds a few obscure geeky features to two existing
mechanisms that vendors have already decided not to adopt (wrongly, in my
opinion, but that doesn't change the lack of adoption).  Why would they
suddenly rush to support this one if they've ignored the other two (and a
string of earlier drafts along the same lines)?

(As a more general comment, this draft should be, if anything, an Experimental
and not a Standards-Track, given its context).

>I'm curious why you are not asking the authors of the SEED, Camellia, and
>Clefia drafts what those drafts give us that the AES ciphersuites don't
>already do.

Those three are fashion-statement RFCs whose reasons for existence have little
(if anything) to do with security.  Does that mean this draft is also a
fashion statement?

Peter.

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 5 Oct 2011 18:52:50 -0700 (PDT)

> it's still against IETF policy.

  I asked Peter and I'll ask you: why have you not brought up this
with Camellia, SEED, and Clefia?

  And I'd be really interested in seeing the IETF policy statement
that mandates one and only one way of doing one particular thing.

> through an experimental RFC), which is far from being proved for now.

  I don't think such language is appropriate for an I-D. But in an
email exchange I'll tell you that this scheme allows the cryptographic
strength of the domain parameter set to be matched with ciphersuites of
commensurate strength. This also allows for the use of elliptic curves.
It doesn't hard-code a particular hash algorithm (that the IETF is
planning on moving away from) so it's more "crypto agile".

> patent with a royalty free license, which makes it safer to use.

  This key exchange is not patented.

> initially. If you really want to send the password instead, you just can.

  You can change the way RFC 5054 works but then it's not SRP anymore and
then people will start telling you that it's "against IETF policy".

  Furthermore, the client doesn't send the verifier to the server in SRP
so I'm not really sure what you're talking about.

  Dan.

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 5 Oct 2011 19:17:12 -0700 (PDT)

> string of earlier drafts along the same lines)?

  This came out of some discussions around security for "smart energy"
applications whose specifications do much hand waving and assume that
certificates magically appear on the most unlikely of places and are
all used properly. They also make it highly problematic for any
off-the-shelf device that is supposed to be integrated into a network
of other "smart energy" devices from working properly. They assume an
unrealistic level of security clue on the people installing and
provisioning the device. Having Joe Random enter a simple password on
the UI of his thermostat, for instance, is much more believable.

  Also, this is the same key exchange used by 802.11 mesh networks to
secure traffic going across the mesh, as well as traffic to create and
maintain the mesh (e.g. routing). Using the same key exchange to secure a
management interface (i.e. a TLS-protected connection to the GUI or a
UI) of a mesh networking device would be useful-- conservation of crypto
algorithms, it's straightforward to set a consistent security level
across interfaces, etc.

  As a general purpose ciphersuite, no I don't imagine it will get
much more widespread use than SRP though. But I don't think that's
necessarily a reason to oppose it.

> and not a Standards-Track, given its context).

  I highly doubt that this hopeful stab at a track would be supported
by the ADs. But I can hope.

> (if anything) to do with security.  Does that mean this draft is also a

  No, it's not a fashion statement. I just don't like following a whole
bunch of other people only to have the door slammed in my face. It
does not jibe with my notion of fairness.

  Dan.

---

From: Marsh Ray <[email-masked]>
Date: Thu, 06 Oct 2011 00:47:27 -0500

On 10/05/2011 08:49 PM, Peter Gutmann wrote:
> "Dan Harkins"<[email-masked]>  writes:
>
> mechanisms

Almost everything in crypto-land starts out obscure and geeky to even 
your average geek.

> that vendors have already decided not to adopt (wrongly, in my

That's not a particularly strong argument against this one though.

You never know when vendors will have to change their minds, often in a 
hurry. When they do, it's better if there's something in place ahead of 
time IMHO.

>> Clefia drafts what those drafts give us that the AES ciphersuites don't

I think a lot of people have been asking that. Probably more would ask 
it out loud on the list if they didn't feel it would be unnecessarily 
redundant and confrontational.

> (if anything) to do with security.

They're also less new protocol and more of a code point assignment for 
an existing spec. Perhaps in some cases there will even be a little 
interoperating usage to justify it.

The above notwithstanding, I have to say my initial reaction is also a 
bit skeptical of the utility of this thing.

- Marsh

---

From: Yoav Nir <[email-masked]>
Date: Thu, 6 Oct 2011 08:47:31 +0200

> the UI of his thermostat, for instance, is much more believable.

Joe Random will throw out a thermostat that regularly requires entering a password. The use case is more likely entering the password once at installation, and then that password is one chosen by the utility. For the last 17 years, Microsoft has trained us all to enter 30-digit numbers. Once. In that use case the passwords can be (relatively) high entropy, and then TLS-PSK is acceptable. I am far more interested in using a password method for TLS for authenticating to web sites.

>>> Clefia drafts what those drafts give us that the AES ciphersuites don't

Oh, they get a lot of grief every time they come up with "XXXX and its use in IPSec/TLS/SSH". They always get that question, and they say something about it being a standard of some national government. Sometimes the documents end up as proposed standards (SEED, Camelia), and other times they end up as Informational (GOST).

Protocol changes get a lot more scrutiny than algorithms, probably because many more of us think we are qualified to have informed opinions about protocols than about algorithms. And protocol changes are far less likely to be published. 

> does not jibe with my notion of fairness.

Peter and I have been trying to push draft-nir-tls-eap for over 4 years now, and the TLS WG is not biting. You are following a bunch of people who have already had the door slammed in their faces.

Yoav

---

From: Marsh Ray <[email-masked]>
Date: Thu, 06 Oct 2011 01:58:32 -0500

http://tools.ietf.org/html/draft-harkins-tls-pwd-00 :
> 4.  Specification of the TLS-PWD Handshake
>
>    The authenticated key exchange is accomplished by each side deriving
>    a password-based element, PE, in the chosen group, making a
>    "committment" to a single guess of the password using PE, and
>    generating the Premaster Secret.  The ability of each side to produce
>    a valid finished message authenticates itself to the other side.

Here are my comments. Some of them probably apply to other TLS 
password-only schemes too.

Comment 1:

Are you familiar with the studies showing that the great majority of 
users re-use passwords across sites and a large percentage have same 
password everywhere?

http://www.pcworld.com/article/188763/too_many_people_reuse_logins_study_finds.html
http://nakedsecurity.sophos.com/2009/03/10/password-website/

This one finds that the average password is used at 6 different sites:
http://research.microsoft.com/apps/pubs/?id=74164

I don't see anything in this protocol that allows the client endpoint to 
actually authenticate the server. Can the client know if he's 
authenticating with the legitimate server?

If not, perhaps it's OK as long as either the handshake fails or the bad 
guy is reduced to the role of a dumb router between the legit client and 
server.

Comment 2:

But the server DNS name and port do not appear to be bound into the 
authentication. Couldn't the bad guy take a connection destined for one 
web site/service and feed it to another?

Comment 3:

The standard of practice for actual "secure" web sites (e.g. PCI 
compliance if you want to handle credit cards) forbids storing plaintext 
passwords on the server side. Any web app developer who was not using at 
least salted hashes today would be ridiculed as incompetent (e.g., 
Sony). The industry seems to be recognizing the importance of imposing a 
work factor (PBKDF2, bcrypt, scrypt) to resist dictionary attacks when 
the authentication database gets compromised, say, by a typical SQL 
injection.

Is there any way to impose a work factor onto the attacker's guesses?

Who do you envision will deploy a protocol that requires the storage of 
plaintext passwords?

Conceivably there could be special-purpose systems that could generate 
handle these passwords securely, but couldn't they just as easily manage 
a private cert infrastructure?

Comment 4:

The hunting and pecking loops for both the ECC and FFC password elements 
look like a timing oracle to me. They seem to require a large 
exponentiation or sqrt on every iteration and the number of iterations 
is data-dependent. If I'm not mistaken, every input to the loop except 
the password itself is transmitted in cleartext during the handshake.

Couldn't an attacker observe the timings of a sufficient number of 
failed handshakes to enable an offline brute force attack on the 
low-entropy password?

- Marsh

---

From: "Dan Harkins" <[email-masked]>
Date: Thu, 6 Oct 2011 09:38:58 -0700 (PDT)

Hello,

> guy is reduced to the role of a dumb router between the legit client and

  The client definitely authenticates the server. They both perform the
same calculations to arrive at the same premaster secret. If either side
has the wrong password, the secret group element will be different and
they'll be doing their calculations with a different generator and
that won't work.

> web site/service and feed it to another?

  Only if that other website had provisioned the same username/password.

> Is there any way to impose a work factor onto the attacker's guesses?

  As I mentioned in a previous email it's possible to salt the password
at provisioning time and have the server send the salt to the client in
the ServerKeyExchange. I will do that in -01.

> Who do you envision will deploy a protocol that requires the storage of

  That sounds like a general, non-TLS-specific, question so I'll answer
it generally: when either side can initiate to the other, or in a true
peer-to-peer situation where both sides could theoretically initiate
simultaneously. But that's not the case for TLS where there are strict
client and server roles. And, as I mentioned, I'll add some salt to the
stored password.

> failed handshakes to enable an offline brute force attack on the

  This is a very good point. I think the attacker would have to observe
successful handshakes though. It's the number of times through the loop
until the PE is determined that the attacker wants to know and a failed
guess will not provide any useful information.

  And I don't think this attack enables an offline dictionary attack.
I think that it will allow the attacker to exclude large chunks of the
password pool with each observed successful exchange until what's left
is manageable (or until there's just 1 entry left in the pool).

  But I'm not sure how concerned I am about this. After finding PE
there will be a modular exponentiation or point multiply using this
random element as the generator. That's a random generator and a random
scalar and the timing variablities on that will make it hard to isolate
the timing dependencies of the hunting-and-pecking loop. Especially
since it's a random PE used for each run of the protocol. Combine that
with the system knowledge and control required to glean timing information
out of an observed run of the protocol and I'm not sure how practical
this would be.

  Thanks for your comments. Regards,

  Dan.

---

From: Marsh Ray <[email-masked]>
Date: Thu, 06 Oct 2011 12:59:50 -0500

> they'll be doing their calculations with a different generator and

But that's not exactly the same as the client authenticating the server. 
That's the client authenticating that "the server endpoint knows the 
password for the username I supplied", the server name and port are not 
bound into the authentication anywhere. There's an implied assumption 
that only the intended server would know the password, but this 
assumption is not reliable in practice. IMHO this does not constitute 
strong authentication of the server to the client.

>    Only if that other website had provisioned the same username/password.

This is a common case and the security properties differ dramatically in 
this regard from most existing uses of TLS. So it probably should be 
discussed in the security considerations section.

> the ServerKeyExchange. I will do that in -01.

I think people will be looking for bcrypt, scrypt, or PBKDF2 with some 
SHA > 1. They will want to choose the work factor.

> client and server roles.

http://tools.ietf.org/html/rfc2246
>    client
>        The application entity that initiates a TLS connection to a
>        server. This may or may not imply that the client initiated the
>        underlying transport connection. The primary operational
>        difference between the server and client is that the server is
>        generally authenticated, while the client is only optionally
>        authenticated.

Those roles are not actually so strict, and this proposal seems to sort 
of reverse the primary direction of authentication compared to existing 
uses of TLS.

Could be useful, but deserves to be stated explicitly.

> guess will not provide any useful information.

Won't at least one of the attacked endpoints still be working from the 
correct password? Won't his timing be enough?

> is manageable (or until there's just 1 entry left in the pool).

That probably would be more sophisticated, but he could probably also 
just run through the 10000 most common passwords and see which ones fit 
the observed timings.

A busy server is going to have orders of magnitude more TLS handshakes 
than users over any reasonable period of time.

> since it's a random PE used for each run of the protocol.

But if it's perfectly random (or at least doesn't correlate to the 
number of iterations) then all that averages out quite nicely. It's 
simply a question of how many samples are needed.

> Combine that

Famous last words.

- Marsh

---

From: Martin Rex <[email-masked]>
Date: Thu, 6 Oct 2011 21:06:52 +0200 (MEST)

Dan Harkins wrote:
> Marsh Ray wrote:

I agree with Marsh, it is difficult to conceive how to implement
this without being a timing oracle.

The question is, how much does it help you.

If you already have an account or could create one, then the timing
would help you sort out unlikely passwords, I assume, because you
know the algorithm and can determine "off-line" whether a computation
for a newly guessed password is faster or slower than your own password
and you can measure the servers response times for your password and
for the unknown password and therefore know their relation.

> guess will not provide any useful information.

I don't find it very attractive if an authentication protocol gives
an attacker a huge advantage at guessing an unknown account credential
if he can create or obtain a valid account credential.

I also feel very uncomforable with the extremely vague term
"low-entropy password" and the idea that this could be secure.

"low-entropy" to me means something like a 4-digit numeric PIN,
e.g. a complexity of 10^4 or 2^13.28

The only means to retain a meaningful security margin against
brute-force attacks is a very low lockout counter (e.g 2^4 or less).

If the whole handshake takes 1 second to complete (or fail), then
a brute force of the entire 2^13.28 entropy universe completes
in less than 3 hours.  Without a lockout, there just is not any
meaningful security possible.

-Martin

---

From: Anders Rundgren <[email-masked]>
Date: Thu, 06 Oct 2011 21:50:15 +0200

On 2011-10-06 08:47, Yoav Nir wrote:
<snip>
> Peter and I have been trying to push draft-nir-tls-eap for over 4 years now,
> and the TLS WG is not biting. You are following a bunch of people who have
> already had the door slammed in their faces.

In TrustedComputingGroup Intel was recently suggesting TLS-EAP as an
alternative to another TCG TLS-hack in progress.

Why isn't the TLS WG "biting"?  Who cares if an IETF WG says no?
Why not try other venues such as actually donating code?

The IETF has en huge stack of s.c. "standards" that aren't even worth
the disk-space they occupy!

Anders

---

From: Marsh Ray <[email-masked]>
Date: Thu, 06 Oct 2011 14:58:56 -0500

On 10/06/2011 02:50 PM, Anders Rundgren wrote:

> Who cares if an IETF WG says no?

You won't get a code point assignment for your extension otherwise.

- Marsh

---

From: Marsh Ray <[email-masked]>
Date: Thu, 06 Oct 2011 15:25:59 -0500

> this without being a timing oracle.

I disagree with Martin. :-)

It probably could be implemented without being a timing oracle, but 
blinding the timing channel might impose something approximating 
worst-case latency in all cases. Without benchmarking, I don't know if 
that means microseconds or milliseconds.

But mainly the fix wouldn't happen by accident. It needs to be pointed 
out with a high profile in the security considerations section.

> for the unknown password and therefore know their relation.

Collect timing on a few thousand handshakes for a given user. Observe 
the server response time clustering into buckets with a log_2 decaying 
distribution.

> if he can create or obtain a valid account credential.

I don't think it requires the attacker to obtain an account on the same 
server (but even if it did, that would still be bad).

> "low-entropy password" and the idea that this could be secure.

Sometimes we have to make the best of what we've got. Maybe sometimes 
all we've got is a password.

Still, I'm skeptical about who would use this thing and that they 
wouldn't be better served with something else.

> meaningful security possible.

Consider a "smart grid" of electric meters with a service lifetime of 30 
years. The meters probably have very slow CPUs making timing values 
relatively large and easy to distinguish. They may handshake regularly 
with the controlling systems. The power line network is about as open 
and undefended as you can get.

An attacker may be able to gather timing statistics for several years, 
after which he has obtained complete "blinkenlights capability" over the 
service region. That would be bad.

- Marsh

---

From: "Dan Harkins" <[email-masked]>
Date: Thu, 6 Oct 2011 14:03:14 -0700 (PDT)

> The question is, how much does it help you.

  Indeed. And I think the answer is, not much.

> for the unknown password and therefore know their relation.

  The relation-- yours is "faster" than the unknown one-- means nothing.
That knowledge doesn't help. Knowing how many iterations the hunting-
and-pecking loop went through to find PE for an unknown password might
but the relationship between two means nothing. In fact, since both
sides are contributing randomness into the hunting-and-pecking loop
yours might be "faster" one time and considerably slower the next time.
That knowledge doesn't really help.

  After the hunting-and-pecking loop there is a modular exponentiation
(or equivalent in EEC) using a random generator raised to a random
exponent. The timing variations in that calculation will be tremendous.

  The server won't respond until it has done both of these actions
so what the attacker sees is a sum of the time it took to perform both
actions. But the high variability in the time it takes to perform one of
those actions will interfere with the attacker's attempt to find out how
long the other action took.

  This is not a feasible attack.

> if he can create or obtain a valid account credential.

  I don't think it's attractive for an authentication protocol to give
an attack a huge advantage either. And this one doesn't.

> meaningful security possible.

  Yes, good point. At the bottom of section 6 I mention some
countermeasures to deal with repeated, failed, active attacks. I
should be more specific and mention what those countermeasures might
look like.

  thanks,

  Dan.

---

From: Philip Gladstone <[email-masked]>
Date: Thu, 06 Oct 2011 19:22:01 -0400

>    Please take a look. The authors solicit comments.
There is a note in Security Considerations section that indicates that 
an active attack that tried a hundred thousand passwords would be easily 
detected. The problem is that, in many cases, finding the password of a 
single user is sufficient (and you don't care which user it is). This 
means that you iterate over all users, only trying a single password for 
each user. This is *much* more difficult to detect and stop. [It does 
assume that usernames are drawn from a small pool. This may well be the 
case for electricity meters where the username might well be the device 
serial number -- and these are in a small, consecutive, range]

Philip

-- 
Philip Gladstone
Phone: +1 978-ZEN-TOAD (+1 978 936 8623)
Google: +1 978 800 1010
Ham radio: N1DQ

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 07 Oct 2011 18:16:41 +1300

"Dan Harkins" <[email-masked]> writes:

>certificates magically appear on the most unlikely of places and are all used 
>properly. They also make it highly problematic for any off-the-shelf device 
>that is supposed to be integrated into a network of other "smart energy" 
>devices from working properly. They assume an unrealistic level of security 
>clue on the people installing and provisioning the device. Having Joe Random 
>enter a simple password on the UI of his thermostat, for instance, is much 
>more believable.

Hmm, that was pretty much the argument that was made for TLS-PSK (well, not
thermostats, but that it was something that didn't require deploying certs and
was suitable for low-power devices).

>As a general purpose ciphersuite, no I don't imagine it will get much more 
>widespread use than SRP though. But I don't think that's necessarily a reason 
>to oppose it.

Speaking of SRP, I'm told the EKE patent expired a few days ago.

Peter.

---

From: "Dan Harkins" <[email-masked]>
Date: Thu, 6 Oct 2011 23:00:52 -0700 (PDT)

Hi,

> serial number -- and these are in a small, consecutive, range]

  That's a great observation. It does suppose that for some given
password there is at least one user in the pool of usernames that has
that password. I'm not sure how true that is in general, but some text
in the security considerations on this is probably needed. Do you have
any?

  Dan.

---

From: "Dan Harkins" <[email-masked]>
Date: Thu, 6 Oct 2011 23:13:41 -0700 (PDT)

> Speaking of SRP, I'm told the EKE patent expired a few days ago.

  Yes! This is a good thing.

  But EKE cannot be used with elliptic curves and has its own particular
constraints on what types of finite field domain parameter sets it can
use (for instance, it can't be used with groups 1-3 in RFC 5054). This
puts more of a burden on the client in evaluating whether an offer by the
server should be accepted or not.

  Unlike EKE, the scheme described in draft-harkins-tls-eap can be used
with any domain parameter set from RFC 3526, RFC 5114 or RFC 5639.

  Dan.

---

From: "Dan Harkins" <[email-masked]>
Date: Thu, 6 Oct 2011 23:16:05 -0700 (PDT)

Oh Jesus, what a typo...

   s/tls-eap/tls-pwd/

  Dan.

On Thu, October 6, 2011 11:13 pm, Dan Harkins wrote:
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 07 Oct 2011 19:47:32 +1300

"Dan Harkins" <[email-masked]> writes:

>But EKE cannot be used with elliptic curves

Speaking of PAKE for ECC, from reading a writeup of PACE (for passport EAC) a 
while back, the claimed reason for introducing PACE was that a lot of standard 
DLP PAKE mechanisms aren't secure when used with ECDLPs.  OTOH this RFC 
proposes a complex protocol for ECDLP use with no explanation of how it's 
derived, what its security properties are, or why it's secure.  What's the 
security argument for it?

Peter.

---

From: "Dan Harkins" <[email-masked]>
Date: Thu, 6 Oct 2011 23:58:35 -0700 (PDT)

> security argument for it?

  I'm sorry, but I don't understand. Are you asking questions of a different
PAKE scheme (PACE)? Which RFC are you talking about? Do you think there is
something missing from the security considerations of our draft? Is there
some statement of security, or argument, you'd like to see?

  Dan.

---

From: Jean-Marc Desperrier <[email-masked]>
Date: Fri, 07 Oct 2011 16:28:43 +0200

> Speaking of SRP, I'm told the EKE patent expired a few days ago.

True for US 5,241,599 :
http://www.google.com/patents?id=LxgbAAAAEBAJ
Filing date: Oct 2, 1991, Issue date: Aug 31, 1993
(US patent law for patents filed before Aug 95 : Valid for 20 years 
after filing date, or 17 years after issue date, whichever is longer )

Not true for US 5,440,635 :
http://www.google.com/patents?id=ByMhAAAAEBAJ
Filing date: Aug 23, 1993, Issue date: Aug 8, 1995
=> Valid until Aug 23, 2013

Lucent used to claim both /could/ apply to SRP 
http://www.ietf.org/proceedings/53/slides/ips-9/tsld010.htm before 
reverting to a position of pure FUD on the subject 
http://www.ietf.org/proceedings/53/slides/ips-9/tsld011.htm

---

From: Martin Rex <[email-masked]>
Date: Fri, 7 Oct 2011 19:58:49 +0200 (MEST)

> That knowledge doesn't really help.

The number of iterations for the hunting and pecking is visible in the
timing unless a reliable response time blending is employed (which would
have to account for an attacker running multiple requests in parallel to
slow down server-side processing).

Although both sides contribute randomness into the process, the only
unknown in the low-entropy password, everything else is revealed.
Since it is revealed, the attacker can use the timing "distance"
between processing his own password and processing guessed passwords
with the EXACT same parameters to sort out unlikely candidates.

-Martin

---

From: Rene Struik <[email-masked]>
Date: Fri, 07 Oct 2011 14:40:23 -0400

Dear colleagues:

The discussion re draft-harkins-tls-pwd-00 seems to focus on two
elements, viz.:
1) use case of password-based key agreement schemes and differentiation
w.r.t. other IETF work products (EKE, etc.);
2) the mapping from passwords to elliptic curve points.

As to #2, indeed, the procedure in Section 4.1.1 for mapping a password
to a point on the curve ("hunting and pecking") has indeed a
non-deterministic running time, due to "trial-and-error" approach and
may, therefore, by vulnerable to a side channel attack. Note, however,
that there are also deterministic methods for mapping a a value to a
curve as introduced, e.g., in the Crypto 2010 paper by Icart, Coron, et
al (cf. also IACR ePrint 2009-340) and the CRYPTO 2009 paper by Icart et
al. The CRYPTO 2009 paper discusses the probabilistic method Dan Harkins
describes (cf. Section 1.1 - Try and Increment Method; Section 5 -
Practical Implementations). Table 1 of Section 6 (Try and Increment v3)
provides results for an implementation that supposedly prevents
potential leakage of information from determining whether x^3 + a x + b
is a quadratic residue in GFp via the Legendre symbol computations.
Thus, that paper suggests that side channel resistance can be dealt
with, at the expense of time latency. The paper also illustrates that
the deterministic method for "hashing to a curve" has better performance
(again, refer to Table 1 of Section 6 of the CRYPTO 2009 paper).

I hope this helps.

Best regards, Rene

-- 
email: [email-masked]
Skype: rstruik
cell: +1 (647) 867-5658
USA Google voice: +1 (415) 690-7363

---

From: Nico Williams <[email-masked]>
Date: Fri, 7 Oct 2011 16:09:24 -0500

On Fri, Oct 7, 2011 at 1:40 PM, Rene Struik <[email-masked]> wrote:
> As to #2, indeed, the procedure in Section 4.1.1 for mapping a password to a
> point on the curve ("hunting and pecking") has indeed a non-deterministic
> running time, due to “trial-and-error” approach and may, therefore, by
> vulnerable to a side channel attack. Note, however, that there are also
> deterministic methods for mapping a a value to a curve as introduced, e.g.,
> in the Crypto 2010 paper by Icart, Coron, et al (cf. also IACR ePrint
> 2009-340) and the CRYPTO 2009 paper by Icart et al. The CRYPTO 2009 paper
> discusses the probabilistic method Dan Harkins describes (cf. Section 1.1 -
> Try and Increment Method; Section 5 - Practical Implementations). Table 1 of
> Section 6 (Try and Increment v3) provides results for an implementation that
> supposedly prevents potential leakage of information from determining
> whether x^3 + a x + b is a quadratic residue in GFp via the Legendre symbol
> computations. Thus, that paper suggests that side channel resistance can be
> dealt with, at the expense of time latency. The paper also illustrates that

Curve25519 is trivial to generate private keys for.

"Security Analysis of the PACE Key-Agreement Protocol", by Jens
Bender, Marc Fischlin, and Dennis Kügler discusses and refers to
papers about hashing to point values.

I like and recommend recommend PACE.

Nico
--

---

From: Peter Gutmann <[email-masked]>
Date: Sat, 08 Oct 2011 10:59:21 +1300

>I like and recommend recommend PACE.

I think it's interesting, but it's also waaaay too new.  Anyone with a paper
that potentially breaks it hasn't even had time to decide which conference to
submit it to yet.

Peter.

---

From: Nico Williams <[email-masked]>
Date: Fri, 7 Oct 2011 17:08:23 -0500

> that potentially breaks it hasn't even had time to decide which conference to

J-PAKE's been around a few more years.

Or wait until more patents expire.  We've waited long enough...

---

From: Peter Gutmann <[email-masked]>
Date: Sat, 08 Oct 2011 11:28:59 +1300

"Dan Harkins" <[email-masked]> writes:

>PAKE scheme (PACE)? 

The PACE discussion pointed out problems in doing PAKE for ECDLP, which PACE
was introduced to deal with.  The scheme proposed in your draft is not PACE,
and has no indication of where it came from or why it's secure.

>Which RFC are you talking about? 

Your RFC draft.

>Do you think there is something missing from the security considerations of
>our draft? Is there some statement of security, or argument, you'd like to
>see?

Yes, something like a pointer to a conference/journal paper explaining where
the scheme in the RFC draft came from and why it's secure.

Peter.

---

From: Steven Bellovin <[email-masked]>
Date: Sat, 29 Oct 2011 12:48:28 -0400

> Speaking of SRP, I'm told the EKE patent expired a few days ago.

Speaking only for myself and not for Alcatel-Lucent, I think you're
correct -- http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=5,241,599.PN.&OS=PN/5,241,599&RS=PN/5,241,599
shows it was filed on October 2, 1991; my understanding is that was valid
for 20 years from date of filing.  (It might have fallen into the category
of "the later of that date or 17 years from date of issue, but that would
have yielded an expiration date of August 31, 2010.)

		--Steve Bellovin, https://www.cs.columbia.edu/~smb

---

From: Anders Rundgren <[email-masked]>
Date: Sat, 29 Oct 2011 18:56:46 +0200

The "Window of opportunity" has also since long time passed.
It must have been a very "profitable" patent :-) :-)

Anders

---

From: Steven Bellovin <[email-masked]>
Date: Sat, 29 Oct 2011 13:36:13 -0400

I don't know of any licensees, though of course since it went to Lucent
when AT&T fissioned I have little knowledge of what happened after 1996-7.