×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Ask Slashdot: Post-Quantum Asymmetric Key Exchange?

timothy posted more than 2 years ago | from the tin-can-no-string dept.

Communications 262

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?"

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

262 comments

I use analingus-based key exchange (-1, Troll)

Anonymous Coward | more than 2 years ago | (#38014252)

It happened when I was 19, a guy I met a guy in my College library took to his dorm and turned me around having pulled pants down. I figured he wanted to eat me doggystyle, when he stuck his tongue up my anus...

7 years later and more than 30 partners of all shades; half of whom have performed analingus on me, has me thinking its perhaps the new cunnilingus and 10 years time it will be part of foreplay.

PS: I return the favour.

Your thoughts.

Fine. You find an asymmetric primitive (1)

Anonymous Coward | more than 2 years ago | (#38014258)

that isn't vulnerable to Shor's algorithm and get back to us. (Is ECC even vulnerable? I know RSA and Diffie-Hellman are...)

Re:Fine. You find an asymmetric primitive (5, Informative)

Anonymous Coward | more than 2 years ago | (#38014288)

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...

Re:Fine. You find an asymmetric primitive (0)

Anonymous Coward | more than 2 years ago | (#38014590)

I'm the same anonymous coward who posted the FP. Somebody with mod points please mod this other anonymous coward up?

Re:Fine. You find an asymmetric primitive (-1, Offtopic)

Anonymous Coward | more than 2 years ago | (#38014624)

No, *I* am the same anonymous coward who posted the FP. Don't listen to the other one, he is lying! Don't mod it up!

Re:Fine. You find an asymmetric primitive (2)

marcosdumay (620877) | more than 2 years ago | (#38015036)

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.

Sky isn't falling (1)

Desler (1608317) | more than 2 years ago | (#38014266)

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?

Re:Sky isn't falling (4, Insightful)

hawguy (1600213) | more than 2 years ago | (#38014534)

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".

Re:Sky isn't falling (5, Funny)

Fallingcow (213461) | more than 2 years ago | (#38014612)

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".

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.

Re:Sky isn't falling (1)

Java Pimp (98454) | more than 2 years ago | (#38015006)

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...

Re:Sky isn't falling (5, Insightful)

hawguy (1600213) | more than 2 years ago | (#38015082)

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.

Re:Sky isn't falling (1)

shadowrat (1069614) | more than 2 years ago | (#38014660)

yeah. i've always felt ssh and rsa are pretty good against the current imaginary state of quantum computers.

There's one uncrackable method (1)

Anonymous Coward | more than 2 years ago | (#38014270)

One Time Pad.

Re:There's one uncrackable method (1)

GameboyRMH (1153867) | more than 2 years ago | (#38014290)

This doesn't help with one of the most common uses of asymmetric keys, which is secure initial key exchange...

Re:There's one uncrackable method (2)

nomadic (141991) | more than 2 years ago | (#38014410)

Easy, one time pad to encrypt your one time pad exchange.

Re:There's one uncrackable method (0)

Anonymous Coward | more than 2 years ago | (#38014578)

But what about the first key ? shouldn't we encrypt it as well with a one time pad ?

Re:There's one uncrackable method (0)

Anonymous Coward | more than 2 years ago | (#38014632)

Nah, after the first two One Time Pads, it's turtles all the way down.

Re:There's one uncrackable method (1)

Anonymous Coward | more than 2 years ago | (#38015176)

yo dawg, i heard you like unbreakable encryption, so we put a one-time pad in your one-time pad so you can encrypt while you encrypt.

Re:There's one uncrackable method (0)

Anonymous Coward | more than 2 years ago | (#38014636)

You take advantage of SSH today to send a 100 Terabyte one time pad key. duh

Re:There's one uncrackable method (1)

Opportunist (166417) | more than 2 years ago | (#38014682)

You forgot data retention. Didn't you hear? They record everything you send through the net. Now we know why.

Re:There's one uncrackable method (1)

TemporalBeing (803363) | more than 2 years ago | (#38015130)

This doesn't help with one of the most common uses of asymmetric keys, which is secure initial key exchange...

You could probably build the one-time pad into the initial message and then use the data stream itself to continue the one-time pad on. It does leave you vulnerable to anyone that receives that initial message, but would probably be otherwise unbreakable unless you start repeating a lot of data in the data stream - but then, even a true one time pad would then be vulnerable too.

Vulnerable in 20 years (1)

TaoPhoenix (980487) | more than 2 years ago | (#38014278)

Without overly snarking, 20 years is too long a time frame to care.

When we get down to 3 years take a "miniscule amount" of $100,000 (in "then dollars") and hire 30 mathematicians/cryptos/NSA types + 1 Slashdot Geek/1 Local Prodigy/2 Hotshots of the month/1 Sales guy/1 admin/1 Hotel Lodging rep and tell them to get cracking for 3 months. Problem solved.

Re:Vulnerable in 20 years (4, Informative)

steevven1 (1045978) | more than 2 years ago | (#38014312)

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.

Re:Vulnerable in 20 years (-1, Troll)

Desler (1608317) | more than 2 years ago | (#38014342)

Well the person is an idiot. His estimation of 20 years is laughably naive.

Re:Vulnerable in 20 years (5, Insightful)

Waffle Iron (339739) | more than 2 years ago | (#38014476)

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.

Re:Vulnerable in 20 years (1)

postbigbang (761081) | more than 2 years ago | (#38014858)

More practically, it presupposes that his traffic is being captured. To capture 100% of the traffic of the Internet exceeds all forms of storage.

Let's say that his traffic is being targeted right now, and 100% of his currently secret SSL/SSH traffic is being captured and madly attacked. The poster supposes that he/she wants 100yrs of privacy. The poster is a three letter agency, or similar. That agency can pay for its own problems and I suspect that there are back doors to RSA, and most forms of encryption today. Twenty years? Few secrets need to be kept twenty years. The post is too nebulous to even begin to answer-- if it were real-- and I suspect it's not.

Re:Vulnerable in 20 years (2)

MozeeToby (1163751) | more than 2 years ago | (#38014408)

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?

Re:Vulnerable in 20 years (0)

Anonymous Coward | more than 2 years ago | (#38014464)

You need to add a few 000's to that. One NSA type will cost you more that $100k.

It's not that bad (1)

Anonymous Coward | more than 2 years ago | (#38014292)

Quantum is still in it's infancy, and it still has a lot of moore's law to catch up on. There are quantum safe (at least so far) cryptomethods, but the danger of untested and poorly understood crypto is larger than the danger of quantum computers to regular crypto.

One Time Pads (0)

TheMiddleRoad (1153113) | more than 2 years ago | (#38014296)

Last I checked, they're still secure.

There's also security through obscurity. If they don't know the math you're doing, it can be hard for them to analyze its flaws.

Re:One Time Pads (1)

Desler (1608317) | more than 2 years ago | (#38014328)

And how is a one-time pad going to help for asymmetric key exchange?

Re:One Time Pads (1)

TheMiddleRoad (1153113) | more than 2 years ago | (#38014574)

And how is a one-time pad going to help for asymmetric key exchange?

You just might have to go symmetric if you care that much about your data.

Re:One Time Pads (3, Insightful)

Desler (1608317) | more than 2 years ago | (#38014472)

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?

Re:One Time Pads (1)

Surt (22457) | more than 2 years ago | (#38014732)

Well, if you have a one time pad, you don't have to exchange your key in the clear, for one thing.

Re:One Time Pads (1)

adonoman (624929) | more than 2 years ago | (#38015026)

No, but if you have a secure channel to get the one time pad to both parties, why not just use that to transmit the data you want to send. And if you don't have a secure channel to get the one time pad to both parties, then it becomes useless.

The only time that a one-time pad works, is if you have a secure channel at one point in time, but need to send the data at a later time over an unsecure channel. So if you want to start going to your bank in person once a month to pick up a DVD worth of random data for the convenience of being able to do your online banking, then it might be possible.

Re:One Time Pads (1)

TheMiddleRoad (1153113) | more than 2 years ago | (#38014744)

I'm saying that you don't swap keys in the clear if your data is so important that it needs to be secure 20 years from now. Clear?

Quantum computer = circumvention device (0)

Anonymous Coward | more than 2 years ago | (#38014302)

Since DRM is based on encryption, devices that break encryption are TPM-circumvention devices. Canada is about to outlaw them as well in proposed Bill C-11 (even in non-infringing situations, and even when the copyright expired (after hell froze over).

Oblig. (2, Insightful)

MachDelta (704883) | more than 2 years ago | (#38014338)

Get your most closely kept personal thought:
put it in the Word .doc with a password lock.
Stock it deep in the .rar with extraction precluded
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 .rar because so far they ain’t impressed.
You better take the .pgp and print the hex of it out,
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.

Re:Oblig. (0)

Anonymous Coward | more than 2 years ago | (#38014434)

What's with the short margins? Makes you sound crazy.

Re:Oblig. (0)

Anonymous Coward | more than 2 years ago | (#38014592)

What's with the short margins? Makes you sound crazy.

They're lyrics from MC Frontalot [frontalot.com] . The track is Secrets from the Future [frontalot.com] , and was "[c]omposed at a hacker convention, while Front muttered curses at himself for having just logged into three different chat accounts across the 'free' wireless."

Estimate on what grounds ? (2)

dirvine (1008915) | more than 2 years ago | (#38014344)

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!

Re:Estimate on what grounds ? (1)

afabbro (33948) | more than 2 years ago | (#38014514)

Indeed. After reading "I'd estimate that there's a 10% chance RSA will be useless within 20 years" I knew the poster was just a kid who'd read Crypto-Gram for the first time and wanted to sound crypto-l33t.

2 vs. 3 (1)

Anonymous Coward | more than 2 years ago | (#38014358)

The article mentions two ways to overcome the problem of QC breaking traditional cryptography, but IIRC there are three ways:

1. Develop "classical" algorithms that are immune to QC, which is what the article mainly refers to
2. Develop crypto algorithms that require QC to execute with viable performance and would require at least "QC^2" to be broken, which we don't assume to exist (not mentioned by the article)
3. Quantum cryptography, which the article mentions but which is totally different and required specialized communication hardware (non-switched optical fibers or a similar medium that doesn't interact with the signal at all)

ECC is not voulerable (1, Informative)

Anonymous Coward | more than 2 years ago | (#38014370)

There is no known attack on ECC using quantum computers.

If you assume it might be broken because there is no proove that it's secure, you might assume the same fron any other method - there is no known method to proove that some algorithm is _not_ attackable by quantum computers.

(Of course, knowing the "new" slashdot, AC comments are never moderated +1, so noone will read this).

(And, hey, my captcha is 'druggist'...)

Re:ECC is not voulerable (2)

n01 (693310) | more than 2 years ago | (#38014912)

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.)

what's old is new again (4, Informative)

Nightshade (37114) | more than 2 years ago | (#38014388)

This 1978 crypto is supposed to be safe against quantum computers: http://www.technologyreview.com/blog/arxiv/25629/ [technologyreview.com] (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).

Non-issue to 99.9% of us (4, Insightful)

pla (258480) | more than 2 years ago | (#38014392)

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.

Re:Non-issue to 99.9% of us (2)

bberens (965711) | more than 2 years ago | (#38014650)

I record all of your encrypted transactions. In 20 years I will gain access to your 20 year old bank statements. Muahahaha!

Re:Non-issue to 99.9% of us (1)

mrxak (727974) | more than 2 years ago | (#38015140)

Plus all your current transactions, if you never changed your password on a line I wasn't watching.

This is actually very easy... (-1)

Anonymous Coward | more than 2 years ago | (#38014438)

You can do a diffie-hellman key exchange to get a one-time pad. Of course, DH does not solve the authentication - but since it's still secure, you can use RSA or ECC.

So:
- Open a channel with RSA or ECC to do the authentication
- Exchange a OTP using diffie-hellman (or an AES-256 key).

Done.

Re:This is actually very easy... (0)

Anonymous Coward | more than 2 years ago | (#38014798)

Assume hypothetically that every packet of your transmission has been recorded for future decryption when technology has advanced sufficiently.
Can you confirm or deny that your method is safe if, say, quantum or otherwise fast solutions have been discovered that solve both the factorization problem and discrete logarithm problem?

No expert but... (3, Informative)

TheCarp (96830) | more than 2 years ago | (#38014450)

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 ):

However, other existing cryptographic algorithms do not appear to be broken by these algorithms.[11][12] Some public-key algorithms are based on problems other than the integer factorization and discrete logarithm problems to which Shor's algorithm applies, like the McEliece cryptosystem based on a problem in coding theory.[11][13] Lattice based cryptosystems are also not known to be broken by quantum computers, and finding a polynomial time algorithm for solving the dihedral hidden subgroup problem, which would break many lattice based cryptosystems, is a well-studied open problem.[14] It has been proven that applying Grover's algorithm to break a symmetric (secret key) algorithm by brute force requires roughly 2n/2 invocations of the underlying cryptographic algorithm, compared with roughly 2n in the classical case,[15] meaning that symmetric key lengths are effectively halved: AES-256 would have the same security against an attack using Grover's algorithm that AES-128 has against classical brute-force search (see Key size). Quantum cryptography could potentially fulfill some of the functions of public key cryptography.

Re:No expert but... (1)

Nightshade (37114) | more than 2 years ago | (#38014562)

see the comment above on the 1978 cryptosystem...

Re:No expert but... (1)

TheCarp (96830) | more than 2 years ago | (#38014738)

Um.... I have expanded every comment posted to this article so far, above and below, and yours is the only that contains the string "1978".

What kind of data? (1)

hawguy (1600213) | more than 2 years ago | (#38014488)

I'm more interested in finding out what kind of data you're protecting that needs to remain private for a century. A century ago, telephones were new and uncommon in homes (a few million phones existed, but no transatlantic lines, there was no dialing -- calls were placed through manual exchanges where a switchboard operator manually connected the callers), there was no TV, there were no commercial radio broadcasts. Electricity to the home was uncommon except to the wealthy in urban areas.

I'd really like to know what kind of information you have that still needs to be a secret in the year 2111 when we'll all be driving fusion powered flying time traveling cars and vacationing in hotels on the Moon and Mars and carrying petabyes of data on our iMicrosoftPods with end-to-end DRM that terminates in chip implanted in our brains.

Re:What kind of data? (1)

Dewin (989206) | more than 2 years ago | (#38014618)

I'd really like to know what kind of information you have that still needs to be a secret in the year 2111 when we'll all be driving fusion powered flying time traveling cars and vacationing in hotels on the Moon and Mars and carrying petabyes of data on our iMicrosoftPods with end-to-end DRM that terminates in chip implanted in our brains.

The keys to the DRM, of course.

Re:What kind of data? (0)

tepples (727027) | more than 2 years ago | (#38014764)

I'm more interested in finding out what kind of data you're protecting that needs to remain private for a century. [By that time] we'll all be driving fusion powered flying time traveling cars and vacationing in hotels on the Moon and Mars and carrying petabyes of data on our iMicrosoftPods with end-to-end DRM that terminates in chip implanted in our brains.

The keys for said end-to-end DRM.

Not so worried about quantum (4, Interesting)

tempest69 (572798) | more than 2 years ago | (#38014530)

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?

Re:Not so worried about quantum (1)

Anonymous Coward | more than 2 years ago | (#38014756)

Basically you're asking "what if P=NP?"
Suffice it to say the question has been considered quite thoroughly, and everyone agrees it would be something of a big deal.
Not very likely though.

Re:Not so worried about quantum (1)

Anonymous Coward | more than 2 years ago | (#38015050)

Factoring is in NP. It is not known if it is in P. It is not known if it is NP complete. Thus there might be a polynomial algorithm and the world might still not be any wiser about P=NP.

Re:Not so worried about quantum (1)

junglebeast (1497399) | more than 2 years ago | (#38014860)

I would probably inform some major banks, CC companies, etc and offer to withhold the secret for $10,000 a day up till 1 month. Then I'd go public and collect some of the prizes and scientific awards, retire and live a life of luxury never having to work again.

Re:Not so worried about quantum (1)

Professr3 (670356) | more than 2 years ago | (#38014934)

Didn't they make a movie about this? It looked like an answering machine, but it was really a [REDACTED] in disguise.

Re:Not so worried about quantum (1)

gedhrel (241953) | more than 2 years ago | (#38014940)

"What would you do..?"

Publish it as widely as possible, publically. As a secret it's worth killing over.

GPG / PGP works for me (1)

randomErr (172078) | more than 2 years ago | (#38014582)

I believe that GPG maybe your best alternative to look into. If those don't work for you there are the fishes - Blowfish and Twofish.

Re:GPG / PGP works for me (0)

Anonymous Coward | more than 2 years ago | (#38014626)

GPG's underlying algorithms of RSA and DSA will fall. Symmetric won't save you when the key can be extracted from the handshake.

I cannot find a reference that DH will fall but I believe it will fall if DSA falls.

20 years is extremely unlikely (3, Informative)

JoshuaZ (1134087) | more than 2 years ago | (#38014604)

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 [wikipedia.org] . 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.

Re:20 years is extremely unlikely (1)

Surt (22457) | more than 2 years ago | (#38014784)

Factoring 100 requires a 7bit quantum computer. We've successfully operated a 4 bit computer to factor 15. You really think it will take 20 years more to get those next 3 bits?

Re:20 years is extremely unlikely (3, Interesting)

JoshuaZ (1134087) | more than 2 years ago | (#38014896)

15 has been factored using NMR machines which have been abandoned for most serious research precisely because they can't be scaled very well. There are other systems which are more scalable in theory but they haven't been successful so far as getting the minimum number of qbits needed to factor 15. (Also this isn't quite accurate in that you need slightly more than log_2 n qbits to factor n in the general case, but the basic point is sound.)

Re:20 years is extremely unlikely (1)

blueg3 (192743) | more than 2 years ago | (#38015124)

15 happens to be an unfairly easy number to factor with a quantum computer.

Factoring 100 using Shor's algorithm really requires closer to 70 qbits.

Nothing to respond to. (2)

Vellmont (569020) | more than 2 years ago | (#38014628)

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.

Things to keep in mind. (4, Insightful)

KeithIrwin (243301) | more than 2 years ago | (#38014666)

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.

Ooops (1)

KeithIrwin (243301) | more than 2 years ago | (#38014692)

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.

Submitter, RTFA (1)

shadowrat (1069614) | more than 2 years ago | (#38014684)

Even though current publicly known experimental quantum computing is nowhere near powerful enough to attack real cryptosystems, many cryptographers are researching new algorithms, in case quantum computing becomes a threat in the future.

Did the submitter even read TFA? Everyone is happy with ssh and rsa because they work. People are working on encryption methods for when they don't. Nobody knows what's going to happen in the future but it's not here yet because there are no flying cars.

Quantum menace? (0)

Anonymous Coward | more than 2 years ago | (#38014702)

Not really a menace, it will take some effort to implement a quantum cryptographic system. So it will be more than 20 years out. But AES is still good and has a future.

The one thing you have to look at is its to prevent tapping into communications real time. If someone were to get the packets of a vpn tunnel and decrypt them oh lets say in a few weeks most likely months or years depending on the equipment, how will that data be relevant?

Well, (1)

AdamJS (2466928) | more than 2 years ago | (#38014720)

Chances are, anything that does need to be secured against such threats, already is. Anything that does not, is probably fine with RSA.
Barring gross incompetence.

probably (5, Insightful)

superwiz (655733) | more than 2 years ago | (#38014766)

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.

You can't hide secrets from the future with math (4, Interesting)

Captain Spam (66120) | more than 2 years ago | (#38014870)

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.

NTRUEncrypt and NTRUSign (1)

Anonymous Coward | more than 2 years ago | (#38014874)

NTRU [sf.net] is probably the most trustworthy and useable post-quantum cryptosystem.

There are good algorithms (1)

johndoe42 (179131) | more than 2 years ago | (#38014894)

There are several asymmetric protocols with very nice security properties, even against adversaries with quantum computers. My personal favorite is based on the Learning With Errors problem, which is in turn based on some lattice results. Wikipedia has a decent summary [wikimedia.org] , and the original paper is here [psu.edu] . The old McEliece cryptosystem might be secure against quantum attack. NTRU is commercialized but its security bounds make me very nervous. There also systems based on elliptic curve isogenies, but a new quantum algorithm [arxiv.org] comes somewhat close to breaking them. The main problem with these cryptosystems is that the resulting ciphertexts and signatures tend to be fairly long. RSA produces ciphertexts that are about the same length as the original messages and DSA produces nice, short signatures. ECC protocols are even better, but Shor's algorithm breaks them just as easily as RSA and DSA. The fancy post-quantum protocols, on the other hand, tend to produce large messages that are slow to work with.

One-Time Pad (2)

solinari (69433) | more than 2 years ago | (#38014904)

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.

What world do you live in? (3, Informative)

slaad (589282) | more than 2 years ago | (#38014954)

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.

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.

NP remains NP (0)

migloo (671559) | more than 2 years ago | (#38014964)

So called quantum computing does not break the computational complexity barriers, it just shifts them a bit.
What is exponential (like the RSA) remains exponential; we may have to increase the key size a little and that's it.

Quantum Computing (1)

Cameron Fwoosh (2504966) | more than 2 years ago | (#38015064)

I think a key argument being lost here is that, while Quantum Computing may tear through current encryption, it will also be responsible for the creation of new and improved cryptography methods. In fact, with quantum factoring, there is a theoretic possibility to create an encryption that is so difficult to break, it could be considered impossible...and it could be done with very basic quantum mathematics (If you can call quantum mathematics basic). As for SSH and RSA, until the "Quantum Menace" actually rounds that corner, these will remain the industry standard for a while. Even once someone creates a quantum computer that is actively breaking encryption, companies will not likely have the technology available to counter this for a while. You can't simply walk into Radio Shack and pick a quantum computer up. All we can hope is that the good guys get it up and running first, and make a solid encryption method that follows.

Steganography Cryptograhphy (0)

Anonymous Coward | more than 2 years ago | (#38015112)

...For future-proofing, at least. Encryption always tends to be broken (think Enigma), but it's quite effective to combine encryption with, yknow, actually HIDING the stuff:

http://en.wikipedia.org/wiki/Steganography#Digital_steganography

The Quantum Menace? (1)

geekoid (135745) | more than 2 years ago | (#38015158)

hahaha.

Creating messages that can be decrypted more then one way; one of which is used to the key from a book only known to the actor pretty mush solves that.

For the rest of us, I'm not sure when it will become cost effective to implement.

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...