Subject: Re: [TLS] New drafts: adding input to the TLS master secret

From: Simon Josefsson <[email-masked]>
Date: Tue, 02 Feb 2010 15:30:34 +0100

I have read these two documents and believe they are generally fine.  As
far as I can tell, they are not backwards compatible with earlier
proposals.  But that is not important.

There is one thing in draft-hoffman-tls-additional-random-ext-00.txt
that bothers me: There is no requirement that additional random data is
generated using cryptographic principles.  This means the extension can
be used as a general-purpose extension mechanism to exchange data that
has meaning to, for example, some middle-ware that sits between the
client and server.

Is this the intention?  I'm assuming no, and that the
additional_random_value actually are intended to be, well, just an
additional random value.

Therefor, I would suggest that a new requirement is added:

   The client and server MUST generate the additional_random_value data
   using a secure random number generator.  [RANDOM] provides guidance
   on the generation of random values.
...
   [RANDOM]   Eastlake, D., 3rd, Schiller, J., and S. Crocker,
              "Randomness Requirements for Security", BCP 106, RFC 4086,
              June 2005.

This is similar to what's in RFC 5246 says about the random_bytes field:

7.4.1.2.  Client Hello
...
      random_bytes
         28 bytes generated by a secure random number generator.

/Simon

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 2 Feb 2010 09:38:11 -0800

At 3:30 PM +0100 2/2/10, Simon Josefsson wrote:
>proposals. 

Correct.

>But that is not important.

I believe that is the case as well. The changes only are needed if both parties agree to use a TLS/DTLS extension that need the changes, and that negotiation is completely explicit. If an implementation doesn't support any such extension, there is no reason for it to support the changes either.

>additional_random_value actually are intended to be, well, just an

Correct. That's why the document says:
   The recipient of an additional_random extension MUST NOT try to parse
   the additional_random_value.

>              "Randomness Requirements for Security", BCP 106, RFC 4086,

This is a great addition, thanks. It will be in the -01.

--Paul Hoffman, Director
--VPN Consortium

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 02 Feb 2010 20:28:00 +0100

>    the additional_random_value.

I noticed that, but as I (perhaps incorrectly) interpreted "recipient"
to mean "client or server", I was left with an uncertainty whether or
not the extension was intended for transporting data (e.g.,
authorization information) intended for middle-ware.

> This is a great addition, thanks. It will be in the -01.

That solves my issues with two documents, and I support their
publication.

Thanks,
Simon

---

From: "Brian Smith" <[email-masked]>
Date: Tue, 2 Feb 2010 14:03:05 -0600

Paul Hoffman wrote:
> >that bothers me: There is no requirement that additional random data
> >is generated using cryptographic principles.  This means the extension
> >can be used as a general-purpose extension mechanism to exchange data
> >that has meaning to, for example, some middle-ware that sits between
> >the client and server.
> >
>    The recipient of an additional_random extension MUST NOT try to
>    parse the additional_random_value.
> 
> >   The client and server MUST generate the additional_random_value
> >   data using a secure random number generator.  [RANDOM] provides
> >   guidance on the generation of random values.
> 

 (a) Why does the intro say that extensions want to mix "particular data"
into the calculation of the master secret? I think "additional random data"
would be clearer.

(b) Why does there need to be more than one kind of additional input type?
It seems like the sending side could just concatenate all the additional
input into a single "additional_input" extension before it sends it. I think
it's because this foundational work for channel binding mechanism. In that
case, the IETF should treat the this mechanism and the channel binding
mechanism as a single item to be accepted/rejected together--if channel
binding gets rejected then there's no need (AFAICT) for multiple
additional_input extensions.

(c) Besides channel binding, an implementation might support this to help
ensure a certain level of entropy was used for the pseudorandom inputs to
the PRF for calculating the master secret. Why not include the definition of
this extension in the same document, instead of requiring a separate
document to define it?

(d) Wouldn't it be better to use the normal master_secret calculations to
establish a secure channel, and then send the parameters for modifying the
master secret over that secure connection? This would reduce the amount of
data sent in the clear, so that an outside observer could not tell if/which
channels are bound together. And it would reduce DoS on the entropy source
of the PRNGs of each party, by allowing each party to authenticate the other
before processing the extension. Finally, it would keep ClientHello messages
small, which is important for improving latency.

Regards,
Brian

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 2 Feb 2010 12:19:28 -0800

>into the calculation of the master secret? I think "additional random data"

That phrase appears in the introduction to draft-hoffman-tls-master-secret-input, *not* in draft-hoffman-tls-additional-random-ext. The former is the description of how to make extensions that mix particular data into the master secret; the latter is the definition of one such extension.

>additional_input extensions.

