Subject: Re: Last Call: draft-hoffman-tls-additional-random-ext (Additional Random

From: Martin Rex <[email-masked]>
Date: Thu, 22 Apr 2010 00:05:51 +0200 (MEST)

The IESG wrote:
> 
> The IESG has received a request from an individual submitter to consider 
> the following document:
> 
> - 'Additional Random Extension to TLS '
>    <draft-hoffman-tls-additional-random-ext-01.txt> as a Proposed Standard

I'm somewhat confused to see a Last Call for this proposal.

We had a discussion on this document on the TLS WG mailing list and
determined that this proposal is completely unable to achieve
the stated goal.  This extension is completely bogus.

The accompanying document draft-hoffman-tls-master-secret-input-01.txt
may have some useful purpose for some unspoken environments, but
draft-hoffman-tls-additional-random-ext-01.txt is definitely NOT among those.

-Martin

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 21 Apr 2010 15:29:06 -0700

>the stated goal.  This extension is completely bogus.

You came to that conclusion; many other folks disagreed. You stated that you thought it was not useful in some environments, namely with RSA authentication where the client has a broken PRNG. If that is the only environment you care about, then this extension is not useful. TLS is used in many other environments, of course.

--Paul Hoffman, Director
--VPN Consortium

---

From: Simon Josefsson <[email-masked]>
Date: Thu, 22 Apr 2010 00:51:57 +0200

Paul Hoffman <[email-masked]> writes:

> You came to that conclusion; many other folks disagreed. You stated
> that you thought it was not useful in some environments, namely with
> RSA authentication where the client has a broken PRNG. If that is the
> only environment you care about, then this extension is not
> useful. TLS is used in many other environments, of course.

In which environments is the extension useful?

The only motivation in the document that I can find is this:

  In some application environments, it is desirable to have the client
  and/or the server be able to input more random material in the master
  key calculation than is allowed by the fixed-length Random value.

I believe more justification than that is required for Proposed
Standard.

In particular, what I'd like to see is references to some application
environments where the extension is desirable, and the rationale why it
is desirable in that environment.

Without a rationale for when the extension is useful, it is impossible
for implementers to know when use of this extension is warranted or not.

/Simon

---

From: Martin Rex <[email-masked]>
Date: Thu, 22 Apr 2010 00:55:18 +0200 (MEST)

Paul Hoffman wrote:
> only environment you care about, then this extension is not useful.
> TLS is used in many other environments, of course.

Well, I'm sorry.

There was not a single technical argument against the determination
that this extension is completely bogus in the discussion.

It is simply impossible to make up for the lack of entropy
(= secret randomness) with the addition of any amount of
published randomness, such as this extension suggests.

Get a cryptographer to make a convincing case for the value of
this extension in TLS, otherwise this extension should *NOT* be
standardized by the IETF.

-Martin

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 22 Apr 2010 07:29:46 -0700

>for implementers to know when use of this extension is warranted or not.

The environment I described in the earlier thread is TLS with
Diffie-Hellman. I thought that saying that was sufficient, but I guess
it wasn't.

In Diffie-Hellman key establishment with static keys, even if the PRNG
of one side is bad, the resulting pre-master secret is still sound.
Neither side knows whether or not the PRNG of the other side is bad, so
each side wants to supply sufficient randomness for the master secret
even if the other side's PRNG is bad. If a side with a bad PRNG adds its
own input, it doesn't hurt the randomness of the result, but a side with
a good PRNG can bring up the amount of randomness.

I did not want to list this as the justification because there may be
other reasons to use the extension, and I don't want readers to think
that this is the only one. For example, future types of TLS key
establishment might have similar properties as static-static
Diffie-Hellman.

Does that help?

--Paul Hoffman, Director
--VPN Consortium

---

From: Martin Rex <[email-masked]>
Date: Thu, 22 Apr 2010 17:52:08 +0200 (MEST)

> establishment might have similar properties as static-static

This will need a lot of big caveats.

Static DH requires DH-certificates, something which is
within [unusual,esoteric,not-implemented] for the
installed base of TLS and CAs.

And if your low-entropy device creates the static DH keypair itself
then you are still screwed, even with this extension.

In the past there have been serious TLS security problems related
to lack-of-entropy for one of the communicating entities.

In 1995 a weakness in the TLS encryption was found in the Netscape
browser based on a lack of entropy in the randomness that was
used for generation of the RSA premaster secret.
http://seclists.org/bugtraq/1995/Sep/62

In 2008, there was an bad change made to Debian's OpenSSL distribution
which totally crippled its cryptographic number generator.
http://www.debian.org/security/2008/dsa-1571

The lack of real entropy creates security problems for (examples):

 - generation of shared secrets (session keys) for
   symmetric cryptography or keyed hashes/MACs
 - generation of asymmetric cryptographic keys (RSA,DSA,DH,EC*,...),
   e.g. for use in credentials, host credentials,
   certificates & certificate requests
 - client-side generation of TLS pre-master secrets for RSA-ciphersuites
 - key exchange with ephemeral Diffie Helman
 - DSA-signatures

so if this extension has any value, it must be tailored to
that specific purpose.  Currently, it leaves _very_ dangerous
impressions with readers and implementors.

-Martin

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Thu, 22 Apr 2010 18:01:05 +0200

> establishment might have similar properties as static-static

Maybe or maybe not. I'd prefer extensions to TLS that solve existing
issues or  augment with new functionality. If there really an issue
with TLS with static DH keys that is solved by this draft I can
understand specifying it, or better I'd prefer solving them within the
protocol and without any extensions to it. But if there no practical
issue I see no point. In the end who's really getting affected by this
proposal?

regards,
Nikos

---

From: Martin Rex <[email-masked]>
Date: Thu, 22 Apr 2010 18:24:17 +0200 (MEST)

> of one side is bad, the resulting pre-master secret is still sound.

TLS needs _more_ than the secrecy of the pre-master secret to be secure.

Snippets from rfc-5246 (TLS v1.2):

http://tools.ietf.org/html/rfc5246#section-6.2.3.2

   6.2.3.2. CBC Block Cipher

   [...]

      The Initialization Vector (IV) SHOULD be chosen at random, and
      MUST be unpredictable.

http://tools.ietf.org/html/rfc5246#appendix-F.1.1.3

   F.1.1.3.  Diffie-Hellman Key Exchange with Authentication

   [...]

   If the client has a certificate containing fixed Diffie-Hellman
   parameters, its certificate contains the information required to
   complete the key exchange.  Note that in this case the client and
   server will generate the same Diffie-Hellman result (i.e.,
   pre_master_secret) every time they communicate.

   [...]

   If the same DH keypair is to be used for multiple handshakes, either
   because the client or server has a certificate containing a fixed DH
   keypair or because the server is reusing DH keys, care must be taken
   to prevent small subgroup attacks.  Implementations SHOULD follow the
   guidelines found in [SUBGROUP].

-Martin

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 21 Apr 2010 18:14:57 -0500

The introduction of this I-D is very, very thin, and, more importantly,
there's no applicability information.  I have asked before and gotten no
additional information.  I've also suggested one use for this that the
author rejected on the grounds, IIRC, that this extension is not
intended for that use, though without addressing why the extension
couldn't be used for that use.  How are others to know whether this
extension can be used for any one particular purpose if there's no
applicability statement?

Nico
--

---

From: Paul Hoffman <[email-masked]>
Date: Fri, 23 Apr 2010 07:13:14 -0700

Hi again. It appears that people have a hard time with the additional random extension because it has limited applicability but I cannot fully state what that is. The purpose here is to help fix problems that shouldn't happen, and to be harmless when the bad situation doesn't happen. This has led some people to think that an implementer will therefore feel free to code more carelessly. I have a higher respect for TLS implementers, but maybe I shouldn't.

I am not sure that I can convince people of what seems like an obvious fact: the PRNG on a system might fail in a way that the TLS implementation cannot detect. If it could detect the failure, of course it should shut down, screaming. But lots of PNRG failures seem undetectable to the implementation but possibly detectable to an attacker. Remedying that was the motivation for these drafts. If that problem is not of interest, or is considered to induce developers to do a worse job, I can see why people would not want these drafts to move forwards.

I still believe that this extension itself is harmless in all cases, and helpful in limited ones; I have not seen anyone directly prove otherwise. Having said that, I'm of course willing to go along with IETF consensus if people think that the mere standardization of this extension will somehow weaken existing implementations.

--Paul Hoffman, Director
--VPN Consortium

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 23 Apr 2010 17:28:48 +0200

Paul Hoffman <[email-masked]> writes:

> Hi again. It appears that people have a hard time with the additional
> random extension because it has limited applicability but I cannot
> fully state what that is. The purpose here is to help fix problems
> that shouldn't happen, and to be harmless when the bad situation
> doesn't happen. This has led some people to think that an implementer
> will therefore feel free to code more carelessly. I have a higher
> respect for TLS implementers, but maybe I shouldn't.
>
> I am not sure that I can convince people of what seems like an obvious
> fact: the PRNG on a system might fail in a way that the TLS
> implementation cannot detect. If it could detect the failure, of
> course it should shut down, screaming. But lots of PNRG failures seem
> undetectable to the implementation but possibly detectable to an
> attacker. Remedying that was the motivation for these drafts. If that
> problem is not of interest, or is considered to induce developers to
> do a worse job, I can see why people would not want these drafts to
> move forwards.
>
> I still believe that this extension itself is harmless in all cases,
> and helpful in limited ones; I have not seen anyone directly prove
> otherwise. Having said that, I'm of course willing to go along with
> IETF consensus if people think that the mere standardization of this
> extension will somehow weaken existing implementations.

I disagree with your description of people's objections.  My impression
is that people actually have been arguing precisely that the draft does
not solve the problem you describe.

My main concern with the document is that the problem you describe isn't
sufficiently well explained in the document itself for implementers and
application protocol designers to understand when use of the extension
is warranted.

If the PRNG is broken, your draft does not solve the many other places
in TLS that requires a working PRNG to provide a secure protocol: key
generation, CBC IV, random record padding, etc.  If you have 5 weak
links in a chain, making one of them stronger is not terribly relevant.

I sympathize with the goals of the draft, and I believe it would help in
theoretical proofs about entropy flows in secure protocols.

I don't believe implementing and enabling the draft would have any
overall positive effect on security on the Internet when all things are
considered, therefor I'm having a problem with it going on the standards
track.

/Simon

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 23 Apr 2010 17:36:02 +0200

> Diffie-Hellman. I thought that saying that was sufficient, but I guess

People shouldn't have to read the mailing list to understand the
applicability, so please describe some environments in the document.

> a good PRNG can bring up the amount of randomness.

Are you saying that the 28 bytes of randomness provided in the client
and server hello is not sufficient?

> establishment might have similar properties as static-static

This information certainly helps, but it belongs in the document.

/Simon

---

From: Nicolas Williams <[email-masked]>
Date: Fri, 23 Apr 2010 12:12:16 -0500

> respect for TLS implementers, but maybe I shouldn't.

Why can't you add text explaining that this particular extension (as
opposed to master-secret-input generally) can only be used with certain
cipher suites and is intended only for the purpose of strengthening the
maste secret computation.  Stay away from discussions of entropy, except
to explain that any random octet strings sent in cleartext contain zero
entropy relative to attackers (since they can see it passively).

