Shamir reveals more about optical 512-bit cracker 55
MattJ writes "The AP reports that Shamir (the 'S' in RSA) has revealed more details of his optical 512-bit cracking machine, TWINKLE, at a cryptography conference. " It's a pretty darn cool machine, and at only 2 million dollars, it'll be a bargain *grin*!
Re:512 already not safe (Score:1)
512 already not safe (Score:1)
The more interesting part of this article is that the computer is optical in nature. For $2 mil you could build a much cheaper distributed PC network that has more cracking power. Perhaps someday this device will become more economical/useful, but for now it's just a play toy for researchers trying to make a name in a field that is now fairly mature.
Re:Means that NSA already has one (Score:1)
Re:Hmmm... color me skeptical... (Score:1)
There is a big fat IF right here, in that a quantum computer would be so sensitive that nutrinos or gamma rays might disturb the state of the computer - and we all know just how easy it is to block a gamma ray... just a wall of lead as thick as the solar system.
Regardless, it is interesting -- and maybe a similar effect (base infinity??) could be done within an optical computer.... but then again, perhaps as you suggest, it would be a nightmare to actually extract the answer... maybe even a quantum impossibility.
Re:Ok, I'm worried... (Score:2)
Most encrypted communication on the net, and virtually all that's automatically negotiated (e.g. the SSL encryption spec your browser uses) consists of both a private and a public key section. RSA is the usual choice for the public key. That key is 512 bits long in your average export-crippled browser. The RSA key -- which is strong and has the public-key exchangeability benefit, is also computationally extremely slow -- RSA is slow, that's just how it is. So rather than encrypting the whole communication with RSA, RSA is used to encrypt another key, that being the secret key for the faster block cipher, typically IDEA, RC5, 3DES or (gods forbid) single-DES. The block ciphers generally use smaller keys because the computation involved in breaking a 128 bit IDEA or DES key is in the general neighborhood of breaking a 1024 bit RSA key; different algorithms, different relative strengths.
So, to summarize, your 56-bit browser crypto is referring to the private-key portion (rc5-56 and des-56). Your RSA is probably using 512-bit public keys; your browser should be able to tell you when you make an SSL connect f you want to check. So don't feel _quite_ so bad, but still, ditch the crippled browser. 56-bit secret-key crypto is too weak for any serious use, and 512-bit RSA, as Mr. S demonstrated, is now likewise.
I expect it's been posted elsewhere, but Navigator/Communicator 4.0x and earlier could be patched easily with a copy of sed(1). 4.5 and later probably could but I haven't worked out how; use Forify [fortify.net] for them; it's effective and easy to use.
Re:Asymetric vs. Symetric & I'm not worried... (Score:1)
Well, as long as you're complaining about the scarcity of technical detail in the article -- what in the article said that this machine would take twice as long for each extra bit on the key? (I assume that's what your calculations are based on). Who says that rule applies to this sort of machine? Maybe each bit just requires
adding an extra diode to solve it in the same time...
There's no need to be skeptical! (Score:1)
Don't be fooled by RSA's huge key sizes in thinking that it's impervious to attack. 128 bit symetric crypto is for now, and in the distant future, considered unbreakable. A 128 bit public key would be breakable by me & my pocket calculator (exageration! actually, no, it isn't
It disturbs me when articles mention the strengths of the encryption of various products, methods, or algorithms, without mentioning the basic differences between them.
The info was posted before... (Score:2)
The description of the original device has been posted here [nytimes.com] (slashdot discussion: here [slashdot.org]).
an analysis of the device by the RSA Labs has been posted here [rsa.com] (related slashdot posting [slashdot.org]).
Re:Asymetric vs. Symetric & I'm not worried... (Score:2)
Read read read read it! Right before bed every night, and right when you wake up in the morning. Peruse the web in search of information (searches for terms like PGP, RSA, Diffie, Public Key, Key Server, Cryptography, Cryptanalysis, security, privacy and other related terms will probably yield some more helpful info...
Counterpane [counterpane.com] is probably one of the best places to start. Read the white papers there. Subscribe to the newsletter. Check out the links. You might want to check out RSA [rsa.com] as well. They've got a bunch of FAQ's on their website, most of which will answer your questions. You may also want to check out PGP [mit.edu] (that link's only if you're not a business... The PDF manual has a lot of info as to how the product works. Verisign [verisign.com] will probably have some more information... I haven't been there recently, but i'm sure you can unearth something...
Anyone else want to pile on some more resources for this guy (or girl)?
(That was still a lot less typing than answering all those questions, and will probably supply better information that I could type in an hour...)
Re:Asymetric vs. Symetric & I'm not worried... (Score:1)
I believe that if the machine worked in the way that you implied, we'd hear about it coming from someone like Cray or IBM (if we even did hear about it) - and not a cryptographer. An implentation like that would seem to have far many more uses and could quite possibly lead to a paradgrim shift in the computing world, not simply speed the decryption of 512 bit RSA.
Without more information, I'm lead to believe that he's simply created a new machine architecture for a machine that's still using a brute force attack. It's much faster any previous implentation of the idea, being that it's based on light rather than electrical currents running through a circuit board, but in the end it's most likely using a known factoring algorithm, being that there was no mention otherwise, which would be an actual breakthrough... Without that, he's simply sped up the process.
If it was simply a matter of adding a diode, or even an array of diodes, to eventually be able to target 1024 bit RSA, someone would have mentioned that.
But then, if that was the case, the story probably would not have found it's way to the press in the first place. It would completely undermine everyone's confidence in the computer systems that they use and depend on, which could completely disrupt our economy, nation, and eventually, way of life. We've grown extremely dependant on secure transfer of information in this age, and it would be extremely irresponsible to just blast this information out to the public without at least having an idea for a plan as to how banks and other companies could adapt to this.
That would be beyond open-source development. It is beyond finding holes in Windows NT and posting instructions and an executable on your website. This is about society. I hope that Shamir, or anyone, would be responsible enough to have an idea for a fall back plan prior to telling the world that every transaction that's ever been conducted is now vulnerable.
Based on those assumptions assumptions on my part, and RSA is demonstratably safer with larger keys against brute force attacks, I, like a previous poster, believe that idea that this machine is solely an exercise to show the theoretical weakness of 512-bit RSA keys.
For the conspiracy minded: their patent does expire this or next year, I believe? At which point, there's sure to be a push to move onto another algorithm that makes *SOMEONE* money. The way that that would be done would be to show everyone that it's demonstratibly better than RSA.
hmm ok (Score:1)
From the way the article talked, it seems very very possible.
do a little research then (Score:3)
A paper from the first announcement of this back in May [slashdot.org] is available in a couple of places (zipped eps [cryptome.org] and postscript [cryptome.org]), as well as an analysis by RSA [rsa.com]. see also the RISKS posting [ncl.ac.uk].
If you meant just that the design is untried, I suppose this won't convince you, though optical computers of this sort have been build (on a much smaller scale) before. Anyway, we have this thing called "engineering" for figuring out if something's going to work or not.
I don't seen any new information on the web. Can someone from the conference let us know what progress has been made on the design front?
Re:512 already not safe (Score:1)
http://www.rsa.com/rsalabs/html/twinkle.html
Also, not to reduce the work of R,S, and A but they didn't invent the field of public key encryption. It was actually invented by the British Secret Service during WWII (even before Diffie-Hilleman), but this fact wasn't made known until fairly recently.
http://www.cesg.gov.uk/about/nsecret.htm
Re:number of atoms in the universe (Score:1)
Besides, I'm on a no good computer which has Excel on it. When I did a sort on 1+E86 vs 2+E128, 2+E128 came out as the greater as the two... This is Excel. This is a Pentium chip. This is me. I may be wrong!
CAN SOMEONE help us clarify this???
Re:number of atoms in the universe (Score:1)
I knew someone out there could shed some light on this...
Out of intelligence.... (Score:1)
Ok, I'm worried... (Score:1)
Well considering that my browser uses ever-so-strong 56 bit key encryption, I'm duly worried.
However, technological advances as reported by AP and Reuters are always worth reserving judgement on, so I'll believe it when I see it.
--Remove SPAM from my address to mail me
Oops (Score:1)
"Longer keys, such as 1,024-bit, are already employed for many sensitive communications. But, out of intelligence and other concerns, the U.S. government requires special permission to export software with the longer keys."
muahahaha 'Out of intelligence and other concerns'
Re:Hmmm... color me skeptical... (Score:1)
Anyhow, my rough guess of what I know of the encryption routines...
The 6x6 diode is probably representing a 6x6 matrix which is used in deciphering the code. A key? A kernel? I don't know what it's called.
The beauty of light is that, amongst other things, it can do Fourier transforms, convolutions, etc. virtually INSTANTANEOUSLY. It, in fact, doesn't even scale with the size of the "image" you want to transform. Obviously I can't go into an optics discussion here, but you can "view" the transform simply by looking a certain distance away.
I'm guess it is something like this which enables this machine...
Hmmm... color me skeptical... (Score:2)
Shamir knows what he's doing. (Score:1)
--
I love it..... (Score:1)
"Oh, no, we cant hide anything anymore!"
Well, they didnt want us hiding info either.
Personally, I think encryption is a fine thing. Each person should be guaranteed their privacy.
I wonder... how many people are still using 40 and 56 bit keys?
56 bits keys aren't for RSA (Score:2)
Means that NSA already has one (Score:1)
Remember the big flap over "new, 64bit architectures" for computers when the Alpha and MIPS 64 bit processors came out?
A guy I used to work for once ran a minicomputer company during the 1970s. The military guys had 64bit computers back then.
Usually if something of a "national security" or "military use" product gets developed, the public won't know about it until it is "invented" 10 or 20 years later.
For instance, there is evidence to suggest that the US military had some sort of working cloning technology working 20 years ago, including human cloning. Only now are we hearing about "Dolly the cloned sheep" etc.
Patrick
p17501@yahoo.com
Re:Ok, I'm worried... (Score:1)
Why are you using a browser with 56 bit encryption? If it's due to living in the UK, just mosey on over to replay.com and dowload a 128 bit browser. Not located on American soil, not subject to silly American export controls.
Re:56 bits keys aren't for RSA (Score:1)
Cracking the 56bit DES challenge took a few days last time
Less than 24 hours, actually. See the distributed.net press release [distributed.net].
Re:Hmmm... color me skeptical... (Score:2)
(which are what you're describing) have been tried
many times to solve difficult problems (NP-hard,
hard optmization). While they allow, as in this
case, great increases in parallelism, the answer
becomes harder to discriminate. With NP-hard
problems it is often the case that the answer
can actually be known to be found (at least
with a high degree of probability) in the
"machine", it just takes exponentially more
effort to retrieve it as the size of the problem
instance increases.
This happened with Adleman's (the "A" in RSA)
"genetic computer" -- it took exponentially more
effort to extract the problem solution as the
size of the problem increased (well, that and
it took exponentially more slush to compute the
answer).
Lacking any details on how the system works I
would assume parallelism is key, as well as a
speed-up due to being optical. But if I
remember correctly, breaking RSA is equivalent
to finding the primes in the key. So, this is
essentially a factoring machine as well. While
factoring is not known to be NP-hard, it is
"pretty damned hard" in a colloquial sense, and
one doesn't tend to get something for nothing
where complexity theory is concerned. I'm sure
that whatever he has done, while presumably
incredible, it has similar exponential slowdown
as the key length is increased.
btw, whatever happened to the pundits a couple of
years ago who said that a 512-bit key would last
for 20 years? The technology hasn't speed up
that much (i.e., we are still keeping check with
Moore's Law), but the methods have... I'd be
interested to see an adaptation of Moore's Law
for *actual* gains in key cracking (for something
like RSA where there are known values), as
opposed to the bullshit projections which depend
only on processor speed.
yeah, right... (Score:1)
Need real info to comment. (Score:1)
Modern mainstream news organizations have come up with a content-free grammar.
Re:Asymetric vs. Symetric & I'm not worried... (Score:1)
---------------
The key lengths of symmetric and asymetric encryption are not directly comparable.
RSA-public keys are extremely long, because of two things. Number one, they only make use of the prime numbers available within the limits of the key. They also need to be longer and use more complex math functions because they are available for anyone to see. The basis of the idea of the public key is that someone can use that key only to encrypt data for the intended recipient. You can not, in theory, take a public key and use that to determine the corresponding private key. What Shamir has shown is that it is feasible to do this, with a 512 bit key.
Symetric keys are shorter and much faster, because they are kept secret and they make use of the entire spectrum of numbers available, rather than just the primes. However, by gaining access to a symetric key, not only can you encrypt data, but also decrypt it as well.
In order to initiate a secure session with a web server, I believe the sequence goes: the server generates a RSA public key and passes that to the browser. The browser then generates a 40 (for exportable browses) or 128 bit symetric session key, encrypts that with the public key, and sends that back to the webserver. The webserver and webbrowser from that point forward use the smaller and faster symetric key. So long as the symetric session key is passed using an RSA key larger than 512 bits (supposing for this instance that 512 bits is crackable but 513 and more bits is not),
In trying to keep this on the shorter side, I'll point you towards Bruce Scheiner's Counterpane [counterpane.com] website, which provides a huge amount of resources and links to other sites.
Basically, among other things, I believe you'll find information that says 128-bit cryto:
1. Has more keys than atoms in the universe.
2. Would take longer than the universe has been in existance to brute force a 128 bit key using all available computers.
I don't remember any pundits saying that... (Score:1)
There are real, fielded systems like "Crest" which protect millions of pounds worth of transactions with mandatory 512-bit keys, but this is not on the advice of those who know what they're talking about.
--
Re:I love it..... (Score:1)
adam
Re:There's no need to be skeptical! (Score:2)
I don't know how long 1024 bit RSA will stand... Which is partially why I use a 4096-bit key. Why should I want to generate new keys 20 years from now and worry that all my old "secure" communications are now visible to prying eyes?
Processors have grown to the point where they can handle larger key sizes with not much inconvience, I simply don't see a reason to use smaller keys, when only delay the inevitable... Yes, it may be overkill these days, but I'm sure at one point people thought that 384 bits was safe, and 512 bits were overkill...
Not relevant (Score:3)
Intel and others are just now getting to true 64 bit architecture because they are sticking it all on one chip. That doesn't mean the government had 64 bit chips 30 years ago. They just bought whatever the computer manufacturers made at the time, and I'm sure some of them internally had 64+ bits of bus width or accumulator space.
The U.S. government classified teflon (PTFE) during the war, because it was used to line pipes in uranium extraction equipment. But a french chemist discovered the same thing in 1957, and took out a patent on it, then sold the patent to a frying pan company so they could make non-stick pans. A few years later the U.S. government discovered what was going on when the pans started showing up in department stores and went ape shit.
They made one attempt asking the french government to classify the substance before they realised it was a hopeless cause. The french like to recall this story every time the U.S. tries to get europeans to do things the 'Merkin way. Its the same for encryption.
If Shamir is touting this design, I think it is more to scare people into believing short keys are soon to be crackable, and this will get them to demand much longer keys. The design is very "blue sky", with all the emphasis on optical computing on a very large scale. But if OC takes off in the next few years, then any university with an OC lab could produce a machine like this as a student group project. Then all the short key length RSA protected systems are at risk. Shamir is just trying to bump the key length up to something reasonable for the next decade or so.
my
the AC
Re:Not relevant (Score:1)
The TWINKLE device simply makes factoring large composites of primes a couple of orders of magnitude faster than it is now. The best known factoring algorithms are super-polynomial, so making keys large enough to overcome any constant increase in computing speed is not difficult.
Also, note that the design is not very "blue sky". It is not a general-purpose optical computer. It uses a property of light - that it can be used to implement very large, imprecise adders - to massively speed up part of a factoring algorithm.
Asymetric vs. Symetric & I'm not worried... (Score:2)
And if i got it straight, it implied that the machine could break a key in *two days*... So, given MS Excels limitations, and me not wanting to attempt to type in exponents, it would seem to me that a 546 bit RSA key would be breakable within only 94,136,269.5 years... YIKES... I'm scared.
But then, for only
Even then, it'd be several milleniums before they aquired the wealth needed to be able purchase enough of these machines to do the job... And they'ed probably fill up all of Rhode Island!
Just because this machine has the possiblity of rendering 512 bit RSA keys obsolete, it in no way endangers the 128 bit encryption of web browsers/servers (So long as they initiate the key exchange with "at least" 768 bits...)
However, I still don't understand why anyone would use weaker encryption than the strongest available. Such as, recommending 2048-bit PGP keys rather than 4096 bits? If you're taking the time to encrypt your data, surely you can spare a few extra minutes a day to be sure that your data will be safe for an extra 20 years (and that 20 year figure is quite generous!)... Instead, I always see people go "Oh, 512 bits is breakable? Time to change my key to 1024 bits"... Computers are powerful enough these days where you shouldn't need to settle for less than the strongest available.
It seems ludicrious to encrypt data with weaker encryption, most of the time, and stronger encryption only when it's sensitive information. Just by doing that, you're flagging that information as the data that's actually important.
Re:Ok, I'm worried... (Score:1)