The Day When Computers Can Break All Encryption Is Coming
wsj.com
wsj.com
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.
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.
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.
Using side channel to share single 512-bit key that is used to generate other keys keys is enough.
If you share one master key for long time, having (effectively) 128-bit secret shared state is too small.
Right. And the first RCE+escalation 0-day will enable someone to wipe out your accounts.
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.
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.
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...
Blank lines separate paragraphs.
Text surrounded by asterisks is italicized, if the character after the first asterisk isn't whitespace.
Text after a blank line that is indented by two or more spaces is reproduced verbatim. (This is intended for code.)
Urls become links, except in the text field of a submission.
I think many are seriously underestimating the engineering breakthroughs needed for a computer that can break 2048 bit RSA. Hopefully I'm proven wrong.
An example: casting You can cast wax nearly for free, given that you salvage the mold materials and carve them by hand, sunlight can be used to melt the wax (~70C), and almost no materials are needed to control heat. Casting pewter is a bit more difficult, as a wooden mold will burn a bit, and you'll need some type of heat control tech, such as an oven or microwave or solar forge (~200C). The temperature has only tripled, but already materials no longer work and costs are significantly higher. I've worked in a titanium foundry and the cost is enormous compared to low energy areas.
But I doubt either can beat what solar and wind are poised to produce. They are cheaper than installed coal now, and are targeting installed natural gas.
Battery will handle the rest of storage/load needs.
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.
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...
With this much on the line, someone has to have a detailed model they keep up to date...
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)
(First hashing the input counts as trivial because that would reduce the effective number of bits)
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.
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...
If it’s criminals stealing your passwords then it would take decades after QC until it would become universal enough to be a problem, by then likely current traffic would not be affected.
If it’s state level actors then you might be in a bigger bind.
If we take the NSA for example today there isn’t a single cryptographic system they can’t compromise.
And I’m using the term system intentionally as the NSA can’t break 4096bit RSA or AES or any other competent cipher.
They can and do break cryptographic systems on a daily basis by compromising the hardware, software and people which the system relies on.
But this is a very targeted and costly operation which means that general internet traffic isn’t looked at because it’s not worth it.
However if they also capture encrypted traffic and store it indefinitely as most key exchanges today are not necessarily QC resistant they could potentially go back and decrypt all that traffic.
This is why while the house is not on fire I think there is value in pushing post-QC ciphers sooner rather than later.
And even if the NSA can be kept in check we have little control over Russia and China and the list of actors capable of operating at large enough scales for this to be a problem grows bigger every day.
However if the NSA is currently your adversary and you are worried of being targeted then pre QC or post QC encryption isn't going to matter push comes to shove they'll beat it out of you.
But as I said if the NSA or any other agency is currently capturing and storing encrypted data they can't afford to decrypt via targeted means they'll be able to retroactively decrypt it if they do manage to build a quantum computer and quantum supremacy would be a definite thing.
But right now there isn't an encryption the NSA can't break as long as there are people and additional assets involved in the process.
In fact I would be that for targeted attacks it would still bet easier to bribe, raid/hack the server farm or beat the snot out of someone in a black site than to use a quantum computer for quite a while after these things would be become a reality to factor the RSA private key corresponding with the key exchange of the traffic you want to decrypt.
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
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.
That said, quantum computer resistant cryptography does exist, but is not currently in wide-spread use for various reasons.
> 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
Cryptosystems based on isogenies of elliptic curves are one form of (conjectured) post-quantum-secure cryptography.
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.
Verifying classical hardware and removing side channels is hard enough.
Gee, are all the down votes because of the issue that quantum computers will have with random access memory