Slashdot Mirror
Time Running Out for Public Key Encryption
holy_calamity writes "Two research teams have independently made quantum computers that run the prime-number-factorising Shor's algorithm — a significant step towards breaking public key cryptography. Most of the article is sadly behind a pay-wall, but a blog post at the New Scientist site nicely explains how the algorithm works. From the blurb: 'The advent of quantum computers that can run a routine called Shor's algorithm could have profound consequences. It means the most dangerous threat posed by quantum computing - the ability to break the codes that protect our banking, business and e-commerce data - is now a step nearer reality. Adding to the worry is the fact that this feat has been performed by not one but two research groups, independently of each other. One team is led by Andrew White at the University of Queensland in Brisbane, Australia, and the other by Chao-Yang Lu of the University of Science and Technology of China, in Hefei.'"
it's a bit like nuclear weapons, in that you can pretty much "know" how a bomb works, but even if you had detailed plans, it's pretty much only governments who can build them.
of course, it's not such a good thing for governments to have unfettered access to all communications and banking details, but in general it won't be like your neighbours can spy on all of your banking transactions?
The Magic Words are Squeamish Ossifrage
The thing I worry about, is, regardless of which government or group is working on it is this, if this is what they're releasing to the public, how much farther ahead are they behind closed doors.
They mention this is a threat to public key cryptography, but what about private key (aka symmetric) encryption? How is that affected by quantum computers, and these algorithms?
Anthropic principle: We see the universe the way it is because if it were different we would not be here to see it.
Can quantum computers be used to create encryption keys that other quantum computers cannot solve in linear time? Perhaps computers will someday each include a QPU (quantum processing unit) that would be dedicated to performing such tasks.
*sigh*
This doesn't break "public-key cryptography". Even if you could build a Shor-factorization machine big enough to use against real-world keys (and that's a *big* if), it's only good against RSA. Elliptic-curve cryptosystems, for example, would be entirely unaffected. In general, the question of whether general-purpose quantum computers would break all public-key cryptography is a really hard one. It's equivalent to whether there are any trapdoor one-way functions which are in P but with inverses not in BQP. Even the existence of non-trapdoor one-way functions is still an open question; they would have to have inverses in , and proving that would also imply P != NP. All the existence of Shor's algorithm really shows about that problem is that there is at least one problem, integer factorization, which is in BQP but (probably) not in P.
Anyway, it's a long way from running Shor's algorithm to factor 15 to being able to factor a 4096-bit RSA key. Remember that because of the no-cloning theorem you can't build a flip-flop for qubits, so quantum circuits are all combinatorial logic. Applying Shor's algorithm to real-world RSA keys would require building a complete modular exponentiator combinatorially out of quantum logic gates, wide enough to deal with the biggest key sizes practical for anyone to use (and the cost of RSA encryption/decryption only scales linearly with the key size). We couldn't even build that out of regular non-quantum logic.
Know how many keys there are out there in use? Unless they have a method that can break keys in real time while messages are being sent they're screwed.
Take this example. Person A sends a message to person B. Every tenth character person A switches to a new key. Person B, who knows what keys are in use, but not the order for today, collects the message, and runs their key 'recipes' on it until one makes sense of the first ten blocks, being enough to identify which sequence of keys is in use. Person B then decrypts the whole message.
Anyone snooping on that may have to crack thousands of keys just to extract one coherent message. Good luck on that one.
On the other hand, the difficulty of building a quantum computer seems to be exponential with the number of bits, so maybe we'll be all right.
So far, the biggest QC is 12 bits or so. And some physicists think they never will get much bigger than that.
Factoring and discrete logs are codependent on each other being hard problems. Either one can solve the other. I'm not familiar enough with ECC to know if being able to solve regular discrete logs necessary breaks it; but if so, then factoring breaks it too.
Cheap storage will eventually destroy any kind of crypto/anti-crypto technology.
What are the new DVD formats getting? 50GB of data RW? Will options up to 250GB or so of RW storage?
How much information do you really, really need to hide, anyway? Maybe a couple of megabytes of financial-related data per day? A one-time pad on a DVD should provide you with centuries of totally secure communications.
So you sign up for your bank account. The bank snail mails you a 10GB random noise memory stick. You add it to your 10TB secure random storage system and you and the bank can talk for the rest of your life without anybody else being able to listen in.
DES 56 has been broken, brute forced. It uses a single 56 bit key to encrypt data.
You get the key, you get the data.
3DES 168 encryption is still, in my opinion, unbreakable. The people who laugh at that statement need to read this.
3DES uses TWO Separate 56 bit DES keys. The first key is used to encrypt the data, just like standard DES. Then the second key is used to re-encrypt the data. Finally the first key is used again to encrypt the data yet a third time. As you can see, it isn't simply using a 168 bit key.
You now have your data triple-encrypted, thereby giving you 168bit encryption.
Brute forcing a key is simply trying every possible numeric combination until you land upon the key that unlocks your data. Even if you guessed correctly the first DES56 key on the very first try, you wouldn't know it because the data you're looking at is still encrypted garbage. With 3DES, you need to guess the first key, then after every single guess, brute force the second key, then try the first key AGAIN and see if you come back with readable data.
And to further confound things, the DES 168 bit standard does not specify whether the second key is used to encrypt or decrypt the data on the second pass. If you have data, encrypt it once, and look at it, you have unreadable garbage. If you then decrypt it using the wrong key, you will end up with different-looking garbage. So, the DES 168 standard only states that you have two keys, and they be used to Encrypt, Encrypt, Encrypt - OR - to Encrypt, Decrypt, Encrypt, but it leaves that choice up to the vendor.
SO, to summarize, you can have:
DES 168 EEE
DES 168 EDE
Now, back to my brute forcing, after I guess the first key, then immediately try to guess the second key. And with that 2nd key, do I try encrypting the data again or decrypting it before I try the first key again to see if I wind up with readable data?
This EEE vs. EDE was infuriating as an administrator, as the VPN vendors would each implement their own method of EDE, or EEE, or DED, or DDD, and this is why you could have a Cisco VPN concentrator using 100% standards compliant DES168 encryption, but you could NOT connect to it using the Nortel VPN client, or the Microsoft client, or any other client besides Cisco's client.
It was the LOOSE standards that obsoleted DES168, not its relative key-length weakness.
I seriously doubt that DES168 could ever be broken.
Good security is based upon reality and common sense. Common sense is a function of having common knowledge.
It's been a while since I looked at Shor's algorithm, but I was under the impression that you needed a quantum computer with a number of qbits greater than or equal to the key length in order to get that kind of scalability with the algorithm. Due to entanglement problems, building a quantum computer with a sufficiently large capacity to run Shor's algorithm on keys of a useful length is still very hard. We've had quantum computers that can use it to quickly factorise trivial keys for a while now, but making bigger ones is very hard.
I am TheRaven on Soylent News
I agree, this is normally the case. But Public key had turned into a hammer and everything looks like a nail. Meaning it's over used and not the best approach for many applications. I guess it's great if your some deep pocket government with cracking machines set up for it.
Someone you need a shared secret to be passed the first time. If there is alway someone listening it will not work.
But I am assuming your moving around and no one can intercept all conversation, but more like the case of a Credit card where or SSL
where someone can intercept a a single transaction, record it and giving enough time crack it. With credit cards this time = 0 since it's in clear text 16 digits.
But once you have your shared "key" I don't like to call it a key, but pad or shared secret, and your mobile (like in wifi/bluetooth) no short term transaction interception will give away any information giving any computing power unlike SSL.
You have to read my patent, but I am using it in combination with SSL/SSH Public key encryption.
But this is just for transmission, not storage, it's also layered with onetime pad and one use numbers.
I also had an idea for public pad encryption using really really large pads, based on the premise that memory is more of a bottleneck then computing power.
I am always doing that which I can not do, in order that I may learn how to do it. - Pablo Picasso
So, just like with classic attacks, can't we just increase the keyspace to stay ahead of the quantum curve indefinately? The only real problem I see is that passwords will eventually be obsolete, but that's essentially the case already. Passphrases will help to some extent, but again, it's just a matter of time before the computational ability outstrips the capacity to remember (and patience to enter) a sufficiently long and/or incoherent passphrase.
https://www.eff.org/https-everywhere
See Shor's paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer