Over the weekend, it emerged that a flaw in Android's Java-derived pseudo-random number generator (PRNG) created a vulnerability that allowed the theft of Bitcoins. The individual responsible identifying the nasty bug, Jean-Pierre Rupp, has now contacted The Register by e-mail to confirm how he was able to track down the …

COMMENTS

House rules Send corrections

This topic is closed for new posts.

Tuesday 13th August 2013 03:18 GMT Schultz

Random numbers

With so many sensors in every modern computer or phone, isn't there a way to generate random numbers from a physical device? Bit-noise of a camera, fluctuations in a temperature sensor, ... there should be a lot of randomness at the limits of any physical measurement. Somebody might even build a special random number generator based on some measurement, it shouldn't be too hard (although testing it under all possible operating conditions might take some efforts).

2 0
1. Tuesday 13th August 2013 05:44 GMT T. F. M. Reader
  
  Re: Random numbers
  
  The problems with "real" random number are a) performance and b) limited entropy pool. So they are very useful for seeding, but heavy lifting is normally done by PRNGs (disclaimer: my experience is more in simulations than cryptography - the latter has more requirements but maybe does not need as many random numbers, depending on application).
  
  It is not always clear that you can measure physical parameters (such as temperature) with precision that would be useful for the purpose.
  
  What is often useful is timings. E.g., the only useful entropy source in a server is the tiny fluctuations (least significant bits) in disk seek times due to the air turbulence generated between the rotating disk and its enclosure [side note: I have no idea how the problem is solved in servers with SSDs only - I don't think it is discussed much]. In PCs, timings of keyboard/mouse events are used (we humans are unpredictable, apparently). I would be interested to know if Android/iOS/WP utilize timings of touch events for the purpose. On Linux, ou get that entropy from /dev/urandom and friends, but I have never looked at the Android kernel to see what the sources are.
  
  But then, again, all that would be to seed a PRNG, which you still need if you need a lot of randomness fast. And a good, i.e., random, PRNG is notoriously difficult to create. Most of those you are familiar with (those from standard libraries that come with different languages, popular common numerical libraries, operating systems, etc.) are not very good.
  
  3 0
2. Tuesday 13th August 2013 05:48 GMT kain preacher
  
  Re: Random numbers
  
  You mine like combining the motion, light and temp sensor with time and date . Literally just shake your phone to get an secure rnd. Then and all of the other senor. Wouldn't that count as a true rnd ?
  
  1 0
  1. Tuesday 13th August 2013 06:04 GMT bazza
    
    Re: Random numbers
    
    Shake a device to get randomness? That'll be not very good, especially if the user is told to shake the phone for that purpose...
    
    0 0
    1. Wednesday 14th August 2013 04:30 GMT kain preacher
      
      Re: Random numbers
      
      Fine have them tilt it 5 times. Plus You would use other sensors. No one sensor would give you the number.
      
      0 0
3. Tuesday 13th August 2013 08:23 GMT g e
  
  Re: Random numbers
  
  Coincidence is a strange thing isn't it. I was just suggesting to someone yesterday that they could use stock exchange or forex values as a crypt seed or something bizarre like the humidity in Bolivia.
  
  1 0
4. Tuesday 13th August 2013 10:20 GMT Matthew 3
  
  Re: Random numbers
  
  This was a feature on BlackBerries. (remember them?) You used to be asked to move around the trackball-thingy™ which generated genuinely random data.
  
  0 0
  1. Tuesday 13th August 2013 10:47 GMT WraithCadmus
    
    Re: Random numbers
    
    In a similar vein Connectbot on Android invites you to rub the touchscreen when generating an SSH key.
    
    1 0
Tuesday 13th August 2013 11:13 GMT Jason Bloomberg

Define "random"

The problem here does not seem to be with randomness but that randomness was relied upon to not produce a key collision when that's entirely possible with any finite set of 'random numbers'.

It seems to me to be the exclusion of key collisions which failed, not the means of generating the number which simply has to be different from all previously selected numbers, though 'quite different' is probably a desirable property in the selected numbers.

0 0
1. Tuesday 13th August 2013 22:01 GMT Old Handle
  
  Re: Define "random"
  
  I don't think that's it. If there was some kind of safety check to that effect, it might have helped catch the bug sooner, but relying on random numbers not to collide isn't unreasonable, as long as they're big enough. Bitcoin itself relies on this. The private keys are 256-bit random numbers, and since you don't know other people's private keys, obviously it's impossible to exclude them. But 2^256 is so mind bogglingly big (roughly 1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000) that the risk of collision is small. How small? Lets say a billion Bitcoin addresses currently exist. I have no idea if that's that true, what the heck, let's make it a trillion. Go ahead and knock 12 zeros off that number. The odds of a new key colliding are 1 in... that. Provided, you're generating properly random enough numbers, of course.
  
  0 0
2. Wednesday 14th August 2013 17:34 GMT Michael Wojcik
  
  Re: Define "random"
  
  The problem here does not seem to be with randomness but that randomness was relied upon to not produce a key collision when that's entirely possible with any finite set of 'random numbers'.
  
  The problem was not with randomness in any way, shape, or form. It was with pseudo-randomness, and specifically with not seeding the PRNG, which caused collisions in one of the parameters for the EC signature algorithm.
  
  It's not clear from the article (or the linked-to materials) whether the issue was actually in the Android implementation of SecureRandom, or in how the BitcoinJ code used SecureRandom. The latter seems a bit more likely, given the various comments from Rupp, Hearn, and others, but this story and the one yesterday are both pretty confused. (Re yesterday's: while it may well be the case that "Android phones/tablets are weak", that's not what Hearn said. He said that the keys generated by such devices were weak.)
  
  What's really annoying here is that weak PRNG seeding is one of the most famous attacks on modern cryptosystems, as it was successfully used against Netscape's first SSL implementation. It's like example #1 of a side-channel attack in Intro to Cryptography. These days, I often find half-assed crypto code agonizing over harvesting entropy for the PRNG, despite plenty of more glaring vulnerabilities elsewhere. We shouldn't be seeing this, particularly not in an application where there's an easy and significant payoff for breaking the system.
  
  1 0