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?
The Sunday Times also broke the 'Hitler Diaries' as a news story. We definitely need independent corroboration, plus an explanation of how this particular piece of kit might do its job in 12us.
if you believe this I have the USS Enterprise parked in my garage, want it?
I'm a loner Dottie, a Rebel.
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
The problem is, they can break the codes that banks use to communicate with each other. They can break the codes ATMs use to communicate with the bank. You'd only be completely safe if your bank uses no electronics at all, just pencil and paper and a big metal vault.
---
END OF LINE
The big question seems to be this: could it be true? Or are the Israelis just pulling Europe's chain?
I say this: does it really matter? Since when has the presence of an actual threat over the presence of a perceived threat really meant much in international politics? If the Israelis can convince the world they can do it, without ever proving it, they've succeeded either way.
Personally, I think that better encryption for banking systems is a good thing. I don't want anyone messing with my money, and as stated in a previous post, I like internet banking. So, regardless of whether or not this is a hoax, it's causing an increased notice of cryptography issues. The more people that are aware of security and crypto problems in computing, the better.
Regardless, if it's not a hoax, imagine the implications of the quantum computing! Is it closer than we think?
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.
The Internet is only the latest place where cryptographic systems are being used to implement security; DES has been used for years to secure ATMs, and the present availability of DES-cracking schemes establishes that that is undercut by available technologies.
If "quantum computing" were to undercut Internet-based crypto schemes, it would undercut all of the presently constituted cryptographic distributed banking protocols, which would be Quite A Bad Thing, irrespective of your rejoicing or lack thereof...
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.
Just run your encrypted text into a heisenberg compensator which is cross connected into a infinite improbability generator. After this the message still looks the same but the universe will have to be decrypted in order to read it.
:)
Linux is only free if your time has no value. Windows is only free if you threaten to use Linux.
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 previous record for a privately held single machine on RSA 56 bit was 3 days with a 250,000$ machine. This comes out to, assuming technology is linearly scalable for money, 5.4e15$ (5,400,000,000,000,000$) (5.4 quadrillion dollars). Now, to scale this to 512 bit encryption, each extra bit is a power of 2 more possibilities, so this is 2^456 times the possibilies, resulting in a ~1e153$ machine (1,000,000,000,000,000,000,000,000,000,000,000,000 ,000,000,000,000,000,000,000,000,000,000 ,000,000,000,000,000,000,000,000,000,000,000,000,0 00,000,000,000,000,000,000,000,000,000,0 00,000,000,000,000,000,000$) (no name for this number) ;)
So, assuming they spent a billion dollars making this 1 chip, they're still getting a 1e144 times better buy on computing power than modern day computers. Excuse me while I cast "Disbelieve" on this article
Not to mention the physical impossibilities involved (such as, our favorite, the speed of light versus the smallest pathways we can make)
Honestly, if we had a chip with a 144 orders of magnitude better performance than today's computers, there is no way it would only be mentioned in an article on encryption. There would be hundreds of companies competing for the rights; the net would be flooded with places trying to get this chip to the market. 144 orders of magnitude! a computer that costs a penny being more powerful than the most powerful supercomputers in the world! think about this.
Don't believe what you read.
- Rei
The sotry doesn't seem very believable. The most recent reports were of quantum computers able to factor the number 4. Although breakthroughs happen, I doubt that any breakthrough of this magnitude happened. It's sort of like someone suddenly building a pentium III when everyone else was building 8088 or m68ks. In addition the lack of details make the story pretty suspect.
"When you sit with a nice girl for two hours, it seems like two minutes. When you sit on a hot stove for two minutes, it
Not exactly. Essentially, a quantum computer of 8 bits can do an operation on all of the possible variations, i.e. 0->255. To expand this, a 56 bit quantum computer could go through all the variations of a 56 bit key in one pass.
The real question is what sorts of lengths you can generate. Currently, I think they have constructed 5 bit quantum computers (anybody care to enlighten me?), but have yet to apporoach the 512 bit length needed for serious factorization.
IIRC, the TWINKLE device they mentioned here is a *theorectical* device that generates numbers that have a good chance being prime factors of the RSA key in question. A real (a.k.a. normal) computer then checks these numbers in hopes of stumbling accross the solution.
I think the Times has confused a paper with something that exists. After all, why would you tell banks you can crack their encryption when you could create some accounts for yourself? : )
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.
Ok first off, this is just a claim. One that is absolutely unverified. You tell me, why would they be so quiet about this thing? Why make a claim about being able to crack RSA, but not actually do it? Why crack RSA? There are so many larger things they could do which would garner more attention.
Secondly, this is just a claim, a second hand one at that. They never even stated that they "HAVE" cracked RSA, they said they could.
The word "could" can be interpreted many different ways. Could can be: They've created a working proof of concept, and this technology could crack RSA, they think, in X microseconds (2 billion dollars and 10 years later). And a few thousand variations thereof.
This whole story, or atleast the way its being interpreted just doesn't compute. So I repeat, I'll believe it when I see it. Care to wager that they won't have a single 512bit RSA actually cracked within a year with this technology (let alone in X seconds)?
>One way to solve NP problems in linear time is to break assumption number 3. This is how they used DNA to solve a (rather short) travelling salesman problem by creating a parallel environment.
The most interesting aspect to DNA computing is that it employs the physical/chemical properties of molecules to structure a problem solver.
But the only real advantage is that these problem solvers are small and cheap, so you can apply a great many of them to the problem.
The overall computation is still naive brute force. In fact, it's not even coordinated (across all the "computation units").
The only reason it's of interest is simply because you can create such a lot of very small computers each trying one step of a brute force search...they still have to do (on the order of) the same number of steps as a program on a single processor machine.
Now I don't care how small you think a molecule is, you'll need a bloody big test tube to search a 512-bit key space.
Defining the significance of NP-complete problems to lay-people often involves showing them how for very small problem sets *there aren't enough atoms in the universe* to solve it.
DNA computing has nothing what-so-ever to do with quantum computing.
"'It was the best of times, it was the blurst of times?' Stupid monkey!"
All roads lead to The Simpsons
-- This and all my posts are in the public domain. I am a lawyer. I am not your lawyer, and this is not legal advice.
It's no good. bad. Free kevin?! no, but really the crackers are good for the economy.
Joseph Elwell.