Subject: [TLS] 32 byte randoms in TLS1.3 hello's

From: Stephen Farrell <[email-masked]>
Date: Mon, 24 Jul 2017 16:15:10 +0100

Hiya,

I'm guessing many folks interested in TLS may have been
at the QUIC session in Prague and hence missed out on the
excellent talk by Stephen Checkoway on the juniper dual-ec
incident. (I highly recommend taking a peek at the slides [1]
or reading the paper [2] or watching the video wherever
that may be;-).

Anyway, in TLS1.3 we've gotten rid of the gmt time option
in the client and server hello, which is good, (and I do
recall that discussion) but we've also changed from:

   // RFC5246
   struct {
      uint32 gmt_unix_time;
      opaque random_bytes[28];
   } Random;

to:

   // tls1.3 -21
   opaque Random[32];

Now if some TLS1.3 deployment were affected by a dual-ec
attack, it'd seem like the -21 version of Random might be
even better than the TLS1.2 version, for the attacker.

I tried to see where that 28->32 change came from but
didn't find it (apologies if I missed that). I guess it
just ensures that the overall length of the struct is
the same.

So, a question and a possible suggestion:

Q: Why do we need 32 bytes of Random?

Suggestion: if we don't need that much, maybe we could
change the length there, (I can see that might trigger
bugs and middlebox issues) or encourage/require folks
to mask out some of those bits (e.g. with zeros or some
catchy hex encoded message about dual-ec:-).

Cheers,
S.

[1]
https://www.ietf.org/proceedings/99/slides/slides-99-irtfopen-anrp-stephen-checkoway-a-systematic-analysis-of-the-juniper-dual-ec-incident-00.pdf
[2] https://web.eecs.utk.edu/~mschucha/netsec/readings/p468-checkoway.pdf

---

From: Watson Ladd <[email-masked]>
Date: Mon, 24 Jul 2017 08:29:40 -0700

On Jul 24, 2017 8:15 AM, "Stephen Farrell" <[email-masked]>
wrote:

Hiya,

   // RFC5246
   struct {
      uint32 gmt_unix_time;
      opaque random_bytes[28];
   } Random;

to:

   // tls1.3 -21
   opaque Random[32];

Anti-kleptography is not a matter of avoiding known attacks one at a time.
The fact is that someone could add backdoor login credentials or a buffer
overflow if they can also force dual-
EC to be used.

Don't use bad prngs. And don't buy products from vendors who ship back
doors and refuse to come completely clean when confronted.

Cheers,
S.

[1]
https://www.ietf.org/proceedings/99/slides/slides-99-irtfopen-anrp-stephen-
checkoway-a-systematic-analysis-of-the-juniper-dual-ec-incident-00.pdf
[2] https://web.eecs.utk.edu/~mschucha/netsec/readings/p468-checkoway.pdf

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

---

From: Dan Brown <[email-masked]>
Date: Mon, 24 Jul 2017 16:40:24 +0000

Hmm, I'd appreciate a brief reminder* of why 1.3 needs nonces at all, given that ephemeral DH is mandated, if anybody has the time/patience. (* ok, not that I truly ever knew).

I assume that the risk of misusing the nonces, to exfiltrate keys etc, is small enough compared to other side channels to justify their added value.

  Original Message
From: Stephen Farrell
Sent: Monday, July 24, 2017 11:15 AM
To: [email-masked]
Subject: [TLS] 32 byte randoms in TLS1.3 hello's

Hiya,

   // RFC5246
   struct {
      uint32 gmt_unix_time;
      opaque random_bytes[28];
   } Random;

to:

   // tls1.3 -21
   opaque Random[32];

Cheers,
S.

[1]

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 24 Jul 2017 19:51:31 +0300

On Mon, Jul 24, 2017 at 04:40:24PM +0000, Dan Brown wrote:
> Hmm, I'd appreciate a brief reminder* of why 1.3 needs nonces at all,
> given that ephemeral DH is mandated, if anybody has the time/
> patience. (* ok, not that I truly ever knew).

Two reasons:

- The DH shares can be reused (even if this is bad practice, there is
  no requirement not to).
- There still is pure-PSK mode, which has no entropy injection apart
  from Random values.

-Ilari

---

From: Russ Housley <[email-masked]>
Date: Mon, 24 Jul 2017 12:58:00 -0400

there was a discussion of adding a statement that a fresh ephemeral key MUST be used for each session.  It was decided not to do that.  Without such a requirement, nonces are needed.

Russ

> On Jul 24, 2017, at 12:40 PM, Dan Brown <[email-masked]> wrote:
>

---

From: Colm MacCárthaigh <[email-masked]>
Date: Mon, 24 Jul 2017 10:09:34 -0700

> even better than the TLS1.2 version, for the attacker.

I think the fix for this is really at the application level; if you want
defense-in-depth against PRNG problems, it's probably best to use separate
RNG instances for public data (e.g. client_random, server_random,
explicit_IV) and for secret data (keys) so that a leak in the public data
doesn't compromise the private one. We do this in s2n, and I think
BouncyCastle does it too.

A protocol level fix probably isn't as helpful because the attacker can
make more connections and collect more data to derive more and more
information about the RNG state anyway.

-- 
Colm

---

From: Colm MacCárthaigh <[email-masked]>
Date: Mon, 24 Jul 2017 10:15:56 -0700

