1024-bit RSA encryption cracked by carefully starving CPU of electricity

Engadget ^ | 3/9/10 | Sean Hollister

[dangerdoc]

Since 1977, RSA public-key encryption has protected privacy and verified authenticity when using computers, gadgets and web browsers around the globe, with only the most brutish of brute force efforts (and 1,500 years of processing time) felling its 768-bit variety earlier this year. Now, three eggheads (or Wolverines, as it were) at the University of Michigan claim they can break it simply by tweaking a device's power supply. By fluctuating the voltage to the CPU such that it generated a single hardware error per clock cycle, they found that they could cause the server to flip single bits of the private key at a time, allowing them to slowly piece together the password. With a small cluster of 81 Pentium 4 chips and 104 hours of processing time, they were able to successfully hack 1024-bit encryption in OpenSSL on a SPARC-based system, without damaging the computer, leaving a single trace or ending human life as we know it. That's why they're presenting a paper at the Design, Automation and Test conference this week in Europe, and that's why -- until RSA hopefully fixes the flaw -- you should keep a close eye on your server room's power supply.

[zeugma]

I didn’t know pedophile news was pushed here

WTF are you talking about? I think your commennt demands explanation.

[dangerdoc]

I don’t get the reply either. I looked back for anything that could be taken the wrong way as a joke, I just don’t get it.

[Uncle Miltie]

Ruh Roh!

[dangerdoc]

Can you translate to English?

I have a feeling that you posted something interesting but I don’t have the context.

[CodeToad]

Wrong thread, or too much booze.

[2 Kool 2 Be 4-Gotten]

It’s a bit hard but basically there are a huge class of problems in computer science which have the property that they are “hard” (i.e. take enormous amounts of computing power/time/resources) to “solve” but “easy” (take small amounts of computing power) to “verify” (i.e. check if the answer is correct.

This is the classic “P vs. NP” conjecture.

The RSA encryption algorithms definitely fall into this category.

If somehow you could find a way to “solve” the problem in the same time as you can “verify” an answer, you have achieved a major breakthrough.

Now here’s where it gets hard to explain so hang on :)

Think of finding an answer as exploring all paths through a decision tree, which if the tree is big enough, will take a LONG time. Think of verifying an answer as simply going down one path of the tree and confirming that some logical proposition holds.

If you find a way to non-deterministically go down all paths of a tree “at once” - you would basically have it. Here’s where you really have to wave your hands to even think about what that might mean. But in a theoretical sense, you can at least have this discussion. Like in a chess problem, it would be like instead of thinking of all possible combinations of moves going out 10 moves ahead, it would be like exploring them all in parallel in the time it takes to work through only one move.

I know this doesn’t read well, but that’s kind of the basic idea. And it involves the notion of non-determinism i.e. pure randomness.

[Erasmus]

I suspect downwdims has at least a couple of FR threads open; non sequitur comments usually result from responding in the wrong window.

Of course, you need to be a hard core FReeper to do that.

≤]b^)

[Calvinist_Dark_Lord]

So hard wire to an UPS?

[Erasmus]

DWD, at least I provided you with a good excuse.

≤};^)

[zeugma]

That was an excellent description of the issue in layman's terms.

 If you find a way to non-deterministically go down all paths of a tree “at once” - you would basically have it.

This is the holy grail of the folks working on quantum computers and quantum cryptography. I'm still on the fence about that entire field. I'm not really sure if we're going to be able to use QM to solve real-world problems though, as the tech is tough, and the uncertainty is great. :-)

[dangerdoc]

No you explained your idea well, it is basically the promise of quantum computing. Solving for all states at the same time.

It sounds like this solution is somewhat different. By starving the CPU, they can force it to give keys in a non random way giving more information about the solution, decreasing the processing time to get the answer.

Of course, I am no expert so take my take for what it is worth.

[zeugma]

I suspect downwdims has at least a couple of FR threads open; non sequitur comments usually result from responding in the wrong window.

 Of course, you need to be a hard core FReeper to do that.

 Or a newbie :-) 

Rank	Poster	FR Age	Posts	Replies	Replies per Post
1	dangerdoc	6.9y	5	13	2.6
2	stainlessbanner	8.8y	1	0	0.0
3	rdl6989	5.6y	1	0	0.0
4	JoeProBono	1.4y	1	0	0.0
5	Uri’el-2012	10.9y	1	2	2.0
6	Pessimist	4.9y	1	0	0.0
7	downwdims	1.6y	1	5	5.0
8	ShadowAce	9.3y	1	1	1.0
9	Yossarian	11.5y	1	0	0.0
10	AussieJoe	1.4y	1	0	0.0
11	rarestia	6.1y	1	1	1.0
12	2 Kool 2 Be 4-Gotten	11.4y	3	4	1.3
13	KarlInOhio	9.3y	1	0	0.0
14	Yo-Yo	11.7y	1	0	0.0
15	philetus	8.4y	1	0	0.0
16	Diogenesis	9.3y	1	0	0.0
17	Ro_Thunder	5.7y	1	1	1.0
18	driftdiver	4.1y	1	0	0.0
19	zeugma	11.9y	2	2	1.0
20	Uncle Miltie	10.3y	1	0	0.0
21	CodeToad	4.6y	1	0	0.0
22	Erasmus	12.0y	2	1	0.5
23	Calvinist_Dark_Lord	7.2y	1	0	0.0

31 total posts, by 23 distinct posters. 1.3 average posts per poster.
Average poster seniority: 7.6y.

[Maceman]

In this theory, the class P consists of all those decision problems (defined below) that can be solved on a deterministic sequential machine in an amount of time that is polynomial in the size of the input; the class NP consists of all those decision problems whose positive solutions can be verified in polynomial time given the right information, or equivalently, whose solution can be found in polynomial time on a non-deterministic machine.[6] Arguably the biggest open question in theoretical computer science concerns the relationship between those two classes

Well, du-uh.

;-)

[dangerdoc]

I get the FR Age, what are the other stats that you posted? Are they posts per month, per week etc.?

[JerseyHighlander]

Her Highness cynwoody frowns upon your argumentum ad verecundiam.

[JerseyHighlander]

This is a really cool article you posted, but above my paygrade as they say.

The info posted above is from a greasemonkey script written by freeper cynwoody... here is her homepage, you want to pick up the FR Tree Viewer, the above posted was the included Poster Report in the script.

http://www.freerepublic.com/~cynwoody/index?U=%2Ftag%2F%2A%2Findex

[zeugma]

Nope. Those are just for this thread. greasemonkey script that generates all that. It will also make the thread threaded by responses. :-)

[Hank Kerchief]

“pure randomness”

I’d be curious to know what you think that is?

Here is a proposition:

There cannot be true randomness, and all apparent randomness is the consequence of ignorance.

I believe the proposition is true. I’d be interested in your opinion.

Hank

[dangerdoc]

At the quantum level, there is no alternative to ignorance and the entire universe is created from particles that behave in some fundamentally random ways.

[dangerdoc]

Thanks for the link.