Subject: Re: [TLS] 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: Russ Housley <[email-masked]>
Date: Wed, 21 Apr 2010 20:18:51 -0400

Martin:

I do not agree with your summary.

The question asked was whether the TLSG wanted to take on the document.
 That answer was 'no'.

Russ

On 4/21/2010 6:05 PM, Martin Rex wrote:
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

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: Marsh Ray <[email-masked]>
Date: Thu, 22 Apr 2010 12:44:49 -0500

>> I believe more justification than that is required for Proposed

I too do not feel that this proposed Proposed Standard is a good
candidate for last call.

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

The RFCs state "TLS requires a cryptographically secure pseudorandom
number generator (PRNG). Care must be taken in designing and seeding
PRNGs." Clearly the intent here is a TLS implementation requires a
cryptographically secure true RNG, presumably built from a PRNG
initialized with sufficient entropy. Thus, there is no such such thing
as a TLS implementation without a good PRNG.

Insofar as it is the only justification for the proposed extension,
draft-hoffman-tls-additional-random-ext would appear to introduce an
endpoint-sans-entropy configuration as a supported feature of the
protocol. I don't think that could be cleanly retrofitted into the TLS
protocol at this stage.

The endpoint-sans-entropy role would have to be negotiated but AFAICT no
mechanism for doing this has been proposed. Obviously it would be a bad
thing if both endpoints thought they could be the one without a working RNG!

This negotiation would need to be strongly authenticated. Currently,
most TLS negotiated parameters (e.g. version, ciphers and macs, renego)
are exchanged in the hello messages. These are presumed by the endpoints
to not be modified by an attacker while they are used during the
handshake. Receipt of the valid Finished message retroactively
authenticates (*danger*danger*) the parameters exchanged in the hello
messages.

So what prevents the attacker from forging the Finished messages? Only
his lack of access to the MAC_secrets. (We have to assume he's
downgraded the cipher to null or something he can break.) These are
generated from the key block using master_secret, client_random, and
server_random as inputs.

Any proposed mechanism for negotiating which of the endpoints is the one
that is allowed to have a predictable RNG must be able to securely
authenticate without benefit of the client_random and server_random
inputs. The attacker may be telling both sides "hey don't bother sending
any entropy on this handshake I've got it covered".

That leaves only the master_secret input, how is it calculated? Well, it
comes from the premaster_secret and also the client_random and
server_random inputs, but again they must be assumed to now be
untrustworthy.

In the case of static DH, the premaster_secret is always the same. So
the attacker can replay a previous random to the side(s) with the
predictable RNG and arrange for this second handshake to appear to
complete successfully and re-use exactly the same keys, IVs, and
MAC_secrets as before.

But he doesn't have to generate the same Finished message. The attacker
can include some unrecognized extension with crafted data in one or both
of the hellos. It'll be ignored by the endpoint and it doesn't affect
key generation but it will change the finished message.

Now that the attacker has fixed the key and IV, he can perform
chosen-plaintext attacks against the cipher (or worse).

> even if the other side's PRNG is bad.

Without this extension, each side can supply between 224 and 256 bits of
entropy, depending on how inaccurate you want to get with the
gmt_unix_time parameter. The PRF which expands these bits has multiple
layers of redundancy and perhaps even overkill (but in a good way).
"224 bits ought to be enough for anybody". :-)

Even an offline birthday attack on something that size is likely to be
forever impractical.

I'm all for adding entropy to RNGs in general. But in this case does not
sound to me like a good tradeoff to spend any additional protocol
complexity just to contributing more of it in effectively the same
manner as the current 224 bits.

> If a side with a bad PRNG adds its

Where it hurts is when an implementation's security analysis depends on
that effect.

> establishment might have similar properties as static-static

The problem is that in TLS these things are negotiated in the handshake
and the attacker gets to choose most of the inputs into the negotiation
up until the Finished messages are exchanged and validated. So the
attacker gets his choice of the _weakest_ of all supported key exchange
and MAC schemes of the client and server (individually) in attacking the
handshake. Scary, isn't it?

- Marsh

---

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: Marsh Ray <[email-masked]>
Date: Mon, 26 Apr 2010 12:12:36 -0500

> they are sent in cleartext) then this extension is completely orthogonal

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.

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
--

---

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

> 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: Dean Anderson <[email-masked]>
Date: Mon, 26 Apr 2010 14:04:59 -0400 (EDT)

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

Except they aren't actaully random, they are pseudo-random.