There needs to be more than one additional input type because different parties might want to use different extensions. For example, if someone comes up with an extension for mixing in user identities (I'm using this as an example, not a suggestion), they might not want to mix in additional random. Thus, the extensions should remain separate.

And, to be clear, this is not "foundational work for channel binding mechanism". It is orthogonal to the work that has been proposed in that area. Note that the term "channel binding" does not appear in the drafts. 

>this extension in the same document, instead of requiring a separate

Pasi Eronen, the AD, preferred the two proposals be split into two separate documents.

>small, which is important for improving latency.

Again, this presumes that the purpose is channel binding, and it is not.

--Paul Hoffman, Director
--VPN Consortium

---

From: "Brian Smith" <[email-masked]>
Date: Tue, 2 Feb 2010 15:03:41 -0600

Paul Hoffman wrote:
> That phrase appears in the introduction to draft-hoffman-tls-master-
> secret-input, *not* in draft-hoffman-tls-additional-random-ext. The
> former is the description of how to make extensions that mix particular
> data into the master secret; the latter is the definition of one such
> extension.

> There needs to be more than one additional input type because different
> parties might want to use different extensions. For example, if someone
> comes up with an extension for mixing in user identities (I'm using
> this as an example, not a suggestion), they might not want to mix in
> additional random. Thus, the extensions should remain separate.

I misunderstood how the extensions work. Thanks for the clarification.
But...

> >(d) Wouldn't it be better to use the normal master_secret calculations
> to establish a secure channel, and then send the parameters for modifying
> the master secret over that secure connection? This would reduce the
> amount of data sent in the clear, so that an outside observer could not
> tell if/which channels are bound together. And it would reduce DoS on
> the entropy source of the PRNGs of each party, by allowing each party
> to authenticate the other before processing the extension. Finally,
> it would keep ClientHello messages small, which is important for
> improving latency.
> 

OK, I shouldn't have said "channel binding," but all of the concerns still
stand, AFAICT. If the additional inputs are random data then it may be OK to
send them in the clear. However, other kinds of additional inputs like user
identities would be better off protected. And, it is better not to increase
the size/processing of the hello messages required before each party gets to
see the other's certificate. If these additional inputs appear in hello
messages then the only way to protect them is with the handshake/renegotiate
anti-pattern, which makes connection latency even worse by adding more round
trips.

Any  extensions that contain non-trivial amounts of data and/or possibly
sensitive information should be transmitted after change_cipher_spec
messages--not in hello messages--whenever practical. When a hello extension
does contain non-trivial amounts of information or sensitive information,
then the security considerations section of its specification should explain
why the extension cannot be moved to after the change_cipher_spec messages. 

Anyway, please disregard my mention of channel binding. What I really meant
is that it's hard to understand and evaluate
draft-hoffman-tls-master-secret-input without seeing the definitions of the
other kinds of additional input--in particular, whether or not those kinds
of additional input are better put before or after the first
change_cipher_spec message (consequently, before or after an initial master
secret is calculated).

Regards,
Brian

---

From: Martin Rex <[email-masked]>
Date: Tue, 2 Feb 2010 22:55:06 +0100 (MET)

> why the extension cannot be moved to after the change_cipher_spec messages. 

As far as I understand, the proposals are about adding entropy into
the TLS MasterSecret computation, not about adding sensitive information.

When using an extension, that additional entropy could also be used
for deriving new keying material (connection parameters) on
TLS session resumption (because these handshake messages do exist
in the abbreviated handshake), but since the existing proposal are
specific about MasterSecret computation, that seems not to be an
issue here (session resumption does _not_ change the session's
MasterSecret).

Currently, the entropy depends on the ClientHello.Random
and ServerHello.Random (28 bytes for use available for each peer),
plus the result of the keyExchange algorithm (with plain RSA ciphersuites,
the client gets to chose/generate all that data/randomness)

In the existing TLS architecture, it is not allowed to send
any message between ChangeCipherSpec and Finished, and Finished
is also the very first message protected under the connection
parameters for the newly created TLS session based on the
sessions MasterSecret.

Before the transmission of the ClientKeyExchange handshake message,
there are no common cryptographic parameters that could be used
for protection at all.

If you wanted to get some sensitive data transfered within the
initial TLS handshake, it would have to be done after ClientKeyExchange
(and if we ever come up with a scheme to protect the client identity
in TLS already in the initial handshake, the (client's) Certificate
and ClientKeyExchange handshake message would have to change their
places in order from where they are currently sent.

What puzzles me a little is that why the existing 28 bytes of
Random in both Hello handshake messages should not be sufficient
for the purpose.  Is there problem in "compressing" large amount
of low-entropy data into that 28-byte of randomness (lack of
suitable compression function)?

Technically, I could conceive that a TLS implementation offers to
application callers a possibility to supply extra entropy that the
TLS implementation will "consume" when producing the 28 bytes
of Hello.Random.  That could be done immediately at the discretion
of every TLS implementation and not require any protocol changes
at all.

-Martin

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 2 Feb 2010 13:56:15 -0800

>change_cipher_spec message (consequently, before or after an initial master

Nothing in draft-hoffman-tls-master-secret-input prevents someone from writing an extension that uses data exchange after the change_cipher_spec message. Folks have been welcome to write such extensions before now, and will continue to be welcome to after this. This proposed protocol change is only relevant to scenarios where there is a cryptographic reason to mix inherently non-sensitive data passed before the change_cipher_spec message into the master secret.

--Paul Hoffman, Director
--VPN Consortium

---

From: Marsh Ray <[email-masked]>
Date: Tue, 02 Feb 2010 19:50:42 -0600

Paul Hoffman wrote:
> 
> This proposed protocol change is only relevant to scenarios where
> there is a cryptographic reason to mix inherently non-sensitive data
> passed before the change_cipher_spec message into the master secret.

I don't get it. (Sorry I am a little dense sometimes)

You said the data is "not sensitive" and it is sent in plain text. So an
attacker has it as soon as the endpoints do.

What does this accomplish over just hashing your extra data into the 28
byte random field? (which would not require a new protocol structure)

224 bits of from each endpoint ... is 448 bits really not enough entropy
somehow? 448 bits ought to be enough for anybody :-)

It looks to me (but IANAC) like the PRF maxes out at 672 bits of entropy
doing key block expansion (master_secret[48]*8 + 128md5 + 160sha), so
you can only effectively add 224 bits (only 50% more) from any source.

How big were you planning to make those symmetric keys anyway?

- Marsh

---

From: Martin Rex <[email-masked]>
Date: Wed, 3 Feb 2010 03:18:06 +0100 (MET)

> byte random field? (which would not require a new protocol structure)

I had the same thought.  Have the endpoints hash it into the
random fields that are sent in the ClientHellos.

Adding extra data onto every TLS handshake that will _only_ be
used during full handshake and completely useless for all session
resumptions seems like a waste.  (For large&busy servers, a
session resumption rate of >95% is desired).

> you can only effectively add 224 bits (only 50% more) from any source.

The PRF will have to do some kind of compression of all the entropy
from the inputs.

> How big were you planning to make those symmetric keys anyway?

I would prefer to _not_ call anything "key" that is going to
travel in the clear.  Personally, I always think of "keys" being
secret or even private information.   I would prefer the term
"random" or "entropy".

-Martin

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 2 Feb 2010 18:20:13 -0800

>attacker has it as soon as the endpoints do.

Of course.

>byte random field? (which would not require a new protocol structure)

You get more random bits mixed into the master secret. This gives you better cryptographic properties if your PRF has an output that is larger than 28 bytes, such as SHA-256 and SHA-384 (but not SHA-1, of course).

>somehow? 448 bits ought to be enough for anybody :-)

That's one opinion, maybe that of the people who wrote the current key mechanism. There is also an explicit assumption there that both users have good sources of randomness; if one doesn't, then it sure looks more like 224 bits total, which is not good enough for some people. This extension allows each party to introduce enough randomness to the master secret to overcome a complete failure of their peer's RNG.

>you can only effectively add 224 bits (only 50% more) from any source.

Adding 224 bits to your earlier 224 bits should, indeed, be enough for most people's security needs.

>How big were you planning to make those symmetric keys anyway?

48 bytes, as shown in the document.

--Paul Hoffman, Director
--VPN Consortium

---

From: Marsh Ray <[email-masked]>
Date: Tue, 02 Feb 2010 20:24:45 -0600

> secret or even private information.   I would prefer the term

Sorry if this wasn't clear. I was referring to the actual keys that are
used for the symmetric algorithm. Negotiating these is one of the main
goals of the handshake process.

The point is that it seems like a bit of overkill to require
more than 448 bits of entropy to generate a key for AES-128.

- Marsh

---

From: Martin Rex <[email-masked]>
Date: Wed, 3 Feb 2010 04:00:16 +0100 (MET)

> more than 448 bits of entropy to generate a key for AES-128.

The useful limit here is probably the size of the MasterSecret (48 bytes)
as Paul indicated.

I share his concern that some TLS peers (those operating in
constrained environments, like small devices, including
handheld devices like PDAs or phones) do not necessarily
have good sources of randomness.

But then, asking them to deplete their pools of randomness
with every SSL handshake and sending that data in the clear
over the network doesn't seem to improve that.

In theory, it would be OK if e.g. such a constrained client
would indicate to the server that it has little randomness
to offer (and itself send an empty extension), and the server
could then take this offer and return additional entropy in
the ServerHello when _NOT_ doing session resumption
(and ignore the extension when doing session resumption),

However, it is not clear to me how this could make up for the lack
of true entropy that goes into the keyexchange performed by the client.

-Martin

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 2 Feb 2010 19:14:13 -0800

>random fields that are sent in the ClientHellos.

This makes no sense from a cryptographic standpoint. The ClientHello has a fixed size of 28 bytes, so you have 28 bytes of randomness. Combining that with more random data, hashing, and truncating to 28 bytes leaves you with exactly 28 bytes of randomness: you don't gain anything. This isn't a protocol issue, it's a cryptographic fact.

>resumptions seems like a waste.

This is incorrect. Session resumption uses the original master key. Therefore, whatever data was mixed in to the original master key is mixed into all future keys as well. Or are you saying that the security analysis in F.1.4 of RFC 5246 is wrong in some way?

>secret or even private information.   I would prefer the term

Ah, I didn't see that Marsh meant "random input" when he said "key" there. Martin is correct about the terminology. These are *not* keys, and nothing in the draft suggests that they are.

--Paul Hoffman, Director
--VPN Consortium

---

From: Marsh Ray <[email-masked]>
Date: Tue, 02 Feb 2010 21:26:43 -0600

Paul Hoffman wrote:
>> What does this accomplish over just hashing your extra data into
>> the 28 byte random field? (which would not require a new protocol
>> structure)
> 
> You get more random bits mixed into the master secret. This gives you
> better cryptographic properties if your PRF has an output that is
> larger than 28 bytes, such as SHA-256 and SHA-384 (but not SHA-1, of
> course).
> 
>> 224 bits of from each endpoint ... is 448 bits really not enough
>> entropy somehow? 448 bits ought to be enough for anybody :-)
> 
> That's one opinion, maybe that of the people who wrote the current
> key mechanism. There is also an explicit assumption there that both
> users have good sources of randomness; if one doesn't, then it sure
> looks more like 224 bits total, which is not good enough for some
> people. This extension allows each party to introduce enough
> randomness to the master secret to overcome a complete failure of
> their peer's RNG.

Let's say the server has a perfect RNG and the client is broken Debian Etch.

The client provides 15 bits of usable entropy in the Client Hello, the
server provides 224.

RSA key exchange is negotiated.

The client generates the 48-byte premaster secret with an effective
entropy of less than 15 bits (his first handshake since power on).

Game over, right?

I think similar effects apply with DHE key exchange.

>> It looks to me (but IANAC) like the PRF maxes out at 672 bits of
>> entropy doing key block expansion (master_secret[48]*8 + 128md5 +
>> 160sha), so you can only effectively add 224 bits (only 50% more)
>> from any source.
> 

So at best there are 384 bits of entropy in play?

Assuming the server supplies his expected 224, our Debian Etch client
only has to pull together 160 usable BoE for them to hit that limit.

I do appreciate a healthy safety margin, but there is some complexity
overhead and potential security risk.

Your point about "potentially would allow an attacker who had partially
compromised the inputs to the master secret calculation greater scope
for influencing the output" is significant. Some kinds of hash attacks
let the attacker mess with the bytes earlier in the handshake by placing
colliding blocks in the Hello Extensions.

It also requires clients and servers to buffer the stuff and later
implement a sorting algorithm based on type order. Lots could go wrong
with that. Pathological sort order DoS attacks, etc.

I like the idea of increasing the available entropy on principle, but it
also looks like other internal limits are too close for an whole
extension framework to be worth the additional complexity. Hate to say
it, but it sounds like a core engineering change for a future version of
TLS to widen the path end-to-end.

- Marsh

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 2 Feb 2010 20:47:51 -0800

>entropy of less than 15 bits (his first handshake since power on).

Wrong. The master secret (the only one that matters for channel security) gets the advantage of all the randomness added by the client *and* the server. Without this extension, that is still probably acceptable for some uses; with the extension (if the server contributes more randomness), for all uses. Look again at section 8.1 in RFC 5246.

>I think similar effects apply with DHE key exchange.

Indeed. You will get half the expected randomness in the master secret.

>So at best there are 384 bits of entropy in play?

Yes.

>only has to pull together 160 usable BoE for them to hit that limit.

Or the server can contribute all that is needed, if you are using the proposed extension.

>overhead and potential security risk.

The complexity overhead is only paid for in systems that want to use these kinds of extensions. (Did I already say that?)

>for influencing the output" is significant.

So does the sentence that follows it: "Hash-based PRFs like the one used in TLS master secret calculations are designed to be fairly indifferent to the input size."

>Some kinds of hash attacks

Are you saying that that affects the HMAC-based PRF calculation in TLS 1.2? If so, this is a pretty significant flaw in TLS that no one else has noticed. Note that there have been papers by well-known cryptographers saying that the HMAC construction does not have the weakness you ascribe to it here.

>implement a sorting algorithm based on type order.

By "later" you mean "still within the same handshake sequence" and by "sorting algorithm" you mean "ascending order of two-byte numbers", yes?

>Lots could go wrong

Please explain further. The TLS spec says that you can only have one instance of an extension in a handshake. Thus, all TLS implementations today already should be looking for multiple instances of the same extension. What is left is a relatively small number of extension values, each of which has a unique two-byte number associated with it. Where does "pathological sort order DoS attacks" or "etc" come in?

--Paul Hoffman, Director
--VPN Consortium

---

From: Marsh Ray <[email-masked]>
Date: Wed, 03 Feb 2010 10:19:13 -0500

Paul Hoffman wrote:
>> The client provides 15 bits of usable entropy in the Client Hello,
>> the server provides 224.
>> 
> Wrong. The master secret (the only one that matters for channel
> security) gets the advantage of all the randomness added by the
> client *and* the server.

Sure but MitM knows all that because it's sent in the clear. The only
thing MitM doesn't know in this scenario is the private key to the
server's cert. So if the premaster secret is predictable (only 32k
possibilities or so), it doesn't matter if it's well encrypted to the
server's cert. A passive attacker can work out the master secret.

> Without this extension, that is still
> probably acceptable for some uses; with the extension (if the server
> contributes more randomness), for all uses. Look again at section 8.1
> in RFC 5246.

That's
> master_secret = PRF(pre_master_secret, "master secret",
>                     ClientHello.random + ServerHello.random)[0..47];

It doesn't matter in this case how much randomness there is in the
hellos, what matters is the unpredicatbility and secrecy of the
pre_master_secret (which is generated by the client).

Perhaps there could be more than that:

>      key_block = PRF(SecurityParameters.master_secret,
>                       "key expansion",
>                       SecurityParameters.server_random +
>                       SecurityParameters.client_random);

The master_secret could contain 384 BoE from the premaster secret
in addition to 448 from server and client random (832 BoE).

But last night (need to look at it again in the morning :-) I got the
impression that the internal structure of the PRF limited it to 672 BoE.

So, at least for plain RSA key exchange, perhaps one could get 672 BoE
going into the key block.

> Or the server can contribute all that is needed, if you are using the

It seems like that cross-checking is important. I try to think of a MitM
replacing either the client or server in the handshake.

>> I do appreciate a healthy safety margin, but there is some
>> complexity overhead and potential security risk.
> 
> The complexity overhead is only paid for in systems that want to use
> these kinds of extensions. (Did I already say that?)

OK.

>> Your point about "potentially would allow an attacker who had
>> partially compromised the inputs to the master secret calculation
>> greater scope for influencing the output" is significant.
> 
> So does the sentence that follows it: "Hash-based PRFs like the one
> used in TLS master secret calculations are designed to be fairly
> indifferent to the input size."

The hash attacks I'm familiar with don't work if the input is
constrained to be under a block or two. Allowing arbitrary length
attacker-supplied inputs makes more manipulations possible.

>> Some kinds of hash attacks let the attacker mess with the bytes
>> earlier in the handshake by placing colliding blocks in the Hello
>> Extensions.
> 
> Are you saying that that affects the HMAC-based PRF calculation in
> TLS 1.2? If so, this is a pretty significant flaw in TLS that no one
> else has noticed. Note that there have been papers by well-known
> cryptographers saying that the HMAC construction does not have the
> weakness you ascribe to it here.

I was thinking of TLS 1.0, since that's what seems to be mostly used.

This is where my authority to speak goes off a cliff. But that never
stopped me before. Anyway, it looks to me like HMAC PRF in TLS 1.0
amounts to little more than the better of the two hash functions, which
in this case is SHA-1.

> By "later" you mean "still within the same handshake sequence" and by
> "sorting algorithm" you mean "ascending order of two-byte numbers",
> yes?

Yes.

>> Lots could go wrong with that. Pathological sort order DoS attacks,
>> etc.
> 
> Please explain further. The TLS spec says that you can only have one
> instance of an extension in a handshake. Thus, all TLS
> implementations today already should be looking for multiple
> instances of the same extension. What is left is a relatively small
> number of extension values, each of which has a unique two-byte
> number associated with it.

Well, you could check for duplicated extension IDs with a hash table
data structure that is O(1) in space and time.

Sorting is a little less predictable.

> Where does "pathological sort order DoS
> attacks" or "etc" come in?

For example, once upon a time Perl used classic quicksort. Quicksort has
this worst-case of O(n**2). Sending thousands of extensions ordered in
the worst way can consume a bunch of CPU (the kind which might not be
offloaded onto crypto accelerator hardware).

I'm not saying this is a significant argument against new features in
general, only that adding new complexity adds new attack possibilities.

So it needs a bit of justification.

I'm not sure where that justification lies among the differences between
224/384/448/672/832 bits of entropy for generating 128 or 256-bit
encryption setup.

- Marsh

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 3 Feb 2010 07:53:43 -0800

>server's cert. A passive attacker can work out the master secret.

Boy, did I misinterpret your "Game over" question. I assumed you were talking about the amount of randomness in the master secret, not the amount of secrecy. OF COURSE adding public randomness to a value with low secrecy and low randomness only adds randomness, not secrecy. You can't magically generate cryptographic secrecy with public values.

If by "game over", you meant for secrecy, yes of course. The SSL world already discovered that with the Netscape SSLv2 debacle.

Let me try again: the proposal in draft-hoffman-tls-additional-random-ext is to add *randomness* to the master secret, not more secrecy. If I have said anything in the draft that makes that unclear, by all means let me know and I will fix it.

--Paul Hoffman, Director
--VPN Consortium

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 3 Feb 2010 08:06:59 -0800

>I was thinking of TLS 1.0, since that's what seems to be mostly used.

draft-hoffman-tls-master-secret-input explicitly says it is modifies TLS 1.2.

>amounts to little more than the better of the two hash functions, which

Mixing cryptographic apples and oranges may not be helpful for this discussion. Please say whether or not you think that there is a cryptographic flaw in draft-hoffman-tls-master-secret-input that applies to TLS 1.2. If there is, then there is probably an underlying flaw in TLS 1.2 by itself, and that should be discussed seriously. I suspect that there is not.

>data structure that is O(1) in space and time.

The proposal in draft-hoffman-tls-master-secret-input does not change this; the one-use-of-each-extension rule comes from the TLS 1.2 spec, not from the draft.

>offloaded onto crypto accelerator hardware).

If there are thousands of extensions that do master secret input, and you have an implementation that is able to do all those thousands, then I would agree with you. However, I believe that the complexity of adding the code for those thousands of extensions is probably higher than the complexity of your algorithm that sorts two-byte numbers

>general, only that adding new complexity adds new attack possibilities.

Ah.

>So it needs a bit of justification.

It is justified because the two sides need to know what order to add in the values to the master secret PRF calculation. If the spec had said "in the order that the extensions came in", then you would be complaining that you need to add a new data structure to remember the order that they came in. Sorting on a value that is already in the extension data seemed like a better choice, yes?

--Paul Hoffman, Director
--VPN Consortium

---

From: Marsh Ray <[email-masked]>
Date: Wed, 03 Feb 2010 11:23:17 -0500

> draft-hoffman-tls-master-secret-input explicitly says it is modifies

Oh, sorry I didn't see that wording.
I guess it's the "Updates: 4347, 5246" part.

> Please say whether or not you think that there is a
> cryptographic flaw in draft-hoffman-tls-master-secret-input that
> applies to TLS 1.2. If there is, then there is probably an underlying
> flaw in TLS 1.2 by itself, and that should be discussed seriously. I
> suspect that there is not.

I know of no flaw in TLS 1.2.

>> Well, you could check for duplicated extension IDs with a hash
>> table data structure that is O(1) in space and time.
> 
> The proposal in draft-hoffman-tls-master-secret-input does not change
> this; the one-use-of-each-extension rule comes from the TLS 1.2 spec,
> not from the draft.

Hmm, I wonder how many implementations actually do it that way?

> If there are thousands of extensions that do master secret input, and
> you have an implementation that is able to do all those thousands,
> then I would agree with you. However, I believe that the complexity
> of adding the code for those thousands of extensions is probably
> higher than the complexity of your algorithm that sorts two-byte
> numbers

Good point, we only need to sort the extensions that we successfully
negotiate and that modify PRF.

> It is justified because the two sides need to know what order to add
> in the values to the master secret PRF calculation. If the spec had
> said "in the order that the extensions came in", then you would be
> complaining that you need to add a new data structure to remember the
> order that they came in. Sorting on a value that is already in the
> extension data seemed like a better choice, yes?

Oh yes, I see the need for the proposal to specify the order.

I'm just not sure I see how the proposal helps all that much if the real
bottleneck on entropy lies deeper in the protocol.

- Marsh

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 3 Feb 2010 08:39:21 -0800

>I guess it's the "Updates: 4347, 5246" part.

Ah, good call. I agree that this should be updating whatever comes out of draft-ietf-tls-rfc4347-bis-03, not 4347. I'll fix that in the -01.

>I know of no flaw in TLS 1.2.

Whew. Good.

--Paul Hoffman, Director
--VPN Consortium

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 03 Feb 2010 21:06:08 -0800

At Tue, 02 Feb 2010 19:50:42 -0600,
> somehow? 448 bits ought to be enough for anybody :-)

Moreover, the the purpose of the random values is *not* to add extra
cryptographic strength, since they're not secret. Rather, it's to
ensure uniqueness of the handshake master secret even if the PMS is
repeated. However, the bound here is just the collision bound for the
random values, which doesn't require anything like 224 bits.

I'm not really against this extension, but I'm not aware of any
coherent security argument for it.

-Ekr

---

From: Dean Anderson <[email-masked]>
Date: Sat, 6 Feb 2010 17:20:05 -0500 (EST)

> coherent security argument for it.

Thinking it over, I have some concerns about the security implications
on the master_secret calculation.  I didn't think about this until Paul
Hoffman wanted to alter and increase the size the client and server
random numbers. I have to dispute that the client random and server
random need not be 'cryptographically random' instead of known but
random values. And I have a concern that they are not secret.  The only
entropy in the calculation is the pre_master_secret.

First, I am concerned that the entropy of the pre_master_secret is
reduced by presence of the revealed random number.  In the absence of a
perfect random number generator, the pre_master_secret and the random
number are not independent.  I think the rule of thumb is never to give
out random numbers to potential attackers if your random numbers aren't
perfectly random, and it's hard in practice to have perfectly random
numbers. So this seems like a crack in security in many implementations
that could potentially be exploited.

Second, if the pre_master_secret is the only real secret, while the
client random and server random are known, then more of the input to the
PRF is known, and thus the output of the PRF must also be more
predictable (at least due to less entropy in the dependent
pre_master_secret).  Changing the client random and/or server random to
be even larger known values seems (intuitively anyway--I'm not sure this
is the case) to impose an even more negative impact on the
predictabilitiy of the PRF output.  It seems to me like that might be a
security vulnerability, too. It has been reported that AES may be
significantly weaker than expected when some bits of the key are known.

Paul Hoffman's draft is only outside the charter because of the
admonition "In the preparation of TLS 1.2, the WG will attempt to avoid
gratuitous changes to TLS 1.1.". However, the master_secret calculation
and changes to it are in scope for the TLS working group--it is not the
case that changes are out of scope, but that the Working Group is under
instructions not to make "gratuitous changes". It seems to me that
Paul's draft circumvents this instruction.

So I think the WG should look into the calculation of the master_secret
for security weaknesses. If there is indeed a security issue, fixing
that would not be a "gratuitous change".

		--Dean

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

---

From: Eric Rescorla <[email-masked]>
Date: Sat, 06 Feb 2010 15:43:59 -0800

At Sat, 6 Feb 2010 17:20:05 -0500 (EST),
Dean Anderson wrote:
> random values. 

I'm not sure what you're disputing. Since both values are
published, the primary value of having them be cryptographically
random is to make them unpredictable in advance to the
attacker. However, I am unaware of any security analysis
that relies on this property.

>> And I have a concern that they are not secret.  The only
> number are not independent. 

Well, this isn't true for the server half of the static RSA 
cipher suites, since the server doesn't contribute to the
PMS at all.

In any case, this is an argument for *not* generating the
Random values with a cryptographic PRNG since then you
would not be leaking information about the PRNG state
in the random values.

> I think the rule of thumb is never to give

I am not aware of any such rule of thumb. In fact, this design
is a fairly standard feature of cryptographic protocols.

> significantly weaker than expected when some bits of the key are known.

This isn't how PRFs like the TLS PRF work. Adding new known
data does not dilute the existing entropy.

-Ekr

---

From: Dean Anderson <[email-masked]>
Date: Mon, 8 Feb 2010 14:29:12 -0500 (EST)

On Sat, 6 Feb 2010, Eric Rescorla wrote:

> At Sat, 6 Feb 2010 17:20:05 -0500 (EST), Dean Anderson wrote:
> > 
> > > Moreover, the the purpose of the random values is *not* to add
> > > extra cryptographic strength, since they're not secret. Rather,
> > > it's to ensure uniqueness of the handshake master secret even if
> > > the PMS is repeated. However, the bound here is just the collision
> > > bound for the random values, which doesn't require anything like
> > > 224 bits.
> > > 
> > Thinking it over, I have some concerns about the security
> > implications on the master_secret calculation.  I didn't think about
> > this until Paul Hoffman wanted to alter and increase the size the
> > client and server random numbers. I have to dispute that the client
> > random and server random need not be 'cryptographically random'
> > instead of known but random values.
> 
> I'm not sure what you're disputing. Since both values are published,
> the primary value of having them be cryptographically random is to
> make them unpredictable in advance to the attacker. However, I am
> unaware of any security analysis that relies on this property.

"cryptographically random" was a poor term. It confuses 'cryptographic
PRNG' with 'truly random' or zero-information numbers. I mean the
latter.

I'm disputing the assertion that these random numbers don't need to be
truly random.  To recast it as a positive assertion: I'm asserting these
randoms have to be either truly random or truly non-cryptographically
random; They cannot be part of a pseudo-random sequence. Particularly:  
they cannot be from the PRNG that the pre_master_secret comes from.

The primary purpose (unique master_secrets) of these random numbers is
unimportant.  If they are not truly random, they expose the
pseudo-random sequence generator sequence. This is an unintended (but
significant) consequence.

> > reduced by presence of the revealed random number.  In the absence
> > of a perfect random number generator, the pre_master_secret and the
> > random number are not independent.
> 
> Well, this isn't true for the server half of the static RSA cipher
> suites, since the server doesn't contribute to the PMS at all.

True, the server random doesn't expose the client's pre_master_secret in
that _particular_ calculation.  But the server IS still exposing its
(possibly dependent) random numbers. If you collect enough of these
through snooping, you can predict its pre_master_secret for connections
orginating from that machine. Same goes for the client machine. Server
machines tend to be both client and server at different times.

> In any case, this is an argument for *not* generating the Random
> values with a cryptographic PRNG since then you would not be leaking
> information about the PRNG state in the random values.

Yes. That's my point. By 'cryptographic PRNG' you mean a PRNG that is
hard to predict. But if you get enough of its sequence and have enough
compute power, all PRNG's are predictable.

> > I think the rule of thumb is never to give out random numbers to
> > potential attackers if your random numbers aren't perfectly random,
> > and it's hard in practice to have perfectly random numbers. So this
> > seems like a crack in security in many implementations that could
> > potentially be exploited.
> 
> I am not aware of any such rule of thumb. In fact, this design is a
> fairly standard feature of cryptographic protocols.

I'll see if I can find a better reference.  I think the cryptographic
fact I'm looking for is that a pseudo-random sequence is compromised by
having part of the sequence known. Having more of the sequence known
makes it even easier to compromise.

> This isn't how PRFs like the TLS PRF work. Adding new known data does
> not dilute the existing entropy.

For SHA-256, I agree--or at least I can't dispute that at this time*.  
But recall that extensions can specify different PRFs. Perhaps it should
be documented somewhere that adding new known data must not dilute the
existing entropy.

[*Actually, I suspect it isn't true. For the algorithm to be reversible,
certain other things have to be true.  The object of the hash function
is to be irreversible, but they all seem never to really get that
property, just the property of being hard to reverse, which doesn't
affect the properties that must be true if they are reversible. If you
assume they are reversible, and add more known data to the limited
output (which began at a maximum entropy, then entropy of the output
must be reduced. To put it another way: If you start with a lump of iron
(at maximum entropy), and beat it into an iron pot of the same mass
(known input), entropy is reduced. Knowing the exact sequence to get the
pot from the rock reveals information about the rock. But this is no
proof.]

		--Dean

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 08 Feb 2010 12:44:25 -0800

At Mon, 8 Feb 2010 14:29:12 -0500 (EST),
> significant) consequence.

With any reasonable PRNG this is not a security concern.

> orginating from that machine.

This is true only in an information theoretic sense. It is not
correct with any reasonable and reasonably seeded CSPRNG.

> compute power, all PRNG's are predictable.

This is true but irrelevant. If you have enough computing power
you can break all ciphers directly. The amount of computing
power required to reverse the PRNG is comparable if not in
excess of the amount required to break the cipher.

> having part of the sequence known.

Well, this isn't true. In fact, it's a basic design requirement
of CSPRNGs that this not be so (up to the input entropy of the
PRNG). If you have any evidence that the standard PRNGs/PRFs fall
significantly short of this requirement, this would be a result
worthy of publication in a good conference.

-Ekr

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 08 Feb 2010 12:45:04 -0800

At Mon, 08 Feb 2010 12:44:25 -0800,
> correct with any reasonable and reasonably seeded CSPRNG.

And by correct I mean "it's not computationally feasible".

-Ekr

---

From: Martin Rex <[email-masked]>
Date: Mon, 8 Feb 2010 23:59:54 +0100 (MET)

> With any reasonable PRNG this is not a security concern.

You may be looking at the problem from the wrong angle.

If there is not enough entropy to seed your CPRNG, then it is
possible to brute force the entire entropy range and check for matches
with the leaked randomness to know about the "unleaked" randomness
that goes into the client key exchange (or premaster secret for RSA).

If you want to create keying material, then you must have sufficient
entropy in order to prevent attackers from brute-forcing your entire
keyspace -- something which is possible when the implementation
(of the CPRNG an protocols using it) is fully known, and the only
unknown is the entropy that seeds the PRNG.

As soon as you have a strong enough seed of the CPRNG, there is no
more need for this extension.

So the situation is that either you have a problem, then
this extension is not going to help you (actually, if you leak
PRNG state through Hello Randoms or the data in this extension,
it gets _much_ worse), or you do not have a problem, then this
extension becomes completely unnecessary.

A TLS peer that does not have good sources of randomness (which are
necessary to seed a good CPRNG), then that TLS peer should not
leak any of that state by publishing randomness from that CPRNG,
neither through Hello.Random, nor through an extension like the
one proposed.  In those cases, it might be more sensible to use
a simple counter for the Hello.Random and fill in the gmt_time
correctly.

-Martin

---

From: Dean Anderson <[email-masked]>
Date: Mon, 8 Feb 2010 18:16:53 -0500 (EST)

On Mon, 8 Feb 2010, Eric Rescorla wrote:
> > 
> > I'll see if I can find a better reference.  I think the
> > cryptographic fact I'm looking for is that a pseudo-random sequence
> > is compromised by having part of the sequence known.
> 
> Well, this isn't true. In fact, it's a basic design requirement of
> CSPRNGs that this not be so (up to the input entropy of the PRNG). If
> you have any evidence that the standard PRNGs/PRFs fall significantly
> short of this requirement, this would be a result worthy of
> publication in a good conference.

Actually, it appears to me that it is an unproven assumption of the
next-bit test. ("it" being that there is no polynomial time algorithm to
calculate the next bit)  I believe the key phrase is "up to the input
entropy of the PRNG". If you have enough of the sequence, you can get
the whole sequence.  The TLS random exposes an essentially unlimited
amount of the pseudo-random sequence.

I don't assert any revelation about PRNG properties. I think all I have
discovered is that in TLS, one can get an essentially unlimited amount
of the PRNG sequence by mere snooping (no decryption).  The
already-known properties of pseudo-random sequences are that one can
compute the whole sequence given knowledge of an unlimited amount of the
sequence because they are not random.

The tests on for "cryptographic security" of PRBG are complicated, but
roughly summarized as based on statistical expectations for the next bit
in the sequence. The 'next-bit' test posits that there are no polynomial
time algorithms for calculating the next bit.  But this is assumed, not
proven property. It was also assumed to be true of Linear Feedback Shift
Registers, but was found false.  There is nothing that proves the PRNG
isn't predictable if you can see a whole lot of its sequence, or that
calculating the next bit is computationally infeasible given a lot of
sequence.

