back to article 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 …

  1. Charles 9

    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).

    1. Anonymous Coward
      Anonymous Coward

      Ditto. I'd be perfectly happy to squander a megabyte or so of 64GB on a big well stirred reserve which could slowly accumulate for those occasions when I need it. It seems like limiting yourself to a button cell when you could be trickle charging an accumulator.

    2. 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.

  2. Anonymous Coward
    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!

    1. DryBones
      Boffin

      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.

      1. DropBear
        Facepalm

        "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?!?

        1. 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!

          1. 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.

            1. Anonymous Coward
              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).

              1. 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.

      2. Michael Wojcik Silver badge

        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.

    2. Anonymous Coward
      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.

    3. Robert Carnegie Silver badge

      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.

      1. Will Godfrey Silver badge

        Talking of shuffles, I saw one that specifically blocked moving an item back into the place it had just come from. The programmer couldn't understand that that is a perfectly valid random operation.

        1. Anonymous Coward
          Anonymous Coward

          That programmer didn't go on to become an "infosec boffin" perchance?

    4. 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.

    5. Michael Wojcik Silver badge

      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.

  3. a_yank_lurker

    To me this research seems to imply that with enough computer there is no perfect encryption scheme just more difficult and easier ones. Also, the theoretical time needed to crack an encryption scheme is much shorter than previously thought.

    1. Preston Munchensonton
      Facepalm

      Of course there's no perfect encryption if there's enough computer time. If computer time is unlimited, entropy and randomness in encryption will never matter due to simple brute force attacks. SMH

    2. Anonymous Coward
      Anonymous Coward

      Does the PCIDSS factor into this?

      By requiring that only a single function be performed per server, are they making this problem worse?

  4. Robert E A Harvey

    Bonds

    I'd be curious to see his analysis of ERNIE.

    1. Richard Taylor 2

      Re: Bonds

      ERNIE was not (maybe no longer is) a pseudo random generator but based on what is still understood to be robust random processes

    2. Anonymous Coward
      Anonymous Coward

      Re: I'd be curious to see his analysis of ERNIE.

      He drove the fastest milk cart in the west.

    3. 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."

      1. Adam Inistrator

        Re: Bonds

        "and the draw is only valid if it is statistically random." ... so if the draw came up 1,2,3,4,5,6,7,8,9 ... they would discard it as not being random?

  5. Roq D. Kasba

    Nonces

    One word, two very different meanings!

    1. Anonymous Coward
      Anonymous Coward

      Re: Nonces

      That's nonce-sense (with thanks to Chris)

      1. This post has been deleted by its author

  6. 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.

    1. Anonymous Coward
      Anonymous Coward

      cheap random number generator

      You could probably get something cheaper by repurposing a sound card, with or without a microphone to pick up noise from a fan in addition to the electrical noise.

      1. Anonymous Coward
        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.

        1. Anonymous Coward
          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.

          1. Anonymous Coward
            Anonymous Coward

            Re: cheap random number generator

            But standard sound cards use chips, too. Who's to say Men In Black wherever it was made subverted the sound chips, too?

  7. JimmyPage Silver badge
    Boffin

    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 ?

    1. Anonymous Coward
      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)

    2. 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.

      1. Anonymous Coward
        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?

      2. Tannin
        Coat

        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?

    3. Nick Kew

      Re: Brainstorming ....

      Schrödinger's cat < /dev/random >> entropy?

    4. Richard Taylor 2
      Happy

      Re: Brainstorming ....

      3) Use next weeks lottery numbers ?

      If you could point me to a source pf next weeks lottery numbers I would be very grateful. Ta in advance.

  8. Anonymous Coward
    Anonymous Coward

    Anyone know whether Simtec is alive or dead?

    http://www.entropykey.co.uk/

    1. Charles 9

      Re: Anyone know whether Simtec is alive or dead?

      Overwhelmed, last I heard. There's a comparable product called the TrueRNG on the market now that seems to have plenty on hand and is competitively priced.

      1. Anonymous Coward
        Anonymous Coward

        Re: Anyone know whether Simtec is alive or dead?

        "Overwhelmed" with what exactly? Opportunity to make some dosh? Bizarre. So much security related bizarreness lately. Bizarrer and bizarrer...

        1. Anonymous Coward
          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.

  9. Dave 32
    Coat

    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.

    1. 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?

  10. 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)

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon