Proof of randomness builds future of digital security

December 22, 2017, Princeton University
Credit: CC0 Public Domain

In an effort to block emerging threats to online security, researchers at Princeton University have developed a method to verify the strength of random number generators that form the basis of most encryption systems.

Nearly all secure online traffic—from shopping to banking to communications—relies on a technique of randomly generating a number that serves as a key to unlock encrypted communication. The problem is that small programming errors can make these systems vulnerable, and those vulnerabilities can often be very difficult to detect.

"Whenever you connect up to Amazon to give them your , whenever you log in somewhere through a secure connection, you're depending on randomly generated cryptographic keys," said Andrew Appel, the Eugene Higgins Professor of Computer Science at Princeton and leader of the research team. "And if the adversary, the spy who is trying to read your messages or impersonate you, could guess what random number your computer was using, then it could know what key you're going to be using and it could impersonate your traffic and read your messages."

In a paper presented to the Association for Computing Machinery 2017 Conference on Computer and Communications Security on Nov. 2, the researchers said it may be impossible to tell whether a number is compromised without examining the generators' source code (and without proper methods, difficult to guarantee security even with access to the code). The programs, called Deterministic Random Bit Generators or DRBGs, are tested typically by analyzing their outputs, either statistically or by using a set of tests to check the results. But the researchers said these methods cannot guarantee the generators' proper function.

"Despite the importance of DRBGs, their development has not received the scrutiny it deserves," the researchers write in their article.

Although often called random number generators, these programs are actually pseudorandom number generators. The programs are algorithms that produce numbers that seem to be random and can practically work as random numbers for many applications. The DRBGs use a variety of methods to create a truly random number called a seed. The program then mathematically expands this seed into a much longer number. The long number is not actually random, but it must appear random enough that an adversary (who does not know the seed) can't predict the output.

The researchers said flaws in number generators, or their implementation, have caused several security breaches in the past few years. "Many security researchers have found these bugs in random number generators," said Katherine Ye of the Class of 2016, a member of the research team who is now a graduate student at Carnegie Mellon University. She said that, in some cases, the bugs were accidental and, in others, they were deliberately added or exploited to breach security.

Ye began working on methods to check number generators as part of her senior thesis at Princeton. She and her co-authors wrote proofs in several existing frameworks for verifying programs, including Appel's Verified Software Toolchain, which includes a logic for reasoning about programs written in the C language.

It was time-consuming and difficult work, and many proofs had to be done manually. Working with colleagues at Princeton, Johns Hopkins University and Oracle, Ye, Appel and their collaborators examined a widely used pseudorandom number generator called HMAC-DRBG. They produced a comprehensive and machine-checked proof that HMAC-DRBG is indeed secure, meaning that its output is sufficiently difficult to distinguish from truly random output.

Ye said the recent results show that it is practical to apply secure tests to other generators, although doing so would require new sets of proofs. (The researchers said the National Institute of Standards and Technology has approved three DRBGs for use by the U.S. government.)

Eugene Spafford, professor and executive director emeritus of Purdue University's Center for Education and Research in Information Assurance and Security, said the research is "an advancement, without a doubt."

The mathematical assurance of the proof provides a "very high level of assurance" of the security of the number generator, he said.

"That means we can use it with great confidence that an observer isn't going to be able to break it and … interfere with our communications," Spafford said.

Spafford agreed that it is feasible, with more engineering work, to adapt the Princeton team's methods to other number generators used for critical applications. He noted that the checks would not necessarily be needed for generators used for other types of applications. "If all I'm using a for is to run simulations, I may not have to prove it's unbreakable at all because they're just simulations," he said.

Ye believes that expanding the research to other number generators is an important step.

"I think our work could be more impactful if someone extended it to apply to DRBGs that are even more widely used than HMAC-DRBG," she said.

In the decades to come, new cryptographic tools using number generators will be developed, and as those tools are introduced, there will be debate over how secure they really are, Appel said.