> any to the online computation.

I would think that if attacker could do what you describe below, he
could mount an attack on your pseudo-random number generator using the
(now) exposed output.  But I'm not really sure.

I am pretty confident that every crypto act that isn't founded in theory
and absolutely necessary, actually makes things worse.

The purpose of these bits are to ensure non-collision in practice. The
easiest, simplest, and least-information-leaking means of achieving that
is to use a counter.  More complication and pseudo-random bits doesn't
help achieve that purpose any more effectively, and leaks information
that might be used by the attacker, somehow, someday.  A counter cannot
be used by the attacker.  And if you think it could be, then pick the
initial counter value pseudo-randomly and count up from there (exposing
at most 1 set of bits per reboot)

> 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?
> 
> 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

-- 
Av8 Internet   Prepared to pay a premium for better service?
www.av8.net         faster, more reliable, better service
617 256 5494

---

From: Marsh Ray <[email-masked]>
Date: Mon, 26 Apr 2010 14:04:29 -0500

http://tools.ietf.org/html/rfc2246 :
> 7.4.1.2. Client hello
> 
> [...]
>
>    random_bytes
>        28 bytes generated by a secure random number generator.

Not pseudorandom, "generated by a secure random number generator".

- Marsh

---

From: Michael D'Errico <[email-masked]>
Date: Mon, 26 Apr 2010 12:47:01 -0700

> Not pseudorandom, "generated by a secure random number generator".

No, if you look at the implementation notes in RFC 5246, you will see that
it really is meant to be pseudo-random:

    Appendix D.  Implementation Notes

    D.1.  Random Number Generation and Seeding

       TLS requires a cryptographically secure pseudorandom number generator
       (PRNG).  Care must be taken in designing and seeding PRNGs.  PRNGs
       based on secure hash operations, most notably SHA-1, are acceptable,
       but cannot provide more security than the size of the random number
       generator state.

A server especially would not want to use an RNG (over a PRNG) since an
attacker could rob it of all its entropy by sending a flood of bogus
ClientHellos.

In my own implementation, the only place I use a true RNG is when a client
generates an RSA premaster secret.  (It may also get used in EDH when
generating private keys, but that happens internal to OpenSSL, and I haven't
looked at that code.)

Mike

---

From: Dean Anderson <[email-masked]>
Date: Mon, 26 Apr 2010 16:21:05 -0400 (EDT)

> Not pseudorandom, "generated by a secure random number generator".

Unfortunately, my CRC handbook is packed up at the moment. I think 
this is right: From
http://www.sunny-beach.net/random_numbers/manual/173.htm

   1. The random numbers should pass statistical tests of randomness.
   2. It should be difficult to predict the output of the random number 
generator from observing some previous outputs of the random number 
generator.
   3. It should be difficult to create the same operating conditions as 
the random generator and then duplicate previously produced output.

Most implementations use a PRNG with hopefully these properties.  I just
read an article on phase-space analysis that shows that many PRNG's that
pass (1) above actually fail at (2) and (3).

Most people don't have access to truly random numbers.  PC's and most
computers don't even have the capability to even get truly random
numbers without some kind of extra hardware.

So where are these non-pseudo, truly secure random numbers going to come
from? I think Nowhere, they don't usually exist in practice, except
maybe at the NSA.

		--Dean

---

From: Nicolas Williams <[email-masked]>
Date: Mon, 26 Apr 2010 15:38:32 -0500

How is the sub-thread on RNGs and PRNGs relevant here?  If nodes don't
have good enough RNGs/PRNGs/seeds then draft-hoffman-tls-additional-
random-ext won't help.  If they do have good enough RNGs/PRNGs/seeds
then the existing client and server randoms are good enough.  Either way
draft-hoffman-tls-additional-random-ext adds nothing.  Or, what am I
missing?

(The RNG discussion is worth having, don't get me wrong, just not in
this context.)

Nico
--

---

From: "Kemp, David P." <[email-masked]>
Date: Mon, 26 Apr 2010 16:53:43 -0400

-----Original Message-----
From: Of Dean Anderson

> from? I think Nowhere, they don't usually exist in practice, except

http://en.wikipedia.org/wiki/Hardware_random_number_generator
http://en.wikipedia.org/wiki//dev/random

---

From: Marsh Ray <[email-masked]>
Date: Mon, 26 Apr 2010 16:18:33 -0500

Taking [email-masked] off of CC list as this seems to be very TLS specific.

