I've always been curious as to why the Linux kernel entropy pool is (AFAIK) normally capped at 4096 bits even in a world where there is an increasing need for good random numbers (which /dev/urandom can't always provide).
Random numbers aren't, says infosec boffin
The randomness (or rather, lack thereof) of pseudo-random number generators (PRNGs) is a persistent pain for those who work at the low layers of cryptography. Security researcher Bruce Potter, whose activity in the field stretches back more than a decade, when he demonstrated war-driving using Bluetooth, says problems both in …
COMMENTS
-
-
Tuesday 11th August 2015 06:26 GMT streaky
If you pool a huge volume of supposedly random data used for crypto you create entirely different challenges. The issue isn't creating volumes of it anyways, the main issue is PRNGs are notoriously hard to both prove and disprove the validity of, unless they're extremely broken.
-
Tuesday 11th August 2015 03:37 GMT Anonymous Coward
“OpenSSL does not check to see the quality of the entropy when it polls /dev/urandom”
And why would it? The small amount you pull will with proportional statistically certainty meet whatever statistical "test" you apply to it and whether or not any specific tiny sample passes a "test" or not is abjectly meaningless. In fact, if you were to start arbitrarily rejecting arbitrary output based on arbitrary "tests" you'd achieve nothing but an arbitrary degradation in the very thing you think you're attempting to improve. Such is the meaning of random. What matters is whether or not the (p)RNG works and this is absolutely not the same thing as whether or not some arbitrary output happens to "look" random... whatever that's supposed to mean...
Jesus!
-
Tuesday 11th August 2015 05:22 GMT DryBones
Well, the problem here is that in order to properly test for randomness, you need a sufficiently large sample size tested against it, and to understand the conditions under which the randomness is maintained. If you test a hundred numbers that look good, but after a thousand it loops back to the beginning...
Take my vehicle's radio. The MP3 "shuffle" functionality at first blush might seem to work just fine. However, once you've drive it for a year you'll realize that it has a very, very strong tendency to a certain pattern of song numbers, and with one or two variations in places, follows it every single time it decides to reset to the start of the pseudorandom sequence. This is a crap implementation, and I've complained to them that beginning programmers learn how to seed their random number generator better than this, please replace their intern and recompile.
-
Tuesday 11th August 2015 11:18 GMT DropBear
"Take my vehicle's radio"
Amen to that - except I have the same problem with my wallpaper changers: I have about a thousand lovely panoramas queued up, but I only ever see about 50 of them, no matter what wallpaper changer I test. Rather astoundingly nobody writing these things seems to have heard of the "any random item picked from the ones that haven't been shown yet" strategy. Seriously, how hard is it to keep a list?!?
-
Tuesday 11th August 2015 12:09 GMT Tim 11
"Take my vehicle's radio"
I have noticed what seems to be a lack of randomness in car audio track selections, but on doing a bit of research I believe this is actually psychological - I'm sure even the most basic computing device easily has the capabilities to generate PRNs that appear random to a casual observer.
However, what you want most of the time is a shuffle, not a random!
-
Tuesday 11th August 2015 13:25 GMT Charles 9
Re: "Take my vehicle's radio"
"However, what you want most of the time is a shuffle, not a random!"
But a shuffle (list randomization) isn't that difficult either. A Modern Fisher–Yates shuffle is iterative and needs no more space than the playlist itself. The only limiting factor is the RNG.
-
Wednesday 12th August 2015 06:24 GMT Anonymous Coward
Re: "Take my vehicle's radio"
A Modern Fisher–Yates shuffle is iterative ... needs no more space than the playlist itself
Actually, in practice FY needs space equivalent to the total size of the collection in quite a few cases unless you're happy with the increased cost of memoising the swaps and losing the O(1) property (that would be a total no-no in crypto apps where side channel attacks need considering).
Floyd's algorithm is basically equivalent, though it will give a different sequence for a given random seed. It's a lot less tricky to implement, too, but that's basically because it hides the complexity by assuming you have efficient set operators available (which are also tricky to do in crypto).
-
Wednesday 12th August 2015 12:52 GMT Charles 9
Re: "Take my vehicle's radio"
"Actually, in practice FY needs space equivalent to the total size of the collection in quite a few cases unless you're happy with the increased cost of memoising the swaps and losing the O(1) property (that would be a total no-no in crypto apps where side channel attacks need considering)."
I was talking in terms of a simple music playlist, in which case the playlist is a separate array from the actual table of music files (stored separately), which makes sense if you want to customize the playback in other ways. With the Modern Fisher-Yates Shuffle, you alter the playlist in situ by going down the list in order (direction doesn't matter) and swapping each entry you come across with any of the ones after it. All you need is one placeholder to hold values during swapping, nothing else. And it's O(1) space, O(n) time, and uses no floating points, so it's something any processor capable of MP3 playback should be able to do.
-
-
-
-
-
Thursday 13th August 2015 02:21 GMT Michael Wojcik
This is a crap implementation, and I've complained to them that beginning programmers learn how to seed their random number generator better than this, please replace their intern and recompile.
It's not a seeding problem. They shouldn't be using a PRNG directly to select the sequence at all. They should be generating a permutation over the entire sequence, exhausting that, and then generating another one. You could do this by selecting a generator, but it's a lot easier to do a straightforward fair shuffle using the standard swapping algorithm.
The problem is 1) you need a small1 amount of additional storage (for the array of shuffled indices), and 2) these things are written by crap programmers who know little about computation.
1Time and space for this algorithm are both O(N)2 with small constants. The space requirement is negligible compared to the size of the files.
2Edit: Just saw Charles 9's post where he points out you can do it with constant (trivial) space. Quite right.
-
-
Tuesday 11th August 2015 12:14 GMT Anonymous Coward
Whoops. My previous splaff should have begun:
"And why would it? The small amount you pull will, with proportional statistical certainty, meet whatever statistical "test" you apply to it.. "
'Twas an unfortunate place for an editing artefact to land - plumb amidst an already grammatically obtuse rambling fulmination. Humblest apologies to all.
-
Tuesday 11th August 2015 15:45 GMT Robert Carnegie
Is the implication that you can, if you so wish, ask the PRNG how much entropy it has, and, if it's not much, then wait until there is more?
Popping up a dialog box that says "Please type some random gibberish to seed the PRNG properly" may be an option.
And you carefully type "Colorless green sheep graze curiously" every single time, just to see what happens.
-
Wednesday 12th August 2015 06:57 GMT Frumious Bandersnatch
re: In fact, if you were to start arbitrarily rejecting arbitrary output ...
Yup. Chi^2 test will tell you your PRNG output is bad some portion of the time. In the same way that PKZIP will sometimes be able to compress some truly random data.
I agree with AC. Rejecting results based on how non-random they look reduces available entropy.
-
Thursday 13th August 2015 02:28 GMT Michael Wojcik
The comment about OpenSSL only seeding the pool "at startup" is complete bullshit too. The caller can add entropy to the pool anytime.
If low pool entropy is a potential problem for an OpenSSL-based application, then it's the application's responsibility to do something about that. OpenSSL isn't responsible for lazy programmers.
-
-
-
Tuesday 11th August 2015 09:14 GMT Graham Marsden
Re: Bonds
"The first ERNIE was built at the Post Office Research Station by a team led by Sidney Broadhurst.The designers were Tommy Flowers[14] and Harry Fensom and it is based on Colossus, the world's first digital computer.[15][16] It was introduced in 1957,[1] and generated bond numbers based on the signal noise created by neon tubes."
[...]
"ERNIE 4 uses thermal noise in transistors as its source of entropy for generating true random numbers; the original ERNIE used a gas neon diode. Pseudorandom numbers, often called simply random, can be recreated by anybody who knows the algorithm used to generate them as they are produced in a deterministic way; true random numbers can not. The randomness of ERNIE's numbers derives from random statistical fluctuations in the physical processes involved. ERNIE's output is independently tested each month by an actuary appointed by the government, and the draw is only valid if it is statistically random."
-
-
-
This post has been deleted by its author
-
-
-
Tuesday 11th August 2015 06:34 GMT silent_count
This bloke is putting together a good quality, hardware RNG for ~$50 USD a pop, which leads me to a couple of observations.
The first is that a few of his RNGs would be a no-brainer purchase for anyone who is serious about crypto-based security. And secondly, I wonder how much it would add to the price of a CPU if someone the scale of Intel or AMD bought him out and gave away a hardware RNG dongle with every CPU sold.
-
-
Tuesday 11th August 2015 11:39 GMT Anonymous Coward
Re: cheap random number generator
I've actually tried it with sound cards and USB webcams (duck-taped over) via a couple daemons by Vanheusden: audio_entropyd and video_entropyd. The problem is that the noise they produce is hard to really call random. The daemons use the FIPS180-2 test suite to try to verify the chunks, but even these have trouble it seems when put up against the chi-squared analysis.
Anyway, the grandchild of these cheap entropy makers has gotta be the EntropyKey, which has sadly vanished probably in the wake of overwhelming demand. In the US, there's the TrueRNG, which is comparably priced to both the EntropyKey and the proposed OneRNG.
PS. I notice on the homepage the OneRNG design still uses a chip. I wonder how one can verify the chip isn't compromised in some way.
-
Tuesday 11th August 2015 12:18 GMT Anonymous Coward
Re: cheap random number generator
"the noise they produce is hard to really call random"
The noise doesn't have to be random (whatever that means); it just has to contain an unpredictable component. You make a cryptohash of the data and take out a number of bits based on a conservative estimate of the size of the unpredictable component.
"I wonder how one can verify the chip isn't compromised in some way."
I would guess that one can't, so it's better to use a standard sound card.
-
-
-
-
Tuesday 11th August 2015 07:59 GMT JimmyPage
Brainstorming ....
1) Use t'internet. Aggregate a few thousand web pages from a dictionary of millions (say every odd result from a Google search for cat videos, plus every even result from yesterdays most popular search), then a running XOR of a selection of bits from said pages to give you a seed ?
2) Surely there is a market for a chip with an inbuilt radioactive source, detector and a clock ? (I've seen an old XT clock chip with an inbuilt battery). You'd only need picograms of material.
3) Use next weeks lottery numbers ?
-
Tuesday 11th August 2015 08:16 GMT Anonymous Coward
Re: Brainstorming ....
1) Poor idea in general but catastrophic if your pipes are being sniffed by an adversary who knows what PRNG you're using
2) Indeed and it's being well served. HRNGs in general used to be prohibitively (for normal-personal use) expensive but recently much more sensible products have started to appear. I suppose the problem is trusting them in a context of free-floating paranoia - the designers, the manufacturers, the couriers, the "customs" process, etc..
3) Now we're cooking.
4) Feed /dev/random (HAVEGED, audio-entropyd etc)
-
Tuesday 11th August 2015 08:23 GMT Nigel 11
Re: Brainstorming ....
You really don't want anything radioactive integrated into a VLSI chip. Each radioactive decay can corrupt a bit of data, just as well as contributing to a bit of random numbers. It all depends on what random direction it is emitted in!
OTOH all motherboards ought to include a noise diode and supporting electronics, and a "gold standard" radioactive-decay noise source on a USB dongle shouldn't be expensive.
-
Tuesday 11th August 2015 08:46 GMT Anonymous Coward
Re: Brainstorming ....
"all motherboards ought to include a noise diode and supporting electronics"
Absolutely! I've never understood why the premium home-build board paddlers at the very least don't do this, or even just a socket for such a HRNG boardlet... Shirely it'd be a superb (dirt cheap but geekgasmic) selling point for the target market? Perhaps US "export" (import) regulations prohibit proper HRNGs or somesuch insanity?
"and a 'gold standard' radioactive-decay noise source on a USB dongle shouldn't be expensive."
Homebrew Arduino/USB Geiger counter & old smoke alarm?
-
Tuesday 11th August 2015 09:27 GMT Tannin
Re: Brainstorming ....
"You really don't want anything radioactive integrated into a VLSI chip. Each radioactive decay can corrupt a bit of data, just as well as contributing to a bit of random numbers."
So you are saying the result of your calculations, given the corrupt bits, is likely to be a bit ...er .... random?
-
-
-
-
-
-
Tuesday 11th August 2015 13:29 GMT Anonymous Coward
Re: Anyone know whether Simtec is alive or dead?
Overwhelmed with demand and not enough supply is seems to keep up. According to their shop page:
"Please note that there is a very long waiting period for Entropy Keys at the moment. We currently have no stock and do not have a date for when we will have more."
So according to them their supply of components has apparently been cut off. Now, why they haven't worked around it by this time, I don't know.
-
-
-
-
Tuesday 11th August 2015 17:14 GMT Dave 32
RNGs
There are some of us here to take RNGs VERY seriously. I happen to work on a hardware cryptographic card, which has an embedded hardware RNG.
The basic rule is that PRNGs are all but useless for anything other than toy applications. Even the best ones are subject to predictability, if one had enough data and knows the algorithm being used (and, one has to believe that there are organizations out there that can reverse engineer the hardware/software being used).
There are even some us who are somewhat skeptical of NIST's SP800-90A "Recommendation for Random Number Generation Using Deterministic Random Bit Generators" as being possibly predictable (although unlikely).
As for noise sources, note that not all sources are necessarily random. Some of the posters here have mentioned using Avalanche/Zener Diodes as a source of randomness. There is some empirical evidence that indicates Avalanche/Zener Diodes may exhibit a negative resistance characteristic, under a certain set of conditions, in which case, the typical circuit will produce a relaxation oscillator, which will produce a VERY non-random signal. As evidence of this, consult figure 5, on page 19, of On-Semi's "TVS/Zener Theory and Design Considerations
Handbook":
http://www.onsemi.com/pub_link/Collateral/HBD854-D.PDF
Especially, note those zigs in the expanded portion of the voltage-current chart, and realize that those zigs represent regions of negative resistance. The theory behind these zigs is something called "Microplasma Discharge Theory", which, as far as I've been able to tell, is not well understood in the physics community.
There are, of course, a LOT more considerations that need to be given to producing a good RNG, but I really don't want to write a book here.
Dave
P.S. I'll get my coat. It's the one with the pair of loaded dice in the pocket.
-
Tuesday 11th August 2015 17:24 GMT Charles 9
Re: RNGs
"The basic rule is that PRNGs are all but useless for anything other than toy applications. Even the best ones are subject to predictability, if one had enough data and knows the algorithm being used (and, one has to believe that there are organizations out there that can reverse engineer the hardware/software being used)."
So you're basically saying Cryptographically-Secure PRNGs (CSPRNGs) is basically a misnomer? Even if it were to be re-seeded in relatively short periods with numbers from a hardware RNG?
-
-
Wednesday 12th August 2015 06:43 GMT Frumious Bandersnatch
what the world needs now ...
is "entropy, sweet entropy?"
Is it really the only thing that there's just not enough of (in /dev/urandom)?
a) use /dev/random, perchance?
b) chain output of a "good" message digest algorithm back into itself?
c) improve (b) by agreeing a nonce and using digest in HMAC mode?
d) "reverse-bias Zener diode" (a magic incantation I remember from many years back)