Subject: Randomizer state attacks

From: Christian Huitema <[email-masked]>
Date: Fri, 21 Jul 2017 03:40:04 -0700

I was just discussing with Stephen past attacks against random number
generation in crypto stacks. In these attacks, the adversaries "induce"
the implementation to generate random numbers for clear text parameters
prior to generating the random numbers used for key generation. The
adversaries can then use the clear text values to predict the state of
the PRNG in the crypto stack, and thus guess the keys.

This was done for example in an attack against the IPSEC/IKE stack used
by Juniper -- look at the IPSEC nonce to retrieve the state of the Dual
EC based PNRG, and guess the private DH values used to negotiate the
IPSEC keys -- check
https://www.ietf.org/proceedings/99/slides/slides-99-irtfopen-anrp-stephen-checkoway-a-systematic-analysis-of-the-juniper-dual-ec-incident-00.pdf.

It is worth thinking about this attack when any random string is visible
in the network. For QUIC, that would be for example the Connection ID
and the initial sequence number. It is probably worth thinking about that.

-- Christian Huitema

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Fri, 21 Jul 2017 07:14:38 -0400

Wasn’t the Dual EC the PRNG everyone suspected was backdoor'ed by NSA until
Snowden practically confirmed it?

More generally, I believe it is reasonable for QUIC to assume that PRNG’s
are safe (where else do you stop?), and for implementers to assume that OS
provided PRNG’s are not.

Windows had a major bug, and Linux, at least a while ago, used a weaker
than necessary PRNG for perceived performance gains, and I'm sure there are
massive data centers allocated to just that cracking that.

https://www.schneier.com/blog/archives/2014/03/the_security_of_7.html

Kind Regards,
Mikkel Fahnøe Jørgensen

On 21 July 2017 at 12.40.18, Christian Huitema ([email-masked]) wrote:

-- Christian Huitema

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Fri, 21 Jul 2017 07:26:09 -0400

Postgresql implemented a fortuna like PRNG that looks reasonable to me

https://github.com/DataSystemsLab/recdb-postgresql/blob/master/PostgreSQL/contrib/pgcrypto/fortuna.c

I hashes entropy from pools and feeds it into an AES counter mode stream.
One could rekey crypto between clear text random and crypto streams.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 21 July 2017 at 13.14.38, Mikkel Fahnøe Jørgensen ([email-masked])
wrote:

Kind Regards,
Mikkel Fahnøe Jørgensen

This was done for example in an attack against the IPSEC/IKE stack used
by Juniper -- look at the IPSEC nonce to retrieve the state of the Dual
EC based PNRG, and guess the private DH values used to negotiate the
IPSEC keys -- check
https://www.ietf.org/proceedings/99/slides/slides-99-irtfopen-anrp-stephen-checkoway-a-systematic-analysis-of-the-juniper-dual-ec-incident-00.pdf
.

-- Christian Huitema

---

From: Ryan Hamilton <[email-masked]>
Date: Fri, 21 Jul 2017 11:01:38 -0700

Interesting! Do these attacks depend on a vulnerable PRNG or is this still
a problem for "good" PRNGs? If it's a problem for "good" PRNGs, what's the
high level advice for dealing with such attacks?

On Fri, Jul 21, 2017 at 3:40 AM, Christian Huitema <[email-masked]>
wrote:

> https://www.ietf.org/proceedings/99/slides/slides-
> 99-irtfopen-anrp-stephen-checkoway-a-systematic-
> analysis-of-the-juniper-dual-ec-incident-00.pdf.
>

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 21 Jul 2017 20:50:37 +0100

Hiya,

On 21/07/17 19:01, Ryan Hamilton wrote:
> a problem for "good" PRNGs? 

In the juniper attack someone took a good prng and turned it into
a bad prng, via those dodgy-looking changes to code. That isn't
visible to the application calling the prng. So, the answer to
your question is "yes, you need a vulnerable prng," but also "no,
a good prng when you're writing your code isn't enough."

So the issue here is: to the extent one can, ensuring a protocol
is designed to be good even if some implementation at some time
uses a borked prng.

> If it's a problem for "good" PRNGs, what's the

First is as Christian says is just to consider the attack and
see how'd it affect QUIC. E.g., count up the bits that are
visible and supposed to be random and see how many there are.

If you end up with say 32 bytes total, that may be a lot worse
than ending up with 20, if faced with an attack like this. In
Checkoway's work part of the attack extended a nonce from 20
to 32 bytes, which moved the dual-ec attack work factor from
2^96 down to 2^16, (see slide 39 of the presentation Christian
referred to below - which was a great talk btw, I'd highly
recommend it).