Also, if you insist on saying that this extension can add entropy, can
you explain what it does that the existing client_random and
server_random don't do?

> implementation cannot detect. If it could detect the failure, of

Irrelevant: if the random octets being sent don't add entropy (because
they are sent in cleartext) then this extension is completely orthogonal
to PRNG failures.

Incidentally, I think this I-D should specifically mention that the
extension is a client and server Hello extension, which will help
clarify for the reader that it is sent in cleartext (except for
renegotiation, but note that when used in renegotiation this extension
still adds no entropy if the same key exchange was used on the outer
negotiation).

> extension will somehow weaken existing implementations.

I do believe it's mostly harmless; I am concerned that 2^16 max octets
seems like a bit much, possibly a source of DoS attacks.  I believe it's
also useless.  As such I'm not opposed to it as an Experimental or even
Informational RFC.

I'm opposed to putting known-useless things on the Standards Track.  I
don't feel too strongly about that: if the IESG and IAB don't mind
putting known-useless things on the Standards Track, I can live with
that, provided, in any case, that the decision to do so explicitly
considers the utility of known-useless Standards.

Note that I believe that draft-hoffman-tls-master-secret-input _is_
useful, and should be on the Standards Track (even if initially there
are no uses of it also on the Standards Track).

Nico
--

---

