[Ach] Random number generators (was Bug/Ba in OpenSSL)

[Ralf Schlatterbeck]

On Mon, Nov 25, 2013 at 06:24:41PM +0100, christian mock wrote:
> From googling around a bit, I found that some people are less than
> happy with haveged:
> 
> http://jakob.engbloms.se/archives/1374
> 
> https://polarssl.org/tech-updates/security-advisories/polarssl-security-advisory-2011-02
> 
> They say adding (fake) entropy to the pool can't be bad since the
> entropy shouldn't decrease, but the danger may be that you think you
> have enough entropy while you haven't...

Both of these results are from virtual machines or simulators. In these
simulators, both, the model of the CPU *and* the timing source can be
non-random. Obviously the "Random" number generator in this case
degenerates to a Pseudo-Random number generator. With no good timing
source the Kernel RNG (/dev/random or /dev/urandom) will also not
produce very random results.

This means we should be worried about hardware random number generators
on virtual machines in general.


On Tue, Nov 26, 2013 at 12:55:44AM +0100, Philipp Gühring wrote:
> 
> I collected several HAVEGE submissions on my random number analysis
> service, and all of them were good:
> http://www.cacert.at/cgi-bin/rngresults
> To me that says that HAVEGE isn?t completely broken, and provides high
> entropy, as it should.

See the second cited blog-post above: As the author of HAVEGE comments
on the blog-post, on a simulator that simulates CPU *and* Timing source
HAVEGE will degenerate to a (good) pseudo-random number generator.
HAVEGE comes with a test-suite that doesn't catch this and I doubt other
statistical methods would. Still on two identical runs of the simulation
you'd get the same pseudo-random sequence (!)

I agree on the other assertions that HAVEGE can be used to augment the
Kernel random number generator in certain situations where your random
sources are limited. This occurs mostly in embedded devices like WLAN
routers etc. For these devices HAVEGE will improve your random-number
source.

So the other types of devices we should be worried about are embedded
devices where the number of randomness sources for the kernel RNG are
limited:

There are two independent papers on RSA factoring where researchers
collected huge amounts of RSA keys and did pairwise GCD on RSA moduli
(the actual approach used for computing pairwise GCD is more efficient
than really doing it pairwise). If two moduli N1 and N2 share a prime
both can be trivially factored recovering the private RSA key. I was
surprised that the number of shared prime keys was in the low percentage
range of all keys tried:

[1] Arjen K. Lenstra et. al.: "Ron was wrong, Whit is right"
http://eprint.iacr.org/2012/064.pdf

[2] Nadia Heninger, Zakir Durumeric, Eric Wustrow and J. Alex Halderman,
"Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network
Devices"
Extended version:
https://factorable.net/weakkeys12.extended.pdf
Conference version:
https://factorable.net/weakkeys12.conference.pdf

When citing [2] in the following I'm referring to the extended version.

If you only have time to read one of those, definitely read the second
one. They did their homework and actually tried to find out which
devices caused the observed behaviour.

Interesting is that Lenstra et. al. conclude that DSA would be more
secure (!) although the other paper finds the opposite: DSA will give
away your private key if the ephemeral key is ever re-used for two
different messages. This actually was observed for devices with low
entropy RNGs (!) [2 section 5.3 p.14 and section 6 p.15].

The Linux kernel has two RNGs, one that blocks if not enough entropy is
available (/dev/random) and one that just returns whatever
non-randomness there is (/dev/urandom). The surveyed crypto
implementations in [2] all use /dev/urandom, unfortunately. Worse: OpenSSL
re-seeds the internal Pseudo-RNG only very seldomly from the hardware
RNG, so an initial predictable RNG-State will be used for a long time.
This means that the dropbear SSH daemon on these devices is vulnerable
because it seed the internal OpenSSL Pseudo-RNG during startup (when no
entropy is available) and keeps using it even if you log in hours later
when enough entropy in the kernel RNG would be available [2, p.14] (!)

One reason for the Linux RNG failing on these devices is that Linux
isn't using interrupt timing as a RNG timing source anymore for some
time (see p.11 of [2]). The intent to replaced this with a collection
mechanism tailored to different interrupt sources is still
unimplemented.


On Mon, Nov 25, 2013 at 07:29:59PM +0300, ianG wrote:
> 
> Typically, when it comes to RNGs, tools should use the default
> available, and mucking around with options isn't advisable.
> 
> If we look at the problems we've had with RNGs, they've been mostly
> unfixable at the user level.  From memory, early Java, Android,
> Debian.

I agree that the bug in debian wouldn't have been fixed by using a
different/better HW RNG (not sure about the others) but I'd recommend to
add additional random sources for embedded devices as these lack a lot
of random sources you have on other machines:
- No persistent clock, so boot-time is not contributing to the initial
  RNG state
- No hard-disk
  - no entropy source of hard-disk timing
  - no storage of previously gathered entropy between reboots
- Interrupt timing gone from Linux RNG
- Use of /dev/urandom
- OpenSSL maintaining its own entropy pool

For me this means: HAVEGE is a good addition for embedded devices and we
should recommend it.

My take-away from these papers and the results on VMs:
- Be worried about entropy sources on virtual machines, adding other
  mechanisms like HAVEGE will probably give you a false sense of
  security as large portions of the hardware may be emulated, including
  timers. This means that both, the HAVEGE entropy *and* the entropy
  collected by the kernel HW RNG might be overestimated.
- Be worried about entropy sources on embedded devices as these lack
  a lot of entropy sources other machines have.
- Even on normal servers entropy may be low due to missing interrupt
  entropy sources in the Linux HW-RNG although [2] state that typical
  Linux distros didn't fail their tests.
- When in doubt about your HW-RNG prefer RSA over DSA as the latter
  might give away your private key in times of low entropy due to re-use
  of an ephemeral key for different messages.


Since I've been only lurking on this list so far a short intro:
I'm working as a developer and consultant self-employed for almost ten
years now. Besides doing software development I'm doing some security
audits -- mostly firewall stuff and VPN configs.

Ralf
-- 
Dr. Ralf Schlatterbeck                  Tel:   +43/2243/26465-16
Open Source Consulting                  www:   http://www.runtux.com
Reichergasse 131, A-3411 Weidling       email: office at runtux.com
allmenda.com member                     email: rsc at allmenda.com