Depending on what that shows one might want to reduce the number
of random bits that are visible in clear. One way to do that
might be to make some of them depend on others, e.g. if there
are two fields where we want random looking values then instead
of getting both from the prng one could make the second a hash
of the first and tell receivers to check that. Whether or not
anything like that would be a good or bad idea will depend on
the details of QUIC. (Details of which I'm ignorant myself, sorry;-)

Regardless of whether or not there's anything that needs changing
you'd probably want to consider adding some security considerations
or implementation guidance text, maybe including a pointer to [1]
(Checkoway's paper that won the anrp). While you could probably
assume that e.g. the TLS library internal code has considered this,
the QUIC code might not, so such text may be useful.

But the reason I raised this with Christian is that at this stage
in the development of QUIC, there's a design principle that the WG
might want to consider as well, which is to minimise the number of
prng-output cleartext bits visible to a network attacker. (I'm
assuming that the kind of change is feasible at this point still.)

Cheers,
S.

[1] https://web.eecs.utk.edu/~mschucha/netsec/readings/p468-checkoway.pdf

---

From: Ryan Hamilton <[email-masked]>
Date: Fri, 21 Jul 2017 13:43:29 -0700

On Fri, Jul 21, 2017 at 12:50 PM, Stephen Farrell <[email-masked]

> is designed to be good even if some implementation at some time

​Ah! Ok, thanks. I missed a bit of subtlety there. Thanks.
​

> assuming that the kind of change is feasible at this point still.)

​Yup, makes sense. Thanks!

---

From: Martin Thomson <[email-masked]>
Date: Sat, 22 Jul 2017 10:46:48 +0200

On 21 July 2017 at 21:50, Stephen Farrell <[email-masked]> wrote:
> [...] there's a design principle that the WG
> prng-output cleartext bits visible to a network attacker.

This principle would have to apply to a peer as well.  That is, even
encrypted bits count.

I'm a little leery of this proposed requirement.  There are many
things that are improved by the injection of entropy.  Think traffic
analysis resistance for instance (disclaimer: I have no good strategy
there) or the ability to verify that a peer is truly on path for the
purposes of DoS protection.  Insisting that that entropy be minimal
might be handcuffing ourselves.

---

From: Stephen Farrell <[email-masked]>
Date: Sat, 22 Jul 2017 13:05:01 +0100

> This principle would have to apply to a peer as well.  That is, even

I'm not sure I understand or agree there. How would encrypted bits
affect a dual-ec kind of attack? Or did you mean something else?

> 
> I'm a little leery of this proposed requirement.  

Leery is fair - thinking about the attack and deciding what, if
anything, to do, is right.

> There are many

Minimising visibility of cleartext prng-output is not the same as
minimising entropy. For example, prior to considering this putative
new principle, it'd be natural to say that a connection ID be
random, and it'd be natural to implement by getting a value from a
prng and using that. But one could equally generate a connection ID
from something else (e.g. via a hash) that has sufficient randomness
(Christian suggested the first flight, though I may be getting the
term wrong there), and achieve the properties one needs, but without
exposing bits output from the prng in clear. If one did follow
Christian's idea there, then a peer could verify that too - the idea
being that'd overall make dual-ec like attacks harder.

Cheers,
S.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Sat, 22 Jul 2017 09:43:18 -0700

> But one could equally generate a connection ID
from something else (e.g. via a hash) that has sufficient randomness
(Christian suggested the first flight, though I may be getting the
term wrong there), and achieve the properties one needs, but without
exposing bits output from the prng in clear.

The problem is similar deriving traffic keys from master session keys and
one could argue that ID generation should be seen as another derived crypto
key if the PRNG is not able to deliver an independent stream on its own.

But it cannot be done naively by just fishing from some entropy pool. There
isn’t unlimited entropy in the system, the PRNG’s job is to harvest this
and produces an pseudo random stream of bytes that does not lead back to
the internal state. Doing this behind the back of the PRNG might allow an
attacker to go directly to the entropy source of the PRNG seed, which is
bad.

>From what I understand these are some the major pitfalls with PRNG’s:

1. inadequate original entropy: No matter how you hash, permutate and
encrypt, there are only so many options once you know the algorithm. Create
a huge database of likely streams and decrypt instantly. This can take down
the best PRNG (and this probably happens somewhere, right now).
2. trust a single entropy source (like possibly backdoor’ed on-chip PRNG)
or a faulty OS implementation, or vice versa, avoiding them entirely and
miss quality entropy.
3. entropy pollution: allowing an attacker to feed bad entropy such that
the PRNG moves to a predictable state space. A good PRNG will only increase
entropy but apparently not all PRNGs have this property. Fortuna attempts
to address this by hashing various entropy sources.
4. failure to isolate quality entropy from output. Fortunate feeds entropy
state into AES counter mode.
5. premature draining of entropy source - keep reading from /dev/urandom
instead hashing enough state to produce an unguessable AES key, then feed
random data from that key. Draining /dev/urandom would just enter case 1.
fast unless the OS has equivalent protection, which is far from guaranteed.
6. failure to adhere to guidelines of PRNG assumptions. For example when
and what something should be independent by some measure.
7. Failure to ensure forward secrecy in case the PRNG state is breached.
Fortunate does some work to protect against this, but I think more could be
done (it’s been a while since I looked). Having this property makes it hard
break into a session after the fact, especially when other crypto does have
forward secrecy.

I would assume 6. is not necessarily the most likely vulnerability, but it
is very difficult to understand, so a quality PRNG ought to make it
self reasonably idiot proof in this respect. Also, if an attacker is able
to random data directly from tap via some other channel where gigabytes of
state can be drawn trivially. No matter how good the PRNG, if this allows
the attacker to guess the original entropy seed, security is not a thing.

Standard crypto libraries are vulnerable to the platform the run on because
some I have looked at just looks for a system provided PRNG, and then it
can all go wrong in a simple build configuration, or by using the wrong OS.
A good library ought, IMHO, to provide a quality PRNG of its own and use
the OS as an entropy source, not as a the direct random source. They could
also improve by not having a single global PRNG context that requires
locking for every value needed.

So there plenty of pitfalls, but requiring that the QUIC implementation to
protect against bad PRNG rather than the crypto library seems wrong to me.
Granted, you don’t need to make the protocol more vulnerable than
necessary, and indeed, I have also thought about all these random values
being released into the wild is an easy way to make serious crypto mistakes.
.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 22 July 2017 at 14.05.13, Stephen Farrell ([email-masked])
wrote:

But one could equally generate a connection ID
from something else (e.g. via a hash) that has sufficient randomness
(Christian suggested the first flight, though I may be getting the
term wrong there), and achieve the properties one needs, but without
exposing bits output from the prng in clear. I

---

From: Stephen Farrell <[email-masked]>
Date: Sat, 22 Jul 2017 18:58:03 +0100

> being released into the wild is an easy way to make serious crypto mistakes.

I'd assert that lack of entropy or a significantly imperfect prng
is a different issue, compared to the dual-ec attack.

Dual-ec is a deliberate attack such that the prng output looks nicely
random unless you're the attacker, in which case you can guess the
internal state of the prng without much effort if you can see enough
cleartext prng output bits.

And the question for protocol design is whether we can make such
attacks harder and then if doing so is worthwhile.

So I agree that we don't really need to consider issues related to
entropy here, (that mostly being a crypto-library responsibility)
unless the WG somehow go over the top and produce something with
too few states, though I'd say that's pretty unlikely:-)

