Subject: [dsfjdssdfsd] What has gone wrong with RNGs in practice

From: Nick Mathewson <[email-masked]>
Date: Fri, 15 Nov 2013 11:36:14 -0500

Hi!

I thought it might be helpful to enumerate all the RNG failures I'm
aware of.  There are probably more, and my focus here has been on
failures that have actually led to working attacks.  See also CWE-330
[0].  Please let me know what I've missed.

== What has gone wrong in practice and led to actual working attacks:

A. Not actually using randomness at all for something that needs some
or all of the properties of a random bitstring.

Example: Sony's implementation of ECDSA failed to actually change the
k value between signatures; they just had a constant.[1]

Example: The SSL CBC weakness that enabled the BEAST attack where,
instead of using a new IV for each record, SSL and older TLS versions
would use the last record's last block as the IV for the next record.

B. Relying on an RNG output for something that doesn't need to be random.

Example: Most ECDSA implementations rely on having a strong RNG at
signing time. In fact, there are more robust ways to generate an
unpredictable value -- for example, by a cryptographic hash of the
message, the public key, and a secret value generated at key
generation time.  See the references in the  "Pseudorandom generation
or r" section of the Ed25519 paper [2]. Arguably, this is what went
wrong with the Android bitcoin problem.  (See item G below.)

C. The cryptographic function that is produces the RNG output or
updates its state is periodic, predictable, or otherwise
cryptologically inadequate.

Example: Traditional arc4random() implementations: the original RC4
cipher is not only insecure versus modern cryptanalysis [3]; it has
actual biases in its output.

Example: The core function Dual_EC_DBRG is distinguishable from a
random bitstring. Also, it has a  backdoor that could not be more
obvious if it were a drive-through car wash.

D. Using a noncryptographic PRNG when a stronger function is required
for security.

Example: When reviewing an inexperienced hobbyist's first cryptography
software, it's even money you'll find them using (say) Mersenne
Twister to generate a keystream.

Example: It has been well known for ages that initial TCP sequence
numbers need to be unpredictable to prevent various spoofing attacks.
Even so, people still used PRNGs with insufficient unpredictability,
such as linear congruental generators. The summary at [4] has a list
of CVEs for inadequate PRNGs.

E. Using an RNG that has been exposed before it can be adequately seeded.

Example: Various embedded hardware devices generate private keys on
their initial startup. Unfortunately, they tend to do this before
they've been able to collect any entropy from sources like HD timings
(what's an HD?) network timings (what's a network?) and so forth. This
has been one of the causes of a rash of predictable keys, as explored
in [5].

F. Disabling some or all of the seed inputs to an RNG.

Example: In the Debian OpenSSL PRNG bug [6], maintainers thought that
they were disabling a feature that added uninitialized RAM to the PRNG
state. Instead, they had accidentally disabled *all* inputs to the
PRNG state. (Except for the PID.)

Example: One of the reasons that Linux kernels entropy was sometimes
low around startup was (If I understand correctly!) that important
drivers or subsystems often avoided adding timing information to the
kernel entropy pool, for fear it would slow them down. More recent
Linux kernels, (again, IIUC) take the responsibility away from the
drivers, and use clever implementation hacks to ensure that no
performance penalty is felt.

G. Using the same RNG state to generate two bitstreams.

Example: The SecureRandom structure in Android was initialized once,
and then used as the initial SecureRandom for multiple processes. This
led to a large compromise in Android bitcoin wallets. [7]

Example: Python had the same problem [8]: the same RNG state was used
after fork.

H. Falling back to insecure sources.

Example: Too many supposedly strong RNG libraries have had a fallback
to random() if /dev/urandom can't be read. See for example the
discussion of Apache Harmony in [9].

I. Implementation errors.

Example: Too many to list. See for example the discussion of Apache
Harmony in [9], where the implementors thought they had a 128 bit
seed, but they only had a 64-bit seed.

== What has gone wrong, and is probably bad, but has not (AFAICT) led
to any publicized attacks yet:

These may well be getting exploited.  If you've got documentation on
that, please let me know.

AA. Backtracking from compromised state
BB. Prediction from compromised state

It's not necessary that reading an RNG's current state should enable a
attacker to learn all previous and future outputs of that RNG.
Resisting backtracking attacks is easy. Resisting prediction attacks
is a little harder, but permits a not too unattractive
performance/security tradeoff.

CC. Theoretically unsound pool constructions