> doors and refuse to come completely clean when confronted.

Just yesterday DJB posted a blog post about AES-CTR-DRBG, one of the most
widely-used PRNGs, and he points out a security optimization that can be
applied to it, one that escaped years of review. The optimization only
applies if you're generating large chunks of random data, so doesn't apply
to TLS, where the chunks are small; but it's still interesting that we're
still finding improvements and problems in this area.

The PRNG sits at the very bottom of the security of TLS, and biases there
have the potential to break everything, including back in time; they could
defeat PFS and uncloak years worth of data. We don't always know what's bad
t the time that we are using it; e.g. arc4random was considered fine for
years.

I think it's wise to take some measures to handle the "Well, if it were
broken, how would we add defense in depth ...".

-- 
Colm

---

From: Dan Brown <[email-masked]>
Date: Mon, 24 Jul 2017 19:32:49 +0000

Thanks for the quick answers.

Yet more naive quick questions: ‎in the reused DH setting could a counter do the job of random nonce?‎ doesn't the record layer have an IV or nonce too? (or is that passe?).

If these questions are too naive, or too last minute, let me know and I'll withdraw them. I did look over 1.3 once, fwiw, but have since forgot the details, sorry.
  Original Message
From: Russ Housley
Sent: Monday, July 24, 2017 12:58 PM
To: Dan Brown
Cc: IETF TLS
Subject: Re: [TLS] 32 byte randoms in TLS1.3 hello's

Russ

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 25 Jul 2017 03:53:53 +0000

Colm MacCárthaigh <[email-masked]> writes:

>I think the fix for this is really at the application level; if you 
>want defense-in-depth against PRNG problems, it's probably best to use 
>separate RNG instances for public data (e.g. client_random, 
>server_random, explicit_IV) and for secret data (keys) so that a leak 
>in the public data doesn't compromise the private one. We do this in 
>s2n, and I think BouncyCastle does it too. 

I do that too.  It's also specified in the LTS draft, it's just common 
sense really.

Peter.

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 25 Jul 2017 13:20:14 +0100

> I do that too.  It's also specified in the LTS draft, it's just common 

I guess you mean this:

"
   TLS-LTS drops the requirement to generate the Client.random and
   Server.random using "a secure random number generator", typically the
   one used to generate encryption keys.  The use of a secure/
   cryptographic random number generator serves no obvious purpose (all
   that's required is a unique value), but exposes 224 bits of the
   cryptographic RNG output to an attacker, allowing them to analyse and
   potentially attack the RNG, and by extension any crypto keys that it
   generates:

   o  Implementations SHOULD NOT use the raw output from a
      cryptographic/secure RNG that's used to generate keying material
      to generate the Client.random and Server.random values.  Instead,
      they SHOULD employ a mechanism that doesn't directly expose
      cryptographic RNG output to attackers, for example by using the
      crypto RNG to seed a hash-based PRF such as the TLS PRF and using
      the output of that for the values.
"

I think something along these lines would be good advice to add
to appendix C.1 or to 4.1.2 where Random is defined.

That said, I'd still argue for an approach that a peer could
see was in use when "public" random byes aren't really needed but
fair enough if that doesn't resonate with people.

Cheers,
S.

---

From: Joseph Lorenzo Hall <[email-masked]>
Date: Tue, 25 Jul 2017 13:52:23 -0400

> or reading the paper [2] or watching the video wherever

Video of Steve's talk in the IRTF Open session is here and Steve
begins around 52:15:

https://www.youtube.com/watch?v=JRneMj7LX8U&list=PLC86T-6ZTP5jdbiwi5ggLNnwLn1-r0M4h&t=52m15s

-- 
Joseph Lorenzo Hall
Chief Technologist, Center for Democracy & Technology [https://www.cdt.org]
1401 K ST NW STE 200, Washington DC 20005-3497
e: [email-masked], p: 202.407.8825, pgp: https://josephhall.org/gpg-key
Fingerprint: 3CA2 8D7B 9F6D DBD3 4B10  1607 5F86 6987 40A9 A871

---

From: Christian Huitema <[email-masked]>
Date: Tue, 25 Jul 2017 12:02:47 -0700

> to appendix C.1 or to 4.1.2 where Random is defined.

I am not sure that this recommendation is practical. For one thing, it
conflicts with the general advice that developers should not invent
their own PRNG, and should use a good crypto RNG when available. Also,
when we make such a recommendation in the TLS spec, we can hope that it
will be heeded by the TLS developers, but what about the developers of
applications and protocols sitting on top of TLS, such DTLS, QUIC or HTTP?

We want defense in depth, but in TLS 1.3 we mostly want to defend the
private [EC]DH keys. So maybe the recommendation should apply there.
Developers could for example mix the output of the crypto RNG with a
locally held secret before generating the private keys.

-- 
Christian Huitema

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 25 Jul 2017 23:57:16 +0000

Christian Huitema <[email-masked]> writes:

>For one thing, it conflicts with the general advice that developers should
>not invent their own PRNG, 

You're not inventing your own PRNG, you're using the TLS PRF, or some
equivalent (I use PBKDF2, HKDF is also nice).

>and should use a good crypto RNG when available.

You're generating public nonces, you could use SHA-1 in a loop or a CRC32 or
whatever, the values are public.  All you're doing is isolating the output of
the nonce generator from your crypto-key generator.  In fact the very thing
you absolutely don't want to use here is your good crypto RNG.

>Also, when we make such a recommendation in the TLS spec, we can hope that it

They don't need to know or care about this, it's being used to generate the
TLS nonce which is invisible to anything running over TLS.

Are we talking about the same thing here?

Peter.

---

From: Christian Huitema <[email-masked]>
Date: Tue, 25 Jul 2017 18:21:37 -0700

> Are we talking about the same thing here?

Not sure. I am looking at the implementations of QUIC. QUIC needs its
own set of random numbers for things like connection ID or initial
sequence number. The most natural thing to do is do get them from the OS
API, /dev/random or cryptogenrandom(), but that requires platform
specific code. The next natural thing to do is to reuse the random
number generator configured for the TLS context, because it is not OS
dependent. If that is not OK, then developers will need lots of explaining.

-- 
Christian Huitema

---

From: Watson Ladd <[email-masked]>
Date: Tue, 25 Jul 2017 18:32:27 -0700

On Tue, Jul 25, 2017 at 6:21 PM, Christian Huitema <[email-masked]> wrote:
> Not sure. I am looking at the implementations of QUIC. QUIC needs its own
> set of random numbers for things like connection ID or initial sequence
> number. The most natural thing to do is do get them from the OS API,
> /dev/random or cryptogenrandom(), but that requires platform specific code.
> The next natural thing to do is to reuse the random number generator
> configured for the TLS context, because it is not OS dependent. If that is
> not OK, then developers will need lots of explaining.

Why not write a cross-platform shim that calls the underlying OS
specific API, instead of implementing another broken RNG?

I feel the solution to broken RNG is don't use them. This entire
discussion is premised on an idea that anything can be done about this
"problem".

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Peter Gutmann <[email-masked]>
Date: Wed, 26 Jul 2017 12:11:51 +0000

Christian Huitema <[email-masked]> writes:
 
>Not sure. 

OK, I'd say we are :-).  This isn't about which PRNG or randomness source to
use but the need for a separation between PRNG-for-secret-values and PRNG-for-
public-values.  In particular you don't want to feed large amounts of output
from your PRNG-for-secret-values to an attacker for analysis via nonces,
client/server randoms, and other things, in case they can use that to attack
your PRNG state.

The prime example of this is the EC-DRBG fiasco, which relied on the attacker
seeing the client/server random just before the same PRNG was used to generate
the master secret.  If the client/server random had come from PRNG instance #1
and the master secret from PRNG instance #2, it would have been... well, still
a bad PRNG, but not as catastrophic a failure.

So the advice was to seed the public-PRNG from the private-PRNG and use the
public-PRNG for nonces, sequence numbers, and so on, and the private-PRNG for
encryption keys and the like.

Peter.

---

From: [email-masked] (Martin Rex)
Date: Wed, 26 Jul 2017 15:22:39 +0200 (CEST)

> encryption keys and the like.

Whenever you're using "some" CPRNG as a black box, you should very probably
take 4x to 16x of CPRNG native output size and run it through a cryptgraphic
compression function (such as a secure hash or PRF) to produce 1x output
size (a) as a safety precaution and (b) to obtain reasonable entropy.

Just look at the Intel RDRAND fiasko.  It isn't just a bad design, it
is a clearly documented bad design.  They openly admit that they're
artificially inflating the output by factor of 2x, i.e. that an output
of 256 bits is based on entropy of _at_best_ 128 bits.

Since you also have no idea whether and how the internal hardware design
behind Intel RDRAND is backdoored, you should not be using any of its
output without an at least 10x cryptographic compression in any case.

-Martin

---

From: Colm MacCárthaigh <[email-masked]>
Date: Wed, 26 Jul 2017 09:06:18 -0700

> output without an at least 10x cryptographic compression in any case.

Obviously your CPU can fully compromise you locally, so that's not very
interesting to think about. But for remote attacks, like the one you
describe here, where an adversary may use predictable PRNG output, it is
probably better to mix RDRAND output with something else. There are a few
layers of defense here, such as multi-source NRBGs, or personalization
strings. Those significantly distance the output from the RDRAND. The kind
of compression you mention here can be easily precomputed and tables
generated by someone with a large amount of resources, since it's a pure
function.

In BoringSSL, and s2n, we mix RDRAND in as part of the reseeding. But the
initial seed came from urandom (which is not pure RDRAND). In s2n, we also
use personalization strings to provide another degree of defense.

-- 
Colm

---

From: Jeffrey Walton <[email-masked]>
Date: Wed, 26 Jul 2017 13:18:54 -0400

On Tue, Jul 25, 2017 at 9:21 PM, Christian Huitema <[email-masked]> wrote:
> ...
> /dev/random or cryptogenrandom(), but that requires platform specific code...

Somewhat related (but OT for TLS-WG): According to the Linux Kernel
Crypto folks, you should not use /dev/random because it is a
deprecated interface. You should use /dev/urandom, and it has been
recommend for the last decade or so. Also see "[RFC PATCH v12 3/4]
Linux Random Number Generator" (https://lkml.org/lkml/2017/7/20/993)
on the kernel-crypto mailing list.

The BSDs, OS X, DragonFly, and others may be different. But for Linux
the advice is clear.

Jeff

---

From: [email-masked] (Martin Rex)
Date: Wed, 26 Jul 2017 20:58:56 +0200 (CEST)

Colm MacCárthaigh wrote:
> Martin Rex <[email-masked]> wrote:
>> 

We're either talking about different things, or I fail to understand
what you're talking about.

The predictable failure of EC_Dual was based on the fact that the
internal state and the output had (almost) the _same_ size.

With RDRAND, you would use e.g. SHA-256 to compress 10*256 = 2560 Bits of
a black-box CPRNG output into a 256-bit _new_ output that you
actually use in communication protocols.

Should the creator of a backdoored black-box-CPRNG be able to recompute
the internal state from a few leaked _new_ (post-compression) outputs,
then you _will_ be able to notice a real problem (non-randomness)
problem with the outputs of black-box-CPRNG.

> use personalization strings to provide another degree of defense.

Any half-way portable crypto library will have code for collecting
entropy on pre-RDRAND Intel CPUs and non-Intel CPUs, probably use
an entropy pool that is >=512 bits and outputs of at most half of
the size of the entropy pool, and use compressed RDRAND outputs for
additional entropy gathering, and at most for nonces, but never
use RDRAND alone for generation of secret keying material.

-Martin

---

From: Colm MacCárthaigh <[email-masked]>
Date: Wed, 26 Jul 2017 12:46:36 -0700

> actually use in communication protocols.

If the relation between the RDRAND input and the output of your function is
fixed, then your attacker than just do the same thing. It doesn't help at
all really. You have to mix RDRAND with something else that is unknowable
to the attacker as part of the process.

-- 
Colm

---

From: [email-masked] (Martin Rex)
Date: Wed, 26 Jul 2017 22:57:32 +0200 (CEST)

> to the attacker as part of the process.

Through the 10x compression of the RDRAND output, which will provably
create an incredibly huge amount of collisions, the attacker will be
unable to identify any particular output values of RDRAND.

Your conceived attack could only work under the condition that
10 RDRAND consecutive outputs are always fully deterministic, and
that also the seed used by RDRAND will be fully deterministic to
the attacker -- or can otherwise be learned out-of-band by the attacker
-- while at the same time this property will remain invisible to
all external randomness tests.

Can you shed any light on how you believe and attacker could meet
such preconditions, because I'm not seeing the problem yet.

-Martin

---

From: Watson Ladd <[email-masked]>
Date: Wed, 26 Jul 2017 14:13:30 -0700

On Jul 26, 2017 1:57 PM, "Martin Rex" <[email-masked]> wrote:

Trivially.

Imagine an attack where the attacker restricts the keys used in the final
counter mode step to a 2^40 keyspace and the counter resets to 0 every 2^40
outputs.

Detecting this has happened is extremely difficult: one needs to force 2^40
rekeyings, and so execute 2^80 operations. Extra points for the 2^80 keys
being a function of cpu serial number.

An attacker though can mount a 2^80 search for the internal state across
many CPUs, and can do multitarget as well.

Sincerely,
Watson Ladd

-Martin

---

From: Colm MacCárthaigh <[email-masked]>
Date: Wed, 26 Jul 2017 14:15:27 -0700

> all external randomness tests.

I think this is pretty easy for some conceivable attacks. Suppose that your
adversary makes RDRAND a DRBG seeded with wall-clock time and device-ID.
That's going to produce deterministic output, but it will pass all of the
tests and appear to be random. If the attacker knows your device-ID, or
even just a range of possible device-IDs, they can confirm via a match.

The 10x compression would just make them do a bit more work.

-- 
Colm

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 27 Jul 2017 00:27:07 +0100

I've suggested some text for this in a PR [1]
based on what people have said in this thread.

I'm sure that can be further improved.

It might be no harm to add more pointers to that
appendix from elsewhere in the spec, and/or to
add a list of the various public/private random
numbers that are needed to that appendix. (I'd be
happy to do a pass to identify those if folks
basically like this kind of addition.)

I also need to figure out how to handle the
reference properly:-) Can do that tomorrow.

Cheers,
S.

[1] https://github.com/tlswg/tls13-spec/pull/1068

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 27 Jul 2017 15:33:54 -0700

Spec updated here;
https://github.com/tlswg/tls13-spec/commit/465de0e189b2b59090d0eac0acbc42942af9ca77

-Ekr

---

From: Dan Brown <[email-masked]>
Date: Thu, 27 Jul 2017 23:33:38 +0000

I don't think 2 CSPRNGs is a good idea.

Wasn’t there a few years back some RSA keys with separate p and q, generated independently leading to an attack...

Here if the seeds to initialize the RNGS are related, or one is weak, or worst if the seed is a raw source that doesn’t change in the moments between the two CSPRNG inits, that'd be bad, even if the CSPRNGs were good.
From: Eric Rescorla
Sent: Thursday, July 27, 2017 6:34 PM
To: Stephen Farrell
Cc: [email-masked]
Subject: Re: [TLS] 32 byte randoms in TLS1.3 hello's

Spec updated here;

-Ekr

On Wed, Jul 26, 2017 at 4:27 PM, Stephen Farrell <[email-masked]<mailto:[email-masked]>> wrote:

Cheers,
S.

_______________________________________________
TLS mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/tls

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 27 Jul 2017 23:43:06 +0000

Respectfully disagree. Having two cryptographically independent PRNGs, one for public data and one for key material, IMHO is a good idea. Of course, both should be properly seeded - but that's a different issue.

Regards,
Uri

Sent from my iPhone

> On Jul 27, 2017, at 19:33, Dan Brown <[email-masked]> wrote:
> 
> 
>> On Wed, Jul 26, 2017 at 4:27 PM, Stephen Farrell <[email-masked]> wrote:
>>

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 27 Jul 2017 16:50:32 -0700

I used the term "separate" here, which was intended to convey this, but if
people think "independent" or something is better, happy to change.

-Ekr

On Thu, Jul 27, 2017 at 4:43 PM, Blumenthal, Uri - 0553 - MITLL <
[email-masked]> wrote:

> Respectfully disagree. Having two cryptographically independent PRNGs, one
> for public data and one for key material, IMHO is a good idea. Of course,
> both should be properly seeded - but that's a different issue.
>
> Regards,
> Uri
>
> Sent from my iPhone
>
> Wasn’t there a few years back some RSA keys with separate p and q,
> generated independently leading to an attack...
>
> Here if the seeds to initialize the RNGS are related, or one is weak, or
> worst if the seed is a raw source that doesn’t change in the moments
> between the two CSPRNG inits, that'd be bad, even if the CSPRNGs were good.
> *From: *Eric Rescorla
> *Sent: *Thursday, July 27, 2017 6:34 PM
> *To: *Stephen Farrell
> *Cc: [email-masked]
> *Subject: *Re: [TLS] 32 byte randoms in TLS1.3 hello's
>
> Spec updated here;

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 28 Jul 2017 09:47:00 +0100

Hiya,

> people think "independent" or something is better, happy to change.

I think your change is a fine improvement over -21, thanks.
(And my suggested text was as imperfect as I usually manage:-)

I'm not clear if implementers will or will not get the
ramifications of "separate" (or "independent"), so I
think we ought describe (or reference) at least one way
in which that separation can be achieved.

I also think we ought at least RECOMMEND separate CSPRNGs.
I'd prefer a MUST myself but since there's no one good
way we can describe to achieve the effect that'd work in
all cases, I don't think we can say MUST.

Cheers,
S.

---

From: Dan Brown <[email-masked]>
Date: Fri, 28 Jul 2017 13:37:33 +0000

I try below to better explain my points against separated public and private CSPRNG instances. 

Perhaps the easiest way to get "independent" seeds for the two instances of a CSPRNG, is to use a third CSPRNG instance to generate the seeds.  But then the problem arises again, if the 3 CSPRNGs are bad enough, (0=seeder, 1=public, 2=private), there is a risk that:
 
Public_nonce=output1=>seed1=output0_for_1=>seed0=>output0_for_2=seed2=>output_2=private_key=TLS_insecurity.

In short, generally speaking, three bad CSPRNGs do not combine easily into 1 good CSPRNG.  

(I'm not yet sure if this attack on three CSPRNGs combined applies to Dual_EC, since it may do something hash-like to the seed (I forgot details), and also output leaks the next state, not the previous state, as I recall, so that might break the chain above.)

The alternative to a 3rd CSPRNG is to get the seeds from directly from a raw entropy source. In that case, keep in mind that one of the purposes of CSPRNGs is that raw entropy sources are unreliable (sometimes stall, etc. [references to be added]) and generally weak on the independence (they are non-uniform, hence have correlations).  CSPRNGs are supposed to correct these deficiencies, among other things.  So, if the 2 seeds are generated directly from a raw entropy sources (without a CSPRNG), two things may go wrong. First, deriving one seed from the other might be feasible because of non-uniformity. A bad CSPRNG might enable this this to be exploited, by finding one seed from the other.  Second, if the entropy source stalls (down a trickle of low entropy), between too close seed requests - accidentally - then even a good CSPRNG couldn't cope.

Maybe, all this wouldn't be a problem on many higher end systems, with high entropy, so my concern is lower end systems, and also unnecessary complications of maintaining multiple bad CSPRNGs, potentially to no avail.  

Finally, on systems with a linux-style interface, /dev/urandom and /dev/random could be used as the two CSPRNGs on some systems (or seed sources), although I think one of these is now deprecated? 

-----Original Message-----
From: TLS [mailto:[email-masked]] On Behalf Of Stephen Farrell
Sent: Friday, July 28, 2017 4:47 AM
To: Eric Rescorla <[email-masked]>; Blumenthal, Uri - 0553 - MITLL <[email-masked]>
Cc: [email-masked]
Subject: Re: [TLS] 32 byte randoms in TLS1.3 hello's

Hiya,

On 28/07/17 00:50, Eric Rescorla wrote:
> I used the term "separate" here, which was intended to convey this, 
> but if people think "independent" or something is better, happy to change.

I'm not clear if implementers will or will not get the ramifications of "separate" (or "independent"), so I think we ought describe (or reference) at least one way in which that separation can be achieved.

I also think we ought at least RECOMMEND separate CSPRNGs.
I'd prefer a MUST myself but since there's no one good way we can describe to achieve the effect that'd work in all cases, I don't think we can say MUST.

Cheers,
S.

>> Respectfully disagree. Having two cryptographically independent 
>> PRNGs, one for public data and one for key material, IMHO is a good 
>> idea. Of course, both should be properly seeded - but that's a different issue.
>>
>> Regards,
>> Uri
>>
>> Sent from my iPhone
>>
>> Here if the seeds to initialize the RNGS are related, or one is weak, 
>> or worst if the seed is a raw source that doesn’t change in the 
>> moments between the two CSPRNG inits, that'd be bad, even if the CSPRNGs were good.
>> *From: *Eric Rescorla
>> https://github.com/tlswg/tls13-spec/commit/465de0e189b2b59090d0eac0ac
>> bc42
>> 942af9ca77
>>
>> -Ekr
>>
>>
>>> I've suggested some text for this in a PR [1] based on what people 
>>> have said in this thread.
>>>
>>> It might be no harm to add more pointers to that appendix from 
>>> elsewhere in the spec, and/or to add a list of the various 
>>> public/private random numbers that are needed to that appendix. (I'd 
>>> be happy to do a pass to identify those if folks basically like this 
>>> kind of addition.)
>>>
>>> I also need to figure out how to handle the reference properly:-) 
>>> Can do that tomorrow.
>>>
>>> Cheers,
>>> S.
>>>

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 28 Jul 2017 18:08:50 +0300

On Fri, Jul 28, 2017 at 01:37:33PM +0000, Dan Brown wrote:
> 
> Finally, on systems with a linux-style interface, /dev/urandom and
> /dev/random could be used as the two CSPRNGs on some systems (or
> seed sources), although I think one of these is now deprecated? 

You do not want to use /dev/random as seed source. It can block for
potentially long times. And the output quality is not better than
/dev/urandom. The same goes for the GRND_RANDOM flag.

There is one use for /dev/random tho: AFAIK, one can wait for random
initialization on Linux 3.16 or order by blocking until /dev/random
returns one byte (and then reading /dev/urandom). In 3.17 or newer,
better way is to call sys_getrandom as this blocks until random
initialization.

-Ilari

---

From: Dan Brown <[email-masked]>
Date: Fri, 28 Jul 2017 15:35:56 +0000

Replies in-line (non-standardly enclosed with << >>, sorry ;)

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] 
Sent: Friday, July 28, 2017 11:09 AM
To: Dan Brown <[email-masked]>
Cc: [email-masked]
Subject: Re: [TLS] 32 byte randoms in TLS1.3 hello's