>From "Handbook of Applied Cryptography" Section 5.1.1 on Pseudo Random
Bit Generators:

  "The output of a PRBG is not random; in fact the number of possible
  output sequences is at most a small fraction 2^k/2^l, of all possible
  binary sequences of length l."

So one can see, as l gets larger with k constant, the fraction of all
output sequences gets smaller.  The pre_master_secret is 384 bits and
the Random value is presently 256 bits. So the random exposes 40% of the
sequence.  Paul's proposal increases the exposure. That seems like a bad
idea.  Exposing any part of the sequence seems like a bad idea.

Full enumeration of the PRBG is probably infeasible. But it is not clear
that full enumeration is necessary to predict the sequence. It wasn't
necessary to have very much of the sequence for LFSR.  It may indeed
prove to be computationally infeasible, but it not proven so far.  Some
generators may be better than others. Or not. Not so long ago, linear
feedback shift registers were thought to be computationally infeasible
to break and were the stream cipher for GSM, but then that was
discovered to be wrong, and that calculation was really pretty easy.

When all we need are unique master_secrets across sessions, this seems
like an unnecessary risk.  Why not alter TLS to require a different
pseudo-random sequence generator for Random values?

		--Dean

---

From: Dean Anderson <[email-masked]>
Date: Mon, 8 Feb 2010 19:28:26 -0500 (EST)

+5

		--Dean

---

From: Marsh Ray <[email-masked]>
Date: Mon, 08 Feb 2010 21:00:57 -0500

Dean Anderson wrote:
>> If
> next-bit test.

I think you'll find that all cryptography rests on assumptions that
aren't "proven" to some arbitrarily high standard.

> ("it" being that there is no polynomial time algorithm to
> calculate the next bit)

Starting with good old http://en.wikipedia.org/wiki/P_versus_NP_problem
of course.

> I believe the key phrase is "up to the input

I don't see where you get that. RFC 2246 says:
> Client hello

To me that does not permit a conforming implementation to "expose an
essentially unlimited amount of the pseudo-random sequence".

Any competent implementer would know that they have to keep their
secure RNG seeded to a reasonable degree.

> sequence because they are not random.

Perhaps the problem here is that the TLS RFCs are a bit loose with the
"secure RNG" "PRNG" and "PRF" labels? The RFC seems to jump between them
expecting readers to be familiar with the construction and seeding of a
secure RNG. Sounds like a reasonable assumption to me.

IMHO, the details of establishing a secure RNG are out of scope for the RFC.

> calculating the next bit is computationally infeasible given a lot of

There's nothing that "proves" anything is random to some
arbitrarily-high standard. Indeed, literal religious schisms have been
based on disagreements about the determinism of the universe.

Rather than waste all that energy debating it all over again, you could
just post back here when you've got a useful result. Something like this:
http://travisgoodspeed.blogspot.com/2009/12/prng-vulnerability-of-z-stack-zigbee.html

> the Random value is presently 256 bits. So the random exposes 40% of the

2^256 / 2^384
is not anything like 40%. Looks to me like it's about
0.00000000000000000000000000000000000003%

> Paul's proposal increases the exposure. That seems like a bad
> like an unnecessary risk.

You haven't identified an actual weakness, only asserted that there
could be one.

> Why not alter TLS to require a different

I didn't design it of course, but I would say it's because the actual
input entropy is assumed to be finite and by is impossible to measure
accurately. Dividing it between two separate pools would probably end up
diluting it in one or the other.

For example, many OSes collect and pool entropy in the kernel where it
can be shared by all applications. This is essentially the opposite of
your suggestion.

- Marsh

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 08 Feb 2010 19:27:01 -0800

At Mon, 8 Feb 2010 23:59:54 +0100 (MET),
> that goes into the client key exchange (or premaster secret for RSA).

Yes, I'm aware of this fact. In fact, see [YRS+09] for a worked example.

> a simple counter for the Hello.Random and fill in the gmt_time

It's not clear to me that avoiding leakage of any PRNG output helps
that much, since an attacker who knows the potential outputs of the
PRNG can simply do trial decryption to see if the projected outputs
produce correct decryptions. The reason it helps in the example above
is that you need to track the evolution of the PRNG through multiple
requests. However, this seems like a fairly unusual case. It 
would not, for instance, likely apply to clients, which only
maintain a small number of PRNG contexts.

In general, if you have an acceptable amount of entropy you
don't need to worry about leaking PRNG output. If you don't
you really don't have any business doing TLS.

-Ekr

[YRS+09] S. Yilek, E. Rescorla, H. Shacham, B. Enright, and S. Savage
"When Private Keys are Public: Results from the 2008 Debian OpenSSL
Vulnerability", In Proceedings of IMC 2009, pages 15?27. ACM Press, 
Nov. 2009.

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 08 Feb 2010 19:38:02 -0800

At Mon, 8 Feb 2010 18:16:53 -0500 (EST),
> amount of the pseudo-random sequence.

Again, this is the distinction between information theoretic security
and security based on complexity-theoretic assumptions.  Effectively
all cryptography (with the exception of one time pads) only offers
security up to at best complexity theoretic bounds.

As a non-PRNG example, given a small number of plaintext/ciphertext
pairs it is in principle possible to derive the AES key that performed
the encryption. However, if this were possible to do in less than
2^{k} operations (where k is the size of the key) than this would
constitute a severe weakness in AES.

Similarly, in principle with unlimited computational power one can
derive the PRNG state from the output, as long as the output is longer
than the PRNG internal state. However, in a properly designed PRNG,
actually reversing the state of the PRNG should be computationally
infeasible. (And given that PRNGs are generally based on 
a similar set of cryptographic primitives [e.g., message digests])
it's not crazy to think that PRNGs indeed do have these properties.
If one has a PRNG which does not meet this property, it would be
better to fix that, rather than worry about all possible ways
in which output could leak.

-Ekr

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 08 Feb 2010 20:52:12 -0800

At Mon, 08 Feb 2010 19:27:01 -0800,
> you really don't have any business doing TLS.

This wasn't well phrased. If you're a TLS server and you
just do static RSA, then it is safe to do TLS even without
a good source of entropy. On the other hand, if you're doing
DHE or you're a TLS client doing static RSA, then it's pretty
hard to have a secure system unless you can muster enough
entropy to make exhaustive search of the entropy space
imdeasible.

-Ekr

---

From: Martin Rex <[email-masked]>
Date: Tue, 9 Feb 2010 15:54:33 +0100 (MET)

Eric Rescorla wrote:
> 
> At Mon, 8 Feb 2010 23:59:54 +0100 (MET), Martin Rex wrote:
> > 
> > Eric Rescorla wrote:
> > > 

The issue has come up several times.

I remember this one (Netscape-Browser, SSL session encryption, 1995):
http://marc.info/?l=bugtraq&m=87602167418753&w=2

The problem with debian was more severe for the servers, because the
lack of randomness persisted in the rsa keypairs of the server certificates,
i.e. lack-of-protection for the key-exchange rather than lack of
entropy in the the client-generated premaster secret.

> maintain a small number of PRNG contexts.

I agree that it does not help that much, only making the exhaustive
search of the entropy space more cpu-intensive (similar to the
iteration count on string-to-key operations for PBE).

My primary concern is with the reasoning behind the extension,
what has been given does not seem to improve the situation at all.
If anything, this extension could make the problem slightly worse.

> 
>                                  If you're a TLS server and you
> infeasible.

I would be careful with such a statement.  The most difficult
part about the OpenSSL debian problem wasn't about getting OpenSSL fixed,
it was about replacing all the low-entropy keypairs / server certificates
that had been generated.  The majority of Browsers, and therefore the
entropy in the RSA premaster secrets, did never have this particular
Debian randomness problem. Sessions were affected through the
lack-of-protection on the TLS key-exchange (RSA premaster secret encrypted
with a low-entropy server key).  So if you have a TLS server without a
good source of entropy, you definitely should create the server's keypair
someplace else and transfer both, server key and cert onto that device
rather than having the device create its own keypair.