Machine-checked proofs may help with that process, Appel added.

"It's a very nice result," Spafford said. "Like a lot of other research, it may not directly apply to your life and mine at the moment, but it's building up a set of results that could [lead to] very important results in the future."

Explore further: NIST revises key computer security publication on random number generation

More information: Katherine Q. Ye et al. Verified Correctness and Security of mbedTLS HMAC-DRBG, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security - CCS '17 (2017). DOI: 10.1145/3133956.3133974

Related Stories

Random numbers—hard times ahead for hackers

May 31, 2017

Whenever we need to communicate in secret, a cryptographic key is needed. For this key to work, it must consist of numbers chosen at random without any structure – just the opposite of using the birthdate of our favourite ...

Lightweight true random number generators a step closer

September 20, 2010

The widespread use of true random number generators (TRNGs) has taken a step closer following the creation of the most lightweight designs to date by researchers at Queen's University Belfast's Institute of Electronics, Communications ...

Security loophole found in Windows operating system

November 12, 2007

A group of researchers headed by Dr. Benny Pinkas from the Department of Computer Science at the University of Haifa succeeded in finding a security vulnerability in Microsoft's "Windows 2000" operating system.

Recommended for you

Top takeaways from Consumers Electronics Show

January 13, 2018

The 2018 Consumer Electronics Show, which concluded Friday in Las Vegas, drew some 4,000 exhibitors from dozens of countries and more than 170,000 attendees, showcased some of the latest from the technology world.

Finnish firm detects new Intel security flaw

January 12, 2018

A new security flaw has been found in Intel hardware which could enable hackers to access corporate laptops remotely, Finnish cybersecurity specialist F-Secure said on Friday.

34 comments

Adjust slider to filter visible comments by rank

Display comments: newest first

antialias_physorg
not rated yet Dec 22, 2017
"Despite the importance of DRBGs, their development has not received the scrutiny it deserves,"

Which is rather important, because secret services have already started fudging with random number generation code and the way these are 'verified'
http://www.bbc.co...24048343

(The researchers said the National Institute of Standards and Technology has approved three DRBGs for use by the U.S. government.)

Rather worrying, since in the article I linked it is the NIST which has helped the NSA break random number generators. After that I wouldn't trust a NIST algorithm to verify a random number generator, ever.

If I were to really require secure random numbers I'd build a hotbit generator out of a smoke detector. No one can predict radioactive decay.
Alternative would be some hardware that uses quantum indeterminacy to generate numbers - but that I'd have to buy (which means having to trust the vendor, which is never a good idea with secrecy)

Whydening Gyre
not rated yet Dec 22, 2017
I saw an article about some company that uses hi res, constantly updated pics of a wall of lava lamps as basis for generation...
Da Schneib
not rated yet Dec 22, 2017
You can buy a USB device to generate true random numbers, and if you plug it in to your computer you can use it to seed the PRNG code in your operating system and this will give truly random numbers (according to our understanding of quantum mechanics, anyway). I know for a fact Linux does this in modern versions if the USB RNG is plugged in; for earlier Linux versions you may have to fuss with it a bit. I think Windows has code for this too but don't know the details.

There are various types of the USB RNGs, and they all use underlying physical principles that are generally believed by physicists to be random. One thing to watch out for is that some of them can have detectable bias in the random bit stream introduced by temperature variations around the USB dongle; there are ones that are not vulnerable to this. Generally these are available for under, mostly well under, US$100.
Da Schneib
not rated yet Dec 22, 2017
@anti, this article struck me on a quick read as being more about new mathematical tests for true randomness. There are some tests available, but none of them is really conclusive. I'll have to read up and check into this to find out how good this one is. The article didn't seem very specific on it.

I wouldn't worry too much about anybody from NIST or the NSA putting back doors into RNG evaluation code. The place to put it is into the RNG code itself.
antialias_physorg
5 / 5 (1) Dec 22, 2017
I wouldn't worry too much about anybody from NIST or the NSA putting back doors into RNG evaluation code. The place to put it is into the RNG code itself.