On Fri, Jul 28, 2017 at 01:37:33PM +0000, Dan Brown wrote:
> /dev/random could be used as the two CSPRNGs on some systems (or seed 
> sources), although I think one of these is now deprecated?

You do not want to use /dev/random as seed source. It can block for potentially long times. And the output quality is not better than /dev/urandom. 

<< This is an example of the deprecation of /dev/random, I think (which can be found elsewhere too).

Anyway, this whole thread considers resisting the hypothesis of a CSPRNG, such as /dev/[u]random, leaking its internal state. The idea of /dev/urandom is to not block, allowing the internal state to evolve deterministically (if no new entropy input arrives).  So, finding one /dev/urandom output would lead to finding another (under this hypothesis), by way of the internal state.  By contrast, as I understand it, /dev/random should at least block until it believes it has updated its internal state with a good dose of entropy.  Of course, this muddles the hypothesis somewhat, since first we posit a bad PRNG, then we speak of /dev/random acting like a good PRNG, etc. In a way, /dev/random is sort of doing what people are proposing here (the 2 CSPRNG), by trying to ensure that successive random outputs are not deterministically linked by a random state, so are in a sense two "independent" values..., even if the deterministic part of the RNG, the hashing or whatever, fails... >>

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 28 Jul 2017 16:48:46 +0100