-Martin

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 09 Feb 2010 08:38:10 -0800

At Tue, 9 Feb 2010 15:54:33 +0100 (MET),
> rather than having the device create its own keypair.

Yes, of course.

-Ekr

---

From: Marsh Ray <[email-masked]>
Date: Tue, 09 Feb 2010 12:24:34 -0500

Eric Rescorla wrote:
> This wasn't well phrased.

I liked it.

> a good source of entropy.

It's only safe to that one narrow perspective. Other things:

Did you generate a cert signing request on that box?
The server SSH keys?
Is SSH using DH?
Were stored passwords well-salted?
Is DNS as used by that box vulnerable?
TCP initial sequence numbers broken?
Etc.

- Marsh

---

From: Dean Anderson <[email-masked]>
Date: Tue, 9 Feb 2010 13:22:27 -0500 (EST)

I agree with Martin Rex, I think a counter should be used instead of a 
random number.

Inline

> secure RNG seeded to a reasonable degree.

Actually, secure RNG isn't always an implementer decision, but an
operations option. For example, Apache has an option to turn off the
waiting on the secure random generator.  Otherwise, it hangs until it
gets enough entropy. I suspect there may be a lot of apache sites
without sufficient entropy.

> > From "Handbook of Applied Cryptography" Section 5.1.1 on Pseudo
> > Random Bit Generators:
> > 

You are misreading what I wrote. The number above is the fraction of all
possible sequences of length 384 that can be generated by a PRNG seeded
with 256 bits of entropy. As you note, its a very small fraction.  In
fact, its no more than the original entropy.

However, the 40% referred to:

  640 bits are taken from the PRNG:
     because pre_master_secret (384) + client.random(256) = 640

  256 bits are exposed to the sniffer. 256/640 = .4

So 40% of the sequence bits are exposed to sniffers.  I assume the
sniffer can see every TLS connection.

For LFSR, I /think/ 40% was enough to recover the whole sequence (fact
check, I'm not sure).  So, it might be plausible that this amount might
be enough to recover the pseudo random sequence, too. Particularly if
there isn't suffient entropy in the key to start with.  The 256 bits of
exposed random give an attacker a means to check on the state of the
PRNG.

> You haven't identified an actual weakness, only asserted that there

Yes.  I haven't identified a purely cryptographic weakness. I haven't
found a break in sha256, particularly not if a sufficient amount of key
entropy is used. And if everyone strictly follows total secure practices
on key entropy and there are no sha-1,md5 similar breaks in sha256, then
indeed there is no purely cryptographic problem.

But in practice, there isn't always sufficient entropy for secure RNG.
In that case, there is a crucial exposure of sequence bits that doesn't
need to happen.

If one didn't expose all those bits from the PRNG, there wouldn't be a
break on the PRNG even with less entropy: There would be no way to test
bits from the PRNG to find its state.

I'd say what I've exposed is a design flaw in the way crypto is being
used, not a purely cryptographic weakness.  My assertion comes down to
this: If PRNG bits aren't exposed to sniffers, they can't be exploited
by snifffers. So lets not expose PRNG bits.

> > Why not alter TLS to require a different pseudo-random sequence
> > generator for Random values?
> 
> accurately. Dividing it between two separate pools would probably end
> up diluting it in one or the other.

I agree. A counter should be used, not another PRNG.

> can be shared by all applications. This is essentially the opposite of

Yes. That is the best of a bad choice, too.  The pool was used because
its hard to collect sufficient entropy. But allowing others to get bits
from the pool opens a way to reduce entropy available and cause servers
to either wait (or proceed without sufficient entropy).  The way TLS is
currently arranged, TLS really screws those who don't have sufficient
entropy all the time. And TLS _might_ still screw those who do.

		--Dean

---

From: Marsh Ray <[email-masked]>
Date: Wed, 10 Feb 2010 22:57:27 -0600

> I agree with Martin Rex, I think a counter should be used instead of a 

IMHO, the solution to the design problem of insufficient entropy is not
to use a sequence counter.

> without sufficient entropy.

Unless the documentation is misleading, they deserve what they get.

In particular, they'd better hope the administrator of the other peer
wasn't hoping to freeload on the random data contribution, too.

> sniffer can see every TLS connection.

If that represents a problem, then either there was really lousy seeding
or really interesting attack on the PRNG.

If I used AES-128 to transfer (128*.40) = 51 bits of plaintext known to
the attacker, should I be concerned that he can recover the key?

How does the method used to generate the IV factor in?

How does the method used to generate the MAC secret factor in?

What if I need to transfer 8 Kbits of known plaintext at the beginning
of the connection? How much entropy would need to feed into the key
material in order to be safe?

I don't have solid answers to these.

> check, I'm not sure).

My impression is that an LSFR is greatly inferior to the PRNG which is
built from repeated HMACs with MD5 and SHA-1.

> So, it might be plausible that this amount might
> be enough to recover the pseudo random sequence, too.

Anything might be plausible.

To me, it's far more plausible that, if some of the random data were
replaced by sequences, people would very easily shoot themselves in the
foot with some obscure misconfiguration. Not needing that random data is
only safe in a very specific situation. Admins are used to configuring
these things, and the actual parameters are not known by both sides
until after the random has been sent.

Ideally it would not be trusted until after the Finished messages have
been validated.

> Particularly if

I'm a fan of continual seeding as entropy becomes available.

Are there really important systems with no chaotic interrupts or other
sensors and no high-precision timers which also need to perform TLS
handshakes?

Maybe some embedded system somewhere? These days even the smallest
microcontrollers have an abundance of timers and IO pins and often
several A/D inputs.

> But in practice, there isn't always sufficient entropy for secure RNG.

I am concerned that permitting that case (i.e., trying to make it valid
in retrospective analysis) is unwise. It is likely to violate some
implicit and under-documented assumptions made in the design of SSL/TLS.
(Not to mention the cryptosystems above and below it on the protocol
stack and services on the same OS kernel).

> by snifffers. So lets not expose PRNG bits.

Why stop there? Doesn't that also apply to any ciphertext generated from
not-perfectly-random plaintext?

>> Dividing it between two separate pools would probably end

Which is the ultimate form of dilution in one pool.

> from the pool opens a way to reduce entropy available

I understand the entropy pool depletes over time, in theory.

But it intuitively seems like a pool that had a healthy amount of
entropy merged in (I'm thinking a thousand or more bits) with a strong
mixing function can be expected hold up well. Particularly if a little
additional entropy is mixed in over time.

If you know of any remotely plausible attacks against a well-constructed
PRNG with 1024 bits of entropy I would like to read about them.
[cue specter of self-aware and omipotent NSA quantum computer]  :-)

For example, OpenSSL has this line:
#define ENTROPY_NEEDED 32 /* require 256 bits = 32 bytes of randomness*/

It requires that much at startup and then quits counting. It doesn't
care about deducting from the estimated entropy once the initial
threshold has been reached:
  * Once we've had enough initial seeding we don't bother to
  * adjust the entropy count, though, because we're not ambitious
  * to provide *information-theoretic* randomness.

> and cause servers
> entropy all the time.

You might as well say "TLS really screws with those who don't have a
reliable transport available".

It's just a design requirement.

It seems like you're constructing this strawman of "TLS without a
significant entropy source" then knocking him down and saying we should
modify the design for this case.

> And TLS _might_ still screw those who do.

That part I don't understand.

- Marsh

---

From: Bill Frantz <[email-masked]>
Date: Wed, 10 Feb 2010 23:05:42 -0800

>I'm a fan of continual seeding as entropy becomes available.

However, be aware of "State Compromise Extension Attacks"*. If you dribble
in new entropy a few bits at a time to a compromised PRNG, and also expose
outputs of the PRNG, an attacker can try all possible values for the new
entropy and compare them with the known output continuing the compromise of
the PRNG. If instead, you save the new entropy until a large number of
unguessable bits are available, you foil this attack.

I belong to the school that says, "Give me enough unguessable bits (e.g
256), and a way to keep them secret, I can be secure to the heat death of
the universe." I like continually reseeding in large blocks because these
two requirements may not be possible.

Cheers - Bill

* John Kelsey, Bruce Schneier, David Wagner, Chris Hall: “Cryptanalytic
Attacks on Pseudorandom Number Generators”
<http://www.schneier.com/paper-prngs.pdf>

-----------------------------------------------------------------------
Bill Frantz        | gets() remains as a monument | Periwinkle
(408)356-8506      | to C's continuing support of | 16345 Englewood Ave
www.pwpconsult.com | buffer overruns.             | Los Gatos, CA 95032

---

From: Dean Anderson <[email-masked]>
Date: Fri, 12 Feb 2010 14:29:38 -0500 (EST)

> to use a sequence counter.

The design problem is not insufficient entropy. The problem is that TLS
exposes information that does need to be exposed.  

I propose a design rule:   A PRNG should never be used to obtain a 
unique value. Instead a counter or a date should be used.

> Unless the documentation is misleading, they deserve what they get.

Your lack of sympathy is misplaced. An attack can be used to deplete the 
entropy pool. 

> until after the random has been sent.

This is odd. As you put so much trust in the security of HMAC and by
implication the SHA-256-based PRF, so you can't really argue that the
master_secret calculated by

  PRF(pre_master_secret + client.counter + "master_secret" +  
      server.counter)

is going to be any less secure than it was before with *.random's

Using a counter reveals /nothing/ about pre_master_secret.  Using a 
random reveals /something/ about pre_master_secret.  Security is 
improved by revealing /nothing/ about pre_master_secret.

> sensors and no high-precision timers which also need to perform TLS

There are indeed servers that have to wait TLS connections for entropy
to become available. And as I pointed out, that entropy pool can be
attacked. Hence the apache configuration option, the ability in Linux
kernel to continue without sufficient entropy.

> stack and services on the same OS kernel).

It is way to late to prevent that practice.  The problem is that getting
entropy is actually very hard. Timers and IO pins are often insufficient
in anycase.

> not-perfectly-random plaintext?

Yes and no.  I believe that recommendation is that one should never
encrypt the same plaintext in two different ciphers, and particularly
not the same cipher with different keys, as this exposes a differential
attack. On that condition, the information-theoretic answer is Yes.  
But you said 'not-perfectly-random, which might be different that
re-encrypting the same plaintext.

> Which is the ultimate form of dilution in one pool.

Importantly, though, it doesn't dilute the pool which the
pre_master_secret is using.  

> I understand the entropy pool depletes over time, in theory.

No, it happens in real life. If apache is configured to wait, you wait. 
Anywhere from seconds to Several minutes sometimes.

> additional entropy is mixed in over time.

One can't expand entropy. One can expand the sequence with a PRNG, but
the PRNG has the same entropy as the seed.

>   * to provide *information-theoretic* randomness.

Openssl typically starts, does one thing, and quits.  Applications that
use OpenSsl libs (like apache) continue to get new random numbers from
the kernel.

> > and cause servers to either wait (or proceed without sufficient
> > entropy).  The way TLS is currently arranged, TLS really screws
> > those who don't have sufficient entropy all the time.
> 

It doesn't. That's why it uses TCP instead of UDP.

> It's just a design requirement.

I suppose Colt might have a design requirement: "Inability to shoot foot
with gun"  ;-)  Reality intrudes. Of course, trigger safety was a good
idea.

By contrast, making the *.randoms a counter is an easy thing to do;  it
prevents the unnecessary exposure of information.

> significant entropy source" then knocking him down and saying we
> should modify the design for this case.
> 

I mean, there might be an attack against sha-256, as there was against
sha-1, md5, md4....(every mac in history has been cracked).

However, even if cracked, if its impossible to get the state of the PRNG
because you can't see any output, it wouldn't matter. pre_master_secret
could be a constant, if the constant were kept secret from the sniffer
and the sniffer didn't know it was a constant.

The sniffer needs sufficient cleartext output of the PRNG to obtain its
state.

Exposing the PRNG output gives the possibility that a sniffer can
calculate the pre_master_secret, and thus it isn't a secret.  By
removing the client.random and server.random, it becomes impossible for
a sniffer to calculate the pre_master_secret.

		--Dean

---

From: Martin Rex <[email-masked]>
Date: Sat, 13 Feb 2010 03:16:32 +0100 (MET)

> unique value. Instead a counter or a date should be used.

At some point, some of the output of the CPRNG will have to be exposed,
no matter what.  Every server will obtain the pre-master secret from
the client--encrypted with the public key of the server for RSA
ciphersuites, and that premaster secret is output from the clients CPRNG.

But leaking lots of CPRNG output in the clear in Hello.Randoms
somehow still doesn't feel right.

> Your lack of sympathy is misplaced. An attack can be used to deplete the 

What you do by publishing lots of output values from your CPRNG is
the ability for an attacker to verify that he has a correct
representation of your internal entropy pool.

The effort for an attacker to obtain a correct representation
of your entropy pool may still be computationally infeasible
if you have sufficient real entropy, and sufficient collisions
in the output values (i.e. the output values of your CPRNG are
much smaller than the size of the internal entropy pool of your
CPRNG).

IMHO, a CPRNG where the entropy depletes implies a severly broken design,
i.e. it would mean that you either perform transformations on your
entropy pool that create collisions -- or that you continually mix
in entropy-free data.

If your transformations are collision-free (and secure hash functions
should be collision free unless you "compress"), and if the data
that you add to your pool ("re-seeding" -- continously in tiny quantities,
or every n-th step in larger quantities or both), then there should
be no depletion of entropy.

If you use re-seeding, have a decent pool size (>=256 bits)
have sufficient compression on the CPRNG outputs (<=1/2 pool-size)
and sufficient entropy in your pool from the beginning,
then leaking of CPRNG outputs e.g. through TLS Hello.Random,
should IMHO _not_ be a problem.

> > I'm a fan of continual seeding as entropy becomes available.

I'm a fan of both, half of the new entropy goes in directly,
the other half is accumulated and completely refreshes the pools
entropy every once in a short while.

> kernel to continue without sufficient entropy.

That may sometimes be a lack of proper software engineering rather
than a lack of real entropy that leads to problems like this.

> pre_master_secret is using.  

The Hello.Randoms server exactly two purposes:

 (1) provide a collision-free challenge to prevent replay
     of handshakes

 (2) provide a collision-free input to key derivation when
     TLS sessions are resumed

A "simple" time_t value plus a counter may offer additional
avenues of attack (e.g. if the time_t is synced from a time-server
that listens to a traditional insecure RF-signal and performs
insufficient plausibility checks on the values on clock updates.

But you do have 28 Byte in the Hello.Randoms available for the
counter, so you could actually concatenate it from a lot of
different counter values in order to reduce the probability
of attacker-induced collisions (which many be playing time tricks
or resetting the machine/device (crashing it causing reboots or
manipulating the power/energy supply to the system).

> a sniffer to calculate the pre_master_secret.

Even a completely passive observer/attacker -- if he knows all of
the "deterministic" transformations involved (which isn't unusal for
OpenSource software) could attempt to calculate TLS session keys
for a connection and attempt to decrypt the communication.  There
is always some known data that can be used to verify whether the
initial entropy was correctly guessed -- in case a real shortage
of initial entropy makes the brute force attack on that entropy
feasible.  In that specific scenario, the publishing of CPRNG
output through Hello.Random would help the attacker.

The motivation that Paul described for the creation of this
draft sounded to me like such scenarios do, in fact, exist.
And if they do -- then I have not yet understood how this
proposal could improve the situation.

But then, I'm _not_ a cryptographer, and I also may have
misunderstood Pauls explanation.

-Martin