The Day When Computers Can Break All Encryption Is Coming

https://www.wsj.com/articles/the-race-to-save-encryption-11559646737

by gnicholas • 7 years ago

54 65 7 years ago

wsj.com

zeristor• 7 years ago

Perhaps I’m showing my ignorance, but isn’t elliptic curve cryptography different?

dvdkhlng• 7 years ago

No, elliptic curve cryptography is not different, as it is based on the discrete logarithm problem [1].

That said, quantum computer resistant cryptography does exist, but is not currently in wide-spread use for various reasons.

[1] https://en.wikipedia.org/wiki/Post-quantum_cryptography

jlgaddis• 7 years ago

Slightly but, in reality, not really.

Early public-key systems are secure assuming that it is difficult to factor a large integer composed of two or more large prime factors. For elliptic-curve-based protocols, it is assumed that finding the discrete logarithm of a random elliptic curve element with respect to a publicly known base point is infeasible: this is the "elliptic curve discrete logarithm problem" (ECDLP). The security of elliptic curve cryptography depends on the ability to compute a point multiplication and the inability to compute the multiplicand given the original and product points. The size of the elliptic curve determines the difficulty of the problem.

-- https://en.wikipedia.org/wiki/Elliptic-curve_cryptography

red_admiral• 7 years ago

Run-of-the-mill ECC is just a new implementation of discrete-log cryptography, and falls pretty much immediately to a Shor-type quantum computer.

Cryptosystems based on isogenies of elliptic curves are one form of (conjectured) post-quantum-secure cryptography.

sbhn• 7 years ago

Its not here yet. Im surprised the problem wasn't already solved with ai/ml, big data, and blockchain. I think the problem personally is the sheer amount of ram that is needed and the ram aint ever gonna be fast enough to fill the buffers or to access. But it will be solved, soon im sure.

Gee, are all the down votes because of the issue that quantum computers will have with random access memory

tomglynch• 7 years ago

"We're sorry, but this URL is not supported by Outline" - have outline made a deal with WSJ to not bypass their paywall?

berbec• 7 years ago

And the New York times

dredmorbius• 7 years ago

Several major news sites have done this.

DennisP2• 7 years ago

Currently WSJ articles can be read by appending "?mod=rsswn" to the URL.

hestefisk• 7 years ago

What about quantum encryption? Shouldn’t that theoretically be unbreakable?

sametmax• 7 years ago

And pricey

nabla93• 7 years ago

Theoretically yes, but its impractical and expensive.

Verifying classical hardware and removing side channels is hard enough.

bayareanative• 7 years ago

No classical functions as they exist now without added strengthening will be able to secure secrets against QC for long. OTOH, classical computing is reaching the limits of Moore's law, so barring process and fab cost reductions, CC ASIC costs will approach stability. If one wants to secure secrets without traditional digital logic (CC), it would get pricey, awkward and/or slow. I think we'll have to gradually keep looking more closely at cost to crack functions (i.e., GPU, ASIC, classical and q computation) much closer, in the spirit of scrypt and argon2. Zillions of rounds (is adding orders of magnitude in existing implementations) of AES or SHA3 maybe the tradeoff needed to thwart QC collisions / breakage with reasonable attacker costs & timeframe goals.

AgentME2• 7 years ago

Isn't AES-256 safe from quantum computers? I thought it was mainly assymmetric encryption that's completely breakable with quantum computers.

DennisP2• 7 years ago

That's correct. Quantum computers can effectively halve the key size of symmetric encryption, but 128 bits is still secure, and we could always go to 512-bit keys.

tootahe45• 7 years ago

Not if your key is sent in the clear protected by asymmetric encryption.

alkdfsAFD94• 7 years ago

https://en.wikipedia.org/wiki/Post-quantum_cryptography

amelius2• 7 years ago

Not a crypto expert, but wondering if we could make a classical encryption function where every bit of the output depends nontrivially on every bit of the input, so a long message would be harder to decrypt, even for a QC.

(First hashing the input counts as trivial because that would reduce the effective number of bits)

dogma11385• 7 years ago

Some ciphers use this method, it’s not the problem.

QC isn’t going to break all crypto traditional symmetric ciphers are safe and one of the simplest classical ciphers a one time pad is still the safest method of encryption when it’s done correctly.

QC may break some asymmetric encryption which relies on factoring numbers.

Asymmetric encryption is on some level security through obscurity as you publicly display a key from which your encryption key can be mathematically derived and you rely solely on the fact that it’s a very hard thing to do.

But as far as classical encryption goes XORing a message against a random number of bits equal to the message length would always be secure, especially for long messages the problem is that it ain’t very practical.

That said however we do have QC resistant key exchange and signature algorithms so I don’t think there is that much reason to panic.

I’m pretty sure you can still find 1024bit and lower RSA key systems still in use arguably these are less secure today than 2048 and 4096bit RSA keys will be during the first years of a post QC world.

amelius2• 7 years ago

That said however we do have QC resistant key exchange and signature algorithms so I don’t think there is that much reason to panic.