I don't think this is simply a case of multiple CSPRNGs.

My guess is many TLS implementations don't have visibility
into how the CSPRNG operates. That code does however, know
which output values will be public and which not. For me,
that implies that any good separation scheme applied within
the TLS code that differentiates between public and non
public outputs is a good plan. Yes, if an attacker can bork
your CSPRNG, they may be able to get at the TLS code too
sometimes, but I'd argue the defence in depth is worthwhile.

Cheers,
S.

---

From: "Salz, Rich" <[email-masked]>
Date: Fri, 28 Jul 2017 15:54:18 +0000

> That code does however, know which output values will
> be public and which not. For me, that implies that any good separation
> scheme applied within the TLS code that differentiates between public and
> non public outputs is a good plan.

Agreed.

	/r$, who is moving OpenSSL to DRBG AES128-ctr, and hopefully adding two instances :)

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 28 Jul 2017 20:35:07 +0300

On Fri, Jul 28, 2017 at 03:35:56PM +0000, Dan Brown wrote:
> /dev/urandom. 

No, /dev/random has behaved that way for a long long time.

> Anyway, this whole thread considers resisting the hypothesis of
> a CSPRNG, such as /dev/[u]random, leaking its internal state.
> The idea of /dev/urandom is to not block, allowing the internal
> state to evolve deterministically (if no new entropy input
> arrives).  So, finding one /dev/urandom output would lead to
> finding another (under this hypothesis), by way of the internal
> state. 

