Subject: [TLS] Curve25519 and TLS

From: Watson Ladd <[email-masked]>
Date: Fri, 13 Jun 2014 18:30:46 -0300

Dear all,

TLS with ECC computes the premaster secret as H(abg) where g is the
generator of the group, and a and b are the ephemeral exponents.
Because of protocol weaknesses, this premaster secret must be
"contributory": neither side can be allowed to dictate it.

Curve25519 has order 8*q, where q is some prime. All encoded public
keys lie on this or a twist with order 4*q'. (I might be wrong in the
details, but it's right enough). In particular there is a point of
order 2.

A malicious server can provide a point of order 2, and with 50%
probability get a dictated premaster secret.

The solution is to follow the advice on contributory behaviour and
disallow a fixed list of public keys, namely those of small order.
Alternatively we can compute the premaster secret as the hash of H(ag
| bg | abg): I have not yet confirmed that this solves the problem.

For TLS 1.3 we should ensure contributory behaviour is not required to
avoid these issues.

Sincerely,
Watson Ladd

---

From: Andy Lutomirski <[email-masked]>
Date: Fri, 13 Jun 2014 14:37:31 -0700

> For TLS 1.3 we should ensure contributory behaviour is not required to

What needs to change for this to be the case?  It would be even nicer if
the result were provably correct in some reasonable model.

--Andy

---

From: Watson Ladd <[email-masked]>
Date: Fri, 13 Jun 2014 18:59:39 -0300

> the result were provably correct in some reasonable model.

Hash the entire exchange into the generated key, so that a key made by
someone cheating is only shared with them. I still don't understand
why this isn't done already: it's needed for the finished message, so
nothing is saved by not doing it. This is what the triple handshake
fix is supposed to do, but it does a strange variant that reuses the
oddball finished message.

(And use a strong hash function: apparently the reason we haven't
finished fixing Triple Handshake is that some people want to use
SHA-1. On their heads be it!)

If the protocol is simple enough CryptoVerif can do the proofs with
some prodding: proving shouldn't really be the issue. Hashing helps
here by enabling the formation of a concept of "matching exchange",
and thus significantly constraining an attacker.

Sincerely,
Watson Ladd

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 13 Jun 2014 16:02:02 -0700

> SHA-1. On their heads be it!)

Hmm... I don't believe that this isn't done strictly because of SHA-1.
Looking back at what I wrote a while ago:

http://www.ietf.org/mail-archive/web/tls/current/msg12574.html

I believe the question is whether it is acceptable to have a *hash* of
the handshake hashed into the generated key as opposed to having
the handshake itself hashed into the generated key and whether it's
acceptable to have that hash be the combined MD5/SHA1 variant
in TLS < 1.2 and if not what recommendation we should make for
those versions.

-Ekr

> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: Watson Ladd <[email-masked]>
Date: Fri, 13 Jun 2014 23:05:57 -0300

> in TLS < 1.2 and if not what recommendation we should make for

Why wouldn't it be? If H(m)=H(m'), that's just as much a collision as
if H(m || stuff)=H(m' || stuff).

The MD5/SHA1 combination is only as strong as SHA1 against collisions.
In versions before TLS 1.2 this is unavoidable.
If that isn't good enough, the only recommendation I can offer is
don't use SHA1, but SHA2.

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Sat, 14 Jun 2014 08:59:03 +0200

Yes, we considered Curve25519 for Triple Handshake too.
One immediate protection that the crypto library could provide 
is to check that the received public key is not one of the 8 “degenerate” 
points listed at http://cr.yp.to/ecdh.html

More generally, I agree that using a session hash would protect this exchange too.

Best,
Karthik

---

From: Viktor Dukhovni <[email-masked]>
Date: Sat, 14 Jun 2014 07:39:25 +0000

> details, but it's right enough). In particular there is a point of

As far as I can tell, this is not the case with Diffie-Hellman over
Curve 25519, because the base-point (namely 9) has order 8, and
the cyclic sub-group it generates has prime order.  All private
keys are multiples of 8, so an attacker M who chooses a low order
element must send a public key m of order 1, 2, 4 or 8, which since
Alice's private exponent is a multiple of 8 means that g^{am} is
the identity.

See the "Small-subgroup attacks" section of DJB's paper.  Since
key agreement with Curve25519 is presumably Diffie-Hellman with
(9) as the base point and the recommended constraints on private
exponents, there should be no problem.

> probability get a dictated premaster secret.

Not useful when Alice's (or Bob's depending on whom Mallory is
trying to fool) private exponent is a multiple of 8, the only check
required is that the final shared secret is not the identity (IIRC
the point at infinity is represented by "0" in Curve 25519 so the
check is then just to make sure that the DH shared secret is not
32 zero octets).

