Slashdot Mirror
Ask Slashdot: Post-Quantum Asymmetric Key Exchange?
First time accepted submitter LeDopore writes "Quantum computers might be coming. I'd estimate that there's a 10% chance RSA will be useless within 20 years. Whatever the odds, some of the data we send over ssh and ssl today should remain private for a century, and we simply can't guarantee secrecy anymore using the algorithms with which we have become complacent. Are there any alternatives to RSA and ECC that are trustworthy and properly implemented? Why is everyone still happy with SSH and RSA with the specter of a quantum menace lurking just around the corner?"
ECC is AFAIK theoretically vulnerable (i.e. while there aren't KNOWN quantum gate implementations of ECC, there are no good reasons to think it is unfeasible).
McEliece and the Lattice-based stuff are promising, they just hadn't be as inspected as RSA yet...
I think the author's point is that data sent today could be sniffed, stored, and cracked in 20 years. Some of that data may still be sensitive in 20 years, so we need to switch now.
Get your most closely kept personal thought: .doc with a password lock. .rar with extraction precluded .rar because so far they ain’t impressed. .pgp and print the hex of it out,
put it in the Word
Stock it deep in the
by the ludicrous length and the strength of a reputedly
dictionary-attack-proof string of characters
(this, imperative to thwart all the disparagers
of privacy: the NSA and Homeland S).
You better PGP the
You better take the
scan that into a TIFF. Then, if you seek redoubt
for your data, scramble up the order of the pixels
with a one-time pad that describes the fun time had by the thick-soled-
boot-wearing stomper who danced to produce random
claptrap, all the intervals in between which, set in tandem
with the stomps themselves, begat a seed of math unguessable.
Ain’t no complaint about this cipher that’s redressable!
Best of all, your secret: nothing extant could extract it.
By 2025 a children’s Speak & Spell could crack it.
You can’t hide secrets from the future with math.
You can try, but I bet that in the future they laugh
at the half-assed schemes and algorithms amassed
to enforce cryptographs in the past.
And future people do not give a damn about your shopping,
your Visa number SSL’d to Cherry-Popping
Hot Grampa Action websites that you visit,
nor password-protected partitions, no matter how illicit.
And this, it would seem, is your saving grace:
the amazing haste of people to forget your name, your face,
your litanous* list of indefensible indiscretions.
In fact, the only way that you could pray to make impression
on the era ahead is if, instead of being notable,
you make the data describing you undecodable
for script kiddies sifting in that relic called the internet
(seeking latches on treasure chests that they could wreck in seconds but didn’t yet
get a chance to cue up for disassembly)
to discover and crack the cover like a crème brûlée.
They’ll glance you over, I guess, and then for a bare moment
you’ll persist to exist; almost seems like you’re there, don’t it?
But you’re not. You’re here. Your name will fade as Front’s will,
‘less in the future they don’t know our cryptovariables still.
Now it’s an Enigma machine, a code yelled out at top volume
through a tin can with a thin string, and that ain’t all you
do to broadcast cleartext of your intentions.
Send an email to the government pledging your abstention
from vote fraud this time (next time: can’t promise).
See you don’t get a visit from the department of piranhas.
Be honest; you ain’t hacking those. It’d be too easy,
setting up the next president, pretending that you were through freezing
when you’re nothing but warming up: ‘to do’ list in your diary
(better keep for a long time — and the long time better be tiring
to the distribution of electrical brains
that are guessing every unsalted hash that ever came).
They got alien technology to make the rainbow tables with,
then in an afternoon of glancing at ‘em, secrets don’t resist
the loving coax of the mathematical calculation,
heart of your mystery sent free-fall into palpitations.
Computron will rise up in the dawn, a free agent.
Nobody knows the future now; gonna find out — be patient.
I for one would be interested to understand the grounds of your estimation ? In terms of key exchange you could also estimate quantum entanglement may replace the requirement for intercept-able information exchanges. If the estimate of the latter is greater than the former then I estimate based on that conjecture we will be fine and broadband is dead :-) Oh and long live time travel at the same time!
This 1978 crypto is supposed to be safe against quantum computers: http://www.technologyreview.com/blog/arxiv/25629/ (if that's the specific angle you're worried about). The downside is the key management because the keys have to be really really long (i.e. 20,000+ characters vs having a memorable passowrd or passphrase that you'd be able to use today).
Why is everyone still happy with SSH and RSA with the specter of a quantum menace lurking just around the corner?
Because the vast majority of us don't need to keep our data secure for the next century... Even for some of the most nefarious uses of crypto, merely lasting long enough to exceed the statute of limitations will suffice, and I'd put that as a serious fringe case.
Personally, I only use encryption for my financial documents and to make myself a more difficult target in the present (whether to identity thieves or the government or to my ISP trying to control my traffic). For the former, I consider basic access control (ie, keep it offline) as the first line of defense, and the encryption as a fallback; for the latter, if it takes even five minutes more effort than merely watching the wire, the crypto has done its job.
Even corporations don't tend to care about a scale longer than five years out (and that, only when they can even see past the next quarter)... Which leaves really only governments caring about how soon someone like Assange can find a way to embarrass the talking heads.
20 years is too long to care true; but I see two points to his argument.
First, it's going to take time to roll out a replacement. How fresh does the data have to be for you to consider it worrying? If it takes 5 years to develop a consumer grade replacement and 5 years for it to become ubiquitous online all the sudden data recorded at the end of that window is only 10 years old at the hypothetical 20 year mark. Of course, that just raises the question, is there any asymmetric key encryption algorithm that can't be cracked with quantum computers?
Second, data that is a bit more sensitive than banking information is sent using encryption that is substantially similar. Do governments really want to have potentially classified data from 20 years ago suddenly available to their allies and enemies?
Easy, one time pad to encrypt your one time pad exchange.
In previous discussions it has been pointed out that not all encryption algorithms are susceptible to quantum computers. If I remember right (I am sure someone has a reference that I don't) it only effects RSA and others that rely on the hardness of factoring discrete logarithms.
Anyway...only reference I can find, from wikipedia (http://en.wikipedia.org/wiki/Quantum_computers#Potential ):
"I opened my eyes, and everything went dark again"
To elaborate asymmetric key exchange involves passing a key in the clear to setup the secure channel. How does a one-time pad help you securely exchange that key in the clear? Or did you just make your idiotic post hoping to get modded up for trying to sound smarter than you are?
Well the person is an idiot. His estimation of 20 years is laughably naive.
My response to this statement is a quantum superposition of two thoughts:
A. I agree. A 20 year estimate is ludicrous. It's far too much time.
B. I agree. A 20 year estimate is ridiculous. It's far too short.
Quantum entanglement is being studied hard by bright people, who are publishing. I think that the technology is a ways off, and I expect that there are some limitations on entanglement. Being able to collapse 2^2048 super-positions seems a bit preposterous to me. I could be horribly wrong, but I have a feeling that there are going to be limits on how many "entanglements" can be made by a given subatomic particle.
I'm a bit more worried about someone who finally get's a eureka on factoring large numbers. Then the genie is out of the bottle, and no-one knows it. Heck it might already be cracked, and held as a state secret, only makes sense.
What would you do if you had a factoring algorithm that could factor a RSA number as fast as the generator could make them?
What would be the fallout?
Why is everyone still happy with SSH and RSA with the specter of a quantum menace lurking just around the corner?"
Because the sky isn't falling, chicken little?
I use SSH to keep someone from snooping my password, or hijacking my session to take over my servers.
I'm not so worried that someone is recording all of my SSH streams for future use in the hope that Quantum Computing becomes a reality and they can decode the stream and see that I typed "sudo service apache2 restart".
I wouldn't be surprised if in 20 years we can use a quantum computer to factor a number greater than 100. But that only requires a handful of functioning qbits. It is unlikely that the technology will be that advanced. There are however non-factoring based cryptosystems that are not as of yet known to be vulnerable to quantum computing. Unfortunately, we're a long way from proving that. The claim that there exists an encryption system which is not breakable by a quantum computer is a claim which is much harder than P != NP (you are in fact making a claim that us substantially stronger than NP not being a subset of BQP which many people aren't even sure they believe). In fact, even the existence of encryption secure against classical computers requires believing claims which imply P != NP. Moreover, if one starts implementing other encryption systems that aren't as widely studied as things like RSA one opens up the danger that those encryption systems have their own flaws as well.Also, at a practical level, there's very likely not going to be someone who is going to be recording all your RSS sessions on the offchance that they can decrypt them thirty years down the line. But if you really care then use one variant of elliptic curve cryptography. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography. ECC systems are well-studied and have implementations. The people who study these sorts of things seem to think that ECC is one of the systems that is more likely to not be unable breakable by quantum systems.
Clearly you know more than you're letting on since that's the exact command I ran over SSH on my server an hour ago!
I guess SSH is insecure after all, since you were able to break it so easily and post a line from my super secret command line session on Slashdot.
This article should never have been posted. There's no facts to respond to. Linking to a wikipedia article that talks about the possibility of Quantum computing is not a topic for discussion. Where does the estimate of 20 years come from? What will Quantum computing be able to do in this imagined 20 years? How much will it cost?
Unless the submitter can give real answers to the above question, based on facts and not idle speculation, there's nothing to talk about.
AccountKiller
It's one time pads, all the way down!
You should keep in mind that although theoretically there may be efficient quantum algorithms for a variety of problems on which cryptographic schemes are based, in practice, the only one which has been found is factoring. So, yeah, RSA will become toast if we can get the number of qubits in a quantum computer up into the neighborhood of RSA key lengths (1024, 2048, 4096). But, exceedingly few of the other major cryptographic systems rely on factoring being hard. So, for example, Diffe-Hellman or El Gamal (both integer and elliptic curve versions for both) will probably not be appreciably easier to crack. So, there doesn't seem to be any serious reason to be worried about public key cryptography, just RSA. So changes to SSH are pretty straight-forward.
As for why people aren't worrying about it, my guess would be that most people don't follow quantum computing, and the few which do may have reason to wonder if we will ever actually reach the 1024 qubit size in a functioning quantum computer. A few years ago, I would've told people not to worry about it because I was following the state of the art and it was around 5 qubits and research had shown that under current models, you needed 9 qubits of output to reliably output 1 normal bit (if my memory is correct). So, we weren't even one 0.1% of the way to cracking RSA. These days, the number of qubits is higher, but it's still not clear how long it will be until we can actually functionally factor a 1024 bit number.
because most people estimate that the cost of putting a software of even hardware-based keylogger is cheaper today than quantum computing will be even when matures. ie, the powers that be, that need to keep tabs on you, already can keep tabs on you.
Any guest worker system is indistinguishable from indentured servitude.
Whatever the odds, some of the data we send over ssh and ssl today should remain private for a century, and we simply can't guarantee secrecy anymore using the algorithms with which we have become complacent.
If I may, I would like to quote the MC Frontalot song, "Secrets From The Future":
You can't hide secrets from the future
with math, you can try, but I'll bet that in the future
they laugh at the half-assed schemes and algorithms
amassed to enforce cryptographs in the past.
The rest of the song does a pretty good job of explaining exactly how absurd the entire concept of keeping data private, long-term (like, say, a century as suggested, or even twenty years when RSA is theorized to fall), entirely using encryption algorithms. Brings up points like how nobody's going to care about things like your shopping habits (as embarrassing as they may be), credit card transactions from cards expired twenty years previous, sensitive SSH streams decades old, etc. And that it's a moot point anyway, as it's impossible to predict technology out that far, so it's more than a bit futile to count on math to protect things on a time scale like that.
Best of all, your secret: nothing extant could extract it
By 2025 a children's Speak & Spell could crack it.
Demanding constant attention will only lead to attention.
Your only option for keeping data secret for 100 years is use one-time pad of really good, truly random data and keep it secure until the instant you no longer need to retrieve the data, then completely destroy it. Once it's completely destroyed, then it's even safe from two guys with blowtorches going to work on your knees. On the other hand, now you don't have anything you can say to save your knees! So it may be a matter of defining priorities for you.
If somebody with massive resources is seriously committed to getting a particular piece of data, they are probably going to be able to get it. Yes, I could save network captures of SSL traffic and decrypt it someday to get some credit card numbers, but it's a whole lot easier just to steal your wallet and it's a whole lot more efficient to run a social engineering scheme some credit card processor and steal 100,000+ at once.
Minor correction: the so called one time pad is easily proven to be uncrackable by any method. The only problem with it, of course, is the key exchange. (The key is as long as the message, and needs to be securely transferred beforehand.)
Maybe I'm just paranoid, but I pretty much assume that every algorithm that we have now could well be effectively useless in 20 years. And I would never presume to think any of them even has a chance of lasting 100 years, or even close to that.
Computers will get faster. Weakness will be found in algorithms. Any other number of things that no can predict might happen. It would be silly to assume things encrypted today, left untouched, would be safe in 20 years and completely naive to have even a sliver of hope they'd be safe in 100, quantum computers or not.
~Warning!~ The above is encrypted using rot676!
Tis obvious. There must be one one time pad to rule them all.
"Lack of speed can be overcome. In the worst case by patience." --Znork
They not being as inspected as RSA is a rational reason for not using them, and not using them is a rational reason for not inspecting them. Thus, I forsee that they stay less inspected than the RSA until we discover some importan weakness on RSA, then that fact won't matter anymore. Notice that I'm not complaining about that, this is a reasonable way of handling things, and nobody is getting hurt.
Now, to answer the original question. People are ignoring quantum computing because it is not even on the horizon. Entangling 11 bits (we are here now, aren't we?) is hard, 12 is way harder, and your breathing space gets exponentialy smaller when the number of bits increase. So, when people finally entangle 127 bits, what means that we are roughtly halfway through a quantum computer that can break the currently outdated 128 bits RSA, wake me up. By them I'll be willing to consider those computers a threat.
Rethinking email
I don't think the attacker is so much interested in the "sudo service apache2 restart" command but rather the response to the password prompt immediately following...
If he can break the RSA key exchange to get to the symmetric key encrypting my session, he can already log in as me, he doesn't need the password. But unless he gets his quantum computer within the next 90 days, I'll have already changed the password.
You admit you use sudo instead of logging as root. Wise move. Nobody believes it, but wise move.
---- MISSING MISCELLANEOUS DATA SEGMENT --- [sigdash] trolololol
Lockheed installed a 128bit quantum computer this year
http://www.forbes.com/sites/alexknapp/2011/10/31/lockheed-martin-installs-quantum-computer/
I have no idea of the specifics, but it sounds as if they have a working version.
Different sort of quantum computer, it can't do general computing or schors algorithm, it's more like a quantum calculator, relegated to very specific statistical calculations rather than generic 3 bit computing.
Posting as AC, huh? Are you an NTRU Cryptosystems employee?
Here's a paper that surveys a number of quantum resistant cryptosystems. "NTRUEncrypt has also been found to be vulnerable to chosen ciphertext attacks based on decryption failuress [18, 21, 31, 38], but a padding scheme [30], which has provable security against these attacks, has been developed." "A comparatively greater number of problems have been found in NTRU-based signature schemes." "In 2006, it was shown by Nguyen that the unperturbed NTRUSign could be broken given only 400 signed messages [42]."
I'd say that the jury is still out...
For a company to consider commercial secrets "secure", it should be aiming for around 50 years security, which is why Serpent and MARS were aiming for that sort of level during the AES contest. Government records, including census data, are also covered by a 50 year rule and should again be encrypted to that kind of standard. Highly classified material is usually put under a 100 year rule, assuming it is to ever be released at all. I'd consider a century to be adequate for most national secrets, there really can't be anything so perilous that would actually warrant more. But if you don't think 100 is enough, and obviously some governments do not, then you've got to encrypt accordingly.
Ok, so whilst most of us aren't doing anything super-secret, if even basic commercial and domestic information is supposed to be kept confidential for 50 years then no. 20 years is not too long a time frame to care. If 50 years is the law, then 50 years is the absolute minimum timeframe worth considering. (Remember, people in offices will use what's out there. So if 50 years is a legal minimum for them, 50 years has to be a practical minimum for us because we're the ones who ultimately decide what offices have available to use.)
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
There is no known attack on ECC using quantum computers.
This should not have been modded up, because it is blatantly false. The security of ECC relies on the presumed hardness of the discrete logarithm problem (in elliptic curves over finite fields). But Shor's algorithm can solve the discrete logarithm problem in ANY finite group (assuming you have an efficient way of operating on the group elements).
I double-checked things after I wrote this, and I'm wrong. I didn't realize that Shor's algorithm could be used to solve discrete logarithm problems. So, the ECC versions of things are not affected, but the integer versions of El Gamal and Diffe-Hellman are.
ECC is still the discrete logarithm problem, just applied to a group other than integers mod another integer.
"Screw Sun, cross-platform will never work. Let's move on and steal the Java language." - Visual J++ Product Manager
A one time pad allows you to encrypt one bit of plaintext per bit of key. If you use that plaintext to communicate a new key, you gain precisely nothing.
You're not quite following what I am suggesting, which is along the following:
The only big issue with the above is when the message being sent is larger than the message received. However, that could be resolved by buffering the old messages and only tossing away the data as it is used for the one-time pad, so if the message is sufficiently larger than the few messages after it it may be a few messages before those messages are used in the one-time pad. Of course, you will have a problem if there is not enough data to properly apply a one-time pad to the larger message, but that could be managed by the protocol - e.g. generate a message that sends back a dummy message to get additional data for more one-time pads to have sufficient information. This also means that any two parties would be essentially making new key-exchanges with each message set sent/received.
Now of course, the main security issue is that the entire one-time pad is in the data stream itself. Intercept the data stream and you could have sufficient information to decode it if you knew how the protocol worked and buffered enough of it to decode the one-time pads. Depending on the use, it may be just as secure as a true one-time pad if all messages were equally sized so that you had to get the initial message to really be able to decode anything.
So, I am not saying it is not without fault but that depending on use, it may be good enough.
Now, to your comment, you don't really seem to understand a true one-time pad. The algorithm is rather simple - is just an XOR of bytes over the message. The hard part is the data source. In a true one-time pad all parties wishing to communicate have access to the same exact data source and know where the other is going to operate within that data source to encode the information. This is truly secure - unbreakable - so long as you do not repeat over the same data set.
That is, a one-time pad is secure as long as the source for the one-time pad is never reused. Think of a file of random data. You share the file with the other party and you both exchange data using a known offset into the file. If you both start at the start of the file then as long as you never wrap around to the start of the file you have a secure means of communication that cannot be broken. If you start to wrap around the file, so you start repeating the use of the data used for the one-time pad then the source information can eventually be decoded from the data stream by pattern recognition techniques thus defeating the security of the one-time pad. This is resolved by simply using a file that is large enough to never be wrapped by the data you communicate. Such methods are used by the NSA and CIA and others to securely communicate information with a guarantee that no-one else can intercept and decode the data.
Now back to my proposal - the source of the one-time pad becomes the data stream itself. This has a slight fault in that the source is available, but if properly utilized may be just as secure. The primary vulnerability is receipt of the first message since the second message would use it to pad itself when responding.
Also, you don't typically use a one-time pad to communicate something to setup a key-exchange for Diffie-Hellman or RSA. They have their own protocol already for doing the key exchange. In the case of Diffie-Hellman, you send the public information of your key and get back the public information for the other party's key. You then both use your own private key with the o
Truth is like the sun. You can shut it out for a time, but it ain't goin' away. - Elvis Presley (source: imdb.com)
is there any asymmetric key encryption algorithm that can't be cracked with quantum computers?
Yes and no.
The answer won't collapse until we open the quantum computer box and look inside.
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.