The pool underlying /dev/urandom is reseeded periodically (I think
every minute if enough entropy is available).

> By contrast, as I understand it, /dev/random should at least
> block until it believes it has updated its internal state
> with a good dose of entropy.  

The problem is that /dev/random runs out of entropy REALLY fast if
you try to actually use it.

I think the pool size is equivalent to about 16 ECDH keys or TLS
*randoms. And it can easily take ten seconds to recover enough entropy
for one such. Not good.

If you want to use /dev/random (or GRND_RANDOM) for anything, it better
be long-term key generation (and even that is bit questionable).

-Ilari

---

From: Dan Brown <[email-masked]>
Date: Sat, 29 Jul 2017 15:54:47 +0000

https://eprint.iacr.org/2012/064
mentions the problem of generating multiple secrets instead of a single secret

  Original Message
From: Stephen Farrell
Sent: Friday, July 28, 2017 11:48 AM
To: Dan Brown; Eric Rescorla; Blumenthal, Uri - 0553 - MITLL
Cc: [email-masked]
Subject: Re: [TLS] 32 byte randoms in TLS1.3 hello's

Cheers,
S.

---

From: Colm MacCárthaigh <[email-masked]>
Date: Sat, 29 Jul 2017 11:04:43 -0700

I don't see anything relevant to the problem at hand in that paper. Did you
reference the right one? There are some mentions about not re-using random
secrets, but that applies no matter how many RNGs you use.

