The Register® — Biting the hand that feeds IT

Feeds

Crypto guru warns over random number backdoor

Spooky

Agentless Backup is Not a Myth

A top cryptographer has expressed concern about a possible backdoor in a standard for random-number generators approved by the National Institute of Standards and Technology (NIST) this year.

Random number generators are important because the correct operation of SSL and other protocols relies on their randomness. Standards set in this area by NIST are significant because they are likely to be followed by hardware and software suppliers in much the same way that the Advanced Encryption Standard (AES), which was also approved under the auspices of the NIST, has become widely adopted.

NIST gave its seal of approval to the use of four "Deterministic Random Bit Generators" for random number generation in March, with the release of its NIST Special Publication 800-90 paper (PDF). The four techniques are based on hash functions, Hash Message Authentication Codes, block ciphers and elliptic curves cryptography. All four are based on existing cryptographic primitives, generally a good idea. However, the elliptic curve method adopted by NIST, and championed by the NSA, is both slow and flawed, cryptography guru Bruce Schneier warns.

Flaws in the approach (Dual_EC_DRBG) first emerged in August at the Crypto 2007 conference when cryptographers Dan Shumow and Niels Ferguson demonstrated that two constants in the standard used to define the algorithm's elliptic curve have a relationship with a second, secret set of numbers. Anyone who had access to the second set of numbers would have a kind of skeleton key able to unlock any instance of Dual_EC_DRBG.

Shumow and Ferguson described their finding as a weakness and are at pains to avoid suggestions that NIST intentionally put a back-door in the function. Schneier is less circumspect saying that the "algorithm contains a weakness that can only be described a backdoor".

"You only need to monitor one TLS internet encryption connection in order to crack the security of that protocol. If you know the secret numbers, you can completely break any instantiation of Dual_EC_DRBG," Schneier explains in an essay on the subject in Wired.

"We have no way of knowing whether the NSA knows the secret numbers that break Dual_EC-DRBG... We don't know where the constants came from in the first place. We only know that whoever came up with them could have the key to this backdoor. And we know there's no way for NIST - or anyone else - to prove otherwise." ®

Steps to Take Before Choosing a Business Continuity Partner

Latest Comments

@ The Coin Flippers

All lovely statistics aside, the coin flipping doesn't matter here. Computers can not flip coins, they can only execute an algorithm. There are no "true" random numbers generated by computers, although computers can sample the environment for random numbers (http://www.random.org/)

If you know the seed and the timing of a pseudo random algorithm you can tell what it's going to output, thats how it works. We aren't worried about the accidental possibility that "a set of numbers from a random generator are all the same". We are worried about the intentional breaking and intentional generation of these exact same series.

0
0

Re: Acme Fixer @ Geoff

He's talking about probability of a result for the independant flips, not sequential results or otherwise. The chance of H or T per *single flip* is 50%. Always. Even if you flip the coin 10 billion times, you always have 50/50 chance. The chance of 10 billion heads in a row though... time for a calulator and a very small number :P

It's amazing how many people trip up on this... I learned statistics in year 10 at GCSE and remember complaining that I'd never need that information in "the real world". For reference, if anyone cares: http://www.bbc.co.uk/schools/gcsebitesize/maths/datahandlingih/probabilityirev1.shtml

0
0

Re: Acme Fixer

Not sure what your point is. True, the probability of heads is .5 on each flip but probabilities are multiplicative so that probability of 2 heads in a row is .25, three is .125, and so on.

0
0

More from The Register

 breaking news
Number of cops abusing Police National Computer access on the rise
Only a telegram from the Queen can get you off it
 breaking news
NSA PRISM snoop-gate: Won't someone think of the children, wails Apple
10,000 things probed, mostly about missing kids, Alzheimer patients, we're told
Flash flaw potentially makes every webcam or laptop a PEEPHOLE
But it's a Google problem - Chrome only, insists Adobe
Internet fraud still stings suckers
Australians twice as gullible as Americans
 breaking news
NSA PRISM-gate: Relax, GCHQ spooks 'keep us safe', says Cameron
Whatever they are up to, it's all above board, we're told
 breaking news
Yahoo! joins! rivals! in! PRISM! data! request! admission!
Keep calm and carry on using American tech firms, folks
PRISM snitch claims NSA hacked Chinese targets since 2009
Snowden suddenly looks safer in Hong Kong after revelations
 breaking news
US chief spook: Look, we only want to spy on 6.66 BEELLLION of you
Americans assured they are not in the NSA's sights
Speech-to-text drives motorists to distraction
Will talking to you mean I crash into that car up ahead, Siri?
DHS warns of vulns in hospital medical equipment
Has your doctor's anasthesia machine been hacked?