Interesting. Then shouldn't we (and PR people involved in QC) stop focusing on the cryptographical capabilities of QC, and start focusing on its other potential applications, like protein folding? Until now in the media, it seems like QC is synonymous with crypto ...

est312• 7 years ago

That said however we do have QC resistant key exchange and signature algorithms so I don’t think there is that much reason to panic.

We don't have QC resistant key exchange. Not yet. There are a couple of proposals, and there is a competition going on on, but it hasn't concluded yet: https://csrc.nist.gov/Projects/Post-Quantum-Cryptography

supermatt• 7 years ago

is there a single practical example of a real world problem being solved by a current quantum computer? all the talks i have seen involve a lot of hand waving and talk of the future. i’m very skeptical that these capabilities are around the corner

JohnStrangeII• 7 years ago

AFAIK, currently probably not, but this would be a bad basis for extrapolation about future capabilities. Conventional supercomputers are insanely fast and current quantum computers do not yet have many qubits yet. But - very loosely speaking - if you add one qubit, the processing power can double. See the first answer here: [1]

If the history of technology and cryptography teaches us anything, then quantum computers will break current encryption sooner than expected. If you're very paranoid, you may switch, in certain areas, to "quantum safe" symmetric encryption (higher key size, higher round numbers) with reasonably secure channel for key exchange instead of public key cryptography.

[1] https://www.quora.com/Why-does-the-computing-power-of-a-quan...

evrydayhustling• 7 years ago

Any quantum experts able to share a technical article on (a) what are the main obstacles to a universal quantum decryptor, and (b) what is the current progress curve on those obstacles?

With this much on the line, someone has to have a detailed model they keep up to date...

orbifold• 7 years ago

Yeah a couple of related problems in fact: You are a professor and working on cold quantum gases, synthetic quantum systems, ... and can semi-plausibly claim that this has applications to quantum computing: Problem solved, you will get a whole bunch of funding. You found a bunch of linear algebra algebra algorithms and they use unitary matrices: Problem solved, founding secured.

It is also a good buzzword prefix: Just prepend Quantum to any word and immediately get funding (See the recently 1 Billion Euro funded EU quantum initiative).

In this respect it has similar applications as Neuro-something: A great way to get funding for a few years. (See Human Brain Project)

surelyyoujest• 7 years ago

There is some cognitive dissonance in associating what after more than 30 years is currently, for all purposes still a Sci-Fi concept and Cryptography.

After billions spent and decades of no progress, this is the same repeated article that has been rewritten every other year hyping about the promisses of what, for all purposes, is currently expensive vaporware.

TazeTSchnitzel• 7 years ago

Quantum computers that can do fast factorisation have been demonstrated, they just haven't yet been able to factor large enough numbers to be dangerous.

tialaramex2• 7 years ago

Factoring by Quantum computers able to implement Shor's algorithm (which is the proposed apocalypse for the family of public key algorithms used today) so far isn't just short of "dangerous" it's short of what you'd expect school children to achieve. 21 is 7 times 3. Really, I'm not exagerrating, that's what they've achieved.

As with the work done to try to figure out how we should handle a big rock coming our way, work on post-quantum cryptography is justifiable because it's something we would really regret not working on if it suddenly becomes necessary and it's not _that_ expensive. But just because the threat justifies relatively modest research expenditure doesn't make it worth a newspaper article that will invariably distort the facts and confuse more than it illuminates.

credit_guy2• 7 years ago

they just haven't yet been able to factor large enough numbers to be dangerous.

According to [1], the current highest factorization using Schor's algorithm is 21=3 * 7 published in 2012, up from the 15=3 * 5 that was demonstrated in 2001. This pace is not all that promising.

Sure, there are other quantum factorizations, but they are either stunts (work only for very narrow classes), or are based on a different algorithm than Schor, which does not show hope to scale up.

[1] https://crypto.stackexchange.com/questions/59795/largest-int...

A2017U1• 7 years ago

It's this generations fusion power.

I think many are seriously underestimating the engineering breakthroughs needed for a computer that can break 2048 bit RSA. Hopefully I'm proven wrong.

OskarS• 7 years ago

Successfully developing functional fusion power is considerably more plausible than practical quantum computers in the near term. The problem with fusion research is that it is and has been massively, chronically underfunded.

mrob2• 7 years ago

Agreed. Consider that we don't even know if one-way functions exist, and all public-key cryptography depends on the assumption that they do. Maybe some classical attack will break all the commonly used systems before a big enough quantum computer is built.

abdullahkhalids2• 7 years ago

You are judging an endeavor by how the media reports on it and not how the actual community's estimate of the progress. You are certainly right that a quantum computer big enough to solve a practical computational problem has not been built [1]. The quantum computing community certainly thought a 20 year timeline to QC was viable in the late 90s and early 2000s. However, after the failures of early experimental efforts, the consensus stance at conferences and such is always that QCs will come when they will come. The challenges are big but the path through them is straightforward - keep improving manufacturing capabilities till we can scale [2].

