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

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?

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

Re:how many encryption schemes us floating point?

[lpontiac]

Maybe the FPU shares circuitry with the integer instruction circuitry.

I'm guessing the people modding you +1 funny don't realise that earlier (pre-Prescott) Pentium 4 processors implemented integer multiplication instructions using the floating point unit.

Re:how many encryption schemes us floating point?

[ajs318]

That is done so that the mantissa begins with a one. You don't actually need to denormalise at all. You only lose accuracy if there are more digits in the answer than will fit in your chosen representation. Obviously, a recurring fraction won't fit into any representation (example: 0.1 in decimal is 0.0001100110011 ... 0011 ... in binary). Note that if you isolate the recurring part, the ratio between it and the same number of ones is the exact fraction. i.e. 0011 / 1111 = 3 / 15. But there is one extra 0 in front of it, so it should be 3 / 30 = 0.1. This works in other bases as well (if you replace "1" by "biggest digit") e.g. 0.66666... decimal = 6 / 9 = 2/3.

Historically, not all computer systems have used the same floating-point mathematics, especially when it was being done in software. British 8-bit micros in particular, unconstrained by requirements to line up word boundaries, used to use a 40-bit representation for floating-point values. Eight bits for the exponent and 32 bits for the mantissa. Now we have hardware to do floating-point maths, there probably is more consistency from one machine to another.

Unlikely

[Anonymous Coward]

The math errors tend to be in obscure and complex operations - store long double, divide double, etc.
Important cryptographic stuff tends to use extremely primitive operations, often just shifts, adds, xors, and indirection.

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: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?

Re:No.

[ScrewMaster]

How we govern ourselves beyond our foreign policy is utterly unimportant to their larger goals.

Which, in some cases, involves the elimination of us infidels. So you can't say that we're relevant to them only in terms of foreign policy: we're relevant simply because we exist, and that fact is intolerable to some people.

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.

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.

[dshadowwolf]

1) It's not clear that the ECC PRNG is "backdoored" - everything I've seen says that it "may" or "might" have a weakness where there is a second, related set of numbers - not that there IS a second set of numbers.

2) This article doesn't say anything new. If a processor has a flaw in its math processing then exploiting that flaw could lead to any result - but it's unlikely that it'd just cause the processor to kill the security software. Look at the F00F bug on older Intel chips - it caused the processor to fault and lockup. So a processor fault causing a single process on a system to fault seems like a non-starter.

3) Almost all modern processors actually "decode" a single instruction (like movb %ah, %al) into a series of very low-level instructions. Intel has actually built a way to update this translation process into its newer processors - the "microcode update" system. On Linux and Windows, at least, you can install a new version of the microcode on a processor.* This process could be co-opted by someone with the proper resources to cause a processor to mis-function.

*I think the reason they don't offer things like SSE3 as a microcode update has more to do with economics than limitations of the silicon

---
Sometimes, I wonder if the world isn't just a dream and me the dreamer. Then I stub my toe and know it isn't

Random Numbers in .NET and in General

[randomErr]

Yeah know, I've noticed this problem on a series of processors at my college. I had to write a basic key based cryptography program in C#. Well I created the system with no problem. But if you ran the program in a certain lab where all the computer are identical (hardware and software) I could generate the same 4 key sets each time. My solution was just to use and external DLL with my own generator from another language.

My point for this example is that I don't believe its the processors fault. If the software engineer can't write a decent algorithm to generate random numbers then it the engineer at blame, not the processor. I wrote great random number generator back on the Apple IIe years ago. Why can't people do the same now?

Way to surrender to violence, kaffir

[Anonymous Coward]

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

Re:Way to surrender to violence, kaffir

[Eli Gottlieb]

Let's just be frank: Islamism is nothing more or less than a religious twist on the old pan-Arabic-nationalism.

Islam can coexist with the rest of the world. The type of pan-Arabism that sees all land conquered by the Arab empires of old as rightly belonging to the Arabs of today, cannot, whether or not it drapes itself in a burqa to avoid the eyes of the West.

That's the way you'd do it

[slashdotmsiriv]

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.

Re:Terrorists?

[jimicus]

A very good friend of mine unwittingly gave me an insight which I think explains it very nicely.

As far as I can tell, his source of news is "whatever the headlines in the mainstream media are this week". When the corrections come out much more quietly six months later, buried underneath an advert for a home course in Swahili, he misses them entirely.

As far as he's concerned, Osama bin Laden is from Afghanistan (and is probably still living in a cave there), Saddam Hussein had weapons of mass destruction and Jean Charles de Menzes was wearing a heavy coat and running away from men shouting "Armed police, stop!". None of which are true, but all of which were reported as such when the news first broke.

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.

Re:The NSA

[Anonymous Coward]

It is in the US Governments best interests to be able to decrypt any form of communication they wish to see.
Some of you may remember the Clipper chip initiative in the early 1990's.Clipper would have essentially been an encryption card within PC's using Public/Private keys.
The legislation that the government of the time was trying to get passed was that the agency would have a copy of your private key to ensure that they could decrypt your messages if it was a matter of national security. The whole program was squashed.
Shortly after that at least one prominent CIA director resigned and formed Verisign (or a parent company - not sure of the exact facts). Through the Verisign infrastrucure most of the worlds PKI keys were issued. Except for a fairly large chunk (I think it was close to 30% ) that were being issued by a small South African startup called Thawte, started by Mark Shuttleworth of Ubuntu fame.
Verisign bought Thawte from Mark Shuttleworth for a substantial amount of money, thereby gaining control of all reputable PKI keys issued globally.
So here we have on American company run by ex CIA director(s) who can decrypt most encrypted data on the planet on the fly.
Call me paranoid, or a conspiracy theorist, but you do the math on the facts presented. I can assure you that none of them are co-incidental. If you think that Verisign will not pass on private keys to any relevant government agencies to facilitate decryption for the sake of national security, as the origininal plan required, you are misguided by a false sense of security.

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

Re:NSA/GCHQ Private IS open review, practically

[pthisis]

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.

That used to be absolutely true. Over the last 15 years, there's been a huge boom in private-sector cryptography.

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.

Yeah, at the time the NSA was about 20 years ahead of the open community on things like differential cryptanalysis.

Since then, the lead has deteriorated significantly with the proliferation of public-sector mathematics. Even former NSA employees have been quoted as saying that they're still ahead, but not by very much.