×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Factoring Breakthrough?

michael posted more than 12 years ago | from the for-as-long-as-men-are-capable-of-evil dept.

Encryption 492

An anonymous reader sent in: "In this post to the Cryptography Mailing List, someone who knows more about math than I do claimed "effectively all PGP RSA keys shorter than 2k bits are insecure, and the 2kbit keys are not nearly as secure as we thought they were." Apparently Dan Bernstein of qmail fame figured out how to factor integers faster on the same cost hardware. Should we be revoking our keys and creating larger ones? Is this "the biggest news in crypto in the last decade," as the original poster claims, or only ginger-scale big?"

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

492 comments

Ginger scale big? (-1, Offtopic)

Anonymous Coward | more than 12 years ago | (#3071036)

Eh? What the blazes is that, my good man?

Re:Ginger scale big? (2, Funny)

medicthree (125112) | more than 12 years ago | (#3071070)

don't tell me you haven't converted your judgments of magnitude to the ginger scale. everybody's doing it.

damnit (-1, Redundant)

Anonymous Coward | more than 12 years ago | (#3071039)

now i am FUCKED because of this.

Re:damnit (-1, Offtopic)

Anonymous Coward | more than 12 years ago | (#3071158)

Oh well.

My stupidity is reaching new heights. (-1)

RoboTroll (560160) | more than 12 years ago | (#3071048)

Im not just confused; I am utterly baffled! therefore I am also quite stupid. And I say, again, once more : thanks for your time reading this. I bet you wish you had the last x seconds of your silly life back. HAHAH BITCH. Eat that.

This troll was reposted from the Troll Library [slashdot.org] without permission of the original author. If you object to this post, or if you wish to add your troll to the Troll Library, please reply to this message.

Re:My stupidity is reaching new heights. (-1, Offtopic)

Anonymous Coward | more than 12 years ago | (#3071068)

I object to this post!

Re:My stupidity is reaching new heights. (0)

Anonymous Coward | more than 12 years ago | (#3071089)

Overruled, I'll allow it.

Re:My stupidity is reaching new heights. (-1, Offtopic)

Anonymous Coward | more than 12 years ago | (#3071248)

your honor!! permission to approach the bench?!?!?

It's Big... (-1, Offtopic)

Anonymous Coward | more than 12 years ago | (#3071049)

...really big.

1st (-1, Offtopic)

Anonymous Coward | more than 12 years ago | (#3071050)

dedicated to all my dead homiez

Re:1st (-1, Offtopic)

Anonymous Coward | more than 12 years ago | (#3071230)

first reply to second post !

he he he :)

For the PostScript-impaired (5, Informative)

Hew (31074) | more than 12 years ago | (#3071053)

Try viewing the postscript file using the online viewer here [samurajdata.se] instead.

Re:For the PostScript-impaired (-1, Offtopic)

Anonymous Coward | more than 12 years ago | (#3071067)

forst pist!

Re:For the PostScript-impaired (0)

Anonymous Coward | more than 12 years ago | (#3071097)

I read it, but I just don't understand it. It looks like just a bunch of exponential numbers. SHOW ME THE CODE! =) (Or at least pseudo-code)

Re:For the PostScript-impaired (4, Informative)

killmenow (184444) | more than 12 years ago | (#3071154)

Or view it as this [rr.com] PDF.

Now let's see how well RR's server can handle the /. effect. :^)

AES? (1)

NortonDC (211601) | more than 12 years ago | (#3071066)

What's the impact of this news on the security of the newly accepted AES (DES replacement)?

Re:AES? (4, Insightful)

Hizonner (38491) | more than 12 years ago | (#3071096)

The Rijndael/AES cryptosystem does not depend on the difficulty of factoring. This is a big deal mostly for RSA.

Re:AES? (1)

warkda rrior (23694) | more than 12 years ago | (#3071214)

RSA is an asymmetric (public key) algorithm, while AES is symmetric crypto algo. There is no point in comparing the two.

Doesn't affect AES (2)

Cadre (11051) | more than 12 years ago | (#3071118)

There is no impact. AES is a symmetric system that is not based on factoring. This apparent discovery only affects algorithms that are based on the difficulty factoring large numbers.

Re:AES? (0)

Anonymous Coward | more than 12 years ago | (#3071148)

Not a problem. AES is symm key. The factoring problem affects only public key.

AES impact? NONE! (1, Informative)

Anonymous Coward | more than 12 years ago | (#3071168)

The paper talks about constructing a computer optimized for factoring large numbers. Part of the RSA public key is the product of two large prime numbers. If you can factor that, you can get the private key, and then do whatever.

AES is a symmetric key algorithm -- the same key is used for both encrypting and decrypting. Factoring numbers has nothing to do with any part of the algorithm, so this has no impact at all.

That said, most of the stuff encrypted these days with AES uses a public key algorithm to send along the AES key. If the public key is broken, then out pops the AES key and the message is cracked. So, just because you're using AES doesn't mean you are safe. You have to ask if there is any public key key exchange, and if so, what it is. El-gamal, DSA, Diffie-Hellman are OK, RSA is just weaker than we thought it was.

Re:AES? (5, Informative)

Ronin Developer (67677) | more than 12 years ago | (#3071169)

None at all when considered by itself. AES (ala Rijndael) does not depend upon prime numbers. Hence, it is not subject to factoring. It is a symmetric cipher with key lengths up to 256 bits.

Where it could be susceptible, however, is during a key negotiation session (say via Diffie-Hellman Key Exchange) or a naive approach of simply encoding the session key using the recepients RSA key.

Where I would be truly frightened is in the realm of digital signatures where somebody could forge a digital signature simply by knowing the sender's public key and factoring it. With digital signatures almost as legally binding as handwritten signatures, identity theft may increase using these methods.

The resulting impact may be less acceptance of digital signatures and more reliance on antiquated methods.

RD

Re:AES? (-1)

herbert_axelrod (554087) | more than 12 years ago | (#3071194)

The impact? well, it's HUGE my man, HUGE. I don't know ALL the details but I can tell you this: Rob Malda is a fucking homo. Awesome huh!

Re:AES? (1)

jdegre (531681) | more than 12 years ago | (#3071202)

None. AES is a _simmetric_ cypher (private key known to both, sender and receiver), while integer factoring is used in _asimmetric_ cryptograhpy: each party has a private key (only known by him) and a public key. An asimmetric cypher is RSA, for instance.

not surprising... (4, Insightful)

lyapunov (241045) | more than 12 years ago | (#3071073)

Cryptography is going to be a perpetual game of "measure, counter-measure" as computing power increases and people develop more clever ways of doing things.

Does anybody have good sources about this? Ones based on historical encryption and decryption that lead into modern times would be ideal.

Re:not surprising... (4, Interesting)

monkeydo (173558) | more than 12 years ago | (#3071199)

You are right, and this is a major stumbling block to widespread acceptance of encryption in the civilian world. The military and other organizations with a strong need to keep secrets are used to playing these games, but corporate America just isn't. Current applications aren't flexible enough to plug-and-play cryptography, changing crypto systems often means a complete redeployment of the application, or worse yet a new application.

Imagine the conversation with the CIO when you tell him he has to throw out his 1 year old meesaging platform because some guy figured out how to factor very large numbers effeciently and your current platform doesn't support eliptical curve cryptography.

it's a cool method (1, Redundant)

Frothy Walrus (534163) | more than 12 years ago | (#3071076)

basically what DJB has done is found ways to incorporate extra hardware to eliminate redundant operations when performing number field sieve (NFS). he's implemented NFS in a non-linear way, which results in a threefold increase in speed from linear NFS implementation.

it's a wonder no one thought of it before. oh, wait, i think a three-letter agency might have...
better update those keys!

Re:it's a cool method (5, Insightful)

Ed Avis (5917) | more than 12 years ago | (#3071204)

Only a threefold increase in speed? That would make hardly any difference, you'd get a threefold speed increase just by waiting a few years for Moore's law to deliver.

My understanding is that keys of three times the length can be cracked in about the same time - which is an _exponential_ increase in speed.

Re:it's a cool method (0)

Anonymous Coward | more than 12 years ago | (#3071213)

Way to quote the article for points you whore.

Were they even secure yesterday? (5, Insightful)

Carmody (128723) | more than 12 years ago | (#3071077)

The NSA factors numbers, and their work is top-secret. When I read stories like this, I wonder if people are just discovering things that the NSA has known about for years. If the NSA could factor 2 Kbit keys, would they tell people? Probably not.

So when you ask "Are our keys secure" the logical follow-up question is, "From who?"

From me? Yes. I probably couldn't factor a 1000 digit number.

From your boss? Yes. You could use rot-13 and your boss would probably be baffeled.

From your boss' lawyers? From the police? Here is where we get into the gray area; where the article becomes relevant

From the government? I think you were kidding yourself when you thought it was secure in the first place. I find it easy to believe that the NSA is far ahead of the public in the encryption arms-race.

OT: Your sig (0, Offtopic)

rjamestaylor (117847) | more than 12 years ago | (#3071111)

God is real unless declared an integer.

Orthodox Christians believe God is irrational (triune: an irrational number meaning 3 yet 1, 1 yet 3). Got Faith?

Re:OT: Your sig (0, Offtopic)

namespan (225296) | more than 12 years ago | (#3071177)

Orthodox Christians believe God is irrational (triune: an irrational number meaning 3 yet 1, 1 yet 3). Got Faith?

Or God could be complex.... (part real, part imaginary!).

1+3i?
3+1i?

Or perhaps, some complex number which under different norms yields 3 and 1....

:)

Re:Were they even secure yesterday? (2, Funny)

Anonymous Coward | more than 12 years ago | (#3071120)

You could use rot-13 and your boss would probably be baffeled.

Especially if you misspell everything!

Re:Were they even secure yesterday? (1)

georgeb (472989) | more than 12 years ago | (#3071133)

Well, since important figures high up there wish so hard for control over hardware and software, maybe, at least once upon a time, crypto was secure even from the government....
Just a guess.

Re:Were they even secure yesterday? (0)

mlk (18543) | more than 12 years ago | (#3071135)

Considering the past cryptos & gov. "openeness", I would guess this has been about sence it was released.

Re:Were they even secure yesterday? (4, Interesting)

monkeydo (173558) | more than 12 years ago | (#3071145)

From the referenced post:

Note that there have been rumors of an RSA cracker built by a
three-letter agency in custom silicon before this, but until
analyzing Bernstein's paper I had always dismissed them as
ridiculous paranoid fantasies. Now it looks like such a device
is entirely feasible and, in fact, likely.


There has always been speculation that the NSA could break RSA, but it was dissmised as paranoid by most "in the know." Most of the mathematicians didn't believe that they were that much ahead of the rest of us. Now that this technique is known it explains how the spooks may be able to break crypto everyone else believed was "unbreakable" if they had previously made this discovery.

Re:Were they even secure yesterday? (5, Interesting)

JordoCrouse (178999) | more than 12 years ago | (#3071210)

From the government? I think you were kidding yourself when you thought it was secure in the first place. I find it easy to believe that the NSA is far ahead of the public in the encryption arms-race.

Exactly! One of the most lucid posts I have ever seen on /. The alphabet soup agencies spend millions of dollars and hire the most brilliant minds in the world (not just the US), and their whole existance is based on the premise that they need to be able to find out what every human on earth is doing at any point in time.

I have never thought that I could put one by the government, and I have never encrypted my documents because I was worried that some spook might read it. If they want my password, credit card number or DNA bad enough, they're going to get it no matter what I do. I encrypt my data because I'm more worried about script kiddies and regular old fashioned crooks.

Re:Were they even secure yesterday? (5, Interesting)

Syberghost (10557) | more than 12 years ago | (#3071220)

Remember what happened with DES. The NSA said "make these changes. We can't tell you why." IBM made the changes.

20 years later, when differential cryptography was "discovered", it turned out those changes made it more resistant to differential cryptography...

But would you tell? (0)

Anonymous Coward | more than 12 years ago | (#3071079)


It's always been my dream to figure out how to factor big, big numbers. But I always pondered, if I did figure it out, would I tell? ie, How many companies/gov'ts would kill for that exclusive info?

Re:But would you tell? (1)

alkali (28338) | more than 12 years ago | (#3071187)

It's always been my dream to figure out how to factor big, big numbers. But I always pondered, if I did figure it out, would I tell? ie, How many companies/gov'ts would kill for that exclusive info?

This is the premise for what could be the most boring thriller ever sold at an airport newsstand.

it is from DJB (1, Funny)

Anonymous Coward | more than 12 years ago | (#3071085)

So you're supposed to hate it because it is different from the entrenched status quo. I bet he doesn't allow you to redistribute his paper with modifications, either.

Whew - I'm safe (3, Funny)

Dolph (132127) | more than 12 years ago | (#3071086)

I use a 4096-bit GPG key. It may take a day to encrypt a message, but at least the encryption can't be broken (yet).

No wonder NSA was okay with 128 bit encryption. (0, Troll)

bigpat (158134) | more than 12 years ago | (#3071092)

I think that given that the NSA has allowed stronger encryption to be exported supports the idea that "they" have much more powerful algorithms than "they" have let on.

Re:No wonder NSA was okay with 128 bit encryption. (5, Insightful)

fremen (33537) | more than 12 years ago | (#3071129)

Using 128 bits is fine for symmetric key algorithms like IDEAS and Blowfish. It's not ok for public/private key algorithms like RSA. You're comparing Apples to Oranges.

Re:No wonder NSA was okay with 128 bit encryption. (1, Informative)

Anonymous Coward | more than 12 years ago | (#3071190)

Comparing apples and oranges. 128 is a symmetric key length, where every bit in the key is (potentially) a bit of entropy in the key space. 2048 bit keys are public keys, where not every number less than 2^2048 can be used as a key.

OMFG (0)

Anonymous Coward | more than 12 years ago | (#3071095)

this is indeed astonishing. I too thought the rumors of the big RSA cracker at the NSA was a rumor. I guess it's not. This is huge. it not only makes pgp's current implementations useless, but it also makes decrypting all that "secure" RSA-based ssl and ssh traffic eminently readable (probably not realtime though, it probably took a day to break all that traffic the nsa logs for you)

the tinfoil hat set is going to go nuts.

/me changes everything to blowfish and aes

'scuse me, must run, out of tinfoil!

Re:OMFG (2)

mindstrm (20013) | more than 12 years ago | (#3071201)

This is about a threefold increase in factoring speed.. not an order of magnitude.

The NSA can afford huge hardware.. REALLY huge hardware, for breaking crypto... was there ever any doubt?

Re:OMFG (1, Interesting)

Anonymous Coward | more than 12 years ago | (#3071252)

Who cares? If you're really that paranoid that the NSA cares what you are encrypting then perhaps it SHOULD be broken. You're probably a criminal or international terrorist or something. Frankly, if the NSA wants to spend their computer and human resources on decyphering my porn collection, go right ahead. In fact, I'll stick it on a CD and send it to them unencrypted if they prefer.

Too many secrets... (2)

KodaK (5477) | more than 12 years ago | (#3071098)

Circut for integer factorization?

Reminds me of a certain movie...

Re:Too many secrets... (1)

Xandu (99419) | more than 12 years ago | (#3071125)

Didn't you know that Dan Bernstein now works for some toy company......PlayTronics, I think.

Re:Too many secrets... (-1)

herbert_axelrod (554087) | more than 12 years ago | (#3071227)

'Reminds me of a certain movie...' "CMDRTaco and the Valley of the Queers"?? Great flick! I love the part when Taco invites the plumber over to fix his sink.

Hmm.... (2)

Greyfox (87712) | more than 12 years ago | (#3071103)

I wonder how long the NSA has know about this. I'm betting a decade...

I haven't hit a top limit on the GPG key yet. I had an obnoxiously long 4096 bit one I was testing with for a while and PGP was able to encrypt messages to it but was unable to import the private key. Oh well, time to move to an obnoxiously obnoxious 8096 bit one.

Suddenly the 128 bit netscape encryption isn't looking so good (Not that it was before...)

Re:Hmm.... (5, Informative)

jkujawa (56195) | more than 12 years ago | (#3071149)

The 128 bits Netscape uses are for a symetric key. It takes considerably less bits for a symetric key to be secure, than an asymetric key. (I forget the equivalency, but ISTR that 128 bits symetric is roughly equivalent of 2048 bits asymetric.)
And the symetric keys netscape uses don't depend on factoring primes to be secure ...
Although the key exchange that netscape uses to send the session key probably does.

Re:Hmm.... (1)

LordKronos (470910) | more than 12 years ago | (#3071224)

Suddenly the 128 bit netscape encryption isn't looking so good (Not that it was before...)

Actually, you are comparing 2 different types of keys: public assymmetric keys, and private symmetric keys. Public assymmetric keys (like the ones talked about here) require a longer key for equal security (when compared to private keys) because some additional information is already known (the public part of the key). This information can be used to break the encryption faster, thus you use larger keys to offset this.

When using 128-bit SSL on a web site, you actually use a 128-bit RC4 key (which is a symmetric private key). In order to exchange the key between client and server, a secure channel is first created using 1024-bit RSA (public) key.

So yes, the 1024 bit part isnt as secure as what this artice talks about (2048-bit keys), but the 128-bit SSL key isnt quite as bad as it sounds.

Just wait... (5, Insightful)

JohnBE (411964) | more than 12 years ago | (#3071106)

Shouldn't we all hang on until crypto experts validate this? Is it theoretical? How much does the attack cost? etc. etc.

I wouldn't start sending those revocation certificates just yet.

Goat Attacks Man, Watchers Masturbate (-1, Offtopic)

Anonymous Coward | more than 12 years ago | (#3071112)

A goat [goatse.cx] unexpectedly attacked a man while helpless crowed watched, and some masturbated", Reuters reports.

Really Unique Crypto (1, Interesting)

SGDarkKnight (253157) | more than 12 years ago | (#3071114)

I saw an article once (not sure if it was here or not) about someone using random pictures from a lava lamp to encrypt whatever he wanted. Last i heard was everyone that tried to break the encryption failed... the only way to decode it was to use the orignal picture that was taken of the lave lamp. If anyone else has heard about this or has any other information if this worked or not I would love to hear about it.

Re:Really Unique Crypto (1)

J'raxis (248192) | more than 12 years ago | (#3071144)

Isnt this just a creative variation on the one-time pad technique?

Re:Really Unique Crypto (2, Funny)

Eccles (932) | more than 12 years ago | (#3071198)

Isn't this just a creative variation on the one-time pad technique?

And all of these, really, are just techniques that split up the message, and then assume the decrypters can only get one part. So essentially you could do this with any encryption algorithm, just send part by the internet, and part by carrier pigeon, attack stoat, etc.

Re:Really Unique Crypto (0)

Anonymous Coward | more than 12 years ago | (#3071170)

I remeber hearing about this. Apparantly it didnt work, because the reason we think lava lamps are cool is that the movement of the bubbles isn't random.
Now if you could take random pictures of the lamps
it would be, but I think they were getting the randomness from the lamps not the sampling.

Re:Really Unique Crypto (1, Informative)

Lukey Boy (16717) | more than 12 years ago | (#3071175)

Actually that was a university experiment (MIT maybe?) on actual random number generation. The images from the lava lamp were used as the random number seed, since apparently the lamp is the easiest way to observe "true" randomness.

Silicon Graphics took this farther and made a sellable package of this called lavarand. Check out this article [sciencenews.org] for more.

Re:Really Unique Crypto (0)

Anonymous Coward | more than 12 years ago | (#3071178)

That was probably a vernam cipher applied to the sgi lava lamp output. It's a provably secure technique. But you have an enormous key problem with the lamp's output. It's secure, but not practical.

Re:Really Unique Crypto (1, Flamebait)

arkanes (521690) | more than 12 years ago | (#3071181)

The photos of the lamp are just a clever way of generating random keys (often the hard part of a crypto system), it has nothing to do with the crpyto algorithm itself.

Re:Really Unique Crypto (1)

SGDarkKnight (253157) | more than 12 years ago | (#3071197)

But now could you increase the randomness by simply getting a larger lave lamp with more bubbles?

PGP with 2048 bit RSA keys (0)

Anonymous Coward | more than 12 years ago | (#3071119)

The PGP version the article mentions that had
larger keys (at the expense of compatibility)
was PGP 6.x-CKT (Cyber Knights Templar). AFAIK
they stopped development on their branch a good
while ago, maybe google can dig something up.

close your tags (0)

Anonymous Coward | more than 12 years ago | (#3071121)

remember... close your italics tags :-p

To quote another: (2, Redundant)

PureFiction (10256) | more than 12 years ago | (#3071122)

"Holy shit. The math works. Bernstein has found ways using additional hardware to eliminate redundancies and inefficiencies which appear in any linear implementation of the Number Field Sieve. We just never noticed that they were inefficiencies an redundancies because we kept thinking in terms of linear implementations. This is probably the bigest news in crypto in the last decade."

Yeah, this is big news. It also sheds new light on the relaxation of the export constraints. The NSA has dedicated hardware performing this same procesing, and probably for the last 5-10 years...

"Note that there have been rumors of an RSA cracker built by a three-letter agency in custom silicon before this, but until analyzing Bernstein's paper I had always dismissed as ridiculous paranoid fantasies. Now it looks like such a device is entirely feasible and, in fa ct very likely."

Time to make new keys...

Go Dan!!! (0)

Anonymous Coward | more than 12 years ago | (#3071124)

This is cool news. Glad to see discoveries like these published instead of hushed up.

christ (-1, Offtopic)

Anonymous Coward | more than 12 years ago | (#3071136)














god damnit, why the hell did he have to figure that out. Now I must redo everything. Go to hell turd



You fucker.. i should eat your ass. I am so sick of all these idiots figuring out stuff is insecure.



i have hairy asshole with shit crusties hanging on them. so fun to play with while i sleep at night




So more hardware = linear improvement? (1)

mmca (180858) | more than 12 years ago | (#3071137)

So is this saying that x number of linear-algebra circuits will factor a large number x times faster?

So how much hardware are we talking about to factor a 2k bit key in a day? week? month? year?

Someone w/ the math break this down for us.

-M
0xF824782C the finger print for my (soon to be obsolete?) key.

NSA, et. al. (1, Insightful)

jacobcaz (91509) | more than 12 years ago | (#3071140)

I find it funny and interesting that because the NSA and other TLA agengies are *so* tight lipped we assume their skills and abilities are far ahead of current "joe-sixpack" tech.

I suppose this very well could be the case, but it sure lends itself to great conspiracy theories.

I suppose the TLA agengies don't really need strong crypto to invade on my privacy. They just need a court order.

Sure I use a 2048bit key (soon to be 4096bit I guess), but will that really stop them from making me give up the goods if faced with jail when they come asking for my data?

Nope, because I have nothing really to hide. Maybe I keep my cache of pr0n encrypted so my fiancee doesn't discover it, but I will sure-as-shooting give that information up to keep me out of jail.

I'm to pretty for jail!

A word about Dan. (-1, Offtopic)

Penguinoflight (517245) | more than 12 years ago | (#3071143)

Dan Berinstien is (literally) gay. His projects are generally unorganinzed, and have rediculous licenses.

I'd like to see someone else say there's a problem. Nonetheless, the smaller the key, the less secure, and the larger the key, the more secure.

This is not off topic.

Re:A word about Dan. (-1, Offtopic)

Anonymous Coward | more than 12 years ago | (#3071229)

OH DEAR GOD NO NOT GAY!
Well, that settles it - let's just take him out back and shoot him then. Seriously, how the hell is that relevant AT ALL?

Quamtum Computing (1)

mrd98 (540481) | more than 12 years ago | (#3071147)

Once they get a real quantum coputer working (if the NSA hasn't got one tucked away already) most of the encryption schemes known today will be able to be broken in less than a second - big factors are no match for quantum.

RSA PKI (-1, Troll)

Anonymous Coward | more than 12 years ago | (#3071153)

This is not the same thing as the research I've done in the past but from the work I've done, my gut tells me there's an even faster way to crack RSA keys.

I can't prove anything, and I haven't touched that work in years but my instinct is very strong and it tells me RSA keys can be broken in the same ammount of time that it takes to generate the key in the first place.

Maybe one day I'll publish a paper with my groundbreaking results. haha :)

Wait for verification? (1)

mattvd (44096) | more than 12 years ago | (#3071157)

I don't mean to say that this isn't true, but doesn't something like this come up every few months? Some one thinks they broke some highly respected crypto system, then an expert shows that it is invalid or only valid for a small percentage of keys.

Don't Panic (5, Informative)

SiliconEntity (448450) | more than 12 years ago | (#3071161)

I am a co-author of RFC 2440, the OpenPGP standard. It's important to put this result into perspective. Dan Bernstein is the first to say that it is too early to tell whether his design for a factoring machine would be practical for keys of the size in commmon use today. See for example this recent Usenet posting [google.com] , where he says,

Protecting against the http://cr.yp.to/papers.html#nfscircuit speedup means switching from n-bit keys to f(n)-bit keys. I'd like to emphasize that, at this point, very little is known about the function f. It's clear that f(n) is approximately (3.009...)n for _very large_ sizes n, but I don't know whether f(n) is larger than n for _useful_ sizes n.

Bernstein's paper is excerpted from a grant proposal where he is requesting funds to answer the question of whether the design is applicable to useful key sizes. At this point it is far too early to assume that 1024 to 2048 bit keys can be attacked by his proposed machine more efficiently than with known methods.

SSH Implications???? (1)

Temkin (112574) | more than 12 years ago | (#3071191)


Anyone care to guess what the implications for SSH key exchange is?

Temkin

gay slashdot tacosnotting (-1, Offtopic)

Anonymous Coward | more than 12 years ago | (#3071195)

CmdrTaco is a tacosnotter. He takes taco shells, and wipes his own snot and jizz on them. Then, he eats them!

Re:gay slashdot tacosnotting (-1, Offtopic)

Anonymous Coward | more than 12 years ago | (#3071223)

That's not Taco-snotting. You're confusing Wipotrollian and Weathertrollian techniques. Get with the program.

Math (0)

Anonymous Coward | more than 12 years ago | (#3071217)

I checked the math.
Everything appears correct.
However, the application of discrete calculus on page 4 is a bit strange --- I'm not too sure that Euler's theorem could be applied like that.

--BW

1.5 bits lost? (2, Insightful)

nagora (177841) | more than 12 years ago | (#3071228)

If this new method speeds the calculation by a factor of three, and each extra bit in the keys doubles the amount of time needed then surely this "breakthough" amounts to everyone losing less than 1.5 bits of security, doen't it?

The poster seems to think speeding the calculation by 3x means reducing the strength of 300bits to that of 100bits. I know this is plain wrong but I'm not sure of the correct value.

TWW

Sources sources sources (0)

Anonymous Coward | more than 12 years ago | (#3071231)

I love how one persons perception of a paper is suddenly a news worthy event. Espically a usenet post. Creating dedicated hardware to do anything isn't really a big deal. ASIC designs (custom ICs) can be created by anyone with a little VLSI know how, in fact students can make their own ASIC chips in 2months for about $3k. The fact that someone figured out that, hey, I can implement this directly in hardware and optimize it a bit, isn't anything new. Up until about 2 years ago everyone made their own ASICs to get their 4x-400x speed increase with custom memory, caching schemes, etc.. Having a working prototype might be interesting. But, just saying you've got the basic idea down is really laughable.

Reward (5, Funny)

suso (153703) | more than 12 years ago | (#3071236)

Is he going to pay someone $5000 if they can prove him wrong? (qmail joke)

What about Image Base and Static Encrypts? (0)

Anonymous Coward | more than 12 years ago | (#3071238)

I was under the impression that you could theoretically build an infinite number of quantum computers and that they could never break a random sample static encrypted data stream.

And random image encryption should be pretty much the same story.

How does this effect PGP?

Post script viewers... (2, Informative)

Spatch3 (47581) | more than 12 years ago | (#3071240)

You could view this [cr.yp.to] post script file online here [samurajdata.se] , or you could use the Windows, OS/2 or Linux viewers available here [wisc.edu] .
Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...