Subject: [TLS] DH group validation

From: Eric Rescorla <[email-masked]>
Date: Tue, 16 Oct 2007 08:49:44 -0700

One of the remaining TODOs in TLS 1.2 is what (if anything)
the client should do to validate the server's offered DH
group. I ran this by Bodo Moeller, who writes:

On Thu, Oct 11, 2007 at 12:20:20PM -0700, Eric Rescorla wrote:

> The current TLS 1.2 draft has:
> 
>    Because TLS allows the server to provide arbitrary DH groups, the
>    client SHOULD verify the correctness of the DH group. [TODO: provide
>    a reference to some document describing how] and that it is of
>    suitable size as defined by local policy. The client SHOULD also
>    verify that the DH public exponent appears to be of adequate size.
>    The server MAY choose to assist the client by providing a known
>    group, such as those defined in [IKEALG] or [MODP]. These can be
>    verified by simple comparison.
> 
> Any chance you would be willing to provide some text for this TODO?
> Or a pointer or something?

I suppose I could write something on recommendations for DH groups
(although not right now -- I will be traveling without a computer
later this week and next week), but I don't really see the point of
client verification of server-chosen DH groups, and don't agree that
this should be a "SHOULD".

In the TLS 1.2 standard ciphersuites, a signature authenticates that
the server really has chosen this particular group.  (Or, in anonymous
ciphersuites, even *with* group verification you can't really trust
the DH value if you suspect there might be an active adversary.)  You
can't verify *all* security-relevant aspects of server behavior, so
why spend time verifying this particular one?  If the server
implementation sucks, it could use a perfectly nice DH group in a
perfectly broken way -- such as by using a low-entropy secret
exponent.  I don't see that verifying the DH group doesn't really add
significant value: it does not counter any threats by actual
adversaries.

Looking at the (purported) group size is reasonable because it is
cheap to do, so that the client can detect if the server at least
pretends to use a certain security level.

The client could do some more complex verification to decide if it
would appear secure to reuse its own secret exponent multiple times,
but I don't think this is worth the effort: we have session reuse
capabilities, anyway; so clients should always use fresh DH exponents
if a full handshake happens, and try to reuse a session if they want
to reuse older secret values.

Bodo

I tend to agree with this, and I suggest that we simply suggest
that the client SHOULD check the group size.

Comments in the other direction? I'd like to note that the reason
this section is not filled in is because I don't have any text
I'm comfortable with on how to check a DH group. Accordingly, 
any comments suggesting that we should have validation would
be most convincing if they came with a contribution of text
describing what you want done.

-Ekr

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

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Tue, 16 Oct 2007 22:10:11 +0300

> significant value: it does not counter any threats by actual

I agree with the above. He can post the transaction in plaintext. I don't see 
much to gain by further checking the group.

> pretends to use a certain security level.

But of course then you need to define what a security level is and how it 
applies to DH key exchange.

regards,
Nikos

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 16 Oct 2007 12:33:02 -0700

At Tue, 16 Oct 2007 22:10:11 +0300,
> applies to DH key exchange.

I don't see that this follows. The current text simply leaves the
decision to the client, which seems to do the job:
 
   The client SHOULD also

-Ekr

---

From: [email-masked] (Peter Gutmann)
Date: Wed, 17 Oct 2007 19:26:46 +1300

Eric Rescorla <[email-masked]> writes:

>One of the remaining TODOs in TLS 1.2 is what (if anything) the client should
>do to validate the server's offered DH group.

Isn't this trivially solveable by switching from PKCS #3 to DSA/X9.42/<generic
DLP key mechanism> and referring to any standard that tells people how to
apply this?  Presumably all it'd take is the addition of fields for the new
DLP key parameters, and a reference to the standard of choice for how to
generate and verify the keys.

Peter.

---

From: <[email-masked]>
Date: Wed, 17 Oct 2007 09:48:58 +0300

Bodo Moeller wrote:
> I don't see that verifying the DH group doesn't really add

Not all threats all caused by malicious adversaries. IMHO the 
purpose of doing some kind of DH group validation is to mitigate 
risk from a particular kind of implementation mistake.  This 
particular implementation mistake has been seen in real world, 
so it does have some relevance (although there are, of course, 
other implementation mistakes that can't be found by this 
particular check).

