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

Aaron Zauner azet at azet.org
Tue Nov 26 11:32:37 CET 2013

Hi Ralf,

We’re still looking for someone able to write a comprehensive section (with short introduction) for RNGs. Our current point of view is: One should use RNGs as provided by the operating system - since those are audited frequently. The issue with VMs/Embedded Devices and low-entropy hardware still remains. Maybe someone should write a paragraph on the matter. Are you interested?

I still don’t think that we should recommend switching to other RNGs then those provided by the OS. If we do so, please cite why one should do that.


On 26 Nov 2013, at 10:43, Ralf Schlatterbeck <rsc at runtux.com> wrote:

> 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
> _______________________________________________
> Ach mailing list
> Ach at lists.cert.at
> http://lists.cert.at/cgi-bin/mailman/listinfo/ach

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 1091 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.cert.at/pipermail/ach/attachments/20131126/e0beabd8/attachment.sig>

More information about the Ach mailing list