7 ms·
The Day When Computers Can Break All Encryption Is Coming
- zeristor 7y agoPerhaps I’m showing my ignorance, but isn’t elliptic curve cryptography different?
- dvdkhlng 7y agoNo, 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 https://en.wikipedia.org/wiki/Post-quantum_cryptography
- jlgaddis 7y agoSlightly 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 https://en.wikipedia.org/wiki/Elliptic-curve_cryptography
- red_admiral 7y agoRun-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 7y agoIts 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 7y 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 7y agoAnd the New York times
- dredmorbius 7y agoSeveral major news sites have done this.
- DennisP 7y agoCurrently WSJ articles can be read by appending "?mod=rsswn" to the URL.
- hestefisk 7y agoWhat about quantum encryption? Shouldn’t that theoretically be unbreakable?
- bayareanative 7y agoNo 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.
- AgentME 7y agoIsn't AES-256 safe from quantum computers? I thought it was mainly assymmetric encryption that's completely breakable with quantum computers.
- DennisP 7y agoThat'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 7y agoNot if your key is sent in the clear protected by asymmetric encryption.
- tialaramex 7y agoHowever, in practice modern systems do ephemeral DH key agreement. Now, Shor's algorithm can be brought to bear on DH as well, but it ratchets up your costs because now you're attacking every single connection individually. Suppose, miraculously, that you have a Quantum Computer which breaks any modern assymetric crypto for $1M in one hour. That's very impressive, but you won't use it to snoop on somebody's Google searches, that's $1M and an hour per search. "Big booobs", an hour and $1M later, "Big boobs" (ah, that first one was a typo), another hour, another $1M, "Bigger boobs". Not practical. You _could_ attack the signature algorithm, allowing you to sign messages "as Google" and MITM connections but that's an active attack so it will have very poor deniability. Not a problem if you're the SVR or Mossad, deniability was never part of your mandate anyway, but awkward for the NSA or GCHQ whose governments prefer not to admit what they're up to. And lack of deniability is very awkward if you're organised crooks, that's going to get you banged up.
- alkdfsAFD94 7y agohttps://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography
- amelius 7y agoNot 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)
- dogma1138 7y agoSome 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.
- amelius 7y 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 ...
- wolfgke 7y ago> 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 ... Relevant: > https://en.wikipedia.org/w/index.php?title=Gell-Mann_amnesia_effect&oldid=900197054 https://en.wikipedia.org/w/index.php?title=Gell-Mann_amnesia...
- supermatt 7y agois 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 7y agoAFAIK, 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-quantum-computer-double-with-every-additional-qubit https://www.quora.com/Why-does-the-computing-power-of-a-quan...
- deleted 7y ago[deleted]
- evrydayhustling 7y agoAny 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 7y agoYeah 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 7y agoThere 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 7y agoQuantum computers that can do fast factorisation have been demonstrated, they just haven't yet been able to factor large enough numbers to be dangerous.
- tialaramex 7y agoFactoring 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_guy 7y 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-integer-factored-by-shors-algorithm?noredirect=1&lq=1 https://crypto.stackexchange.com/questions/59795/largest-int...
- _qbxp 7y agoI store moderately sensitive files in VeraCrypt containers. Are there post-quantum encryption algorithms on the roadmap for this type of storage software?
- Laforet 7y agoI don't see any urgent need for a better symmetric cipher as AES-256 is likely to be sufficient in the foreseeable future.
- SanchoPanda 7y agoI 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 7y agoSomething 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 7y agoThe 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)
- Silhouette 7y agoThis 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.
- rini17 7y agoI 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 :)
- boyter 7y agoIn 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.
- deleted 7y ago[deleted]
- SAI_Peregrinus 7y agoAll 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 7y agohttp://archive.is/Z0iJd http://archive.is/Z0iJd