Slashdot Mirror
Cryptography Expert Sounds Alarm At Possible Math Hack
netbuzz writes "First we learn from Bruce Schneier that the NSA may have left itself a secret back door in an officially sanctioned cryptographic random-number generator. Now Adi Shamir is warning that a math error unknown to a chip makers but discovered by a tech-savvy terrorist could lead to serious consequences, too. Remember the Intel blunder of 1996? 'Mr. Shamir wrote that if an intelligence organization discovered a math error in a widely used chip, then security software on a PC with that chip could be "trivially broken with a single chosen message." Executing the attack would require only knowledge of the math flaw and the ability to send a "poisoned" encrypted message to a protected computer, he wrote. It would then be possible to compute the value of the secret key used by the targeted system.'"
The problem with backdoors, is that noone can guarantee who uses them. While it allows for (possibly) justified surveillance by our government, it also allows for it by others.
The United States, or the NSA, doesn't have all the world's best cryptographers. Russia, China, etc, other nations have excellent skill in these endeavors. Ironically, by trying to protect the nation, the NSA runs the risk of opening us up to foreign espionage.
So, if a security bug is present an exploit could happen...?
TFA is just a summary of an article yesterday in the NYT: http://www.nytimes.com/2007/11/17/technology/17code.html?ref=technology
It seems to me that the most likely source of a math error is in the floating point unit, since floating point math is far more complex than integer math. I've always understood that most crypto is based on integer math, both because it's based on number theory and because floating point math isn't exact. Doesn't that make this sort of exploit extremely unlikely?
Wouldn't pulling off something like this require a level of knowledge and togetherness more in line with a government agency, rather than a "terrorist" group? The results would also be more in line with what a government agency would want ("we have your secrets, ha!"), rather than what a terrorist would want ("Maybe I can't blow up a bridge / poison your water supply / whatever. But then maybe I can. So while you're deciding whether to go do things or hide under your bed all day, I have a question for you: do you feel lucky?").
Why does everything have to come back to terrorists? They kill a small number of people and people go nuts about them. Hunger, disease, motor cars, lightning, ... All these things have killed far more people than terrorists and they don't get brought up at every *FUCKING* opportunity. Yeah. I'm pissed off. If the terrorism obsessed turned on their brains for a picosecond they might realise that they have caused far more damage than any terrorist has.
I'm not sure how Mr. Shamir envisions a simple "math error" causing a problem. A buffer overflow exploit, perhaps, but not a math error... A user on a flawed but protected computer receives a "poisoned" encrypted message, opens it... And what happens? The math error, say, elicits some aspects of the user's private key in the decoded message; but how does the attacker then obtain that information without already having access to the machine? Further outgoing messages wouldn't have any usable information, no modern cryptosystem allows a received message from affecting any such message; a code exploit might affect the system's PRNG, but a math error shouldn't feed back to the PRNG unless it was horribly implemented. Without something affecting the user's machine's code execution, I can't see any way for an attacker to utilize a math error in a decryption function.
Um, no. "The terrorists" (a pretty vauge term but I'm assuming you mean those from middle eastern countries by the way you're wording your statement) don't give a rat's ass how we live, whether we have free elections or live with an oppressive government nor do they really care much about how we go about our daily lives, etc, etc. The terrorists wants the US and western countries to stop fucking around in their countries- supporting/installing dictatorships that happen to ally with our interests while bombing and invading countries that we don't like, setting up permanent military bases and just generally exerting our will on them. After a few generations of having western powers screw with their countries and lives it should be little wonder we're not well liked.
Of course, if you were refering to China or someone else then that might be a different story (but again, the wording sounded like someone regurgitating the drivel that gets thrown out by politicians and pundits in the mainstream media).
Terrorists want us to stop screwing around in the Middle East and Central Asia -- specifically they want us to stop supporting Israel and to stop propping up various dictatorships in countries where there'd be a good chance of overthrowing the government and creating a theocracy.
They don't give a flying f--- about "our freedoms" except where they think that shows we are "morally corrupt." Islamic militants are under no illusions that they're going to change our culture any time soon, though. They've got bigger fish to fry back home trying to establish a power block.
How we govern ourselves beyond our foreign policy is utterly unimportant to their larger goals.
If it's for-profit but free, you're not the customer -- you're the product (e.g., the Slashdot Beta's "audience").
Want the citizens to give up some freedom/pay some new tax/whatever? Easy! Play the terrorism trump card.
Without some Evil Empire force (that the US plays so well), it is very hard for terrorists to get the emotions going either. Terrorists & empire building governments need each other.
Engineering is the art of compromise.
Who are the "National Safety Administration"?
They're the sister outfit to the "National Highway Traffic Security Administration".
The higher the technology, the sharper that two-edged sword.
--- We are not in the 8th dimension. We are over New Jersey.
The flaw seems too obvious to really have been something illicit. If it was an attempt at a backdoor, it was pretty stupid. And it was a weird/improbable way to create a backdoor -- it was PRNG, not really a cryptographic function per se, and while knowing its output could help you break a system, it wouldn't guarantee it. The people at the NSA had to know it would be combed over.
But the fact that it seems to be incompetence rather than malice doesn't make me feel a whole lot better. There are still a bunch of secret-algorithm ciphers around and in use (and which the government, in its infinite wisdom, treats as more secure than the openly-reviewed ones), that the NSA is basically the only organization that has any access to. If they could miss such a trivial flaw in a PRNG that they knew was going to go out for public scrutiny, what could they have let slip by in a cryptographic function that was supposed to be a state secret?
"Ladies and gentlemen, my killbot features Lotus Notes and a machine gun. It is the finest available."
You wrote a bunch of counterexamples to show that the poster was wrong, and that his statement really just meant, "everyone that doesn't agree with me is an idiot." And then you called him an idiot. Good job.
A cat can't teach a dog to bark.
You are aware that computers can only generate pseudo-random numbers, right? The random number generator in C# actually doesn't generate random numbers but numbers that look random. These numbers are generated by a 'seed'. If you give the same seed to the computer, it will generate the same set of numbers. The C# implementation (if you don't supply a seed yourself) uses the system clock as seed, hence if you start your random-number-generation session in the same millisecond on same computers, they will generate the same numbers! The rest of the hardware & software is irrelevant here. If you need a REAL random number generator, you should connect your computer to something naturally random, e.g. a Geiger device, because your external DLL from an other language just uses a different model to generate the default seed but it is still predetermined.
So, because they don't like US foreign policy, they think it's alright to kill, and it's the fault of the US?
What the flying fuck planet of twisted "logic" are you living on? You're blaming the victims of murder for the acts of the murderers.
If someone doesn't like people who paint their houses pink and purple and then goes and kills anyone living in such houses, the people who painted their houses in garish colors are not the ones at fault.
And it's not "US foreign policy" that's fueling terrorist rage.
It's Islam. Plain and simple.
Specifically, the concepts of dar al-Harb and dar al-Islam. In the case of Israel, the utter insult it is to Islam to have that part of dar al-Islam revert back to dar al-Harb.
The mere existence of Israel is an affront to fundamentalist Islam.
And if the jihadis manage to "wipe Israel off the map" (gee, they wouldn't ever slip up and actually say that, now would they?), then those other areas of the world that were once part of dar al-Islam but reverted to dar al-Harb will be returned to the ummah. Say, like the Balkans, or Spain, er, I mean ar-Andalus.
And if any kaffirs get in the way, too bad. They're subhumans, anyway.
Maybe you'll get your head out of your ass before the jihadis lop it off - as their holy book directs...
What are you talking about? How is this hard to understand? This is one of the grand daddies of practical encryption stating that a huge freaking security hole could be opened if encryption is performed on faulty hardware. If a piece of hardware with such a fault was in wide spread use, then a large number of people would be susceptible to exploits which would be able to defeat public key encryption (e.g. HTTPS, ssh, etc).
There are lives at stake here!
A little over a trillion dollars, so far.
"I've got more toys than Teruhisa Kitahara."
Comment removed based on user account deletion
Step 1: The attacker an SSL session with a web server
...
Step 2: Generate the "poisoned" SSL session shared key K1, and encrypt it with the server's public RSA key
Step 3: The server decrypts the poisoned SSL session shared key K1 with its private key and obtains a value K2, which is
different than the original poisoned shared key K1. If the shared key K1 was not poisoned, K2 would be equal to K1,
but the attacker is exploiting an error in the CPU implementation that causes K2 != K1.
Step 4: All the AES-encrypted messages from the server will now be transformed with the poisoned K2, which the attacker does not know yet.
Step 6: Carefully select the messages that you send to the server, so that when you get the AES-encrypted with K2 replies to these messages, you
can use them to infer K2.
Step 7: Use K2 to infer the server's private RSA key
And that's the way you do it
This is a chosen ciphertext attack, which does not exploits weaknesses of the RSA scheme, but instead exploits the faulty
hardware.
It doesn't have to be a geiger counter. There is plenty of randomness to be had in the exact timing of key presses, exact behavior of rotating media, incoming network information, etc etc. It can be harder to make use of (poor or unknown distribution, patterns that you might not know about), and it might be insecure (especially if it came from the network card), but there are plenty of physically derived things a modern computer can measure and generate randomness from with enough processing of the raw data.
People generally evaluate risk on largely emotional terms. For this reason, we frequently make gross errors in risk assessment.
1) When we think there's somebody out to get us, we evaluate that risk very highly, even when there are more immediate but "random" risks clearly at hand. For example, a "terrorist" is a bogey-man, it's somebody out to get you. But hunger has no bad guy, and neither do disease, auto accidents, and lightning.
2) We evaluate as "risky" situations where we are not in immediate control, even if they are carefully situated to protect us. For example, riding a horse is far more risky than flying, even in the most dangerous category of flying, single-engine piston planes. Yet people routinely are more concerned about the "motor stalling" in a carefully watched and maintained airplane than they are about their kids riding around without protection on a champion racing horse.
3) Because of our intense pattern-matching, our ability to relate to other people, and our social nature, we routinely underrate risks that are impersonal - the flip-side of #1 above. For example, auto accidents are seen as a "way of life" and "can't be changed" by most, but freak out when the local high-school is held up for a few hours when some teenie gets involved in a love triangle and holds a SINGLE person "hostage" with a pocket knife. Look at the dichotomy - people who don't attend school drive right by a smashed up car on the way to work, tisking as they go, but sit glued to the telly when something happens at the High School.
It's reality. Get used to it. And no, it doesn't make sense.
I have no problem with your religion until you decide it's reason to deprive others of the truth.
Most chips have flaws of one kind or another. Most of these are trivial and can be worked around in microcode. The article mentions the Pentium floating point bug. This caused the original Pentium to return the wrong result for some calculations. In theory, it would be possible to produce a cyphertext that would generate this error if the key contained one of the two values that you needed to generate the error. This then lets you dramatically reduce the key search space.
Other CPU flaws are more serious. There are a few in the Core 2 which allow a process to violate the page protection mechanism, for example. If an attacker found one that caused the program counter to be modified as a side effect of an arithmetic operation then they could create a cyphertext which contained a program at the end and some data at the beginning that caused execution to jump into the exploit code. This is much easier for cypertexts than arbitrary data because the attacker has can make some good guesses about how a cyphertext will be processed.
It seems like this is a very theoretical category of vulnerability to use for anything more than a DoS. On the other hand, as Theo de Raadt says, the only difference between a bug and a vulnerability is the intelligence of your attacker.
I am TheRaven on Soylent News
In that case, the benefit of open review (that, just possibly, someone in the small pool of non-spook cryptographers who know what they're doing might find a flaw) is far less than the downside (that your opponents get to see what a modern code system looks like). The lowdown on a modern close-world cipher system would reveal attacks they are defending against, give a good impression of their real capabilities and so on. Yes, in a real shooting war, the spooks have to allow for their crypto systems falling into the wrong hands. But in the current climate, the tactical stuff will be exposed, but the strategic stuff can be closed algorithms and closed keys: what's not to like?
This reminds us all of the S Box hoo-hah, where elaborate theories were put forward by open community `experts' about the `flaws' in the S Boxes in DES. It turned out, of course, that they were optimal against an attack that wasn't even public, and close to optimal against other attacks that (allegedly) weren't known to anyone. I'd take a cipher system that the NSA or GCHQ approves for government use over anything advocated outside the wire., simply because the chances of an intentional weakness in the former are far smaller than the chances of an accidental weakness in the latter.
We went through all this is the discussion about the S Boxes