In your previous mail, even if an implementer were to seed two RNGs from
one CSPRNG, and all 3 are bad generator, this is still strictly better than
one broken generator; because the amount of work an attacker must do is far
greater.

> > Perhaps the easiest way to get "independent" seeds for the two instances
> of a CSPRNG, is to use a third CSPRNG instance to generate the seeds.  But
> then the problem arises again, if the 3 CSPRNGs are bad enough, (0=seeder,
> 1=public, 2=private), there is a risk that:
> >
> > Public_nonce=output1=>seed1=output0_for_1=>seed0=>output0_
> for_2=seed2=>output_2=private_key=TLS_insecurity.
> >
> > (I'm not yet sure if this attack on three CSPRNGs combined applies to
> Dual_EC, since it may do something hash-like to the seed (I forgot
> details), and also output leaks the next state, not the previous state, as
> I recall, so that might break the chain above.)
> >
> > The alternative to a 3rd CSPRNG is to get the seeds from directly from a
> raw entropy source. In that case, keep in mind that one of the purposes of
> CSPRNGs is that raw entropy sources are unreliable (sometimes stall, etc.
> [references to be added]) and generally weak on the independence (they are
> non-uniform, hence have correlations).  CSPRNGs are supposed to correct
> these deficiencies, among other things.  So, if the 2 seeds are generated
> directly from a raw entropy sources (without a CSPRNG), two things may go
> wrong. First, deriving one seed from the other might be feasible because of
> non-uniformity. A bad CSPRNG might enable this this to be exploited, by
> finding one seed from the other.  Second, if the entropy source stalls
> (down a trickle of low entropy), between too close seed requests -
> accidentally - then even a good CSPRNG couldn't cope.
> >
> > Maybe, all this wouldn't be a problem on many higher end systems, with
> high entropy, so my concern is lower end systems, and also unnecessary
> complications of maintaining multiple bad CSPRNGs, potentially to no avail.
> >
> > I'm not clear if implementers will or will not get the ramifications of
> "separate" (or "independent"), so I think we ought describe (or reference)
> at least one way in which that separation can be achieved.
> >
> > I'd prefer a MUST myself but since there's no one good way we can
> describe to achieve the effect that'd work in all cases, I don't think we
> can say MUST.
> >
> > Cheers,
> > S.
> >
> >
> >>
> >> -Ekr
> >>
> >>

-- 
Colm

---

From: Dan Brown <[email-masked]>
Date: Sat, 29 Jul 2017 20:30:33 +0000

‎Section 3, of the eprint "Ron is wrong, Whit is right", subsection "Moduli with shared primes", suggests to me that it's not unlikely when seeding two secrets near in time, one has low entropy (by accident). That's not the only explanation of the observed shared primes, but is plausible and relevant to the question at hand. (I thought I mentioned this earlier.)
From: Colm MacCárthaigh
Sent: Saturday, July 29, 2017 2:04 PM
To: Dan Brown
Cc: Stephen Farrell; Eric Rescorla; Blumenthal, Uri - 0553 - MITLL; [email-masked]
Subject: Re: [TLS] 32 byte randoms in TLS1.3 hello's

I don't see anything relevant to the problem at hand in that paper. Did you reference the right one? There are some mentions about not re-using random secrets, but that applies no matter how many RNGs you use.

In your previous mail, even if an implementer were to seed two RNGs from one CSPRNG, and all 3 are bad generator, this is still strictly better than one broken generator; because the amount of work an attacker must do is far greater.

On Sat, Jul 29, 2017 at 8:54 AM, Dan Brown <[email-masked]<mailto:[email-masked]>> wrote:
https://eprint.iacr.org/2012/064
mentions the problem of generating multiple secrets instead of a single secret

  Original Message
From: Stephen Farrell
Sent: Friday, July 28, 2017 11:48 AM
To: Dan Brown; Eric Rescorla; Blumenthal, Uri - 0553 - MITLL
Cc: [email-masked]<mailto:[email-masked]>
Subject: Re: [TLS] 32 byte randoms in TLS1.3 hello's

