Hacker News Reader

Comment by andai | Hacker News Reader

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.

View on HN

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.

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.

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

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

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.

Exchange many keys.

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.

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.

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.

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

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.

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

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.

I've never heard of such technique, what does onioning do?

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?

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

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.

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.

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.

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.

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/cryptography@metzdowd.com/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.

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

Doubled key size does not mean twice as hard to break. Algorithm weaknesses are a thing.

This WP is pretty accurate though. It describes the world we think will exist after legitimate quantum computing.

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.

Could you elaborate? I'm not sure I follow. It's been a while since my CS Theory classes.

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.

Good analogy; and quite accurate.

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.

Re: need custom hardware for each algorithm

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

article

https://www.washingtonpost.com/world/national-security/nsa-s...

leaked document

http://apps.washingtonpost.com/g/page/world/a-description-of...

Yes, that's one of the big questions in QC. If people manage to build good error correction for QC some day, scaling will be less of an issue.

Scott Aaronson's blog has some good background information for the layman.

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

200,000 what? Digits? Bits?

the largest number was 200,000 i.e. 6 digits or about 21 bits

20 bits > 1,000,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.

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

Elliptic curves are broken in a quantum setting.

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

> the NSA themselves are concerned that quantum computing will be a great threat to encryption in the near future.

pardon my ignorance. but, isn't this an inevitability? not just a possibility?

I would argue no... there's nothing inevitable about technology. Doubly so for quantum computing. Others will likely disagree.

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.

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.

Our current understanding of Quantum Computing implies Quantum Computing is possible.

So the nice thing about QC research is that we either get shiny new computers to play with, or we learn something new about Quantum Mechanics.

So... how come they are selling them?

yeah- my response neglected "near future"- i don't believe our current encryption methods are "near" broken. to that end, i was obviously wrong.

but i appreciate you reading between the lines and following up with a great response- i have a lot to Google. :)

Maybe it's a lesson that security itself is a flawed approach and we need a fundamentally different system

And the NSA apparently doesn't use Asymmetric Crypto for anything for this reason and perhaps others.

Their most secure devices use FIREFLY, a variant of Photurius protocol.

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

You seen to be so sure quantum computing will actually be done.

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

A signature is a trap-door, encryption is reversible. So they are two entirely different things, you can't use a signature hash for encryption.

I am not claiming that you can though.

Then you probably meant to start a new thread. The one you are replying to is about encryption exclusively.

Nope, the poster I replied to talked about asymmetric crypto in general, which includes signatures.

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.

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

Reply on news.ycombinator.com