Slashdot Mirror
Quantum Computer Not Ready To Break Public Key Encryption For At Least 10 Years, Some Experts Say (theregister.co.uk)
physburn writes: The Register has spoken to some experts to get a better understanding of the risk quantum computers present to the existing encryption systems we have today. Richard Evers, cryptographer for a Canadian security biz called Kryptera, argues that media coverage and corporate pronouncements about quantum computing have left people with the impression that current encryption algorithms will soon become obsolete. But they will not be ready for at least 10 years, he said. As an example, Evers points to remarks made by Arvind Krishna, director of IBM research, at The Churchill Club in San Francisco last May, that those interested in protecting data for at least ten years "should probably seriously consider whether they should start moving to alternate encryption techniques now." In a post Evers penned recently with his business partner Alastair Sweeny, he contends, "The hard truth is that widespread beliefs about security and encryption may prove to be based on fantasy rather than fact." And the reason for this, he suggests, is the desire for funding and fame.
The "experts" say "not possible for 10 years".
This means it will likely happen in the next 18 months.
When will we see a traditional computer and quantum computer side by side, showing the quantum computer actually performing the same computation a million, or maybe just a thousand, or perhaps just ten times faster than the traditional computer?
Let me know when, because before then it's nothing but quantum schmantum pipe-dreaming and weird research projects.
10 years to break today's encryption. We have more modern ciphers that will become used in the next few years that are resistant to the current theoretical models of quantum-computing based attacks.
Also, quantum computing still has trouble of scale with larger keys, I assume that we'll see the next 10 years require 4096 or 8192 bit keys as scalable rental CPU and GPU becomes more powerful.
And people really have to stop planning to have the same security model for the next 10 years in the future. Upgrades and long term support are becoming a necessity.
Custom electronics and digital signage for your business: www.evcircuits.com
10 years? Where have I heard that before? Oh, right, AI in the 1960s.
Seriously though, if your security is immediately breached when someone breaks your encryption, you should rethink your security. Security is about depth - how many layers an adversary must breach before he gains access to your valuables. If you only have one layer between you and your adversary, your valuables are not very secure.
I thinking of you, blockchain.
Moderating "-1, Disagree" is simple censorship. Have the guts to post your opinion.
I've been led to thinking that it will never be feasible. We don't know yet, but there are good reasons to think it might not pan out - for breaking crypto.
E.G. The energy required to cool a volume of space for an n-qbit machine to temps that will maintain entanglement between the qbits will scale with 2^n. So you spend just as much energy doing it in parallel on a quantum computer as you would in a classical computer serially. This isn't known to be true, but try plotting the size of fridge against n for existing quantum computers and see what the curve looks like.
or
You can't achieve the isolation from the surrounding universe (which is kind of the same thing).
I've seen other arguments about noise presented by physicists, but I haven't grokked them sufficiently,
Quantum computing for physics simulation, as envisioned by Feinman, makes a lot more sense.
I should use this sig to advertise my book ISBN-13 : 978-1501515132.
Whether or not people should be switching to encryption methods today that will be resistant to decrypting by quantum computers in thee future depends on the expected relevance of those messages in the future. If you assume that no message sent today will be relevant 10 years from now, then there is no hurry to update encryption methods. On the other hand, if you need to ensure that an encrypted message sent today or in the near future remains unreadable 10 years from now, then maybe you should be researching and changing methods today.
I don't think the military/intelligence agencies are ahead tech wise. In fact, I think they are way behind because of the complex structure and slow moving. When they want something, they don't use state of the art technique but rather simple letter request for it... or you go in jail. Gov don't break security by breaking the protocol, just just ask for a backdoor at the company. Much much easier and put the job on someone else.
Quantum computers work by solving the "hard" problem of prime factorization.
Essentially an RSA key is the product of 2 randomly selected prime numbers. One is chosen by Alice and one is chosen by Bob at which point they exchange their halves, then they multiply to construct the key. Since the key is never transmitted, only the halves, the theory is that anyone attempting to decrypt their communications needs to guess the two halves of the whole key.
So all of RSA is based on this idea that it is very hard to take a large number and deconstruct it into it's prime factors. But this is and always has been smoke and mirrors.
The problem here is that there are a limited number of prime numbers currently known, roughly 2 billion, especially if you discount the smaller primes that wouldn't be cryptographically useful.
Thus the total RSA key space is limited to the square of the total number of known primes, or 4 quintillion possible keys given the known number of primes. This is a really big number, but it isn't at all intractable.
If you simply precompute by multiplying all known primes together, you can get at the shared secret for every RSA exchange. This could be stored in a database of just 500 petabytes.
Considering there are systems that can crunch this kind of data in the 10TB/s range, you could safely crack any RSA message in no more than 14 hours on an HPC cluster, or 5 days running at home on your laptop.
This is why quantum computing isn't particularly useful. State actors like the NSA, and Mossad and of course Bose Allen Hamilton (who handles the contracting work for both and sells the intelligence they gather in the process to the highest bidder) already have this capability and have been using it for decades.
Simply switching over to NaCL https://nacl.cr.yp.to/index.html is enough to defeat this and for message exchanges larger than a few K you can use NaCL to handle AES key exchange, then use AES for the heavy lifting.
But the powers that be will never allow this to become standard because it would prevent them from profiting off you. Hence the whole "quantum computing is coming zomg! schtick"
The "experts" say "not possible for 10 years".
There's also the aspect of, the NSA is about 10 years ahead in relation to crypto and computing related technologies so...
Nothing to worry about! Move along!
"There is more worth loving than we have strength to love." - Brian Jay Stanley
So if you encrypt something today, do you care if itâ(TM)s secret 10 years from now? Depending on what youâ(TM)re encrypting, yes you do.
If your oposition is nation-states, theyâ(TM)re probably collecting things that are interesting now, for decryption later when they have the ability, so ya, you probably care now.
Iâ(TM)ve had multiple professional conversations about âoepost-quantum cryptographyâ in the last 2 years because of exaclty this. Todayâ(TM)s emails are evidence or headlines 10 years from now, so you may care.
Min
On the whole, I find that I prefer Slashdot posts to twitter ones because I don't get limited to 140 chars before
Ah. Spoken like a true armchair security warrior. I love the sweeping declarations. If your security is breached when someone can open all your locks then you should rethink your security.
Here are a few points to consider for you:
1) My electronic security isn't all (or even necessarily mostly) in my hands any more. It's in the hands of banks, government agencies, and (not me but for the rest of you) social networks. I'm just sure that every tired career bureaucrat is just jumping at quantum computing resistant security. They are just right on that.
2) In addition to my most important data residing, for the most part, in the hands beyond my control, so are the standards. Name a major implementation of an encryption technology standard that deprecated an algorithm before it was demonstrably broken. AES is currently broken in a cryptographic sense and there is not whisper on the horizon of deprecating it. Too costly.
3) In addition to data being at the control of others, and available cryptography being at the mercy of established standards, even when standards are quick enough to add "heir and a spare" algorithms, the software that makes use of those standards doesn't necessarily have the configurability to choose the right algos. Dovecot, for example, just recently added in configurations to allow you to select which curves to use. For years you were stuck with terrible NIST curves which are at best horribly suspect, even though most systems had better curves.
All these things are mitigatable to an extent, but you have to be a hermit not to be vulnerable.
Sure, do you remember when DES was going to take the lifetime of the Universe to crack, then some egg-heads had custom ASICS fabbed and built Deep Crack (EFF DES Cracker), which could break DES in a day?
No, I don't remember that for two reasons the most important being that nobody sane ever made such an idiotic claim. In fact in the wikipedia page linked by yourself (that you obviously didn't read) contains this: "One of the major criticisms of DES, when proposed in 1975, was that the key size was too short. Martin Hellman and Whitfield Diffie of Stanford University estimated that a machine fast enough to test that many keys in a day would have cost about $20 million in 1976, an affordable sum to national intelligence agencies such as the US National Security Agency".
So not only didn't anybody make your ludicrous claim but people at the time said it was too easy to crack and estimated that one could realistically build a DES cracker.
10 years? Where have I heard that before? Oh, right, AI in the 1960s.
AI is all based on the ability of software, which is why predictions of reaching a specific point (which itself wasn't all that specific anyway, very nebulous) can and will be wildly inaccurate.
When talking about quantum computing though, you aren't talking about anything nebulous or so hard to predict progress of. Generally predictions around when hardware will be developed by have been pretty accurate (if not underestimated).
"There is more worth loving than we have strength to love." - Brian Jay Stanley
To quote from Cryptonomicon:
... has pointed out to Avi, in an encrypted e-mail message, that if every particle of matter in the universe could be used to construct one single cosmic supercomputer, and this computer was put to work trying to break a 4096-bit encryption key, it would take longer than the lifespan of the universe.
Randy
"Using today's technology," Avi shot back, "that is true. But what about quantum computers? And what if new mathematical techniques are developed that can simplify the factoring of large prime numbers?"
"How long do you want these messages to remain secret?" Randy asked, in his last message before leaving San Francisco. "Five years? Ten years? Twenty-five years?"
After he got to the hotel this afternoon, Randy decrypted and read Avi's answer. It is still hanging in front of his eyes, like the after image of a strobe:
I want them to remain secret for as long as men are capable of evil.
Sure, do you remember when DES was going to take the lifetime of the Universe to crack,
Nope. The precise limitations of DES key size (56 bits) were known from day one, nobody ever thought it would take that long to crack.
Math. It works.
No sig today...
Technology projection:
1 year: The technology works, we are just trying to find a vendor to sell it.
5 years: We have a proof of concept working, however we don't know how to mass produce it.
10 years: We have a theory that a proof of concept should work, trending shows it is possible a goal.
20 years: We have no idea, but it seems possible
100+ years: Impossible and have no idea on where to start. But it sounds nice.
If something is so important that you feel the need to post it on the internet... It probably isn't that important.
I've been led to thinking that it will never be feasible. We don't know yet, but there are good reasons to think it might not pan out - for breaking crypto.
E.G. The energy required to cool a volume of space for an n-qbit machine to temps that will maintain entanglement between the qbits will scale with 2^n. So you spend just as much energy doing it in parallel on a quantum computer as you would in a classical computer serially. This isn't known to be true, but try plotting the size of fridge against n for existing quantum computers and see what the curve looks like.
Also: Increasing key size is very easy. If quantum computers look like they're getting close we can simply double the key size.
The reality is that only old messages will be decrypted and those messages are already out there so there's nothing you can do about that anyway.
.
No sig today...
Burglar just released from prison says not ready to break into houses for a least a few years. "If anyone sees a break in," he offers, "It wasn't me. No sir."
=^..^= all your rodent are belong to us
On the assumption they think it will take 10 years to crack existing crypto before there is a need to migrate to post-quantum algorithms, leads me to think they already have it or will very soon.
I attended the RSA Data Security Conference In, I think it was 1993, when Diffie talked about cracking DES with dedicated hardware in a matter of hours. That same year, 512 bit RSA was cracked as one of the RSA Challenges.
Quantum computing is useless against a one-time pad. It would just come up with all possible pads which convert the ciphertext into all possible plaintexts which makes sense. e.g. It would come up with decryption ciphers which convert the ciphertext to "one of by land, two if by sea" and "two if by land, one if by sea", leaving the code breaker no better off than not being able to break it.
The only reason we use public key encryption is because it's a lot easier than meeting up in person to exchange a one-time pad before you can exchange secure communications. In public key encryption, you can exchange the key publicly yet still have encrypted communication. Also, it's slow enough that it's generally not used for the communications itself. It's used to exchange AES key(s) (basically one-time pads) securely. The encryption of the plaintext is then done using AES.
All breaking public key encryption would do is put us back to the pre-1970s state of encryption, where secure communications required pre-sharing keys in some way. Difficult for random people/sites who have never spoken to each other before. But trivial for things like chipped credit cards, where the credit card company first has to physically mail you the credit card. (The one-time use rule for a one-time pad could be maintained by pre-loading thousands of one-time pads onto the chip, and replacing the credit card before they're all used up. Unthinkable a couple decades ago, but trivial today with modern storage capacities.)
I could see trusted key escrow services popping up, which pre-share one-time pads with online sites and users. So if a user needs to communicate securely with some online site that they hadn't heard of until 5 minutes ago, they could go through the key escrow service to securely exchange keys with the site. User generates temporary key and securely transmits it to the key escrow service. Escrow service relays key to the site using their pre-shared key with the site. Escrow service immediately destroys their interim plaintext copy (the key the user generated). User uses that key to exchange a new key with the site. Then user can go about communicating securely with the site. It's not as secure as public key encryption since there's a third party involved. But it's still workable, and immune to quantum computing.
Not only is the ability likely more than 10 years out, once it arrives it will be fantastically expensive, and fiddly as hell to keep the things running. You would have to be a very high value target (billions of dollars) to even be worth hacking for a while.
AES is currently broken in a cryptographic sense
That cries out for a citation much as a man lost in the desert for a week cries out for water. As far as I know, the very best known attacks of AES256 reduce it to an effective 253 bits. That is FAR from broken in any sense.
To say it's broken is like saying you can break a 2x4 with your bare hands as long as it came from a diseased tree and you saw 90% of the way through it first.
We've been told that once quantum computers reached quantum supremacy they would be able to break current encryption also known as Y2Q. Now you're saying it will be another 10 years? I don't buy it.
https://en.wikipedia.org/wiki/Quantum_supremacy
If that's what they're announcing then it means they've broken it and are now trying to put our minds at ease, in order to "catch the bad guys" of course.
#DeleteFacebook
If there ever was an encryption algorithm that whose creators were realistic about how it would be attacked and the real threat posed, it was DES.
They knew that 56 bits was "right" for the algorithm. That's why you see triple-DES, but not quadruple-DES. It only works well under very specific circumstances and the creators knew those circumstances well. They also knew enough to harden it against differential cryptanalysis, before differential cryptanalysis was publicly discussed.
Please turn off "smart" quotes in your keyboard settings.
No there are fundamentally different level.
Old encryption standard, be it the venerable Enigma or more recently DES, were considered "hard to crack" because the key-space couldn't realistically be searched with the hardware available at the time.
But lo and behold:
- Computer technology emerged, making the enigma search-space manageable (well that, and a few short-coming of the Enigma algorithms, making it easier to crack thanks to clever tricks).
- As mentioned above, DES couldn't be realistically brute forced with the available hardware, but researcher estimated that hardware capable of covering the search-space could be built within budget available to some state-level adversaries. And with Moore's law helping, modest modern hardware can now beat these.
They were never considered "impossible to crack" only "very hard to crack" but eventually over time/with ressources, it could be achieved.
More modern encryption standards such as RC4, AES, etc. are considered "impossible to crack within current laws of physics and/or math" because even if you converted the whole planet Earth into a giant computer, you couldn't cover the whole search-space before the death of the solar system. This time even Moore's law won't save you (in time).
You'd need :
- Cryptanalysis: problems found in a standard such as RC4. Meaning that you don't actually need to spend the heat-death of the universe searching the whole search-space. Instead there are way to find the few most likely candidate to focus on.
- New physics/maths: finding new different ways to solve the problem that won't necessitate individually testing every single key in the search-space.
TL;DR: So in short, old algos weren't secure, because eventually somebody would built a bigger computer faster enough to brute-force the password.
Modern algos are secure, because the "bigger computer" required is beyond what is physically possible.
You either need new physics.
Or discovering that actually the password is always "Swordfish".
"Sufficiently advanced satire is indistinguishable from reality." - [Tips: 1DrYakQDKCQ6y52z6QbnkxHXAocMZJE61o ]
I agree. The number of entangled qbits has been scaling atrociously bad over the last few decades. A linear increase in qbits may well come with an exponential increase in effort and we may never reach even 100 of them. Also, the computations done with entangled qbits do not yet conclusively prove that quantum computing is really possible. The complexity of the computations done so far is so low that this could still be some other effect. Sure, the theory says it works, but remember that basically every physical model so far has failed when accuracy was scaled up enough. The accuracy scaling needed for breaking even simple ciphers is extreme here.
Hence predictions that we will be able to do it at all are, at this time, basically lies, nothing else. There is no reliable data either way and a lot of indicators that it likely is practically impossible and it may still turn out to be theoretically impossible, giving us a better understanding of Physics in the process.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
"10 years" is the time were most people making predictions hope that nobody will remember what they predicted. Here, it is obvious complete nonsense, but only experts can see that. All the others, including a large group of self-proclaimed experts that in reality do not know what they are talking about, are just going with the demented hype.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
Math. It works.
Like basically all things based on rational thought, it is not accessible to most people though.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
Since it is more like > 100 years for publicly available, and may well be "never", nobody has anything here. Also, if any such machine were used, there would be indications. There is none. In fact, the demented push against encryption is repeated again and again, rather strongly indicating that nobody can get into good encryption.
Also remember that even a perfect QC cannot break something like AES-256 in this universe. It would still require 2^128 or so computations and that is just not feasible, no matter what resources you have. Oh, and that is the known-plaintext case, the other ones are harder.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
10 years is also not a time were we will see any significant advances in Quantum Computing. Maybe in 100 years, maybe never. Remember that we have been at this for like 50 years now and there is _still_ no viable computing hardware. All other alternate computing approaches have gone to the trash-heap of tech history long before that. But because many people associate "quantum" with "magic", this is still going, despite no practical results.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
That DES by itself was too weak to withstand a state-funded attack was well known in the 90s, I was not exactly part of the cryptography in-crowd in those days, but I knew that much. I remember discussing the key length issue in a crypto discussion in college in 1985 or so, after a presentation about DES. No hindsight needed.
If by "extremely limited" you mean tens of thousands of people I agree, but it was not exactly a secret. The big issue was that this was before there was "the web" so accessing information about anything was much harder in general, unless you had access to a research library.
Actually broken means it is possible to come up with the key in a practical timeframe. Weakness is highly variable and somewhat subjective. In this case, the weakening doesn't look like it will make more progress and notably, it cannot actually be used since even for a 128 bit key you have to store 9 petabytes of data to use the technique (and anyone serious about security is using 256 bits).
All that and you still have to use enough guesses that your grandchildren will be dead before you get the key.
It's a bit premature to be replacing it.
"Quantum Computer Not Ready To Break Public Key Encryption For At Least 10 Years, Some Experts Say"
That's what they want you to believe.
You know, the mysterious, shadowy "they" that's behind everything- chemtrails, the flat-earth, anti-vaxxers, Reptilians, C++ pointers...it's all them and they. Hopefully they won't delete this post where I blow the lid off of their nefarious activities.
The light in your fridge burned out? They did it. One of your tires suddenly gets low? They did it. Who ate all the ice cream? They did.
It's so obvious, sheeple! Wake up!
Just cruising through this digital world at 33 1/3 rpm...
Nice ad-hominem you got going there. Let me offer a point for you to consider.
I've left my front door open before. Forget locked, I've left the door wide open intending to go back inside, changed my mind in the 20 feet to the car and driven off forgetting the door was wide open.
My security was not breached.
I live in a neighborhood with watchful neighbors and a healthy police presence. Strangers poking around are noticed, reported, stopped. I could leave my door unlocked every day and it's unlikely I'd be burgled because: depth of security.
Locked door. Watchful neighbors, Police presence. An adversary must defeat three distinct layers of security to steal my television. And if I was worried that wasn't enough, I could add an alarm system and a security camera.
My home security does not, does not, does not critically depend on an adversary being unable to defeat the lock on my door.
Encryption is like the lock on my front door. It's only one element of a successful security architecture. If it's the only element of your security system, if someone with the right electronic crowbar can pry your system open with impunity, it's time to rethink your security.
And oh by the way, I've been in one or another part of the information security business for a quarter of a century. If one of us is an amateur, you're looking at the wrong one of us.
Moderating "-1, Disagree" is simple censorship. Have the guts to post your opinion.
Key size doesn't help with public key crypto. Shor's attack is a logarithmic speed up. Key size helps with the Grover attack for symmetric crypto since it's a square root speed up, but that wasn't the topic of TFA.
I should use this sig to advertise my book ISBN-13 : 978-1501515132.
That sounds optimistic
The latest issue of IEEE Spectrum has an article from a quantum computing expert who opines that true quantum computing for any serious task will never happen. It's an argument based on how many qubits are required to create a computing element and how precise the measurments of the wave functions have to be. That's paraphrasing it, but that's the idea.
I tried finding an online link to it but can't.
funny, it seems like we are always being told that we are given encryption tools that are unbreakable, only in hindsight to find out that they were nowhere as secure as advertised.
Maybe the long post wasn't clear enough.
I'm not saying that the algorithms are guaranteed 100% unbreakable for ever.
I'm just saying that the reason of unbreakability have change drastically over time.
- Old algorithms were unbreakable because to break them requires additional computing power. It wasn't available at the time. But with time (and Moore's law) a big enough computer is guaranteed to emerge, eventually.
They were (in a way) *guaranteed* to be breakable one day in the future. Just a matter of (computer) engineering.
- Newer algorithm *WILL NOT* be broken just by a bigger computer. That doesn't guarantee that they'll never be broken, it only guarantees that a bigger computer *IS NOT* the thing that will break.
They'll get broken instead by either one of the following three:
- New type of physics and maths that make the algorithm irrelevant.
( ^- that is what all the quantum-crypto love to speculate about, but currently it's not something that we observe in the wild)
- Bugs are discovered, turns out the algorithm is flawed. In theory no a big enough computer can physically exist to break it, but it in practice, thanks to bugs it turns out it's trivial.
( ^- that's what happens to all cryptography standards that get phased out. See RC4)
- People are stupid. No amount of cryptographic science is going to save you if your password everywhere is always "123". Hey that's my luggage's... Or if it can simply be bypassed due to implementation blunder, because basically the lock is indeed locking the door on the left side, but noone will prevent you from unscrewing the door's hinge on the right side.
( ^- in practice, that's what is happening most of the time time nowadays. See haveibeenpwnd).
So, you can take your condescending attitude and have a nice circle-jerk with megol whilst feeling secure nobody will break the encryption on your video
Nobody is saying that the encryption of the video is never ever going to by broken.
The things that we try to say is that the way it will be broken have changed.
Back in the old days, the hairy-porn video with moustaches will eventually get broken, because somebody will eventually make a big enough computer.
Nowadays, most of the time, the amateur-porn will get broken/private nudie pick will get disseminated, because most likely some bozo though that "pa$$w0rd" was secure enough (but, it follows the required numbers/signs rules !), or because some researcher has noticed that the reportedly "military grade super secret crypto technique" used by the video storage, if you twiddle the bits in a certain un-expected way, boils down to a simple ROT-13 that your pocket calculator could break.
But nowadays a bigger computer isn't the thing that will break it, it's physically not possible *now*.
(but it was physically possible a long time ago, but considered distant enough, so such crypto did get used back then)
To go back to the subject,
- 56bits DES got broken, because 56bits is small and eventually a big computer could be built (even back then people were drawing attention and sending alerts that a government *could* have the budget to make such a big computer quite soon).
- 256bits AES cannot be broken by a physical computer. Not now, not in 1'000 years from now. It could be broken by an entire new physics and maths to make an exotic new type of computer (that's what quantum computing is touted by some to be able to open as possibilites), or because some scientist will discover bugs, enabling ways to break AES, without needing to go through all 2^256 combinations (and this just hasn't happened yet for any meaningful reduction of this big number).
AES considered unbreakable and potentially getting broken on
"Sufficiently advanced satire is indistinguishable from reality." - [Tips: 1DrYakQDKCQ6y52z6QbnkxHXAocMZJE61o ]