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.

Google has been experimenting with it in chrome https://security.googleblog.com/2016/07/experimenting-with-p... though it is just an experiment in Canary.

The sad truth is, until we've spent a lot more time analysing and attacking those algorithms, they aren't as secure as what we've got.

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've never heard of such technique, what does onioning do?

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.

[1] https://en.wikipedia.org/wiki/Onion_routing

Algorithms composition? (similar to function compositions[1], since algorithms are just function that take an input and return an output.)

[1] https://en.wikipedia.org/wiki/Function_composition

Use of new encryption algorithm on the ciphertext encrypted by the old algorithm.

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.

Not a simple problem to solve.

Why wouldn't that work? Exchange all n keys with their respective methods in parallel?

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.

Google's canary test also does regular ECDH requiring it to be broken as well

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.

Agreed, it won't help much in that case.

This case is a targeted breach of confidentiality not unlike a phone wire tap, still not allowing bulk surveillance. Not bad altogether.

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.)

Dropbox de-duplicates your files with other users who have the same ones, and are capable of serving them all to you through a web site.

There's no encryption there at all, except TLS in transit.

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.

It's effectively nothing when Dropbox themselves have access to all your files whenever they want.

And whoever hacks dropbox, yours or all of them.

They do, but Dropbox controls the key and their services can decrypt customer data, so the value of the encryption is limited at best.

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.

It's only about avoiding automatic dragnet, so making a person listen to the conversation and figure out the key counts as success.

Automatic voice transcriptions has been a technology for greater than two decades.

And it doesn't count as surveillance until someone looks at it...

Exchange many keys.

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.

Mathematically unbreakable if your pad is truly random

Sure, but if your RNG is compromised, there's no point talking about encryption in the first place.

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.

Snarkily: a one time pad reduces the problem of exchanging secret messages to exchanging secret keys of the same length..

The only thing that OTP buys you is that you can exchange the pads at your convenience any time before.

You only need to meet once.

With a few GB (a couple bucks in a supermarket will buy a 8GB usb stick) you can communicate in text about 16 thousand books worth of words.

In other words, to deplete the pad you would have to write sixteen thousand books.

I think that's pretty convenient, as far as literally unbreakable encryption goes!

Oh, definitely. The convenience of being able to secure your communication in advance is great.

It's just that key-sharing is basically the most complicated and vulnerable part of modern cryptography.

I saw that strongSwan had already supported two post-quantum key exchange algorithms (NTRU and NewHope) for IPSec IKEv2. Good.

https://wiki.strongswan.org/projects/strongswan/wiki/IKEv2Ci...

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?

http://www.mail-archive.com/[email protected]/msg123...

https://www.schneier.com/academic/paperfiles/paper-ipsec.pdf

From Schneier's IPSec paper

Conclusions

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.