Subject: [TLS] Negotiated Discrete Log DHE revision [was: Re: Confirming Consensus on removing RSA key Transport from TLS 1.3]

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 08 Apr 2014 01:41:34 -0400

On Fri 2014-03-28 21:33:39 -0400, Daniel Kahn Gillmor <[email-masked]> wrote:
> I've submitted an initial stab at a proposal for negotiated discrete log
> diffie-hellman ciphersuites:
>
>  http://tools.ietf.org/html/draft-gillmor-tls-negotiated-dl-dhe-00

Thanks to feedback from Watson Ladd and Samuel Neves over on the CFRG,
i've updated the named groups in the above draft.

I've also done another pass over the text:

  https://tools.ietf.org/html/draft-gillmor-tls-negotiated-dl-dhe-01

Comments, questions and critiques welcome.

    --dkg

---

From: Michael D'Errico <[email-masked]>
Date: Tue, 08 Apr 2014 09:53:23 -0700

There is already a list of DH groups managed by the IANA for IKE that was
established by RFC 2409 and includes the MODP groups from RFC 3526 plus
others.  Why not just use this existing registry and add your new e-based
groups to it?

Mike

---

From: Michael D'Errico <[email-masked]>
Date: Tue, 08 Apr 2014 10:22:04 -0700

Also, I'm curious why "e" is chosen for constructing these primes.  Since
the natural log of e is 1, doesn't it seem like a bad idea to stick a bunch
of bits of e in a prime where the security is based on logarithms?

Mike

---

From: Henrick Hellström <[email-masked]>
Date: Tue, 08 Apr 2014 20:07:25 +0200

There is no discrete logarithm algorithm that can take advantage of the 
fact you mention.

However, e might be a less optimal choice for another reason, namely 
that the next higher safe prime is relatively far away from the starting 
points you get when you use e this way. For instance, in the case of the 
6144 bit prime, it is more than 2^33 steps away from the starting point, 
which means it will take a lot of time to verify the correctness of 
these primes (once you found them).

On 2014-04-08 19:22, Michael D'Errico wrote:
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 08 Apr 2014 20:53:44 -0400

> others.  Why not just use this existing registry and add your new e-based

I tried to address this question in section 8.4 of the current draft:

https://tools.ietf.org/html/draft-gillmor-tls-negotiated-dl-dhe-01#section-8.4

-----------------
8.4.  Choice of groups

   Other lists of named discrete log Diffie-Hellman groups
   [STRONGSWAN-IKE] exist.  This draft chooses to not reuse them for
   several reasons:

      Using the same groups in multiple protocols increases the value
      for an attacker with the resources to crack any single group.

      The IKE groups include weak groups like MODP768 which are
      unacceptable for secure TLS traffic.

      Mixing group parameters across multiple implementations leaves
      open the possibility of some sort of cross-protocol attack.  This
      shouldn't be relevant for ephemeral scenarios, and even with non-
      ephemeral keying, services shouldn't share keys; however, using
      different groups avoids these failure modes entirely.

      Other lists of named DL DHE groups are not collected in a single
      IANA registry, or are mixed with non-DL DHE groups, which makes
      them inconvenient for re-use in a TLS DHE key exchange context.
-----------------

Do you find these arguments unconvincing, or do you have suggestions for
how the text should be changed?

	--dkg

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 08 Apr 2014 21:07:48 -0400

> these primes (once you found them).

Have you done the calculations to derive the 6144-bit prime in this
series?  If so, are you willing to share your code?

I confess i don't see why the safe primes should be farther for this
construction than a similar construction with pi, but it certainly seems
to be the case.  Is there a reference that i should read to understand
this better?

	--dkg

---

From: Samuel Neves <[email-masked]>
Date: Wed, 09 Apr 2014 03:36:31 +0100

> to be the case.  Is there a reference that i should read to understand

It seems to be an unlucky choice. The probability that p is prime is roughly 1/log(p) by the Prime Number Theorem.
Assuming independence, the probability that (p-1)/2 is also prime can be given by the same expression. Thus we can get a
rough approximation of the number of integers to go through: log(p)^2. In the case of p ~ 2^6144, the expected iteration
number is ~2^24.