> it really is meant to be pseudo-random:

I believe this wording is particularly unfortunate and needs to be fixed.

Perhaps Ekr will weigh in on this?

Here's my interpretation:

>       (PRNG).

Yes, it does.

Note that this does not modify the definition of random_bytes as
"28 bytes generated by a secure random number generator."

> Care must be taken in designing and seeding PRNGs.

Yes, it must.

Note the term "seeding".

> PRNGs

None of this is literally untrue, but the placement of this whole
paragraph seems to confuse the RNG/PRNG distinction.

I believe it was expected that the reader would understand that a True
RNG was being talked about. It seems to be taken for granted that this
will follow the conventional implementation of as pool of bits
containing sufficient entropy which is stirred by a strong
hash-function-based PRNG.

Places in the spec that need the "pseudo" generator define a
"pseudorandom function (PRF)" and use that term. The TLS 1.1 spec
refererences:
>    [RANDOM]   Eastlake, D., 3rd, Schiller, J., and S. Crocker,
>               "Randomness Requirements for Security", BCP 106, RFC 4086,
>               June 2005.
which I intend to read immediately.

> attacker could rob it of all its entropy by sending a flood of bogus

You need a good true RNG to implement TLS securely.

You shouldn't worry about it "running out of entropy". That it won't is
inherent in the definition of "good true RNG" as a primitive operation.
Another way of saying it is: if you're worried about running out of
entropy then fix your RNG, don't weaken the protocol implementation.

If you dump enough entropy* in the pool and stir it and extract it using
a strong hash function, the attacker can't reverse its state. This
fascinating topic is treated at length in "the literature" and I learned
a lot last time this thread came up.

*I think we've established that 2**224 is "probably enough".

> generates an RSA premaster secret.

Are you saying that your client_hello and server_hello are predictable?
Better fix that.

On 4/26/2010 3:38 PM, Nicolas Williams wrote:
> How is the sub-thread on RNGs and PRNGs relevant here?

The draft was said to strengthen some properties of the protocol,
particularly entropy in the RNG. In order to evaluate the draft, we need
to agree on what those properties are supposed to be and how they affect
the different protocol structures.

It looks like the TLS RFCs are a bit unclear. From the comments, it
would appear that not all implementers have interpreted the spec in the
same way as it relates to true RNGs, PRNGs, the PRF, etc.

- Marsh

---

From: Nicolas Williams <[email-masked]>
Date: Mon, 26 Apr 2010 16:36:34 -0500

> Taking [email-masked] off of CC list as this seems to be very TLS specific.

This is an IETF LC, not a WG LC; IETF LC comments should be sent to
[email-masked].  If anything, we might want to drop [email-masked].

> the different protocol structures.

By analogy to legal review, if we don't need to reach the issue, then we
don't need to discuss it.

RNG/PRNG matters either apply, in which case we can might in, or they
don't.  I believe it is correct to assert that we don't need to discuss
[P]PRNGs in detail, or even at all if we agree that the existing TLS
client_random and server_random fields are sufficient.

Thus ISTM that we should first consider either whether the client_random
and server_random fields are sufficient _assuming_ compliant [P]RNGs or
consider how draft-hoffman-tls-additional-random-ext can ameliorate TLS
implementations that have poor [P]RNGs.

