I don't see any mention of quantum computers in here so I thought I'd mention:
the NSA themselves are concerned that quantum computing will be a great threat to encryption in the near future.
Keep in mind that the NSA and god knows who else are storing encrypted communications to break them later.
Quantum computing will defeat RSA, DH, ECC, asymmetric crypto, but it will only weaken symmetric crypto (eg. AES) by a factor of two.
So according to my Internet research: if your symmetric crypto is twice as secure (key size) as needs be, it is future proof.
Also (and please correct me if I'm wrong) I believe the triple encryption Serpent(Twofish(AES)) available in VeraCrypt (TrueCrypt fork) even protects against weaknesses which may be discovered in any of these cryptosystems: they would have to defeat all three.
Symmetric encryption not being broken doesn't really help you if the encryption key has been exchanged using a (presumably quantum-breakable) form of asymmetric encryption. Most encryption in the wild works this way.
True. Note that some "post-quantum" key exchange schemes already exist (based on lattice cryptography, for which there are no known poly-time quantum attacks), e.g. https://eprint.iacr.org/2015/1092 . But I haven't heard of it being used anywhere.
There's an extremely simple method which is to onion multiple algorithms. If you want to add the promised security features of a new algorithm that hasn't been battle-tested it's well worth the effort.
Your proposed use seems intended to add randomness. However, Schor's algorithm (for example) doesn't attack the randomness of a message but factors keys.
How would you propose to securely exchange the keys for the several algorithms? If there is enough meta or implied information for you to know what algorithms are used, an attacker would also know what algorithms are in use.
The obstacle isn't lack of randomness or an excess of decipherability but not using a quantum resistant algorithm.
I know next to nothing about this subject, but this suggestion sounds like the kinds of things that amateurs suggest but experts scoff at. So my question to any actual experts: is this legit? Note that breaking A+B is not necessarily as hard as breaking both A and B, but it certainly seems likely to be true most of the time.
I'm far from an expert, but I believe the big worry with layering systems like this is you double the amount of key management and implementation attack surface (which is often the weakest part of a cryptosystem), and traditionally it's not for much benefit.
Ignoring quantum computing, doubling up algorithms doesn't really protect you against unknown unknowns all that much as there is a good chance that a massive flaw in one of them could apply to the others (since they are all somewhat based on the same "problem").
When you start layering lattice based crypto with traditional crypto the payoff might change and make it more viable.
I don't think there is an exact term (and if there is I'm all ears), so the closest one I found pertains to onion routing[1], except instead of each layer being a different key, each layer is a different algorithm and a different key. I.E if you wanted to use algorithm X and algorithm Y, you could encrypt your plaintext with cyphertext_x = X(x_key,plaintext), and then cyphertext = Y(y_key,cyphertext_x). If X is terrible, Y still protects your data. if Y is terrible, X still protects your data. Note that the order in which X and Y are applied doesn't matter.
Sounds good for symmetric crypto, but not for public key exchanges, which is what quantum compute attacks are so far all about.
There could be double-tree PKI, where nodes in the tree are represented by two key pairs in different kinds of key spaces, with the different signatures terminating in two ephemeral key pairs, which are then used for key derivation, and the subsequent secret perhaps concatenated and boosted into a higher key space? The complexity would be mind boggling. And, weaknesses in one half of the tree could translate into a security reduction on the final symmetric key, so it would have to be way over powered to be effective.
Lattice based schemes are roughly as old as ECC. They also enjoy something called worst-case to average-case redictions for certain parameter ranges, which gives us confidence in their strength.
TLS implements PFS (perfect forward secrecy) by generating an ephemeral asymmetric key pair for the session, usually through DH. In other words, breaking the session key pair will only reveal the plaintext of the current session for the current client. No previous communication is broken, so the NSA would have to traverse the history for each client.
And for a target of interest, given quantum computing, it would not really provide any real protections. I could see how recalculating the key would be well worth it, if you really want the data.
That's understandable, since the point of asymmetric encryption is communication. But people can use symmetric encryption when it's about your own data security (i.e. you encrypt it, you decrypt it).
If you're using encryption to keep your data safe (e.g. local files, full disk encryption), then you don't actually need asymmetric encryption.
Agreed. However, the kind of mass surveillance people are worried about isn't really concerned with personal data at rest. That data already requires targeted surveillance to get at.
Additionally... unless you generated all the bytes you are encrypting yourself without transmitting them over a network at any time... e.g. video/pictures you took yourself and then stored to your own encrypted disk, your data could be compromised by quantum-breakable encrypted communication protocols at the time of transmission. I would wager that most data worth surveilling goes over the network at some point using TLS.
There is still tremendous value in symmetric encryption for off-site storage, especially cloud-based storage.
This allows storage to be off-loaded wherever without needing the storage location to be trusted. All that needs to be stored locally is the key.
Done right, this means quantum won't get you access to dropbox-like stuff. (Dropbox itself probably doesn't work like that, it'll store the symmetric keys server side somehow.)
Found that hard to believe, so I googled it. Not positive this is a trustworthy source, but it sounds like Dropbox does use encryption for files at rest and in motion: https://www.virtru.com/blog/dropbox-encryption/
Dropbox is known to have intergration with PhotoDNA, a state program that matches file signature with a database of known illicit images. This would be impossible if the encryption used is irreversible and as far as I know dropbox never claimed otherwise.
Couldn't dropbox hash the images on the client, and upload the encrypted images as well as the hash? No need to upload an unencrypted file to do matching.
Depends on what kind of hashing they do: a scheme like yours using a cryptographic hash would be defeated by just randomly changing a single bit in the image (eg appending some garbage bytes at the end); or re-encoding the jpeg. Of course, it could still catch non-techy people.
I'm not claiming it is end-to-end, nor did I expect it to be, but perhaps some people would assume that. I thought you were claiming they don't use encryption at all.
You shouldn't be trusting your commodity cloud storage provider for that stuff anyway. Use your own client side encryption program to encrypt whatever you need to. Arq, borg backup, zip files with a password, sparse encrypted dmg directories, etc.
Even for your own data, asymmetric encryption can be useful.
Eg think you want to encrypt your logs: with asymmetric encryption you can store the public keys on all your servers, encrypt your logs as you generated them and forget the plain text as soon as possible. You keep your private key hidden away on a secure server, and only use it when you actually want to look at your logs (which doesn't happen all that often).
One thing you could do is to exchange the keys in a nonstandard way. Phone or whatever. Obviously still breakable but at least not by a standard dragnet.
I wouldn't use the phone for exchanging plaintext keys. You're forgetting about ECHELON, wiretaps, and the dragnets where LEA are ignoring (or purposefully misinterpreting) the law.
It's really cheap to store ALL phone calls these days, and just "playback" when you get the legal search warrant.
If you're exchanging keys in person, I suggest looking into OTP, currently the only known mathematically unbreakable form of encryption, and so simple it has been used since at least World War I.
That's not really the case. OTP requires a large amount of perfectly unbiased randomness, implicitly from a hardware randomness source (otherwise what you have is more accurately a stream cipher).
Contrast with deriving a key using cryptographic primitives, which can accept low-quality randomness (as long as there is sufficient entropy), that can be easily and transparently collected.
Yes, in theory OTP requires perfectly uniform uncorrelated random input. However, in practice, you can use a randomness extractor… at which point, yes, we can't prove that someone with unbounded computational power wouldn't be able to crack it. But all known computational power is bounded.
Right. So now you have to figure out how to get a secure RNG into people's hands, so they can create pads. How does that work? Genuinely curious whether there's a reasonable solution.
Devices that produce a trickle of truly random numbers can be produced for a few bucks. They're included in modern CPUs, for example.
But that was never the problem. The problem is, now what? To use this OTP you need to securely deliver pads to everybody you'll ever send a message to. So, OTP is practical for a handful of secret agents who'll receive messages of a few dozen words per year from a single controller, and useless for most of us in the real world.
_This_ problem is why we have public key cryptography.
If IPSec is a complicated, commitee-designed and NSA interfered technology, and moreover not recommended by information security researchers, isn't a detail such as support for post-quantum algorithms irrelevant?
We are of two minds about IPsec. On the one hand, IPsec is far better than any IP security protocol that has come before: Microsoft PPTP, L2TP, etc.
On the other hand, we do not believe that it will ever result in a secure operational system.
It is far too complex, and the complexity has lead to a large number of ambiguities, contradictions, inefficiencies, and weaknesses.
It has been very hard work to perform any kind of security analysis; we do not feel that we fully understand the system, let alone have fully analyzed it.
There is someone evidence that QM will result in weaker signals to the point where you can't use it to break real world crypto. It's something of an open question at this point.
Basically, you can do 64 bit calculations on a 16 bit traditional computer, it just takes more steps and some RAM. However, to do 64 bit quantum calculations you need a 64 quibit quantum computer. Now, we may be able to build a 64 QC, bout even that is useless for real world encryption. Further, it while it does not take more time to run a 64vs 4096 quibit QC, it does become exponentially harder to build.
Sort of like trying to measure a building to the nearest inch is harder than nearest foot, and every added digit of accuracy is even harder.
It's not just the number of bits that affects signal to noise ratio, though... It's also the complexity of the calculation; more gate operations and longer storage in memory leads to more quantum decoherence. And AFAIK, each type of calculation must be implemented in hardware, because reversible quantum gates must be used. This means you would need a specialized chip for each algorithm. I haven't confirmed this understanding with someone that specializes in QC, but I don't see a way around it, other than to combine many algos onto a single chip, sharing as many gates as possible, but degrading S/N further.
Something tells me, for an intelligence agency, building a quantum computer only for the purpose of breaking cryptographic keys would be a worthwhile investment.
An investment they have already made:
The effort to build “a cryptologically useful quantum computer” -- a machine exponentially faster than classical computers-- is part of a $79.7 million research program called “Penetrating Hard Targets.”
Current quantum computers lack the amount of qubits required to implement practical quantum integer factorization (e.g: Shor's algorithm) at the scale required to break encryption.
For example the NIST standard for the controversial dual eliptic curve deterministic random bit generator standard, involves two numbers, p and q, which are 100 digit long. To date, largest integer factored in a quantum computer is reported to be around 200,000...
> So according to my Internet research: if your symmetric crypto is twice as secure (key size) as needs be, it is future proof.
New attacks are discovered from time to time. It is unlikely someone will try to bruteforce your encrypted data. Much more likely that some vulnerability will be discovered in AES or the way you generate keys for it.
Considering DH is often used along with AES, I'd assume many encrypted communication streams implementing these that have been captured will likely be broken when this becomes a reality. Anyone care to shed some light on this? As far as ECDH goes... (afaik) most ECC implementations are vulnerable to quantum computing attacks...are there any decent post-quantum key exchange algorithms / protocols?
EDIT: nevermind, i've now read through the thread more and have found answers. :)
Its more of a problem if you have key exchange (like RSA); here [1] it says that with AES is supposedly secure against quantum computers with 'sufficiently sized key sizes'; For key exchange they are trying to adapt elliptic curves.
There is an approach (called Supersingular isogeny Diffie-Hellman or SIDH) using certain types of mappings between elliptic curves being researched that _may_ be secure in a quantum setting. (edit to add:) I think this may be what the grandparent poster is referring to by "trying to adapt elliptic curves".
No. For two reasons, a general reason and a specific reason.
Firstly, quantum computing at scale _might_ be possible in our universe but it might not. One of the spookiest things that might still be true would be a thing called finite non-local hidden state. In this scenario the whole universe has some sort of hidden state, a bit like the seed value of a Minecraft world. Quantum computing in a universe with finite non-local hidden state just weirdly "doesn't work" when you scale it up, because it's basically using the universe's hidden state as magic working storage, and that runs out. Simulation nuts would tell you finite non-local hidden state makes it pretty clear we're in a simulation, but then they would say say that...
Secondly it says "near future". We have every reason to believe there will be serious obstacles to scaling up quantum computing. Somebody else gave the example of Babbage's engine. Just because we can conceive of fusion power generation doesn't mean it's going to happen next week.
Or at all. At the start of the 20th century some mathematicians thought all of mathematics could be formulated as a handful of assumptions plus a huge chain of inference. It was just a matter of writing it out precisely. Surely an inevitability. This project was begun by mathematicians and philosophers and it was going pretty well (proving that 1+1=2 for example) up until this chap Gödel comes along and straight up proves it's impossible with his Incompleteness Theorem, if you can do 1+1=2 then Gödel shows how you can write out effectively the equivalent of "This statement is false" and blow up your whole system.
It's a possibility that it'll be a great threat in the near future. Remember that Babbage's Analytical Engine was designed on paper in 1837, and nothing similar was constructed for over a century.
If it's not the near future, we might move to post-quantum algorithms (or quantum cryptography, a field almost entirely unrelated to classical cryptography which involves carefully moving entangled pairs of particles around) before quantum computers become any good at cryptanalyzing realistically-sized encryption algorithms.
> Quantum computing will defeat RSA, DH, ECC, asymmetric crypto, but it will only weaken symmetric crypto (eg. AES) by a factor of two.
That's quite a bummer. I finally managed to convince someone to use gpg and now I learn that this just makes sure your emails will be read/analyzed by anyone who has an interest in it in the future.
"anyone who has an interest in it in the future" is a very vague term. I'm confident lots of things will happen in crypto centuries after I die, but that's not in my threat model.
Neither do I care about what happens in a couple of centuries. My main worry is that in a somewhat foreseeable future data of electronic communications can be used to construct a model of how a society of interest works to a degree useful enough to attack/control it.
So it isn't necessarily about what I am communicating or to whom I talk but the fact that it seems impossible for society as a whole the hide the details of its functioning.
I viewed pgp/gpg as a tool that could counter this. Convincing people to use it would've been an uphill battle but there would have been a slim chance of succeeding to a useful degree.
It's already been done, just not on very many qubits. Scaling up to more qubits is a tractable engineering challenge, and there's plenty of money on the table, so we have every reason to expect that practical quantum computers will emerge in the near future.
If, and that is a big if, quantum computing was here, you won't be reading about qbits.
All the headlines will be: "Heisenberg uncertainty principle violated; science, technology and life as you know it will change'.
This has nothing to do with 'engineering challenges'. You are dealing with hard cold physics limiting our understanding of the standard model, just because the barrier is there.
I find it weird that hash signatures are not commonly used since most asymmetric hash signature schemes (if not all) are provably safe as long as the hash function used is safe and they are also quantum-safe and very trivial to implement.
It is also extremely annoying that programs like gpg do not support the generation of large RSA keysizes such as 15360 bits which would require many more qbits in order to break (and since RSA 4096 and 2048 are much more commonly used, they might not even build a quantum computer capable of breaking them or they might create a much smaller amount of them).
You are correct, but we're talking about asymmetric key crypto in general, not just encryption. Presumably the GP is referring to quantum-resistant hash-based signature schemes such as https://en.wikipedia.org/wiki/Merkle_signature_scheme
I think that was in reference to public key cryptography, not in reference to hashing, but I'll leave it to the OP to clarify, that's at least how I interpreted it.
the NSA themselves are concerned that quantum computing will be a great threat to encryption in the near future.
Keep in mind that the NSA and god knows who else are storing encrypted communications to break them later.
Quantum computing will defeat RSA, DH, ECC, asymmetric crypto, but it will only weaken symmetric crypto (eg. AES) by a factor of two.
So according to my Internet research: if your symmetric crypto is twice as secure (key size) as needs be, it is future proof.
Also (and please correct me if I'm wrong) I believe the triple encryption Serpent(Twofish(AES)) available in VeraCrypt (TrueCrypt fork) even protects against weaknesses which may be discovered in any of these cryptosystems: they would have to defeat all three.