However, it seems that as long as we don't require any particular
verifiable prime generation algorithm (such as X9.42), or use only
"known" groups (like IKE does), the only validation we can easily 
do (without non-trivial computation) is checking the size of "p".
We could rephrase the text something like this:

   The security level offered by TLS also depends on the DH group.
   The client SHOULD verify that the DH modulus appears to be of
   adequate size (some implementations of earlier versions of TLS are
   known to generate very small DH moduli, offering little security). 
   Other aspects of DH group correctness (such as the subgroup size)
   are more difficult to verify.  The server MAY choose to assist the 
   client by providing a group with known level security, such as 
   those defined in [IKEALG] or [MODP]. These can be verified by 
   simple comparison.

Best regards,
Pasi

---

From: Bodo Moeller <[email-masked]>
Date: Wed, 17 Oct 2007 09:35:49 +0200

>> I don't see that verifying the DH group doesn't really add

Oops, unintended double negation.  But apparently everyone got what
I meant: "I don't see that verifying the DH group really adds
significant value."

> other implementation mistakes that can't be found by this 

Yes, this is my point (as stated earlier in the paragraph part of
which you quoted here).

> do (without non-trivial computation) is checking the size of "p".

I am hoping that we can agree to (optionally?) include "q" into DH
parameters for the next version of the standard, allowing for more
meaningful quick "validation" on the one hand, and for efficiency
improvements on the other hand.  (Efficiency improvements since if you
have a 2048-bit p with a 224-bit q, the client has much less work to
do if it knows it only has to choose an exponent in the range (2, q-1)
and not a 2048-bit exponent.)  In this case, the client would look
at the size of q to see if it looks reasonably large, and presumably
also would check that q is at least one bit longer than q.

Bodo

---

From: Eric Rescorla <[email-masked]>
Date: Sat, 20 Oct 2007 12:25:45 -0700

At Wed, 17 Oct 2007 09:35:49 +0200,
> also would check that q is at least one bit longer than q.

Bodo:

I want to make sure I understand this:

1. Is knowing the factorization important in this case? I'm not
   really a DH expert, but this paper http://eprint.iacr.org/2004/099
   seems to argue that if you're digesting ZZ, you don't need to
   know the factorization of p-1. It looks like this may only be
   true if the generator is random? Maybe Hugo can weigh in
   here...

2. This is an optimization only for the client, right? The server at
   least potentially knows the factorization of p-1, so sending 
   this information doesn't make the server any faster.

-Ekr

---

From: Bodo Moeller <[email-masked]>
Date: Mon, 29 Oct 2007 16:14:58 +0100

>    true if the generator is random? Maybe Hugo can weigh in

When above I say "q", I actually mean that q would be a prime, and
that the given DH generator would be the generator of an order-q
group.  This is something that the specification would have to
require.  We could make the specification more complex and allow other
configurations, but this looks pretty pointless to me: Instead, for
non-prime group order (or if you don't know the order), I figure you'd
simply omit q in the handshake message.

Groups of non-prime order can work too for DH.  I won't rehash (no pun
intended) the results of the Hashed Diffie-Hellman paper that you are
citing, but merely point out that it does *not* state that DH
exponents can be as short when *not* using a prime-order generator as
they can be when using a prime-order generator!  In fact, if the group
is not of prime order, this usually means that exponents do have to be
longer.  If you don't even know the group order, you'll have to use
longer exponents just in case.

>    this information doesn't make the server any faster.

Certainly!  This is about information that the server sends to the
client, since in TLS any DH parameters are always provided by the
server.  If the server can send the information, then the server also
knows the information; and it can use it without having to know
whether the client is making use of it too: The server simply will
pick its private DH exponent from the positive integers below q if it
knows that the DH generator has order q, or even from a subset of
shorter integers as determined by the required security level (which
can be safely done assuming that, as required above, q is prime).

Bodo

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 29 Oct 2007 09:09:21 -0700

At Mon, 29 Oct 2007 16:14:58 +0100,
> can be safely done assuming that, as required above, q is prime).

OK, so this seems like a minor optimization but it does require a
change to TLS, which, as I've commented before, my instinct is
to avoid. My general intuition is that client public key performance 
isn't an enormous concern, since it's generally a latency issue
as opposed to a throughput issue, so I'm mildly negative on this
change, just on the theory of changing as little as possible.

Right now my sense is that you and Peter Gutmann would like to
see this change made and I would rather not. That's a pretty
small set of opinions to decide from. Pasi may eventually need
to run a straw poll, but first can I ask if there are other
WG members who want to weigh in with their feelings on this? The
general feeling of the WG may turn out to be clear...

Folks?
-Ekr

---

From: Bodo Moeller <[email-masked]>
Date: Tue, 30 Oct 2007 09:02:31 +0100

> isn't an enormous concern,

This depends very much on the setting.  Clients such as cellphones can
be quite slow, and this is about a factor of five and more
(1024/160 = 6.4) for the time the client has to spend on handshake
calculations to achieve forward secrecy.

---

From: Nelson B Bolyard <[email-masked]>
Date: Tue, 30 Oct 2007 17:21:35 -0700

> general feeling of the WG may turn out to be clear...

If we add q to the DH params, IMO it must be optional.

-- 
Nelson B

---

From: <[email-masked]>
Date: Wed, 31 Oct 2007 09:04:31 +0200

> change, just on the theory of changing as little as possible.

If a server wants to allow clients this chance for optimization, 
it can do so today: just send a known group (e.g. one of those 
used in IKE). Those groups also have special properties which 
make using short private exponents safer, and use generator 
"2", which makes calculations even faster.

This possibility is already mentioned in the current draft
as "MAY"; I wouldn't object to changing it to "SHOULD assist
the client by providing one of the groups defined in [some
ref]", and adding a note this allows clients to perform
certain optimizations.

Best regards,
Pasi

---

From: Bodo Moeller <[email-masked]>
Date: Wed, 31 Oct 2007 09:06:35 +0100

> "2", which makes calculations even faster.

While this would work to get the speed advantage, it is not very good
as an optimization in general because it requires clients to have
large tables of known groups to match against.  This could be a
problem especially for those small devices that would most benefit
from short q.

Also, known groups always are a trade-off.  If everyone were using the
same group, then discrete log attacks for this particular modulus and
generator might become worthwile.  If different servers are using
different groups, then there isn't one particular target group.  So
while using known groups certainly is reasonable, I think we shouldn't
create artificial incentives for using known groups.

Bodo

---

From: <[email-masked]>
Date: Wed, 31 Oct 2007 10:50:21 +0200

Bodo Moeller wrote:

> > If a server wants to allow clients this chance for
> > optimization, it can do so today: just send a known group
> > (e.g. one of those used in IKE). Those groups also have special
> > properties which make using short private exponents safer, and
> > use generator "2", which makes calculations even faster.
> 
> While this would work to get the speed advantage, it is not very
> good as an optimization in general because it requires clients to
> have large tables of known groups to match against.  This could
> be a problem especially for those small devices that would most
> benefit from short q.

A table the storing the current SHOULD/MUST level groups used in 
IKEv2 would take <400 bytes -- not a small table, but not especially 
large either (and I guess you could survive with just storing hashes
of the p's).
 
> create artificial incentives for using known groups.

In IKEv1/IKEv2, everyone is using the same group. Íf this caused
huge problems, I think we'd know by now...

Best regards,
Pasi

---

From: Bodo Moeller <[email-masked]>
Date: Wed, 31 Oct 2007 10:25:18 +0100

> large either (and I guess you could survive with just storing hashes

True in this case.  I was assuming more known groups from other
sources, not just the IKE ones.  Still this approach has a rather
kludgey feel to it.

> huge problems, I think we'd know by now...

Remember how the index calculus approach for computing discrete
logarithms works: the first stage of computations depends on the
modulus only, not on the specific DL problem.  This means that
considerable effort can be saved if many DL problems share a single
modulus.  This hasn't been a huge problem since with the specific
algorithms known now and the specific computing equipment available
now, it looks like the 1024-bit OAKLEY group is out of reach.  At the
edge, though, a k-bit known group must be expected to be less secure
in practice than a well-chosen k-bit unknown group.

On the positive side, with well-known groups, everyone has the chance
to use fixed precomputation to speed up some of the DH computations.
So the penalty for using a larger group for compensation isn't
necessarily too bad.

Bodo

---

From: Mike <[email-masked]>
Date: Wed, 31 Oct 2007 11:25:09 -0700

It seems to me that the goal of this proposed change is to
allow constrained clients to enjoy the benefits of forward
secrecy without suffering a large performance hit.  Trying
to adjust Diffie-Hellman may not be the best option.

On my Windows machine, here is a performance comparison of
RSA and DH:

             48-byte
    size   RSA encrypt   DH generate key   DH compute secret
    1536     0.00086         0.0691             0.0687
    2048     0.00140         0.1547             0.1531

(The DH groups used are from RFC 3526 MODP.)

Resurrecting the RSA_EXPORT key exchange mechanism and
repackaging it as ephemeral RSA (and removing the key length
restrictions) would solve this problem and there is already
a body of existing code to do it.  These constrained clients
could even ditch all their Diffie-Hellman code, saving some
memory.

Using the above numbers, a 1536-bit ephemeral RSA exchange
would require 0.86 milliseconds of cryptographic computation
by the client, whereas with 1536-bit ephemeral Diffie-Hellman
would require 138 ms, a factor of 160.  A 2048-bit exchange
takes 1.4 ms and 308 ms respectively, a factor of 220.  (I
don't know how much faster these DH computations would be if
the q parameter was incorporated.)

Mike

---

From: Nelson B Bolyard <[email-masked]>
Date: Wed, 31 Oct 2007 12:37:45 -0700

Mike wrote:

> a body of existing code to do it.  

I would support a proposal to do that.

It would also address NIST/NSA's desire that signature keys never be
used for encryption and vice-versa.

-- 
Nelson B

---

From: "Kemp, David P." <[email-masked]>
Date: Wed, 31 Oct 2007 16:36:07 -0400

Mike,

Do you have comparable numbers for RSA decrypt (for constrained
devices or machines requiring higher throughput) and for
ECDHE_RSA or ECDHE_ECDSA with equivalent (secp192/secp224)
key sizes?

-----Original Message-----
From: Mike [mailto:[email-masked]] 
Sent: Wednesday, October 31, 2007 2:25 PM
To: [email-masked]
Subject: Re: [TLS] DH group validation

             48-byte

Mike

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 31 Oct 2007 13:47:50 -0700

Actually the relevant number is RSA key generation time, which is
MUCH slower than DH key generation. On my laptop, RSA key 
generation is about 50x slower than RSA decryption, making
it basically prohibitive to generate a new RSA key pair for
each transaction, which is of course what is required for PFS.

-Ekr

At Wed, 31 Oct 2007 16:36:07 -0400,

---

From: Mike <[email-masked]>
Date: Wed, 31 Oct 2007 14:56:31 -0700

> ECDHE_RSA or ECDHE_ECDSA with equivalent (secp192/secp224)

I don't have access to any constrained devices to try this on,
but these numbers are based on OpenSSL 0.9.8 on a 3.2GHz
Windows XP machine.

  size  RSA keygen   encrypt   decrypt   DH keygen   DH secret
  1536     0.485     0.00084    0.020      0.0691      0.0691
  2048     1.647     0.00138    0.047      0.1545      0.1534

The RSA key generation time is an average of generating 5 keys
of each size, which on this machine is a factor of 7 to 11
slower than computing DH keys.  The decrypt operation is more
than 3 times as fast as computing the DH secret.

I haven't implemented any elliptic curve code, so I can't
produce any numbers for that.

But for ephemeral RSA vs. ephemeral DH, there is a clear win
for clients:

   size   ephemeral Diffie-Hellman    eph-RSA    speedup
   1536   0.0691 + 0.0691 = 0.1382    0.00084     160x
   2048   0.1545 + 0.1534 = 0.3079    0.00138     220x

The server takes a hit if it generates a new ephemeral key for
every connection:

   size   eph-DH        ephemeral-RSA         slowdown
   1536   0.1382    0.485 + 0.020 = 0.505       3.6x
   2048   0.3079    1.647 + 0.047 = 1.694       5.5x

If the server reused ephemeral keys just 10 times, the numbers
would be:

   size         ephemeral-DH               ephemeral-RSA
   1536   0.00691 + 0.0691 = 0.076    0.0485 + 0.020 = 0.0685
   2048   0.01545 + 0.1534 = 0.169    0.1647 + 0.047 = 0.2117

Reusing an ephemeral key 10 times achieves "almost" perfect
forward secrecy with similar server performance, and a 160x
to 220x increase in client performance.

Mike

---

From: Mike <[email-masked]>
Date: Wed, 31 Oct 2007 15:13:28 -0700

> each transaction, which is of course what is required for PFS.

Yes on the server end RSA key generation is the biggest factor,
but the comparison is not RSA keygen vs. RSA decryption, but
rather (RSA keygen + RSA decrypt) vs. (DH keygen + DH secret).
As I noted in my last message, this is a factor of 4 to 6 times
on my machine.  However, if you reuse the ephemeral keys just
10 times, the performance is roughly the same.

Of course reusing keys doesn't achieve -perfect- forward secrecy,
but is very close.  To attack a million sessions using simple
RSA key exchange requires breaking one key, whereas you would
need to break 100,000 ephemeral RSA keys to achieve the same
result.

Mike

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 31 Oct 2007 15:58:56 -0700

At Wed, 31 Oct 2007 14:56:31 -0700,
>   size  RSA keygen   encrypt   decrypt   DH keygen   DH secret

You're using full-length exponentials, right? Using short exponentials
produces a pretty significant performance improvement. DH in
a 1024-bit group with a 256-bit exponent is about 50% slower than
RSA with a 1024-bit modulus. And remember that the server can
get this edge without modifying the protocol. So, now you're 
looking at more like a factor of 30.

-Ekr

---

From: Vipul Gupta <[email-masked]>
Date: Wed, 31 Oct 2007 16:03:51 -0700

>  size  RSA keygen   encrypt   decrypt   DH keygen   DH secret

Recent versions of OpenSSL (yours might qualify) have ECC built in.
You can get timing information for secp192/secp224 as follows:

% openssl speed ecdhp192 ecdhp224 ecdsap192 escdsap224

(Unlike RSA, ECC verification is slower than signing)

vipul

p.s. We have some papers with performance numbers on constrained  
devices at
research.sun.com/projects/crypto (they are from a couple of years ago)

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 31 Oct 2007 15:58:56 -0700

-Ekr

---

From: Vipul Gupta <[email-masked]>
Date: Wed, 31 Oct 2007 16:03:51 -0700

vipul

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 31 Oct 2007 17:12:19 -0700

At Wed, 31 Oct 2007 15:13:28 -0700,
> need to break 100,000 ephemeral RSA keys to achieve the same

This isn't necessarily the threat model. I don't consider the
major objective of PFS to protect against large scale computation
attacks but against targeted attacks on specific data flows after
the termination of those flows. E.g., the FBI subpenas the server
sometime after your connection has occurred. The relevant 
issue then becomes not the number of times the key is used
but rather the length of time during which it is used. These
are of course somewhat related but not necessarily in a predictable
way. 

To see this, consider a server such as Apache, which operates
multiple independent processes. There are two ways to have an
ephemeral key with a limited lifespan: have it shared across
multiple processes or have one key per process. Obviously
in the second model a key used for 100 transactions will have
a much longer lifespan than the first.

-Ekr

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Thu, 1 Nov 2007 00:30:31 +0000

On Wed, 31 Oct 2007 17:12:19 -0700

> are of course somewhat related but not necessarily in a predictable
Add an implementation note suggesting low priority, background
generation of new keys, but only block waiting for one when the use
count threshold is reached.  (We suggested something very similar in
the JFK drafts.)

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

---

From: Mike <[email-masked]>
Date: Wed, 31 Oct 2007 20:55:56 -0700

> looking at more like a factor of 30.

I don't know.  For RSA, I use RSA_generate_key and RSA_blinding_on
to create the keys, RSA_public_encrypt and RSA_private_decrypt.
(With ephemeral RSA, maybe you don't need to turn blinding on?)
For DH I use DH_generate_key and DH_compute_key.  I don't know of
a way to tell these functions to use a certain exponent, so they
are using their defaults.

Mike