From: Martin Rex <[email-masked]>
Date: Mon, 26 Apr 2010 19:50:09 +0200 (MEST)

Marsh Ray wrote:
> 
> On 4/23/2010 12:12 PM, Nicolas Williams wrote:
> > 
> Even though they are sent in-the-clear, the random data do serve the
> same useful purpose as the existing [cs]_random data.
> 
> (Mathemeticians and professional cryptographers should probably avert
> their eyes from the fast-and-loose reasoning which follows.)
> 
> Because they are unpredictable they make offline precomputation harder.
> I think of it as adding entropy into offline computation, without adding
> any to the online computation.

This data does add the exact same workfactor to the rightful user
than it adds to each of the attackers brute force attempts.

When you look at the two things that are done to raise the
work factor on password based encryption: random salts and
iteration count, then this data is equivalent to the
random salt.

The advantage of the random salt over the iteration count is,
that it thwarts the creation of "rainbow tables", i.e. attacks
aided by precomputed data.  The disadvantage is that it requires
persisting or exchanging more data (the random salt).

-Martin

---

From: Marsh Ray <[email-masked]>
Date: Mon, 26 Apr 2010 12:12:36 -0500

I would think that the current 224-256 bits is enough to thwart offline
attacks. The attacker would need something proportional to 2**224
storage to store the results of his precomputation, no?

