Slashdot Mirror
Israelis Crack RSA 512 Bit in Microseconds
wojo writes "According to this story, the Israeli Weizmann Institute has broken RSA 512 bit encryption in, get this, 12uS (microseconds). And if that was not enough, it's handheld using a mix of quantum and optical computing technology. I need proof, how about you?" Hey, if it's in theThe Sunday Time (UK) it must be true, right?
Good thing that only Americans are able to do things with cryptography. I mean, if we were allowed to export our expertise, those _foreigners_ would be able to... hey, wait a mintue...
Can your IM do this?
Now suppose that this is real.. and suppose that someone in israel has managed to put together quantum logic gates enough to crack 512bit encryption(last time I heard someone had a single nand-gate somewhat operational).. now the question being: why reveal it to the world?!? This is worth a lot of money as such.. Someone just leaked it out of the institute? Surely they understand the value of this. Why not sell it to nsa etc(or maybe they have it). They could decrypt most public key encryption at their will and now they go and announce it in SUNDAY TIMES of UK?
The way quantum computers work, it would take the same amount of time to crack 512 bits as it would to crack 56 bits, or any other value.
See, quantum computers don't do things serially like standard computers. They perform their operations on the entire data set all at once. It doesn't matter if the data set has 1 item or 1 billion items, it takes the same amount of time.
This is known as superposition. I don't know a terrible lot about the theory, but you can find out more at The Center for Quantum Computing. This Quantum Computing Tutorial is difficult to understand if you haven't done at least a little comp sci, and the one at qubit.org is better for people who've never heard of quantum computing at all.
---
END OF LINE
For all who want an explaination of what quantum computing is all about, point your browsers to http://cryptome.org/qc-grover.htm for a thorough explaination of how exactly such mammoth feats of computing are possible.
Yes this is a very interesting read. 12uSecs is damn impressive I have to hand it to them. Even more impressive if you read the "Thermodynamic Limitations" section of Applied Cryptography (see page 157 of the second edition) where he talks about how if you were to build a dyson sphere around the sun you could still only count up to 2^192. So to brute force computers need be made of something other than matter and occupy something other than space. (go read it)
Anyway, lets look at something. Even with a 512 bit number, we can look at a 513 bit number and it should be twice as complex. A 520 bit number is 256 times as complex. It grows at a rate of 2^n. Which is basically useless from an algorithmic point of view, as most useful algorithms should be around n^k where K is a constant or some derivation thereof.
Let me show something. I use a 2048 bit gnupg key (I'm paranoid okay?). This comes out to be 2^1536 times more complex. Thus (courtesy of my handy Ti-85 calculator) it should take about 2.892x10^457 seconds to factor. This comes out to be roughly 9.17x10^449 years.
The only issues that come up are the following. What are the energy requirements for such a device. Do they grow linearly or exponentially? Also what with keyspace does it increase exponentially or linearly. If it is only a linear growth then yes my 2048 bit key is as good as swiss cheese against this and I better come up with a damn good one time pad system.
I couldn't tell from the article, but it sounds as though part of this is based of Shamir's idea on how to factor 512 bit numbers. I seem to remember there was some mathematical oddity that allowed them to be easier for some reason. Can someone fill me in?
My Slashdot account is old enough to drink...
They have got Adi Shamir's TWINKLE _concept_ confused with a finished product. NTK took the piss out of this on Friday.
/.
This is a classic demonstration of how poor The Times has become. The paper as a whole and especially it's computer suppliment has been very factually challenged ever since Rupert Murdoch took over. He has attempted to make up for crappy quality with price cuts (20p for the paper some days [30cents]) and has so far failed.
The Times is the worse broadsheet paper in the UK and the sooner American's realise this (no-flamage intended), the sooner we won't have joke stories like this on
I haven't seen anyone point out the obvious red flag here.
Suppose I am part of a crack research team, and we succeed in building the world's first, working quantum computer, one capable of almost unbelievable feats of brute-force code-breaking. Imagine our conversation:
"Ladies and gentlemen, by God I think we've done it!" smiles the project coordinator. "Where do we go from here? Ideas, anyone?"
"Publish!" cries a fresh, young intern. Having barely a handful of articles under his belt, he's eager to get his name on something like this.
"Well, perhaps we should hold off, give the world time to prepare," suggests an older and wiser researcher. "This caliber of cipher is still in active use worldwide. It's protecting some pretty sensitive data." She pauses, then adds jokingly, "maybe we could sell it to the highest bidder." This is greeted by nervous laughter.
Me, I'm looking at the mess of patch wires and tangled circuit boards. The machine must cover two desktops! "Why don't we turn it into a handheld device?" I suggest.
The others are startled at first. But as they exchange looks, I see some nods and hear muttered agreement. This is the only logical course of action, and now we all know what must be done.
Firstly, it doesn't address just what is supposed to be "broken" in 12 microseconds. I'm not sure that one would be able to decrypt a message of meaningful size with the private key in that period of time.
Secondly, there's a real mixture of "apparent reality" and "future fiction."
It doesn't make sense for both of the following to be true:
The one claim suggest that there is an actual implementation; the other suggests that implementation is still off in the future.
Thirdly, it does not appear to address the consideration that a huge amount of the security of these systems come not simply in the "cool algorithms" being used, but from the careful use of protocols. Recognizing actual information within a message requires analysis of the protocol, and that's something that cryptanalysis does not, in and of itself, address.
RSA-512 may not be of vast strength; the article still does not strike me as believable.
(Aside: I was in a bookstore yesterday and saw Yet Another Book on Codes. Bible Codes, as it happens, but there has been, of late, an increase in the number of books on Real Crypto on bookstore shelves. I can generally evaluate the quality of the book by a 5 second riffle through the pages; if I don't notice large numbers of mathematical equations, I consider that the book is ludicrously worthless. In the case of Bible Codes, large numbers of equations would indicate Probably Serious But Still Worthless... )
If you're not part of the solution, you're part of the precipitate.
... to this. Instead of speculating, let's look at the primary source:
/.ers.
"After an Israeli research institute said it could break Europe's banking codes in less than a second, a initiative has been launched that could result in unbreakable codes."
Notice the would "could." Not "did," not "has," but "could." This means it hasn't happened yet.
"[Weizmann Institute] claims it has developed a hand-held device that can break the code in 12 microseconds."
Again: claims to have developed a device. Not "cracked a huge RSA key in a completely scientific test."
This offers no proof whatsoever, nor does it go into detail about what the "device" is, except to say that it uses a "mixture of quantum computing and special optical technology." Is this Twinkle? It being a full-fledged quantum computer would be *shocking*, since the most I've heard a quantum computer be able to handle is 5 qbits. Twinkle seems much more likely, and has less repercussions: the attack can't be extended to larger primes in the same amount of time.
What about the RSA implementation? It would be fairly easy to crack an insecure implementation of RSA.
Instead of rasing our blood pressue with speculation and conspiracy theories, let's wait until some facts come through. If this was really that important, it would be making waves in the crypto community instead of impressing
-- I can't think of anything witty to put here. Sorry.
You state that each extra bit in the key doubles the cracking time. That statement is true only if:
- the key is a symmetric key,
- brute force is used as the cracking method.
When cracking public key cryptosystems, the first assumption is just completely wrong, and the second assumption is often not the case. In this particular case you are completely wrong -- the best known factoring algorithm is the number field sieve, with calculation time O(exp(c (log n)^(1/3) (log log n)^(2/3)). This running time is considerably below the 2^n time that you state.If you leave out the section stating that complexity doubles with each bit, then the rest of your post actually makes good sense.
The "Bible Code" isn't cryptography. Well, not cryptography by mere mortals.
/. always strip leading spaces, even when us silly posters use 'pre' tags? Anyway...
Anyway, the idea behind the Bible Code is that the first five books of the Bible were dictated to Moses by God, as tradition says. If you take every Nth character (skipping spaces?) you will get words scattered among the garble. That's standard statistics and nobody sees any significance in it.
The "Bible Code" explores the shocking, *shocking*, discovery that if you look at *two* different periods you occasionally get words that intersect and are actually meaningful. E.g., you might see something like
H
K I L L S
T
L
E U R O P E
R
Except it would actually look like a scrabble board. Why does
Cue spooky music. The authors made a big point of the fact that they warned the late Israeli leader Rabin (?) that his name appeared with "assassinate", but the warnings were ignored. This is a "prediction" like that skeptics demand, right? Not really. The problems with the Bible Code are:
1) there are often multiple hits on the same concept. BC supporters claim that it's proof of humanity's free will, but many of use are skeptical.
2) there are a lot of garbage hits (e.g., something along the lines of "Hitler" and "peacemaker".) Oh yeah, that's free will again!
3) the same algorithms applied to modern texts produce similar amazing hits. I remember one of the skeptic magazines discussed the amazing prophecies encoded in Moby Dick.
In my view, one shared by many statisticians, the Bible Code is nothing more than proof that if you look hard enough you will eventually find a monkey wildly typing away at "Romeo and Julies". If you assume the first five books of the bible contain 2^16 symbols, then explore every pair of periods between 2 and 2^12 (so you'll get sentence of at least 16 characters), you'll have a sequence of (approximately)
2^16 * (2^12) * (2^12)/ 2 = 2^39
symbols, or on the order of one trillion symbols. No wonder it takes powerful computers weeks to find "meaningful" combinations. It's not because God hid His message well, it's that the message space is so huge.
For every complex problem there is an answer that is clear, simple, and wrong. -- H L Mencken
Well, it actually exists and it actually was started last Monday. However, several things on the site itself point to the fact that quantum computing has not been developed that can crack RSA 512.
The first bit of evidence is a quote that is on the front page of the site: "NASA are now planning on the basis that Quantum Computing will be mainstream within five years" --Dennis Bushill, Chief Scientist, Langley Research Centre of NASA
Now if the organization was founded in response to the actual development of a quantum computer, I don't think that that quote would be up there. It would say something like "Quantum computing is a reality, and we need to do something NOW"Additionally, it seems to me that the Sunday Times got a lot of its information from the site's news section which mentions the TWINKLE project. The TWINKLE project says that 512 bit encryption could be cracked (meaning if this thing were ever to be developed), and I think that that is where the Times figured it could write After an Israeli research institute said it could break Europe's banking codes in less than a second
After reading the site and rereading the article, it seems to me that the (mis?)information is a collection of three things.... a description of the *potential* power of a *to be built* quantum computer, a misread of the TWINKLE project, and a very creative interpretation of the European Institute of Quantum Computing's website.
Actually, if you read the article with this in mind it never actually *says* that they have the device or the encryption has been cracked. The only thing that it explicitly says this is: "It claims it has developed a hand-held device that can break the code in 12 microseconds." which more than likely is a misinterpration on the reporter's part of something the Weizmann Instutite mentioned than actual fact.
All in all, I think that the Sunday Times has done a horrible job of reporting this, and should be held responsible for the misinformation that they are spreading.