7 ms·
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 t
by andai 10y ago
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.
- hendzen 10y agoSymmetric 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.
- praptak 10y agoOne 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.
- andai 10y agoIf 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.
- acjohnson55 10y agoMathematically unbreakable if your pad is truly random
- chimeracoder 10y agoSure, but if your RNG is compromised, there's no point talking about encryption in the first place.
- srssays 10y agoThat'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.
- klodolph 10y agoYes, 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.
- acjohnson55 10y agoRight. 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.
- tialaramex 10y agoDevices 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.
- shshhdhs 10y agoI 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.
- jacquesm 10y agoAnd it doesn't count as surveillance until someone looks at it...
- praptak 10y agoIt's only about avoiding automatic dragnet, so making a person listen to the conversation and figure out the key counts as success.
- shshhdhs 10y agoAutomatic voice transcriptions has been a technology for greater than two decades.
- dredmorbius 10y agoExchange many keys.
- bad_user 10y agoThat'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.
- hendzen 10y agoAgreed. 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.
- rocqua 10y agoThere 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.)
- mikepurvis 10y agoDropbox 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.
- smaddox 10y agoFound 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/ https://www.virtru.com/blog/dropbox-encryption/
- y7 10y agoTrue. 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 https://eprint.iacr.org/2015/1092 . But I haven't heard of it being used anywhere.
- da-bacon 10y agoGoogle has been experimenting with it in chrome https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html?m=1 https://security.googleblog.com/2016/07/experimenting-with-p... though it is just an experiment in Canary.
- Filligree 10y agoThe 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.
- hackcasual 10y agoGoogle's canary test also does regular ECDH requiring it to be broken as well
- matthewaveryusa 10y agoThere'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.
- Cyph0n 10y agoTLS 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.
- falcolas 10y agoAnd 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.
- Cyph0n 10y agoAgreed, it won't help much in that case.
- yellowMoneky 10y agoThis case is a targeted breach of confidentiality not unlike a phone wire tap, still not allowing bulk surveillance. Not bad altogether.
- sorz 10y agoI 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/IKEv2CipherSuites#Post-Quantum-Key-Exchange-using-NTRU-Encryption https://wiki.strongswan.org/projects/strongswan/wiki/IKEv2Ci...
- effie 10y agoIf 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/msg12325.html http://www.mail-archive.com/cryptography@metzdowd.com/msg123... https://www.schneier.com/academic/paperfiles/paper-ipsec.pdf https://www.schneier.com/academic/paperfiles/paper-ipsec.pdf
- andai 10y agoFrom 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.
- bitexploder 10y agoYes. https://en.m.wikipedia.org/wiki/Post-quantum_cryptography 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.
- Retric 10y agoThere 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.
- chimeracoder 10y agoCould you elaborate? I'm not sure I follow. It's been a while since my CS Theory classes.
- Retric 10y agoBasically, 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.
- smaddox 10y agoGood 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.
- catshirt 10y ago> 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?
- smaddox 10y agoI would argue no... there's nothing inevitable about technology. Doubly so for quantum computing. Others will likely disagree.
- geofft 10y agoIt'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.
- tialaramex 10y agoNo. 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.
- partycoder 10y agoCurrent 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...
- MichaelMoser123 10y agoIts 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 https://en.wikipedia.org/wiki/Post-quantum_cryptography .
- snakeanus 10y agoElliptic curves are broken in a quantum setting.
- ekiru 10y agoThere 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".
- ycmbntrthrwaway 10y ago> 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.
- snakeanus 10y agoI 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).
- jacquesm 10y agoA signature is a trap-door, encryption is reversible. So they are two entirely different things, you can't use a signature hash for encryption.
- fiatjaf 10y agoYou seen to be so sure quantum computing will actually be done.
- wyager 10y agoIt'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.
- quickben 10y agoIf, 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.
- leetbulb 10y agoConsidering 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. :)
- cJ0th 10y ago> 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.
- geofft 10y ago"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.
- cJ0th 10y agoNeither 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.
- BinaryWaves 10y agoMaybe it's a lesson that security itself is a flawed approach and we need a fundamentally different system
- rand83746 10y agoAnd the NSA apparently doesn't use Asymmetric Crypto for anything for this reason and perhaps others.
- nickpsecurity 10y agoTheir most secure devices use FIREFLY, a variant of Photurius protocol.
- deleted 10y ago[deleted]