Assume attacker can knock off 2**42 using rainbow table techniques (he
has a 1024 unit cluster of CPUs which can each compute one result online
every clock at 4GHz). So he needs to store something like 2**182 results
from his precomputation. Assuming 1 bit per result, probably you'd need
more. Raw HDDs are the cheapest form of mass storage today at $75/TB
(10**12 bytes?). Such a system would cost
             $ 5746858278247083218843801351813700000000000.00
today. Of course those costs are likely to decline over time.

Again, this is the cost you impose on the attacker today by simply
ensuring you use the current protocol as intended.

> also useless.  As such I'm not opposed to it as an Experimental or even

There is a danger with this proposal. In no way do I mean to suggest
that Paul has any unstated motivations here.

One aspect of saying that a data area is random is saying that the RFCs
can impose no restrictions on it. Allowing arbitrary unstructured
"random" data in the protocol opens the door for private extensions to
be added by various parties.

For example, it appears that 4 of the 32 bytes originally specified for
random data got repurposed for GMT leaving "this is GMT but the clock is
not required to be right" in the spec.

Once a few more of these accumulate in the protocol without central
coordination we end up with incompatibilities that the IETF process can
no longer prevent.

- Marsh

---

From: Nicolas Williams <[email-masked]>
Date: Mon, 26 Apr 2010 12:26:29 -0500

> same useful purpose as the existing [cs]_random data.

This is true, but those are already plenty large enough.  If the
argument is that the client and server random from the TLS hellos are
not large enough, then let's hear that argument.

> any to the online computation.

The right term for this might be "confounding" (but then, it's a term
I've only seen in use in the context of Kerberos).

> storage to store the results of his precomputation, no?

Right.

> (10**12 bytes?). Such a system would cost

2^182 bits of storage is not remotely a realistic number: it's about the
number of atoms in the Solar system (if I have my math right).

> > also useless.  As such I'm not opposed to it as an Experimental or even

Actually, I withdraw the above quoted comment: it's already the case
that a hello can bear large extensions.

> be added by various parties.

I also don't think that Paul intends that.

> coordination we end up with incompatibilities that the IETF process can

Yes, but since we do need nonces in our protocol, I think this is a
risk we have to live with.  What you are arguing for, IIUC, is that
nonces shouldn't be extremely large, but just right -- I agree with
this.

Nico
--