Entries Tagged "random numbers"

Page 3 of 5

TSA Considering Implementing Randomized Security

For a change, here’s a good idea by the TSA:

TSA has just issued a Request for Information (RFI) to prospective vendors who could develop and supply such randomizers, which TSA expects to deploy at CAT X through CAT IV airports throughout the United States.

“The Randomizers would be used to route passengers randomly to different checkpoint lines,” says the agency’s RFI.

The article lists a bunch of requirements by the TSA for the device.

I’ve seen something like this at customs in, I think, India. Every passenger walks up to a kiosk and presses a button. If the green light turns on, he walks through. If the red light turns on, his bags get searched. Presumably the customs officials can set the search percentage.

Automatic randomized screening is a good idea. It’s free from bias or profiling. It can’t be gamed. These both make it more secure. Note that this is just an RFI from the TSA. An actual program might be years away, and it might not be implemented well. But it’s certainly a start.

EDITED TO ADD (7/19): This is an opposing view. Basically, it’s based on the argument that profiling makes sense, and randomized screening means that you can’t profile. It’s an argument I’ve argued against before.

EDITED TO ADD (8/10): Another argument that profiling does not work.

Posted on July 19, 2013 at 2:45 PMView Comments

Lousy Random Numbers Cause Insecure Public Keys

There’s some excellent research (paper, news articles) surveying public keys in the wild. Basically, the researchers found that a small fraction of them (27,000 out of 7.1 million, or 0.38%) share a common factor and are inherently weak. The researchers can break those public keys, and anyone who duplicates their research can as well.

The cause of this is almost certainly a lousy random number generator used to create those public keys in the first place. This shouldn’t come as a surprise. One of the hardest parts of cryptography is random number generation. It’s really easy to write a lousy random number generator, and it’s not at all obvious that it is lousy. Randomness is a non-functional requirement, and unless you specifically test for it — and know how to test for it — you’re going to think your cryptosystem is working just fine. (One of the reporters who called me about this story said that the researchers told him about a real-world random number generator that produced just seven different random numbers.) So it’s likely these weak keys are accidental.

It’s certainly possible, though, that some random number generators have been deliberately weakened. The obvious culprits are national intelligence services like the NSA. I have no evidence that this happened, but if I were in charge of weakening cryptosystems in the real world, the first thing I would target is random number generators. They’re easy to weaken, and it’s hard to detect that you’ve done anything. Much safer than tweaking the algorithms, which can be tested against known test vectors and alternate implementations. But again, I’m just speculating here.

What is the security risk? There’s some, but it’s hard to know how much. We can assume that the bad guys can replicate this experiment and find the weak keys. But they’re random, so it’s hard to know how to monetize this attack. Maybe the bad guys will get lucky and one of the weak keys will lead to some obvious way to steal money, or trade secrets, or national intelligence. Maybe.

And what happens now? My hope is that the researchers know which implementations of public-key systems are susceptible to these bad random numbers — they didn’t name names in the paper — and alerted them, and that those companies will fix their systems. (I recommend my own Fortuna, from Cryptography Engineering.) I hope that everyone who implements a home-grown random number generator will rip it out and put in something better. But I don’t hold out much hope. Bad random numbers have broken a lot of cryptosystems in the past, and will continue to do so in the future.

From the introduction to the paper:

In this paper we complement previous studies by concentrating on computational and randomness properties of actual public keys, issues that are usually taken for granted. Compared to the collection of certificates considered in [12], where shared RSA moduli are “not very frequent”, we found a much higher fraction of duplicates. More worrisome is that among the 4.7 million distinct 1024-bit RSA moduli that we had originally collected, more than 12500 have a single prime factor in common. That this happens may be crypto-folklore, but it was new to us, and it does not seem to be a disappearing trend: in our current collection of 7.1 million 1024-bit RSA moduli, almost 27000 are vulnerable and 2048-bit RSA moduli are affected as well. When exploited, it could act the expectation of security that the public key infrastructure is intended to achieve.

And the conclusion:

We checked the computational properties of millions of public keys that we collected on the web. The majority does not seem to suffer from obvious weaknesses and can be expected to provide the expected level of security. We found that on the order of 0.003% of public keys is incorrect, which does not seem to be unacceptable. We were surprised, however, by the extent to which public keys are shared among unrelated parties. For ElGamal and DSA sharing is rare, but for RSA the frequency of sharing may be a cause for concern. What surprised us most is that many thousands of 1024-bit RSA moduli, including thousands that are contained in still valid X.509 certificates, offer no security at all. This may indicate that proper seeding of random number generators is still a problematic issue….

EDITED TO ADD (3/14): The title of the paper, “Ron was wrong, Whit is right” refers to the fact that RSA is inherently less secure because it needs two large random primes. Discrete log based algorithms, like DSA and ElGamal, are less susceptible to this vulnerability because they only need one random prime.

Posted on February 16, 2012 at 6:51 AMView Comments

The History of One-Time Pads and the Origins of SIGABA

Blog post from Steve Bellovin:

It is vital that the keystream values (a) be truly random and (b) never be reused. The Soviets got that wrong in the 1940s; as a result, the U.S. Army’s Signal Intelligence Service was able to read their spies’ traffic in the Venona program. The randomness requirement means that the values cannot be generated by any algorithm; they really have to be random, and created by a physical process, not a mathematical one.

A consequence of these requirements is that the key stream must be as long as the data to be encrypted. If you want to encrypt a 1 megabyte file, you need 1 megabyte of key stream that you somehow have to share securely with the recipient. The recipient, in turn, has to store this data securely. Furthermore, both the sender and the recipient must ensure that they never, ever reuse the key stream. The net result is that, as I’ve often commented, “one-time pads are theoretically unbreakable, but practically very weak. By contrast, conventional ciphers are theoretically breakable, but practically strong.” They’re useful for things like communicating with high-value spies. The Moscow-Washington hotline used them, too. For ordinary computer usage, they’re not particularly practical.

I wrote about one-time pads, and their practical insecurity, in 2002:

What a one-time pad system does is take a difficult message security problem — that’s why you need encryption in the first place — and turn it into a just-as-difficult key distribution problem. It’s a “solution” that doesn’t scale well, doesn’t lend itself to mass-market distribution, is singularly ill-suited to computer networks, and just plain doesn’t work.

[…]

One-time pads may be theoretically secure, but they are not secure in a practical sense. They replace a cryptographic problem that we know a lot about solving — how to design secure algorithms — with an implementation problem we have very little hope of solving.

Posted on September 3, 2009 at 5:36 AMView Comments

Non-Randomness in Coin Flipping

It turns out that flipping a coin has all sorts of non-randomness:

Here are the broad strokes of their research:

  1. If the coin is tossed and caught, it has about a 51% chance of landing on the same face it was launched. (If it starts out as heads, there’s a 51% chance it will end as heads).
  2. If the coin is spun, rather than tossed, it can have a much-larger-than-50% chance of ending with the heavier side down. Spun coins can exhibit “huge bias” (some spun coins will fall tails-up 80% of the time).
  3. If the coin is tossed and allowed to clatter to the floor, this probably adds randomness.
  4. If the coin is tossed and allowed to clatter to the floor where it spins, as will sometimes happen, the above spinning bias probably comes into play.
  5. A coin will land on its edge around 1 in 6000 throws, creating a flipistic singularity.
  6. The same initial coin-flipping conditions produce the same coin flip result. That is, there’s a certain amount of determinism to the coin flip.
  7. A more robust coin toss (more revolutions) decreases the bias.

The paper.

Posted on August 24, 2009 at 7:12 AMView Comments

Social Security Numbers are Not Random

Social Security Numbers are not random. In some cases, you can predict them with date and place of birth.

Abstract:

Information about an individual’s place and date of birth can be exploited to predict his or her Social Security number (SSN). Using only publicly available information, we observed a correlation between individuals’ SSNs and their birth data and found that for younger cohorts the correlation allows statistical inference of private SSNs. The inferences are made possible by the public availability of the Social Security Administration’s Death Master File and the widespread accessibility of personal information from multiple sources, such as data brokers or profiles on social networking sites. Our results highlight the unexpected privacy consequences of the complex interactions among multiple data sources in modern information economies and quantify privacy risks associated with information revelation in public forums.

Full paper, and FAQ.

I don’t see any new insecurities here. We already know that Social Security Numbers are not secrets. And anyone who wants to steal a million SSNs is much more likely to break into one of the gazillion databases out there that store them.

Posted on July 24, 2009 at 10:36 AMView Comments

Automatic Dice Thrower

Impressive:

The Dice-O-Matic is 7 feet tall, 18 inches wide and 18 inches deep. It has an aluminum frame covered with Plexiglas panels. A 6×4 inch square Plexiglas tube runs vertically up the middle almost the entire height. Inside this tube a bucket elevator carries dice from a hopper at the bottom, past a camera, and tosses them onto a ramp at the top. The ramp spirals down between the tube and the outer walls. The camera and synchronizing disk are near the top, the computer, relay board, elevator motor and power supplies are at the bottom.”

Click on the link and watch the short video.

As someone who has designed random number generators professionally, I find this to be an overly complex hardware solution to a relatively straightforward software problem. But the sheer beauty of the machine cannot be denied.

What I am curious about is what kind of statistical anomalies there are in the dice themselves. At 1,330,000 rolls a day, we can certainly learn something about the randomness of commercial dice.

Posted on May 27, 2009 at 6:44 AMView Comments

Random Number Bug in Debian Linux

This is a big deal:

On May 13th, 2008 the Debian project announced that Luciano Bello found an interesting vulnerability in the OpenSSL package they were distributing. The bug in question was caused by the removal of the following line of code from md_rand.c

	MD_Update(&m,buf,j);
	[ .. ]
	MD_Update(&m,buf,j); /* purify complains */

These lines were removed because they caused the Valgrind and Purify tools to produce warnings about the use of uninitialized data in any code that was linked to OpenSSL. You can see one such report to the OpenSSL team here. Removing this code has the side effect of crippling the seeding process for the OpenSSL PRNG. Instead of mixing in random data for the initial seed, the only “random” value that was used was the current process ID. On the Linux platform, the default maximum process ID is 32,768, resulting in a very small number of seed values being used for all PRNG operations.

More info, from Debian, here. And from the hacker community here. Seems that the bug was introduced in September 2006.

More analysis here. And a cartoon.

Random numbers are used everywhere in cryptography, for both short- and long-term security. And, as we’ve seen here, security flaws in random number generators are really easy to accidently create and really hard to discover after the fact. Back when the NSA was routinely weakening commercial cryptography, their favorite technique was reducing the entropy of the random number generator.

Posted on May 19, 2008 at 6:07 AMView Comments

Sidebar photo of Bruce Schneier by Joe MacInnis.