Cheers,
S.

On 28/07/17 14:37, Dan Brown wrote:
> From: TLS [mailto:[email-masked]<mailto:[email-masked]>] On Behalf Of Stephen Farrell
> To: Eric Rescorla <[email-masked]<mailto:[email-masked]>>; Blumenthal, Uri - 0553 - MITLL <[email-masked]<mailto:[email-masked]>>
> Cc: [email-masked]<mailto:[email-masked]>
>> [email-masked]<mailto:[email-masked]>> wrote:
>>
>>> On Jul 27, 2017, at 19:33, Dan Brown <[email-masked]<mailto:[email-masked]>> wrote:
>>>
>>>
>>> *Cc: [email-masked]<mailto:[email-masked]>
>>> On Wed, Jul 26, 2017 at 4:27 PM, Stephen Farrell <
>>> [email-masked]<mailto:[email-masked]>> wrote:
>>>
>>>>

--
Colm

---

From: Colm MacCárthaigh <[email-masked]>
Date: Sat, 29 Jul 2017 14:19:43 -0700

On Sat, Jul 29, 2017 at 1:30 PM, Dan Brown <[email-masked]> wrote:

> ‎Section 3, of the eprint "Ron is wrong, Whit is right", subsection
> "Moduli with shared primes", suggests to me that it's not unlikely when
> seeding two secrets near in time, one has low entropy (by accident). That's
> not the only explanation of the observed shared primes, but is plausible
> and relevant to the question at hand. (I thought I mentioned this earlier.)
>

If the PRNGs produce identical output, that is bad, but that seems easy to
protect against: check that the seeds are actually different.  This is also
what personalization strings are designed to protect against.

-- 
Colm

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Sun, 30 Jul 2017 02:39:13 +0000

Dan, 

I confess I don't understand your logic. 

A PRNG can be good, or it can be bad. If you seed more than one PRNG, your seeds could be cryptographically correlated (worst case), or they may be cryptographically independent (what we want and expect).

At least one of the PRNGs has to have is output exposed (aka public). If this PRNG is (at least partially) broken, an adversary may be able to recover it's state/seed.

I fail to see how the above can justify insisting on having only one PRNG. If you have seeded more than one PRNG, and outputs of others are not exposed - then for the attack to succeed the adversary must know the relationship between the seeds, thus exploiting more vulnerabilities than a broken PRNG. Maybe you don't consider this distinction significant enough, but I do. 

If you are right (hypothetically of course), the proposed setup is no worse than having one exposed PRNG. If you are wrong (as I'm sure you are), the proposed setup makes a difference between a failed system, and one that works. 

Appears a no-brainer. 

Regards,
Uri

Sent from my iPhone

> On Jul 29, 2017, at 16:30, Dan Brown <[email-masked]> wrote:
> 
>> >>> [email-masked]> wrote:
>> >>>
>> >>>>

---

From: Dan Brown <[email-masked]>
Date: Mon, 31 Jul 2017 13:54:29 +0000

-----Original Message-----
From: Stephen Farrell [mailto:[email-masked]] 

DB> Not quite sure what you mean by "simply a case of multiple CSPRNGs", but I am starting to get an idea below.

My guess is many TLS implementations don't have visibility into how the CSPRNG operates. That code does however, know which output values will be public and which not. For me, that implies that any good separation scheme applied within the TLS code that differentiates between public and non public outputs is a good plan. 

DB> Ok, suppose the TLS implementation wishes to just read /dev/urandom, which is presumably a good CSPRNG.  Unlike the NIST RBGs, there's no interface to create independent and separate instantiations of /dev/urandom (as far as I know, although newer versions may provide this feature).  So, what would count as your "separation scheme"?  Are you saying the TLS code should post-process the output of a single CSPRNG?  If so, then that's probably a good idea, if done right.  At least it doesn't have the downside risk of the TLS coder generating its own seeds, writing its own CSPRNG (instead of using /dev/urandom), etc.  (I thought that I was being very specific that launching 2 CSPRNGs was not a good idea, yet it seems I was read as preferring as doing nothing and keeping the status quo, which is not what I intended.)  So, I think some kind of clarification of the currently proposed text (for -21 ?)  may be worthwhile, because I read it creating two separate CSPRNGs.  (Of course, defence in depth is good, and often worth the implementation cost, but if it introduces new security problems, then it is not too good.  More philosophically, in an ideal world, any additions to the TLS spec should be vetted with pedigree.  Trying to create independently seeded CSPRNGs goes against the current best practices as I understand them.  By contrast, TLS already has all kinds of key derivation, separation for different purposes (unless that was dropped in 1.3???), which TLS might as well continue to use.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 31 Jul 2017 15:24:05 +0000

My guess is many TLS implementations don't have visibility into how the CSPRNG operates.
       That code does however, know which output values will be public and which not. For me, that
       implies that any good separation scheme applied within the TLS code that differentiates
       between public and non public outputs is a good plan. 

Hasn’t this been the whole point of the discussion?! The proposal to separate PRNGs into those that supply publicly-visible randomness (nonces, etc), and those that supply “secret” randomness (keying material and such)? Thus, having *two* PRNGs, each (hopefully) properly seeded?

I’m glad you’re now agreeing that the above is a good plan.