If you look at the article I linked the NIST 'verified' RNG code as good that actually wasn't. So when the NIST comes out with an article on new verification code...well...I'll pass.
I'd trust any non-US source over them.
Da Schneib
5 / 5 (1) Dec 22, 2017
Then you're gonna have to roll your own, @anti.

I'll also point out that the article is from 2013. Lotta water under the bridge since then. Meanwhile there are still significant users of Microsoft NTLM and even LM, who have not upgraded to NTLM v.2, and the former expose passwords en clair on the wire, and people who have not upgraded to TLS 1.2 despite known defects in earlier versions of TLS and SSL. This isn't speculation; I have warned customers of mine about this and pursued it with my developers to make sure they enabled TLS 1.2 on their systems. My company hasn't gone so far as to disable earlier TLS and SSL, but we only support NTLM v.2. This was a design-time decision.

Overall I'd say whining about Dual_EC_DRBG is missing the point.
Da Schneib
5 / 5 (1) Dec 22, 2017
I mean, seriously, whatcha gonna do, re implement OpenSSL? Are you serious? You know that you can set OpenSSL up so it doesn't use compromised algorithms, right?

And I'm sorry but if you're counting on NIST to define what's safe, you missed the boat at the dock. I haven't trusted NIST since 1992.
Da Schneib
not rated yet Dec 22, 2017
Oh and one more point: if your seed is from a hardware USB RNG, none of this matters. Spend US$100 and move on if you really need hard encryption.
Whydening Gyre
5 / 5 (1) Dec 22, 2017
Uh-oh.... Looks like DS is drinking his Grumpy Ol' Bastard beer, tonite....:-)
Da Schneib
5 / 5 (1) Dec 22, 2017
Bah, @Whyde, this is what I get paid for.

I do admit to a couple of Stone IPAs, though. ;)
mackita
5 / 5 (1) Dec 23, 2017
The random systems aren't complete random. In random sequence of dice throws the probability of two subsequent throws with the same number should be lower than the probability of three sixes and so on. So that there always exists a Gaussian distribution. Once such a distribution gets broken, then the system is not fully random anymore. On this hidden structure within random distribution my theory of random Universe is based.

Try the following test - which random distribution looks more "random" for you? Humans suffer by egalitarian bias in generating random sequences; they think that randomness looks a lot more uniform and structureless than it really does. The flip side is that, when things really are random, they see patterns that aren't really there (and scientists are doing good money in publishing it).

Da Schneib
not rated yet Dec 23, 2017
Bah. Random means that the result of a trial isn't dependent upon the result of any previous trial. As a good example, and one already mooted in this article, radioactive decays in a sample don't depend upon previous decays. Human perception of randomness is insufficient; what's needed is mathematical study.

But the subject of this article isn't even that; it's merely pseudo-randomness. It's actually deterministic, but by so complex an algorithm that it can't be predicted. The article talks about a white box test where the code is checked as well as the black box output.
Whydening Gyre
5 / 5 (1) Dec 23, 2017
Bah. Random means that the result of a trial isn't dependent upon the result of any previous trial.

An absolutely impossible situation since both trial and result happen in the same reality/universe. So via trickle down (or even trickle up) a wave collapse chain will result, regardless of how minute.
Impossibly chaotic, maybe. But NEVER random.
Of course, this could just be my insufficient human perception talkin'...

Da Schneib
5 / 5 (1) Dec 23, 2017
OK, so how is the decay of one radioactive nuclide in a sample influenced by the decay of another that is not nearby?
mackita
not rated yet Dec 23, 2017
Random means that the result of a trial isn't dependent upon the result of any previous trial
This is internally inconsistent definition. Everyone knows, that the occurrence of the multiple decays with the same energy in line is improbable during random decay. But your definition says, we shouldn't care about it. There are another controversies of random distribution, like the [Benford's law](https://phys.org/...ts.html) and sum or random numbers.
Da Schneib
not rated yet Dec 23, 2017
But your definition says, we shouldn't care about it.
Where, exactly?

And BTW Benford's Law works precisely because the data are truly random; and the more random they are the better it works.
Da Schneib
not rated yet Dec 23, 2017
Incidentally it's worth mentioning that the change in orders of magnitude is completely generated by the arbitrary definition of units and this is what makes Benford's Law work. And work better if the data are truly random and cross these arbitrary orders of magnitude.

You have a tendency, @mak, to mistake arbitrary measurement criteria for some sort of laws of nature.
Whydening Gyre
5 / 5 (1) Dec 23, 2017
OK, so how is the decay of one radioactive nuclide in a sample influenced by the decay of another that is not nearby?

By the action of all the other stuff in-between...
Whydening Gyre
5 / 5 (1) Dec 23, 2017
OK, so how is the decay of one radioactive nuclide in a sample influenced by the decay of another that is not nearby?

By the action of all the other stuff in-between...

change that -
RE- action of...
Oh...
And Merry Xmas to all!
Or whatever it is you're doing - hope you're having fun at it!
Da Schneib
not rated yet Dec 23, 2017
But nothing happens to the stuff in between. It just sits there.
IronhorseA
not rated yet Dec 24, 2017
But nothing happens to the stuff in between. It just sits there.


No thing just 'sits there'. Objects don't decay because they were sitting there minding there own business. Something is happening which leads to the decay, we just don't know what since we can't measure it yet. And until we can, and have an explanation and equations in hand, there's no guarantee that the event is truly random and not just the type of highly complex behavior that only chaos theory can describe.
KBK
not rated yet Dec 24, 2017
"No one can predict radioactive decay." -anti says.

Not quite true, thus - big problem.

Randomness does not exist. A semblance of it does, but not really.... cryptography methodologies can be breached. It's that thing about common knowledge ruling the roost but uncommon knowledge being the future. That's how it works.

In the uncommon knowledge end the pool, research the Pear studies on psychic testing, and casting influence into randomness, with a 3 billion to one odds result of not being wrong about that. (tiny tip of huge iceberg)

This, from many hundreds of peer reviewed studies, all done by well vetted accredited scientists, and all cross referenced in various meta studies.

The 3 billion to one thing is vetted by the US academy of sciences, in their review of the meta works.

This is a small tiny part of why Elon Musk is publicly insistent that this is not a base reality and is a simulacrum. His argument, fleshed out, is intractably true, at 3B:1 odds.
KBK
not rated yet Dec 24, 2017
It's much worse than you think, as randomness dies right here, with this article alone.

https://phys.org/...les.html

Never mind the insanely intractable evidence of psychic influence on randomness. The science is out there. Most important point, in counterarguments to this..is.."if you have not done in depth research into the psychic end of the pool of knowledge, then you have no opinion but that of projection of emotional desires."

Which, humorously enough, the universe allows for. Ie, you get what you project. That's what the studies end up showing, as an adjunct. Scientists can lie to themselves, project it with a fervor, and it works. A tested scenario that encompasses all potential outcomes, which is good universal theory.

It's all in the studies. Hundreds of them performed over many decades with all possible angles for malfeasance and errors in testing methodology covered and dealt with.
someone11235813
5 / 5 (1) Dec 24, 2017
Why couldn't a truly random quantum system be used to generate genuinely random numbers, like a geiger counter reading a radioactive substance and convert the strings of silence and clicks into binary numbers?
Whydening Gyre
5 / 5 (1) Dec 25, 2017
Why couldn't a truly random quantum system be used to generate genuinely random numbers, like a geiger counter reading a radioactive substance and convert the strings of silence and clicks into binary numbers?

Isn't that the way it's already done?
Da Schneib
not rated yet Dec 26, 2017
No thing just 'sits there'.
Then what's it doing?

Objects don't decay because they were sitting there minding there own business.
Apparently, they do. Whatever it is that makes them do so, it depends on whether they have a decay path that allows them to move to a lower energy state by releasing some energy in a permitted manner. When they actually do so, however, is completely random.

Something is happening which leads to the decay, we just don't know what since we can't measure it yet.
The problem there is, the equations that govern quantum mechanics say there can't be anything there. See Bell's Theorem.
Da Schneib
5 / 5 (1) Dec 26, 2017
Why couldn't a truly random quantum system be used to generate genuinely random numbers, like a geiger counter reading a radioactive substance and convert the strings of silence and clicks into binary numbers?
Yeah, they have that, it's what I was talking about above. You can buy US$100 USB dongles that do it. Here's a list of some of them: https://en.wikipe...nerators

You can probably do better than Wikipedia for these.
someone11235813
5 / 5 (2) Dec 26, 2017
@Whydening Gyre, I see I did not know that. Well what then is the problem if a random number can be generated easily using some sort of quantum decay what is the point of testing the strength? because we know it's random. Isn't that the whole point of quantum mechanics that Einstein didn't want to accept but that Bell proved with his theorem and Aspect's experiments.
Da Schneib
5 / 5 (1) Dec 26, 2017
@someone, you don't take the random output of a USB dongle to generate random numbers in an operating system; the output of the dongle is too slow. Modern operating systems use a CSPRNG to generate them. The randomness from the dongle is used as a seed to generate random numbers for the operating system by the CSPRNG as required, and when the CSPRNG software detects the randomness is decaying it halts on read until enough more randomness is generated by the dongle. It's actually a pretty complex process.

I could explain what @antialias was talking about above if you like.

In case it's not obvious, you're asking good questions. Keep asking and I'll give you as much as you care to know about it.
Da Schneib
5 / 5 (1) Dec 26, 2017
Isn't that the way it's already done?
Depends. There are CPUs that have real RNGs built in, but they're not common yet. For other CPUs you buy a dongle if you need really secure randomness.

Update: I did some research and you're a lot better off with the dongles. Seems that the implementation of the on-CPU RNGs is questioned in the security community by some pretty heavy hitters (Tso is one of them, if you know who that is).
Whydening Gyre
not rated yet Dec 26, 2017
Isn't that the way it's already done?
Depends. There are CPUs that have real RNGs built in, but they're not common yet. For other CPUs you buy a dongle if you need really secure randomness.

Update: I did some research and you're a lot better off with the dongles. Seems that the implementation of the on-CPU RNGs is questioned in the security community by some pretty heavy hitters (Tso is one of them, if you know who that is).

Wow... Didn't realize the Trans Siberian Orchestra was such security oriented.
Gotta keep those cello's clean, I guess...:-)
Da Schneib
not rated yet Dec 26, 2017
His first name is Theodore. You might want to go look him up and find out some other names in the cryptology world. He has an article on Wikipedia: https://en.wikipe...e_Ts%27o
mackita
not rated yet Dec 28, 2017
Eikka
not rated yet Jan 02, 2018
In random sequence of dice throws the probability of two subsequent throws with the same number should be lower than the probability of three sixes and so on. So that there always exists a Gaussian distribution.


Not true. Throwing a single die does not result in a gaussian distribution, but an equal distribution assuming the die is not weighted. You're confusing randomness with patterns in the random data. Throwing multiple dice, or throwing the same die multiple times, results in the bell shaped distribution for the sum of the throws or for any other pattern you're looking for. This does not apply to the randomness of the individual dice or throws.

The problem is that you're looking at a -sequence- of dice throws, so you have a definite and finite sample of throws, and in that sequence you find apparent patterns like three sixes in a row, which btw. is NOT more likely than two sixes. Whatever number comes up next has nothing to do with gaussian distributions.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.