Ah!  Perhaps what's happening here is that Paul intends for the
additional random inputs to be provided by the _application_, from
outside the TLS implementation.  In that case an application could make
secure use of TLS even when the underlying TLS implementation has a poor
[P]RNG.  That would make draft-hoffman-tls-additional-random-ext much
more interesting (combined with some editing I'd drop my objections).
Paul?

Nico
--

---

From: Marsh Ray <[email-masked]>
Date: Mon, 26 Apr 2010 17:10:35 -0500

> [email-masked].  If anything, we might want to drop [email-masked].

That makes sense.

> implementations that have poor [P]RNGs.

I think the current space in the protocol of 224-256 bits in each
direction is sufficient. Well-known techniques exist for compressing
whatever format of entropy is available into that space.

> more interesting (combined with some editing I'd drop my objections).

But that facility could be provided by the implementation API without
any need to extend the TLS protocol. Indeed, OpenSSL provides a function
to contribute entropy into its RNG.

Thus I do not think draft-hoffman-tls-additional-random-ext should be
advanced as a standard.

- Marsh

---

From: Nicolas Williams <[email-masked]>
Date: Mon, 26 Apr 2010 17:15:47 -0500

> to contribute entropy into its RNG.

There is a lot of inertia in installed base.  If there are
implementations that allow for arbitrary extensions then Paul would have
acase.  However, I suspect there are not; unless I'm missing something

Nico
--

---

From: Michael D'Errico <[email-masked]>
Date: Mon, 26 Apr 2010 17:53:48 -0700

Here are all the places within my code that generate random
values and whether they are purely random or pseudo-random
(via a CPRNG):

     RNG    generate RSA premaster secrets
     RNG    generate encryption key and HMAC secret used
            for session ticket protection

     CPRNG  generate (part of) session IDs
     CPRNG  generate initialization vectors

     CPRNG  generate hello random values
     CPRNG  generate random premaster secret in server (as
            part of defense against Bleichenbacher attack
            and version rollback detection)

These last two are debatable.  Marsh would have the hello
randoms be purely random, not just unpredictable, and the
OpenSSL implementation uses a CPRNG for the last one, but
has a note that it /should/ use an RNG.

IANAC, but wonder why the hello randoms would need to be purely
random, versus just unpredictable, since they go over the wire
in the clear?

Also, does anyone know why the random premaster secret should
be generated with a real RNG versus a CPRNG?

Thanks,

Mike

---

From: Dean Anderson <[email-masked]>
Date: Tue, 27 Apr 2010 06:23:13 -0400 (EDT)

> [email-masked].  If anything, we might want to drop [email-masked].

I cannot post to [email-masked], for dishonest and apparently unlawful
reasons. I won the consensus call in the PR Action, but the consensus
was fraudulently reported. But the PR Action itself is not consistent
with the legal requirements to suspend member rights in a member
corporation: The law requires a vote of the membership, and that 51% of
the membership vote for the suspension/expulsion.  There are other legal
issues (e.g. antitrust) involved with preventing corporations from
participating in a standards body, but I won't go into those here.

However, fact remains that I cannot post to [email-masked].

> don't.  

The subject of entropy of PRNGs is substance of the draft.

The only way not to reach a question about substance is to not even get
to the contents of the draft for some other reason (e.g. procedural
objection). But you have no such objection, and no reason not to get to
an analysis of the contents of draft, so there is no reason to avoid
analysis of the substance.

		--Dean

---

From: Dean Anderson <[email-masked]>
Date: Tue, 27 Apr 2010 06:25:18 -0400 (EDT)

> http://en.wikipedia.org/wiki/Hardware_random_number_generator

The link you cite above is an example of the extra hardware that most
people don't have.

> http://en.wikipedia.org/wiki//dev/random

The link you cite above isn't a truly random number generator.

		--Dean

---

From: "Kemp, David P." <[email-masked]>
Date: Tue, 27 Apr 2010 08:50:23 -0400

I'm not sure why an entropy pool would not be considered "truly random"
by any of the three criteria you cited.  If there is insufficient
physically-generated entropy (such as on an appliance with no hard
drives, no user timing input, and all other sources observable or
predictable) then the process is not applicable - it cannot create
entropy by magic.

But by what criteria would it fail to be truly random (albeit at a much
lower rate than dedicated hardware) on an uncompromised user desktop?

Dave

-----Original Message-----
From: Dean Anderson [mailto:[email-masked]] 
Sent: Tuesday, April 27, 2010 6:25 AM
To: Kemp, David P.
Cc: [email-masked]; [email-masked]
Subject: Re: [TLS] Last Call: draft-hoffman-tls-additional-random-ext
(Additional Random

		--Dean

---

From: Marsh Ray <[email-masked]>
Date: Tue, 27 Apr 2010 12:19:09 -0500

On 4/26/2010 7:53 PM, Michael D'Errico wrote:
> Here are all the places within my code that generate random values 
> and whether they are purely random or pseudo-random (via a CPRNG):

I can't find a definition of 'CPRNG'. I suspect we may be in agreement
but for use of the terminology.

> RNG    generate RSA premaster secrets RNG    generate encryption key
>  and HMAC secret used for session ticket protection
> 
> CPRNG  generate (part of) session IDs CPRNG  generate initialization
>  vectors
> 
> CPRNG  generate hello random values CPRNG  generate random premaster
>  secret in server (as part of defense against Bleichenbacher attack 
> These last two are debatable.  Marsh would have the hello randoms be
>  purely random, not just unpredictable, and the OpenSSL 
> implementation uses a CPRNG for the last one, but has a note that it 
> /should/ use an RNG.
> 
> random, versus just unpredictable, since they go over the wire in the
> clear?
> 
> Also, does anyone know why the random premaster secret should be 
> generated with a real RNG versus a CPRNG?

I read the spec as having two types of number generation sequences for
TLS implementations:

1. The pseudo-random function 'PRF'. This gets initialized/seeded with
arbitrary data, but then produces a deterministic sequence.

2. A cryptographic quality random number generator. Every bit output
represents one bit of entropy to an attacker on the network. This is a
nondeterministic sequence from the perspective of everyone outside the
implementation itself, which is not to say that there can be no
deterministic methods used in the generation of the sequence.

Because real hardware entropy sources are typically bandwidth-limited,
typically a sufficient real hardware entropy (say hundreds or thousands
of bits) will be accumulated and used to initialize the generator state.
The generator state is secret, at least as large as the needed
initialization entropy, and is advanced as output is extracted. The use
of real hardware entropy reduces the attacker to just that much brute
force guessing in attempts to find the initial state. Using hundreds of
bits of real hardware entropy makes this impractical.

The random number sequence is extracted from the state using secure
one-way functions such that the observer cannot work backwards to learn
anything about the state from the generated sequence.

In this way, a limited-but-sufficient amount of real hardware entropy
can be expanded to arbitrary length-sequences without concern for
"entropy depletion".

This assumes the chosen one-way function works as designed, or at least
any weaknesses don't affect this usage:

KELS98:
> We will treat MD5 as a random function. While there have been 
> interesting cryptanalytic results on MD5 in the last several years, 
> none of them offer an obvious way to attack the RSAREF PRNG.
> 
> [KELS98] John Kelsey, Bruce Schneier, David Wagner, Chris Hall, 
> Cryptanalytic Attacks on Pseudorandom Number Generators, March 1998, 
> available from <http://www.schneier.com/paper-prngs.html>.

As an example, initialize an AES-256 block cipher with a perfectly
random 256 bit key. Encrypt successive counter values starting with 0
("CTR mode") to obtain the random output in blocks. Any method by which
one can predict or otherwise distinguish this output stream from "purely
random bits" with less than 2**256 work represents a weakness in AES-256.

If you're using AES-256 for your TLS cipher, and the attacker knows a
weakness in it, then you might have bigger problems than the quality of
your RNG.

- Marsh

---

From: Nicolas Williams <[email-masked]>
Date: Tue, 27 Apr 2010 12:36:07 -0500

> The subject of entropy of PRNGs is substance of the draft.

If we knew what the extension was for then we could consider the
rationale for it in detail; but we don't.  The I-D is too thin.  This is
my main objection to the I-D _at this time_.

> analysis of the substance.

That's not right.  If the I-D explicitly stated that the purpose for
this extension was to strengthen TLS key exchange by adding more entropy
we could then discuss whether adding more "random" octets from the same
source could help, long, long before we got to examine the source in
detail.  The reason is that either your RNG is good enough or it's not,
and if it's not then we should assume that adding more "random" octets
to the protocol is likely to _hurt_ more than help.  The assumption in
the previous sentence is all we need to know about RNGs for this
discussion.

By analogy to legal processes, there are ways to avoid reaching an issue
that are not procedural.

Nico
--

---

From: Martin Rex <[email-masked]>
Date: Wed, 28 Apr 2010 02:42:03 +0200 (MEST)

> be generated with a real RNG versus a CPRNG?

I am not a cryptographer either, but I believe that it should
be OK to use CPRNG output for all of the uses in TLS, provided
the CPRNG starts with a sufficiently large seed (like the
equivalent of 128+ bits of real entropy) and an sufficiently
large internal pool size (256+ bits) and peridical addition
of fresh entropy to the pool.

Concerning the terminology:

  RNG   supposedly stands for a random number generator that produces
        consecutive output values that are completely uncorrelated

  CPRNG  "cryptographic pseudo random number generator"
        supposedly stands for unpredictable random values
        that are mathematically correlated to the internal
        state of the CPRNG -- which reproduces in a mathematical
        correlation of consecutive CPRNG output values.
        Output values are normally derived with a compression function
        from a significantly larger internal state in a cryptographically
        secure fashion so that it is mathematically infeasible to
        determine the internal state of the CPRNG even for a larger
        sequence of output values, but some correlation remains.

If randomness is needed for the creation of cryptographic keying
material that is larger than the CPRNG output value, then a
concatenation of consecutive CPRNG output values may leave tiny
white spots in the resulting keyspace, caused by the intrinsic
correlation of consecutive CPRNG output values.

Increasing the size of the internal CPRNG state likely reduces the
area of white spots in the resulting keyspace of concatenated
CPRNG output values.  Concatenating more CPRNG output values will
likely increases the area of white spots.

Although it might be extremely difficult to limit
a brute force keyspace search to the non-white areas for
a 3072 DSA or 4096 RSA keypair generated from concatenated
CPRNG instead of concatenated RNG output values.

For the premaster-secret and master-secret computations with
the help of the PRF, I'm more concerned about the overall
entropy than about correlation between concatenated CPRNG
output values (unless, of course, the CPRNG internal state
and output value sizes are patheticalls small (like 128/64 bits).

-Martin

---

From: Martin Rex <[email-masked]>
Date: Wed, 28 Apr 2010 03:10:42 +0200 (MEST)

> weakness in it, then you might have bigger problems than the quality of

IANAC, but I would feel very uncomfortable with such a CPRNG.

If the CPRNG internal entropy pool has the same size as the
CPRNG output value, then consecutive output values will have
an extremely strong correlation, and because of that, it is
possible, at least in theory to determine the internal state
from looking at a "comparatively low" number of the output values.

If, on the other hand, your CPRNG internal entropy pool is at least
twice as large as the CPRNG output value, and you use a cryptographic
compression function, then it requires an unrealisticly huge amount of
consecutive output values before one is theoretically able to determine
the exact state of the internal entropy pool because of the
intentional collisions during computation of output values.

Btw. I assume it is much easier to gather "the equivalent of 256 bits"
of real entropy within a 512-bit "entropy pool" than to condense it
lossless into a 256-bit value.  And if one is a little conservative
in assessing the amount of entropy, then it probably makes sense
to use an entropy pool that can hold more than the equivalent of
256-bit of real entropy instead of using a container that is
guaranteed to unconditionally crush spare entropy.

-Martin

---

From: Marsh Ray <[email-masked]>
Date: Tue, 27 Apr 2010 21:56:15 -0500

> IANAC, but I would feel very uncomfortable with such a CPRNG.

Me too! It was a thought experiment rather than an actual proposed design.

For example, if somehow the internal state were compromised (say the
hard drive was sold on Ebay) you would not want someone to be able to
work backwards to find all previous values. Using a one-way function for
advancing the state (instead of the simple 'increment' of CTR mode)
accomplishes this (provided all traces of the previous state are destroyed).

> from looking at a "comparatively low" number of the output values.

I am continually seeking education on all these points, but my
understanding is that any "correlation" that does not require knowledge
of the secret key represents a noteworthy break in AES-256.

> intentional collisions during computation of output values.

If the internal pool is 256 bits, then maybe you only need about that
much output to know the state. Assuming, that is, you have infinite
computing capability or such a great attack on the one-way function that
your work is reduced from 2**256 to something practical.

So I don't think the theoretical minimum needed to determine "the exact
state of the internal entropy pool" is really relevant if it ignores the
actual work it will take.

An analogy is sending 128 characters of ASCII using AES-128. In theory,
the attacker now knows 128 bits of plaintext (the upper bit is always 0)
and he can reliably distinguish the actual secret key among trial
candidate keys. But in practice, the entire design of AES-128 is to
ensure the attacker can do no better than trying all possible keys in
sequential order.

> lossless into a 256-bit value.

SHA-256 should do nicely. In theory.

> And if one is a little conservative

http://linux.die.net/man/4/random
Suggests that Linux uses a 4096-bit pool. Sounds like a healthy safety
factor to me.

- Marsh

---

From: Dean Anderson <[email-masked]>
Date: Wed, 28 Apr 2010 08:58:50 -0400 (EDT)

The 'entropy pool' of /dev/random in Linux isn't really random. Its
based on keyboard input and possibly other semi-random or entirely
predictable sources.

The 3 criteria are for PRNGs. I don't dispute that /dev/random meets
these criteria; only the assertion that its better than a PRNG or that
its truly random.

It fails to be truly random by depending on non-random processes that
could be identified and predicted and/or manipulated by an attacker.  I
suggest you read resources on creating one-time pads. Its very, very
hard to get truly random numbers, and without truly random numbers, your
one-time pad will fail to be 'one-time'.  There is anecdote (I don't
know if it actually happened) of a one-time pad created by rolling dice
being compromised.

		--Dean