But we should consider the dual-ec and similar attacks.

Cheers,
S.

---

From: Christian Huitema <[email-masked]>
Date: Sat, 22 Jul 2017 17:33:46 -0700

On 7/22/2017 10:58 AM, Stephen Farrell wrote:
> is a different issue, compared to the dual-ec attack...
Stephen, from our previous discussions, I conclude that you are looking
at some kind of "defense in  depth". If the local PRNG is robust, there
is not much risk in disclosing random numbers in connection ID, initial
sequence numbers or nonce. But we don't always know that the PRNG is
robust. In the Dual-EC case, implementers believed it was, when in fact
it was not. The defense in depth argument is that we should somehow
control the random values published in clear text, so that even if the
PRNG happens to be weak, the weakness will be difficult to exploit.
Also, long random fields in protocol messages can be abused as side
channels.

On the other hand,  nonce and other random fields are useful to prevent
off path attacks.

Also, QUIC relies on TLS 1.3. The TLS 1.3 Client Hello and Server Hello
are sent in clear text. Both carry a 32 byte random field. Even if QUIC
did not use 12 bytes used in QUIC for Connection ID and Initial Sequence
Number, TLS would still use 32 bytes, which would be plenty for dual-EC
style attacks. So I am not sure that we should pile a lot of complexity
in QUIC to mitigate random number disclosure.

-- Christian Huitema

-- 
Christian Huitema

---

From: Stephen Farrell <[email-masked]>
Date: Sun, 23 Jul 2017 17:03:51 +0100

> Also, long random fields in protocol messages can be abused as side

Correct.

> On the other hand,  nonce and other random fields are useful to prevent

Also correct.

> are sent in clear text. Both carry a 32 byte random field. 

Yeah, I'll take a peek back at the TLS list/git repo to see why what's
changed from 28->32. I forget tbh.

> Even if QUIC

I agree that adding a "lot of complexity" would be wrong. OTOH,
the dual-ec attack is real and has been attempted multiple times
in multiple ways (bsafe & juniper), so the attacker in that case
appears not to have stopped attacking. So doing the analysis is
worthwhile.

Maybe the right thing for now is to open an issue to check the
protocol vs. dual-ec attacks?

S.

---

From: Martin Thomson <[email-masked]>
Date: Sun, 23 Jul 2017 23:37:50 +0200

State recovery depends only on seeing output. For a server in particular,
if becoming a client is advantageous to an attacker, then that is what they
will do.

For example, prior to considering this putative
new principle, it'd be natural to say that a connection ID be
random, and it'd be natural to implement by getting a value from a
prng and using that.

Fair point. The requirement on connection ID is not randomness, but
uniqueness, or maybe not even that, so it is reasonable to state the actual
requirement.