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.'"

Comments

The NSA

[proudfoot]

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.

Re:The NSA

[Anonymous Coward]

Exactly, which is sort of the best proof against the NSA trying to do something like this. If anything they aren't that stupid and they seem to take their mission pretty seriously. Don't forget that half of their goal is to protect US signals.

I'm not sure, maybe it's election season and so some of these guys are tying to raise the specters again. The Intel bug was with floating point operations and the vast majority of cryptography doesn't use any of that. Of course it's possible that there could be other errors but the logic and integer units on chips are tested so much more thoroughly... it's possible I guess but unlikely if you ask me that they'd know of it and the commercial world wouldn't.

Also, such a bug generally would require a specific implementation to be affected. I guess they could some how exploit the windows crypto code, but even that runs on dozens of different chips so you'd need the same error to be present on all of them.

If you look back, the NSA tampered with DES, they did so to increase it's security. Don Coppersmith even wrote about it in the IBM Journal of Systems Research. I can't think of any example of there being an error or weakness that suggested their tampering. I'm all about not using some algorithm that is showing any types of weaknesses which is really what Bruce first suggested which is a fairly healthy paranoia, and we must maintain our vigilance, but it's a long way from a believable example of NSA rigging something which, if you ask me, is an unhealthy type of paranoia.

Original article

[sk19842]

TFA is just a summary of an article yesterday in the NYT: http://www.nytimes.com/2007/11/17/technology/17code.html?ref=technology

how many encryption schemes us floating point?

[Kuciwalker]

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?

Re:how many encryption schemes us floating point?

[evanbd]

In the past there have existed implementations of integer math that used the floating point unit. The only one I know of off hand is the Prime95 Mersenne prime search program. I imagine there are others, though. The reason for this is simply that the floating point units were faster -- more bits per operation. The x87 FPU instructions operate on 80 bit floating point numbers, compared to 32 bit integers (the floating point numbers can't use the exponent bits, but it's still more than 32 by a lot). If your code is sufficiently parallel, and you put forth the effort, there was a performance gain to be had. I don't know if this is still the case in modern CPUs (especially 64 bit ones), but it's entirely possible to do high-performance integer math on the floating point unit.

Re:how many encryption schemes us floating point?

[gweihir]

The point the OP was trying to say was that if the error is in the FPU, that isn't used for integer calculations at all, and so wouldn't be exercised by security code. I don't know if this is true, but for instance RSA in theory is all integers.

The FPU can be used for integer math. IEEE 754 states that all results from Integer calculations that can be exact, need to be. The exponent gets denormalized for this case. So DOUBLE, for example, can be used as 54 bit unsigned Integer plus sign bit. I have used this occasionally in languages with no 64 bit integers, wne 32 bit were not enough.

WTF "terrorist"

[Timothy Brownawell]

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?").

Re:WTF "terrorist"

[the eric conspiracy]

While government agencies surely have the upper hand here, there is always the possibility that a mole in the NSA gets their hands on the backdoor information, or a lone genius working in say Russia finds a mathematical flaw in the system.

As far as poisoning your water supply etc. lookie here:

http://sandia.gov/scada/home.htm

Hardware errors are a potential problem, but they are #3 on the list after human and software problems. Why search for hardware problems when the first two are far more likely to bear fruit?

Terrorists?

[Anonymous Coward]

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.

don't understand

[TheSHAD0W]

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.

Re:don't understand

[SiliconEntity]

I can't see any way for an attacker to utilize a math error in a decryption function

Actually this is a common attack scenario in security protocol analysis. While it does not always happen in real life there are ways it can occur. For example, you try to decrypt the message and get garbage. So what do you do? You send the garbage back to the guy, saying, I couldn't read your message, all I got was this junk. Now you have been tricked into acting as what is called an "oracle" for the decryption function. This opens up a number of attacks which is why the best cryptosystems are immune to such problems.

Re:don't understand

[garompeta]

>I can't see any way for an attacker to utilize a math error in a decryption function.

In the same way you aren't the "S" in RSA. Give him some credit, will you?

Re:First Post?