If you follow the literature, you will realize everyone is busy optimizing their manufacturing capabilities instead of going for short term goals of factoring ever larger numbers. We have to go from a regime where grad students spend months/years carefully crafting a handful of small parts to mini-industrial processes which can be used to manufacture thousands or millions of identical parts. It takes time and effort to do build such setups, but progress has been consistent over the last decade or so, and will only get better in the next decade.

[1] You should be aware though that there have been several very solid demonstrations of quantum key distribution, including commercial offerings https://en.wikipedia.org/wiki/Quantum_key_distribution

[2] Its like humans on Mars. Everyone knows, in principle its possible, but the challenges are huge and rushing things is simply not a viable option.

_qbxp• 7 years ago

I store moderately sensitive files in VeraCrypt containers. Are there post-quantum encryption algorithms on the roadmap for this type of storage software?

Laforet• 7 years ago

I don't see any urgent need for a better symmetric cipher as AES-256 is likely to be sufficient in the foreseeable future.

SanchoPanda• 7 years ago

I can't get over the picture in the middle. Why is the intercepting computer a turret? Why is the secure bank on a slanted platform? I can just picture a meeting of the graphics team with facepalms and groans all around at having to come up with "something".

DanielBMarkham• 7 years ago

Something to remember: One-Time Pads are unbreakable, and as storage costs continue to drop, there are certainly many scenarios where they could be used and never cracked.

Think about it. How much actual secure data do you and your bank need to transfer back and forth? Certainly not web UI elements or site chrome. For each use of your online account, there's probably 3 or 4k max actual data that you need to be secure. Your bank could mail you a 1GB random noise file, perhaps a backup, and you two could communicate for the rest of your life without any fear of anybody understanding what you're saying.

I understand that there's an entire e-commerce ease-of-use scenario where secure communications becomes mission-critical. And I'm certainly not suggesting to replace all secured comms. My only point is that there are parts of this problem that are very tough and there are parts of this problem that we have made more difficult than it has to be simply in an effort to standardize and abstract everything.

QuicksilverJohn• 7 years ago

The problem with this method is that it requires a side channel. This is the real beauty of public key cryptography, you can negotiate a secure channel over an open channel. (*Authentication sold separately)

rini17• 7 years ago

I don't get why this argument is used so often as if it was valid. Setting up a banking account and many other things require a secure side channel anyway - physical presence :)

Silhouette• 7 years ago

This is the real beauty of public key cryptography, you can negotiate a secure channel over an open channel.

You still need sufficient shared information as a starting point to authenticate the other party, so that doesn't really avoid the need for a secure side channel. In practice we often trust that the baseline of certificates that come with a new device or built into a browser are sufficient for this purpose, but there is still an attack surface there and our existing CA infrastructure and processes are not perfect.

mruts• 7 years ago

I mean, sure, but how are you going to protect the one time key?

What might make more sense is if they gave you a usb drive that was good for a thousand transactions or whatever. Then you could get it replaced in person after the pad was used it.

I didn’t read the article (paywall), but unless they are talking about quantum computers, the computation required to break the key and encrypt the data has a exponential difference. If we all started using keys that were, say, 2^32 bits long, we would be fine for the forseeable future.

nabla93• 7 years ago

In practice schemes based on cryptographic hash functions work just as well and are quantum resistant. 512-bit key length is safe from quantum computers. Use bcrypt, Argon2 if you are pessimistic.

Using side channel to share single 512-bit key that is used to generate other keys keys is enough.

mrob2• 7 years ago

The best known quantum attack against symmetric ciphers uses Grover's algorithm to effectively halve the key size. AES-128 is considered secure against classical attacks, so assuming you have a secure side channel for key distribution, AES-256 is sufficient to defeat quantum attacks.

empath75• 7 years ago

Do you mean like literally mail it to you, or email it to you? If it’s the latter you still have the problem of needing it to be encrypted. If it’s the former, it’s damned inconvenient.

abdullahkhalids2• 7 years ago

There exists quantum key distribution https://en.wikipedia.org/wiki/Quantum_key_distribution#Quant... which is provably secure (up to side channel attacks), and allows two parties (say you and your bank) to remotely create a symmetric key. This will certainly require infrastructure to be built, but its possible that this infrastructure consists of beaming signals from bank->satellite->receiver in your home.

rbanffy• 7 years ago

Your bank could mail you a 1GB random noise file

Right. And the first RCE+escalation 0-day will enable someone to wipe out your accounts.

boyter• 7 years ago

In the race between arms and armor, arms have always won. I wonder if the reverse is true in crypto. Will crypto always evolve to be one step ahead, or make a massive leap such that it will be multiple steps ahead.

SAI_Peregrinus• 7 years ago

All current public-key encryption, and short-key private-key encryption yes. XChaCha20-Poly1305 will still be safe. AES-256 (in an appropriate authenticated mode of operation and side-channel free implementation) will still be safe.

As for public-key encryption there are as-yet standardized algorithms that are likely secure. They're just slow. The NIST standardization should wrap up decades before any practical quantum computer is created, giving plenty of time to add some of these as options in protocols.

neonate• 7 years ago

http://archive.is/Z0iJd

The Day When Computers Can Break All Encryption Is Coming

Related Stories