---

From: Watson Ladd <[email-masked]>
Date: Tue, 8 Apr 2014 22:07:09 -0700

On Tue, Apr 8, 2014 at 7:36 PM, Samuel Neves <[email-masked]> wrote:
> It seems to be an unlucky choice. The probability that p is prime is roughly
> 1/log(p) by the Prime Number Theorem. Assuming independence, the probability
> that (p-1)/2 is also prime can be given by the same expression. Thus we can
> get a rough approximation of the number of integers to go through: log(p)^2.
> In the case of p ~ 2^6144, the expected iteration number is ~2^24.

I don't see why e inherently has this property. Granted this is
probably deep (and nobody at Berkeley does this, so I have no clue),
although it is worth noting that the bounds on pi(x) are quite weak in
comparison to the asymptotics. (It could of course be a quirk of small
numbers).

Burn enough computer time and generation will stop. Once it does
validation (not of minimality) is fairly quick, and we can make a
certificate to enable fast ECPP checking. Minimality certification is
tough: even safecurves.cr.yp.to doesn't do it.

If you give up and want another transcendental constant, \zeta(3)
(Apéry's constant) could be worth a look. So could \e^{\pi}. Logs of
small integers could also work. Alternatively we could use the
precomputed groups for the larger orders: the damage from shared
factor bases is most acute when the group size is close to breakable.

Sincerely,
Watson Ladd

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

---

From: Samuel Neves <[email-masked]>
Date: Wed, 09 Apr 2014 11:50:49 +0100

> comparison to the asymptotics. (It could of course be a quirk of small

Sorry, I was not clear. I was not associating any particular property with e; any choice of constant will have roughly
the same expected ~2^24 attempts. That e happens to require more is a statistical accident.

---

From: Liz meeks <[email-masked]>
Date: Wed, 9 Apr 2014 03:57:33 -0700

Stop sending me these msgs

---

From: Fedor Brunner <[email-masked]>
Date: Wed, 09 Apr 2014 14:44:28 +0200

Are you refering to Java TLS clients in section 1. Introduction ?

" Some  widely-distributed TLS clients are not capable of DH groups
where p >  1024. "

This limitation has been fixed in Java 8

http://bugs.java.com/bugdatabase/view_bug.do?bug_id=7044060
https://stackoverflow.com/questions/6851461/java-why-does-ssl-handshake-give-could-not-generate-dh-keypair-exception

Fedor

---

From: Fedor Brunner <[email-masked]>
Date: Sat, 12 Apr 2014 12:19:36 +0200

On 11.04.2014 19:18, Daniel Kahn Gillmor wrote:
> On 04/11/2014 09:18 AM, Fedor Brunner wrote:
>> Your groups dldhe3072, dldhe4096 look similar to MODP groups 15, 16. If
>> you assume that an attack can be developed for MODP groups, could this
>> attack be also developed for dldhe3072, dldhe4096?
>
> probably, yes.  at the moment, i believe such an attack on any given
> group would be quite expensive in both time and money.  My hope is that
> it is prohibitively expensive in general, because of the large amount of
> computing power and data storage that would be needed to effectively map
> the space.  but it's possible that an extremely well-funded organization
> could pull it off.  will they be able to attack two groups in this way?
>  not without increasing the expenses even further.
>
> if we use a single group for everything (IKE as well as TLS), the cost
> of attacking that group stays the same, but the value of breaking the
> group goes up.
>
>> If you assume an attack exists for fixed DH group then not fixed  DH
>> groups generated for each server (as is current option in TLS) would
>> make the attack much more expensive.
>
> this is true, but it also makes it possible for bad groups to be used,
> either through malice or misconfiguration.  arbitrary groups also
> increases the size of the handshake significantly, and clients have no
> inexpensive way of verifying that the groups have reasonable structure
> and that they are not in a small subgroup.  With named groups, both
> peers can have pre-computed tables that should make ephemeral keying
> cheaper and easier, whereas with arbitrary groups only the server gets
> this advantage.
>
>> For example OpenSSH supplies a set of 40 DH groups for each 1023, 1535,
>> 2047, 3071, 4095, 6143, 8191-bit primes . During key exchange one of
>> these groups with desired size is selected in server by random. The
>> OpenSSH server administrator can also generate his own set DH
>> parameters, for each prime length.
>
> i'm aware of this model.  in practice, nearly everyone seems to be
> content using the moduli that are shipped by their vendor in
> /etc/ssh/moduli.
>
>> Could you please provide estimated strength of the dldhe2432,
dldhe3072, ...
>> groups ? For example see the estimated strength of MODP groups in RFC
3526
>>
>> https://tools.ietf.org/html/rfc3526#section-8
>
> yes, that's a good idea, thanks.
>
>> Please consider describing the algorithm for generation of the groups
>> dldhe2432, dldhe3072, ...
>> The generation of MODP groups is described in RFC 2412 (Appendix E)
>
> do you think the introduction to Appendix A is insufficient?  if so, do
> you have a concrete suggestion for how it should change?

You have stated why the high and low bits are ones (Montgomery or
Barrett reduction), please describe also the decision to use the base of
the natural logarithm for the middle part of discrete log groups.

For example in RFC 2412 (Appendix E)

"
The middle bits
   are taken from the binary expansion of pi.  This guarantees that they
   are effectively random, while avoiding any suspicion that the primes
   have secretly been selected to be weak.
"

---

From: "Joseph Salowey (jsalowey)" <[email-masked]>
Date: Sat, 26 Apr 2014 15:24:41 +0000

The discussion on this list and others supports the consensus in IETF 89 to remove RSA key transport cipher suites from TLS 1.3.  The Editor is requested to make the appropriate changes to the draft on github.

More discussion is needed on both DH and ECDH are used going forward and on if standard DHE parameters will be specified.

Joe
[For the chairs]
On Mar 26, 2014, at 11:43 AM, Joseph Salowey (jsalowey) <[email-masked]> wrote:

> TLS has had cipher suites based on RSA key transport (aka "static RSA", TLS_RSA_WITH_*) since the days of SSL 2.0.   These cipher suites have several drawbacks including lack of PFS, pre-master secret contributed only by the client, and the general weakening of RSA over time.  It would make the security analysis simpler to remove this option from TLS 1.3.  RSA certificates would still be allowed, but the key establishment would be via DHE or ECDHE.  The consensus in the room at IETF-89 was to remove RSA key transport from TLS 1.3.  If you have concerns about this decision please respond on the TLS list by April 11, 2014.
> 
> Thanks,
> 
> Joe
> [Speaking for the TLS chairs]

---

From: [email-masked] (Martin Rex)
Date: Tue, 29 Apr 2014 19:25:26 +0200 (CEST)

Joseph Salowey (jsalowey) wrote:
>
> The discussion on this list and others supports the consensus in IETF 89
> to remove RSA key transport cipher suites from TLS 1.3.

You probably meant TLS cipher suites with the (static) RSA key exchange
method.

> 
> More discussion is needed on both DH and ECDH are used going forward
> and on if standard DHE parameters will be specified.

(static) DH/ECDH key exchange needs to be addressed seperately from 
(ephemeral) DHE/ECDHE key exchange.

Is there any deployment of Server certificates with static DH/ECDH at all?
Is it at all possible to build a regular PKCS#10 certification request
(i.e. one with a proof-of-posession signature) for static DH/ECDH
keys in server certificates?

Personally, I don't think it is reasonable to completely remove from TLSv1.3
*ALL* of the stuff that will be necessary for interop with the installed base.

There also exist small devices with weak random number generators that
could be used with an offline generated RSA server keypair.  I don't see
any value in _not_ supporting static RSA for these.  With a preloaded
strong (EC)DHE keypair, they're worse off that with a static RSA key
(slower and no forward secrecy), and they have difficulties generating
strong ephemeral keys on their own.

The additional code footprint of ECC and the overall brittleness
of ECC crypto is another concern.  Currently, ECC is a mere option,
and a very dangerous one due to the overall brittleness of ECC,
even for implementations of TLSv1.2

-Martin