Corrections/elaboration from folks more familiar with 25519 welcome.

-- 
	Viktor.

---

From: Watson Ladd <[email-masked]>
Date: Sat, 14 Jun 2014 09:36:31 -0300

> Alice's private exponent is a multiple of 8 means that g^{am} is

Yes, the only key that results is the identity. So the attack is 100%,
not 50%, effective.

> exponents, there should be no problem.

Read http://cr.yp.to/ecdh.html, the portion after "contributory behavior".

This is not an attack that recovers the exponent: it's an attack that
involves predicting the premaster secret ahead of time.
> check is then just to make sure that the DH shared secret is not

Yes, but this check isn't specified in the johnsson-tls-curve25519
draft. It needs to be.
Section 2.1 states
   Parties exchange  their public keys (see Section 2.3) and compute a
shared secret as x_S = Curve25519(d, x_peer).  This shared secret is
     used directly as  the premaster secret, which is always exactly
32 bytes when ECDHE  with Curve25519 is used.

That implies there is no check on the value of the shared secret.
Sincerely,
Watson Ladd

---

From: Viktor Dukhovni <[email-masked]>
Date: Sun, 15 Jun 2014 03:01:31 +0000

On Sat, Jun 14, 2014 at 09:36:31AM -0300, Watson Ladd wrote:

> > Curve 25519, because the base-point (namely 9) has order 8,

Sorry, typo, not order 8, rather prime order, it is an 8th power...

> > and

Well, it is not much of an attack, provided the appropriate care
is taken to avoid a public key that represents the group identity
(all zero if I am not mistaken, but this is the result of a cursory
read).

> Yes, but this check isn't specified in the johnsson-tls-curve25519

Yes.  The shared secret is either a single trivial value or strong,
so the sole trivial value needs to be avoided.

> That implies there is no check on the value of the shared secret.

Unless the function Curve25519 is defined to fail rather than
produce the trivial result.  So sure, the (simple) check needs to
be somewhere.

-- 
	Viktor.

---

From: Eric Rescorla <[email-masked]>
Date: Sun, 22 Jun 2014 17:56:27 -0700

> if H(m || stuff)=H(m' || stuff).

Well, this isn't quite the two cases we are considering, since we are
computing either:

HMAC(Key, stuff)

or:

HMAC(Key, H(stuff))

with:
- stuff being under partial control of the attacker and
- the Key being subject to the issue you raise in the message
that started this thread.

It may well be that these are equally secure, and if you have an analysis
that demonstrates that, then it would be useful in assessing how to
move forward with this draft.

Thanks
-Ekr

---

From: Watson Ladd <[email-masked]>
Date: Sun, 22 Jun 2014 18:24:20 -0700

> that started this thread.

HMAC is H(key || H(stuff)) right? So it turns into H(key || H(stuff))
vs H(key || H(H(stuff))). (Yes, there is padding: that's an injective
function, so doesn't matter for this analysis). Once again a collision
means stuff equals stuff both ways.

Of course, this presumes resistance to collisions. But if we don't
have that, there is a lot more going wrong.

Sincerely,
Watson Ladd

---

From: Eric Rescorla <[email-masked]>
Date: Sun, 22 Jun 2014 18:42:49 -0700

On Sun, Jun 22, 2014 at 6:24 PM, Watson Ladd <[email-masked]> wrote:

> >> >> On Fri, Jun 13, 2014 at 6:37 PM, Andy Lutomirski <
> [email-masked]>
> >> >> wrote:
> >> >> >> For TLS 1.3 we should ensure contributory behaviour is not
> required
> >> >> >> to
> >> >> >> avoid these issues.
> >> >> >
> >> >> > What needs to change for this to be the case?  It would be even
> nicer
> >> >> > if
> HMAC is H(key || H(stuff)) right?

Actually: H(key^mask1 || H(key^mask2 || stuff))

where mask1 and mask2 are fixed.

> So it turns into H(key || H(stuff))

Sorry, my mistake for not being clearer: I was assuming that there
was at least some partial failure of collision resistance in the hash
function. As you suggest, that means that a lot of other stuff is going
wrong, so maybe it's not worth worrying about.

-Ekr

---

From: Paul Hoffman <[email-masked]>
Date: Mon, 23 Jun 2014 07:36:51 +0100

> means stuff equals stuff both ways.

Bellare showed that weakening of the collision resistance in the underlying hash doesn't matter, right? <http://cseweb.ucsd.edu/~mihir/papers/hmac-new.html>? I haven't seen any refutation or weakening of that paper, but I could have missed it.

--Paul Hoffman

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Mon, 23 Jun 2014 13:39:21 +0000

You are correct. But the underlying hash must be a PRF for the proofs to hold.

--
Regards,
Uri Blumenthal                            Voice: (781) 981-1638
Cyber Systems and Technology   Fax:   (781) 981-0186
MIT Lincoln Laboratory                Cell:  (339) 223-5363
244 Wood Street                        Email: <[email-masked]>
Lexington, MA  02420-9185       

Web:  http://www.ll.mit.edu/CST/

MIT LL Root CA: 

 <https://www.ll.mit.edu/labcertificateauthority.html>

DSN:   478-5980 ask Lincoln ext.1638

----- Original Message -----
From: Paul Hoffman [mailto:[email-masked]]
Sent: Monday, June 23, 2014 02:36 AM
To: [email-masked] <[email-masked]>
Subject: Re: [TLS] Curve25519 and TLS

--Paul Hoffman

---

From: Watson Ladd <[email-masked]>
Date: Mon, 23 Jun 2014 07:23:55 -0700

> Bellare showed that weakening of the collision resistance in the underlying hash doesn't matter, right? <http://cseweb.ucsd.edu/~mihir/papers/hmac-new.html>? I haven't seen any refutation or weaken…

But here the key is known to the attacker (because it was the result
of a DH operation on a point of small order) : that paper is
completely irrelevant.

Furthermore, all TLS implementations somehow validate signatures: we
can use the collision resistant hash from that and avoid having to
think about these issues.

Sincerely,
Watson Ladd

---

From: Watson Ladd <[email-masked]>
Date: Thu, 26 Jun 2014 07:35:56 -0700

On Thu, Jun 26, 2014 at 1:18 AM, Bodo Moeller <[email-masked]> wrote:
> Watson Ladd <[email-masked]>:
>
> [...]
> Good point.  Given that the cofactor present in your secret key guarantees
> that you'll end up in a prime-order group (regardless of how the peer's
> input was chosen), I think you'd rather want to check the ECDH result
> instead of checking against that larger blacklist of public keys.
>
> Hm, this looks like something that rather belongs into the premaster secret
> => master secret step.  If you have this there (such as when you're using
> the proposed Extended Master Secret Extension
> [draft-bhargavan-tls-session-hash-00]), including the public keys here too
> would be redundant.  If you'd normally be doing a public-key check or an
> ECDH result check, you could just skip this check if the protocol no longer
> has a need for such protection.  In contrast, if you hash those additional
> inputs when computing the premaster secret, that's not something you could
> remove without affecting compatibility.

Yes, we could make EMSE a dependency of Curve25519. Or we could change
the way we compute
the PMS to avoid doing this: I proposed this solution because its very
simple for some implementations.

What do we gain from having the PMS calculated the same way for each curve?
>
> (On the flip site, of course, if an implementation omits a check that's
> necessary for security reasons in the protocol that you're using, you
> wouldn't normally notice interoperability problems as a result.  In
> contrast, if the protocol has those additional hash inputs, implementations
> couldn't get that wrong without failing to interoperate with others.
> However, there are many other more complex essential security checks that we
> trust implementations to get right, so the extra protocol complexity for
> this particular case doesn't seem warranted.)

This is a mistake in the design. Unfortunately I can't go into details
right now.

Sincerely,
Watson Ladd
> Bodo

---

From: Bodo Moeller <[email-masked]>
Date: Thu, 26 Jun 2014 17:27:40 +0200

> What do we gain from having the PMS calculated the same way for each curve?

My argument wasn't about doing things the same way for each curve. What I
don't like is introducing overhead (hashing an input at the premaster
secret level that we'll be hashing at the master secret level too, in
certain protocol variants) that could be avoided by using your other
proposal, a Curve25519-specific check.

(For many hashes, it would be actual computational overhead because those
two public keys are large enough to take up an additional input block.)