back to article 'Predictably random' public keys can be cracked - crypto boffins

Cryptography researchers have discovered flaws in the key generation that underpins the security of important cryptography protocols, including SSL. Two teams of researchers working on the problem have identified the same weak key-generation problems. However, the two teams differ in their assessment of how widespread the …

COMMENTS

This topic is closed for new posts.
  1. elsonroa
    Go

    If this as big a problem as claimed, I've got a suggestion for an on-topic Reg Hardware review. How about taking a look at the Simtec Entropy Key? A true hardware random number generator for 36 quid must be worth investigating.

    Disclaimer: I'm in no way connected with Simtec, not astroturfing, etc...

    1. Destroy All Monsters Silver badge

      Intel has one, too:

      http://spectrum.ieee.org/computing/hardware/behind-intels-new-randomnumber-generator/0

  2. Gareth 7
    Boffin

    "Only one of the factorable SSL keys was signed by a trusted certificate authority"

    that's your problem there.

    Everything else is a non-story.

    1. Anomalous Cowherd Silver badge

      Re: "Only one of the factorable SSL keys was signed by a trusted certificate authority"

      Not really. If true it's quite interesting - routers etc. generate a self-signed keypair for their admin pages, so if there's a weakness there then you're in. From there you can still do fun stuff like DNS poisoning, although SSL sessions passing through the router would likely be OK.

      I'd be very surprised to see this affect "proper" servers other than embedded devices - surely most, if not all OSs include a decent RNG of some sort by now.

  3. Alan Firminger

    Question

    Does this also relate to the story higher up the page describing mobile 'phone money transfer ?

  4. Ru
    Paris Hilton

    I must admit I did not fully understand the original article

    As a result, I'm not entirely certain what the issue is here. Is it:

    - RSA is crap? Cos this would be Bad.

    - 1024bit keys are crap? Because this is somewhat less startling, though the underlying reason would be new.

    - Common random number generator implementations are not really cryptographically secure. This wouldn't really come as a surprise.

    If the real problem is PRNG implementations, then this is basically a non-story. If the problem is RSA, then this is a fair bit more serious. Anyone care to enlighten me?

    1. Destroy All Monsters Silver badge
      Headmaster

      Definitely not RSA. Looks like it's the seeders

      The PRNG algorithms may be good, but it seems they are started off with bad "seeds". Suppose you have a range of devices that hash the current output of "ps", then use the corresponding value as seed in "new Rand(seed)". If these are devices in which ps "more often than not" just lists the "init" process doing nothing and a "routerd" with low activity, then these seed value would tend to not be randomly distributed. As the values returned by "Rand" will be used in taking stabs at possible 1024-bit primes [testing for primality being easy], the primes found will tend to not be randomly distributed. Thus the RSA key (p-1)(q-1) IIRC will tend to not be randomly distributed.

      1. Ru

        Re: Definitely not RSA. Looks like it's the seeders

        Ta.

        So it is merely incompetent use of PRNGs then. Nothing to see here, move along.

        Insert obligatory 'openbsd sorted this out donkey's years ago'.

  5. Anonymous Coward
    Anonymous Coward

    99.8% secure?

    Still more secure than Microsoft products then!

    1. multipharious

      Re: 99.8% secure?

      how would you like to rank the other vendors in your +/- comparison as opposed to your subjective floating fart of a security rating? You anonymous dipshit.

  6. Version 1.0 Silver badge
    FAIL

    Let's go back 60 years ...

    "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin." - John Von Neumann, 1951

    It's not a new problem ... about the first thing I was taught in statistics ("A" level when that actually meant something) was that the term is pseudo-random numbers ... calling them "random" was a guarantee of the imminent meeting of a chalk board eraser and my head.

    1. Destroy All Monsters Silver badge
      Headmaster

      Yes! You! Stand still laddy!!

      > Calling them "random" was a guarantee of the imminent meeting of a chalk board eraser and my head.

      But then again, if your string generated by a good PRNG is "short enough", it will be "random enough for your purpose".

      Note that good definitions of randomness are quite recent too, so your prof may have been exceedingly brutal to you:

      http://en.wikipedia.org/wiki/Algorithmically_random_sequence

  7. Anonymous Coward
    Flame

    The Problem Of Randomness

    Many if not most experienced developers can't think the concept of entropy radically to the end, despite the fact that it is quite simple, actually.

    So what they do is to sample a clock with shoddy resolution (say 10 ms) once and then seed a s**ty PRNG such as rand(5) from that. And then they make rand(5) emit hundreds or thousands of supposedly random bits.

    In reality, what they do is to sample a shoddy timer, which has only 86400*100=8,4 million == 23bits of entropy per day. So if you know a webserver has been started in a timeframe of +/- 5 days, the key space is 5*2*8,6E6== 26 bits of entropy.

    Searching a keyspace of 26bits is well within the reach of the lamest PC which exists in a modern juvenile bedroom. Netscape had exactly this problem in their webservers and I know of a very similar issue from a "e-banking security firm", which thought rand(5) would be good for creating cookies.

    So whenever you sample something, ask yourself *rigorously* how many bits of *real* entropy you actually acquire. Just because you can sample something 100 million times a second does not mean it does change at that rate, for example. Just because you sample at 16 bit accuracy does not mean that measurement interval will be evenly used.

    1. Michael Wojcik Silver badge

      The Problem of Cryptographic Software

      > Many if not most experienced developers...

      ... should not be writing CPRNGs in the first place. Or using them. Or writing cryptographic software.

      It's a specialty area, and should be handled by specialists.

      That said, my guess is that "many if not most ... developers", experienced or otherwise, who have a hand in writing TLS-enabled software are using either OpenSSL or a commercial equivalent, so they're not sampling the RTC or using the C library's rand(). It's quite likely that they're not gathering much entropy for their CPRNG (most of the OpenSSL-based software on Windows I've seen source for just uses RAND_screen(), for example), but they're not writing the primitives.

  8. This post has been deleted by its author

    1. Anonymous Coward
      Anonymous Coward

      Re: Good PRNG?

      For cryptographic puposes nothing short of a strong cipher such as AES or a strong hashing algorithm like SHA256 will suffice as the core of a PRNG.

      The standard rand of stdlib is horribly bad even for simulations, as all random numbers are located on the same plane of a 15-dimensional space, iirc.

      But the biggest issue often is related to insufficient physical randomness.

  9. Anonymous Coward
    Anonymous Coward

    Cheap solution

    We take the bottom bit from a thermally noisy source input into an ADC channel sampled 32 times as a seed. Difficult to argue it is truely random as coupling from other noise sources will occur and you could imagine deliberately intruding power supply noise. The probability of high and low bits is not the same due to the ADC DNL not being perfect but still for practical purposes and at a reasonable threat level it seems a reasonable approach and is very cheap for an embedded device.

    1. Version 1.0 Silver badge
      FAIL

      Re: Cheap solution

      Pretty typical - and unfortunately it's probably not nearly as random as you think. People love to come up with these pseudo-random seed ideas but virtually never actually sit down and test their method to check their values approximate to "random"

      Of course - a lot depends on what you need the random number for - in many cases "good enough" is actually fine for the original design needs - and then someone reuses the function later on for an application that it's actually worth someones while to break.

    2. Michael Wojcik Silver badge

      Re: Cheap solution

      Ah, if only someone like John von Neumann had considered the problem in biased entropy sources and developed algorithms to account for it.

      That said, as another poster noted, external entropy sources often turn out to be weaker than expected, particularly for security purposes. There have been a variety of successful attacks against them. Tons of literature is available on the subject, including sources (thermal noise, Zener diode breakdown, radioactive decay, whether the cat wants in or out), unbiasing, sampling limitations, side-channel attacks, active attacks, etc. After the successful attacks on the CPRNG in Netscape's original SSL implementation it became a favorite parlor topic for crypto nerds.

  10. asdf
    Mushroom

    what a need

    For a true random seed can't beat radioactive decay - www.fourmilab.ch/hotbits/

  11. John Smith 19 Gold badge
    Unhappy

    Good PRNG?

    I've heard there's some fellow called Knuth whose written a big book, some of which is about PRNG's, what makes a good one, how to generate them etc.

    He's a mathematician so I'd guess he might know what he's talking about.

    It seems not many developers have read it.

    1. Michael Wojcik Silver badge

      Re: Good PRNG?

      There's a ton of literature. Anyone implementing a non-trivial PRNG, and certainly a CPRNG, should also read Marsaglia and others.

      But as I noted above, it's a specialist area. While reading up on it is certainly a useful intellectual exercise, there aren't many developers who should be doing it in the first place. We don't need everyone reinventing the wheel, particularly when it's a very complicated wheel with subtle and dangerous failure modes.

This topic is closed for new posts.

Other stories you might like