Slashdot Mirror
Shamir reveals more about optical 512-bit cracker
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*!
Adelman IIRC
512bit RSA keys have not been safe for a long time and it's legal to export it in software from the US because of the ease at which it can be cracked.
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.
-- Virtual Windows Project
Can be found here:b _j.shtml
http://www.info-sec.com/crypto/99/crypto_051299
PostScript format
This is because the US uses public funds to develop technology for the military, cia, nsa, etc. Once the technology is commercially viable, it is released to the commercial sector. One word: Boeing.
According to what Michio Kaku wrote in "Visions", the theoretical "quantum computer" (which has "quantum dots" as the calculation medium - an electron trapped in a potential well - the electron can be set to an infinite number of different states by mixing probability of "spin up" and "spin down".) is capable of factoring a number of any size in an instant.
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.
A W S ----------- QABO : BALA
Thanks for the paradigm shift. Obviously I was being too simplistic in assuming this could be solved by multiplying the number of beam intersections by the frequency. The implied performance gain due to convolution is staggering!
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 for them; it's effective and easy to use.
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
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...
--- Where's my X.400 protocol decoder?
So far as I've understood it (I'll go looking for URL's if you insist!) public key crypto (RSA, in particular) is at best only as strong as symetric keys of 1/10th the length (due to using only prime numbers)... Therefore, 512 bit RSA is roughly equivilant to 56-bit DES, which has been breakable (theoretically) for a while now.
;)...
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.
It would've taken a lot of transputers. They were fast for the time - iff you could fit the code/data in the onchip memory (all ~3.9KB of it on a T800). External memory references bit you big time. Getting good performance on large or more general problems was tricky. Transputers failed because they couldn't keep up with the performance of other processors and the fact that inmos lied about the "transparent" use of transputer networks (that didn't happen until the ill-fated T9000). Their main claim to fame was the ease of h/w design due to the memory controller et al on chip which required very little glue logic to make a system. It was very simple to plug lots of them together. As for being military developed....Hmmm. Not entirely sure but the military did like some versions as they were quite rad. resistent. I base these comments on having been involved in a lot of transputer work (wrote an OS for a machine using them). And I have a wafer of dead T414A's in my desk drawer given to me the day I went to complain to David May about occam-2.
man, am I good at remembering past stories:
The description of the original device has been posted here (slashdot discussion: here).
an analysis of the device by the RSA Labs has been posted here (related slashdot posting).
Quick! Run, don't walk, and find yourself a copy of Applied Cryptography!!!
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 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 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 (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 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...)
IF he's made that much of an advance, then forget about it. However, if that much of an advance was made, I don't think that it would be mentioned on AP.
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.
Hey Adi... I'll take one of those. How much did you say they were?
From the way the article talked, it seems very very possible.
The estimates I see of the number of atoms in the universe come in at about 10^85, MUCH more than 2^128.
... if for no other reason than a lack of information.
:)
A paper from the first announcement of this back in May is available in a couple of places (zipped eps and postscript), as well as an analysis by RSA. see also the RISKS posting.
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?
It's the 'answering machine' from Sneekers! There seems to be a few parallels here...
- 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.
I think you have nutrinos and gamma rays mixed up.
Insert lame-assed Beowulf comment here.
"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...)" could you explane this to me? I thought if the key was longer it was harder to break, why is it that a 128 bit encryption would still work if the 512 bit RSA was broken? Why would the 128 bit key need to have at least 768 bit key exchange?
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'
In any event, users of 512-bit keys ``should be worried,''
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
to hell with html formatting ;)
"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'
Unfortunately, the story doesn't give many technical details about the method. (Where's it mention EHZ?)
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...
... if for no other reason than a lack of information. With nothing even similar having been built, how can they have such confidence that there won't be major performance-limiting issues with the actual implementation? Just because it works in theory doesn't mean it it will work at the anticipated speed until they actually build it -- so they can't possibly know that it is faster than current devices.
Geeky modern art T-shirts
It seems pretty unlikely that someone as competent as Adi Shamir would get this one wrong by an order of magnitude. It seems likely that if he says it's possible, it probably is.
--
Xenu loves you!
I want to see the government quake in their boots!
"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?
So there.
The 40 or 56 bit keys that some browsers use is for non-public key cyphers like RC4, RC5, DES, etc. Those the the things distributed.net is cracking. The 512, 1024 bit keys are for the RSA public key cypher. It's a totally different algorithm, and comparing a 512 bit RSA key to a 56 bit RC5 key and saying "that 56 bit key must suck" just doesn't make sense. The key sizes aren't comparable. Cracking the 56bit DES challenge took a few days last time, cracking a 56bit RSA key could be done by hand in that time.
What this means is that NSA already has one running.
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
I don't think any governments are going to have a hard time switching over to 1k RSA if they consider this a real threat.
Hi, Readers might be interested to see Dan Ryan's (SAIC) key strength table. (Does ./ support tables? Would help here.)
.7 sec 13 hrs. .0002 sec 12 sec
... you get the idea.
[Added: OK; I cannot get this stuff to format. We need a perl genius to create a formatter program for off-line composition. I'm just going to post this table all message up, you can follow along.]
Threat Budget Technology 40 Bits 56 Bits
==============================================
Hacker Small Scavenged
Time 1 week NOT
---------------------------------------------
Small
Business $10K FPGA 12 min 556 days
---------------------------------------------
Corp. $300K FPGA
or ASIC 24 sec 19 days
---------------------------------------------
Big
Corp. $10M FPGA
or ASIC
---------------------------------------------
Gov't $300M ASIC
==============================================
These values are of course out of date. I'm posting this as AC because, well,
Modern mainstream news organizations have come up with a content-free grammar.
Bantam Dominique roosters crow a four-note song. Once you've heard it as "Happy BIRTHday" you can't NOT hear it that way
Preface: If I err in any way, someone please step forward and correct where I'm wrong.
---------------
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 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.
...expert opinion has recommended 1024-bit keys for quite a while.
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.
--
Xenu loves you!
How many transputers would it take to build something of comparable speed? Probably not too many.
I suspect that transputers mysteriously got dropped because they were a big risk to Government encryption systems. They were very powerful, for their time, and had they been developed to their limit, would have been one of the fastest processors for massively parallel machines.
Mind you, they were designed for the military, in the first place. Maybe that's exactly what the military did. Hmmm - a thought - what sort of timeframe was Echelon computerised? I think it might be when the T400 came out.
Yes, there were many different architectures of computers back in the 70's. Some were 36 bit (DEC PDP-10), some were 72 bit (Burroughs something), and others had "really big words" of 128 bits. There was no standard, just whatever the engineers decided was big enough.
.02 euros,
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
Hemos is like...sci-fi fans;he thinks technology is cool, but he hasn't bothered to understand the science it's based on
It was "Sneakers", starring Robert Redford, Sidney Poitier, Dan Akroyd, River Phoenix, et al. Great movie, by the way (a refreshingly less-retarded-than-usual Hollywood-type geek story).....
I really wish that articles that get displayed in the mainstream press such as this, would take the paragraph or two to remind people of the difference between the different types of encryption.
;) $3,435,973,837 dollars, you could get it back to the 2 day range. And that's only 546 bits... who's using that?!? So everyone is using 1024 bit encryption, we can feel safe to say that until the day arrives where the Fed decides to up our taxes to the 99.9999% range, we're safe...
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.