[Anonymous Coward]

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).

No.

[Valdrax]

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.

Re:No.

[Anonymous Coward]

Those people are an absolutely tiny minority and can be dealt with sensibly. The majority of people would just like us to stop meddling.

Stop pissing people off and the nut-jobs who do want us removed will have lost their primary recruitment method.

Re:No.

[Valdrax]

Define Terrorists please. If you're talking about Al-Queda, you're wrong. This group hates democracy as it goes against Sharia law to the most extreme. Anything governed outside this religious foundation is seen as an act of Hubris and thus punishable by death in the eyes of Allah (Arabic word for God).

Yeah, but al-Qaeda doesn't care about our democracy. And seeing us turn into a secular or Christian dictatorship in no way helps further their goals. The more crazy fascist our government becomes, ironically, the less accepting of Islamic fundamentalism it becomes even as it becomes equally repressive. If anything, it's against their long term goals to see us harder ourselves against them.

Next time, educate yourself about our sworn western enemies before justifying their cause. Bluntly put, I don't give a damn about their cause. These people need to die like the parasites they are on humanity.

What does explaining their motivations have to do with justifying them? You seem to be the sort of reactionary type that associates any attempt to understand your enemy with accepting them and capitulating to them.

Geez, it's no wonder you people are losing the War on Terrorism for us.

Terrorist & government symbiosis.

[EmbeddedJanitor]

Of course there's all the stuff that terrorists want you to do, but governments need terrorists too.

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.

Re:National Safety Administration?

[ScrewMaster]

Who are the "National Safety Administration"?

They're the sister outfit to the "National Highway Traffic Security Administration".

NSA "Suite A" is the real problem.

[Kadin2048]

Which is why I, for one, doubt that the back door was intentional. The approval that NSA gives is primarily for use by the US government itself, and most of the obstacles that NSA faces in spying on our own government are bureaucratic ones, not technical ones. I agree, for what it's worth (not much, but we're mostly all armchair generals here, why not join in the fun?).

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?

Re:NSA "Suite A" is the real problem.

[0xygen]

1) is a serious problem though. We can never PROVE it is backdoored unless someone steps forward with those numbers. We can NEVER prove it is NOT backdoored, as we cannot PROVE that no-one has the numbers, so are compelled to treat it as backdoored.

2) is about specific cases where particular categories of mathematical failures actually lead to the compromising of the private key, which is significantly more dangerous. It is not about utilitising typical exploits like buffer overflows to take over and kind of security software. For example, once they private key is known, it may allow the third party to fake messages appearing to originate from the target of the attack.

3) indeed, the problem here is typically relating to very specific edge conditions, eg overflows, underflows, carries which are handled incorrectly, and have been known to go undetected for years. If you do not believe there are issues in the microcode, take a quick look at the current errata list for the Core2Duo, showing many unfixed bugs (and many of them unimportant due to the impossibility of them occurring in modern operating systems).

As for "installing bad microcode", the microcode is something done purely from the software each time the OS boots into volatile memory on the cpu, and so is reset back to the original shipping microcode each time the machine is power-cycled.
If an adversary has access to the booting OS to update the microcode, the adversary already has access to superuser priveleges on your system anyway, so I feel it is irrelevant.

Re:Random Numbers in .NET and in General

[DrJokepu]

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.

Comment removed

[account_deleted]

Comment removed based on user account deletion

Re:first post. TFA = WTF?

[TheRaven64]

When you send someone an encrypted message, their software will typically try to decrypt it. This means that it will run a known algorithm (you typically identify the decryption algorithm along with the cyphertext).

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.

NSA/GCHQ Private IS open review, practically

[igb]

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),

The breadth and depth of cryptographic skill,. experience and knowledge behind the wire at Cheltenham and Fort Meade is orders of magnitude than that outside. The review process internally is actually far higher quality than that externally. This isn't like software, where even Microsoft doesn't employ a measurable fraction of the software engineers in the world. GCHQ plus NSA is the vast majority of the cryptographers, plus they have libraries and testcases and methodologies dating back fifty years that the rest don't have access it.

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