See for example the recent paper on the Linux /dev/*random devices'
constructions [10].

DD. Exclusive reliance on hard-to-audit hardware or software

<Insert RDRAND paranoia here. Insert CryptGenRandom paranoia here.>

EE. Bad entropy estimation

Numerous RNGs rely on each entropy inputs being acccompanied by an
estimate of how many bits of entropy each contains. Historically,
these entropy estimates have been pretty bogus, but I'm not aware of
any attack arising out of that.

== Some antipaterns in randomness

(Here I am being perhaps too opinionated.)

* Exposing under-seeded RNGs.

If people can forget to seed an RNG, somebody will.  If an RNG can be
drained before it has been seeded, it will be.

* Strong, fast: pick one.

In many cases, the programming environment has provided a strong RNG,
but implementors have (erroneously) avoided it either on performance
grounds.  This is a shame, since there's no reason a strong userspace
PRNG can't give performance on par with many of the weak userspace
PRNGs people use today. (Shameless plug: [11])

* Strong, reliable: pick one.

In some cases, programmers avoid the safer option because they can't
rely on it being available, and so use one that might not be as well
seeded. (For example, many programmers avoid /dev/random for fear that
it might block, while using /dev/urandom, which is on some platforms
more likely to return predictable bits near initial system startup.)

* Underdocumented, underexplained randomness requirements.

Before you sniff too loudly at Sony's mistake in [1]: Pretend that you
are a programmer in a hurry looking at FIPS 186-2, or your favorite
(early) standards-body description of DSA. How well does it explain
the importance of making 'k' completely unpredictable for each
message, and how well does it explain the consequences for failing to
do so?

* Falling back to insecure sources

"I couldn't open /dev/urandom. I guess that srandom(getpid() +
malloc()) is the best I can do."

* Entropy purity taboos

This is the converse of DD above. Some implementors refuse to
incorporate entropy sources they don't trust into an entropy pool,
under the apparent belief that combining a good entropy source with an
evil entropy source will produce contaminated entropy.  In reality, a
good PRNG will survive hostile sources just fine, so long as a
sufficient threshold of the entropy inputs are good.

* Inadequate testing

This is a tremendous problem. Unless the RNG is broken, black-box
testing is usually inadequate: an unseeded RNG's output, or an
underseeded RNG's output, or a broken RNG's output, will all look.
Testing an RNG requires, at minimum; verification that it produces the
correct expected outputs given an expected seed, and that it responds
correctly to addition of more fixed seeds.

[0] http://cwe.mitre.org/data/definitions/330.html
[1] http://www.bbc.co.uk/news/technology-12116051
[2] http://ed25519.cr.yp.to/ed25519-20110926.pdf
[3] http://www.isg.rhul.ac.uk/tls/
[4] http://www.cert.org/advisories/CA-2001-09.html
[5] https://factorable.net/paper.html
[6] http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2008-0166
[7] http://bitcoin.org/en/alert/2013-08-11-android
[8] http://bugs.python.org/issue18747
[9] http://hgi.rub.de/media/nds/veroeffentlichungen/2013/03/25/paper_2.pdf
[10] http://eprint.iacr.org/2013/338.pdf
[11] https://github.com/nmathewson/libottery

hoping this was useful,
-- 
Nick Mathewson

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 15 Nov 2013 16:46:12 +0000

> hoping this was useful,

Very useful IMO, thanks.

Its clear that lots of that is stuff that the IETF
can't help make better, but I think its all relevant
for discussion here.

S.

---

From: Theodore Ts'o <[email-masked]>
Date: Fri, 15 Nov 2013 21:42:42 -0500

> See for example the recent paper on the Linux /dev/*random devices'

CC is a bit vague, and is redundant with AA, BB, and EE in your list.

The assertion made in [10] is that an attacker who can control all of
the entropy inputs in such a way that defeats the entropy estimator
(which is EE), could result in a failure of guarantees such as BB
(recovery after compromised state).

Whether or not an attacker could control all entropy inputs in such as
way that it could defeat the entropy estimator was not actually shown
in [10], and I'm not entirely sure that insisting on a theoretical
model which requires that a design should be robust against by
arbitrary control of the entropy sources (as opposed to auditing the
entropy sources actually *used* by the RNG) is a all that useful ---
but that's aside from the point I'm trying to make here, which is if
you're going to have a list of potential RNG failures, they should be
a specific set of things that you can look for, and not something
vague and overarching such as "bad design of the RNG pools".

Cheers,

							- Ted

---

From: Arnold Reinhold <[email-masked]>
Date: Sat, 16 Nov 2013 19:05:37 -0500

> k value between signatures; they just had a constant.[1]
....
> message, and how well does it explain the consequences for failing to

I has also been suggested that Sony's failure to generate unique k's could have been caused by a compiler that optimized the k=crypto_random(); call out of a loop.  Whether that happened or not in the Sony case, the possibility should be dealt with in any RNG standard, as the consequence of a repeated k is easy recovery of the private key. Perhaps there should be a requirement that two (or more) test signatures be generated at application startup to verify independent k's are being generated, as code that worked initially could later be recompiled with different optimization settings for a new release.. 

Arnold Reinhold

---

From: Russ Housley <[email-masked]>
Date: Sat, 16 Nov 2013 19:32:32 -0500

> I has also been suggested that Sony's failure to generate unique k's could have been caused by a compiler that optimized the k=crypto_random(); call out of a loop.  Whether that happened or not in…

There should be a self-test part of the specification that detects this type of failure.  It should not be hard to turn the FIPS 140 test suite into a good-enough-to-continue / fail test.  This would envolve generating 10,000 random bits and doing some statistical checks.

Russ

---

From: Nick Mathewson <[email-masked]>
Date: Sat, 16 Nov 2013 22:04:41 -0500

> Hi!
  [....]
> Example: Python had the same problem [8]: the same RNG state was used

I have received a correction for this one. The original reporter of
the Python bug (Christian Heimes) informs me that the bug is not in
the main Python secure RNG (which just reads /dev/urandom or the local
equivalent), but in OpenSSL's RNG as used in Python, which ought to be
reseeded or invalidated on fork() when Python is using OpenSSL, but
which is difficult to reset from an at_fork() handler because of
issues as discussed in [14].

Additionally, Tanja Lange mentioned [12] another category of
real-world vulnerability as discussed in [13].  These might be called:

J. Using unreliable hardware entropy sources directly rather than as
inputs to a PRNG.

(The cautious behavior is to design your PRNG such that it produces
good outputs if its inputs have *ever* been random enough.)

or

K. Omitting run-time tests for hardware entropy sources

While some failures are undetectable, it's just tempting fate to omit
tests for detectable failures of hardware components.

[12] https://twitter.com/hyperelliptic/status/401831967177461760
[13] http://smartfacts.cr.yp.to/analysis.html
[14] http://bugs.python.org/issue19227

best wishes,
-- 
Nick

---

From: Nick Mathewson <[email-masked]>
Date: Sat, 16 Nov 2013 22:24:18 -0500

> vague and overarching such as "bad design of the RNG pools".

Let me try to clarify what I meant by CC.  I agree that my original
wording was sloppy, and even though I was listing issues which to my
(limited!) knowledge have never actually led to a serious attack,
that's no excuse for being vague.  (To my further discredit,
re-reading what I wrote, I don't think it actually *could* have meant
what I meant it to mean, and the example I chose was a stupid one too.
Whoops.)

So here's what I should have said:

[...]

CC. Unproven cryptographic properties

We have (and continue to come up with) several definitions of what it
means for an RNG construction to be secure. We have some constructions
which we can prove to meet these definitions (though they may have
other issues), and some which don't seem to have security proofs but
which many reasonable practitioners believe to be secure anyway.

*All things being equal*, we would expect to have more confidence in
constructions where we can prove something useful about their security
properties.

(However, I am not personally aware of any example ad-hoc
cryptographic RNG constructions which lacked a security proof,
survived close scrutiny by sensible practitioners, and then later
turned out to be much more broken than expected in some cryptographic
way.  That' s why I'm classifying this as "probably problematic"
rather than "actually leading to attacks."  But if there's a counter
example, I would be excited to learn about it so that I can strengthen
my "you should probably make sure you have a proof" argument.)

((Further, I am aware that "all things" are never quite "equal", and I
would personally sidle away from quite a few current proven
constructions for other engineering reasons.))

best wishes,
-- 
Nick Mathewson

---

From: Arnold Reinhold <[email-masked]>
Date: Mon, 18 Nov 2013 07:42:18 -0500

> There should be a self-test part of the specification that detects this type of failure.  It should not be hard to turn the FIPS 140 test suite into a good-enough-to-continue / fail test.  This wou…

The FIPS 140 statistical test suite won't detect that a complier has optimized a RNG call out of a loop. A special test is require here. Also since any RNG likely to be recommended will either generate or whiten bits using a crypto primitive such as SHAx or AES, statistical tests on the output of such RNGs are of little worth. The output these primitives is guaranteed pass any such test even if their input has be tampered with to allow a small search space.

The place where statistical tests would be very useful is in checking a true random noise source. Here a trustworthy entropy source SHOULD exhibit some deviation from pure randomness. Unfortunately many true random bit generators have built in whitening circuits that prevent downstream software from testing the underlying noise source.  As I understand it, this is the case with Intel's x86 hardware RNG instructions. The lack of access to raw digitized noise makes such RNGs impossible to audit.

We are entering an era where many mission-critical internet devices use solid state mass storage and lack other peripherals that can be used to obtain entropy (such as audio inputs and cameras). There will be a strong tendency to rely solely on random bit generators built into billion-transistor CPUs or SoCs, which can have surreptitious back-doors inserted during production by organizations with enough clout.

Any standard that attempts to deliver real security must include some guidance on choosing hardware that includes more than one independent, auditable entropy source, each capable of delivering at least 128 bits at start up when brand new, at first power up.

Arnold Reinhold