Slashdot Mirror
NIST Asks Public For Help With Quantum-Proof Cryptography (securityledger.com)
chicksdaddy quotes a report from The Security Ledger: With functional, quantum computers on the (distant?) horizon, The National Institute of Standards and Technology (NIST) is asking the public for help heading off what it calls "a looming threat to information security:" powerful quantum computers capable of breaking even the strongest encryption codes used to protect the privacy of digital information. In a statement Tuesday, NIST asked the public to submit ideas for "post-quantum cryptography" algorithms that will be "less susceptible to a quantum computer's attack." NIST formally announced its quest in a publication on The Federal Register. Dustin Moody, a mathematician at NIST said the Institute's main focus is developing new public key cryptography algorithms, which are used today to protect both stored and transmitted information. "We're looking to replace three NIST cryptographic standards and guidelines that would be the most vulnerable to quantum computers," Moody said. They are FIPS 186-4, NIST SP 800-56A and NIST SP 800-56B. Researchers have until November, 2017 to submit their ideas. After the deadline, NIST will review the submissions. Proposals that meet the "post-quantum crypto" standards set up by NIST will be invited to present their algorithms at an open workshop in early 2018.
NIST are hardly credible at this point, they previously were involved in the Dual EC fake random number generator, and now they're an agency under the Executive of Russian puppet leader, Trump. No credibility, means no trust.
FBI has demanded backdoors, Trump has said he'll give them their backdoors. NIST are the backdoor implementers.
Ffs..
So.. You will personally go and visit each and every web site you want to access privately?
Physically visit every inline store you want to deal with?
Then secure all that data carefully! Remember.. If anyone gets a copy.. All security is give.. At either end!
You need to think about things for more than 30 seconds.
Or perhaps you should accept that armchair 'experts' like you who think this is so easy are actually a big part of the problem?
Good crypto is hard.. QC proof crypto will be harder.. Such is life.
The major historical mistake to avoid is over complex 'standards' that are therefore never implemented or used correctly (I am looking at you ipsec..)
Here's a good wikipedia page https://en.wikipedia.org/wiki/... summarizing the known approaches. Interestingly, most symmetric encryption schemes seem to be secure (you just need to increase the key size apparently): it's the public/private schemes that are in trouble.
How does it handle counterfeit or lost messages? Not so well, I bet. Why would I want to spend more time securely obtaining one time pads than actually communicating?
I think it would work like this:
You go to your bank to open an account. While you are filling out paperwork and supplying a thumb-print (thank you 9/11 terrorist - NOT!) the bank generates a very long one-time pad that should provide enough coverage for several year's worth of communications. They keep a copy and they give you a copy. The pad is probably signed with the bank's public key so you know it is really from the bank.
To detect lost messages, every communication will include either an index into the one-time pad (in cleartext or encrypted with some other method) or a pre-determined "synchronization phrase" encrypted with the pad. If it includes the index, then the problem is solved. If it includes a "synchronization phrase" then you start with where the pad left off. If it doesn't match, then you read forward in the pad until it matches, and you know you probably lost a message somewhere along the line.
Also, the pad may be, in effect, two pads: one for sending, one for receiving. This is easly accomplished by having one party start at the beginning of the pad working forwards and the other party start at the end working backwards.
Also, to avoid pad exhaustion, the pad would probably be used to generate temporary/ephemeral symmetric keys and for some other things like the initial setup of the communication. The actual "meat" of the communication would be encrypted with the ephemeral, symmetric keys.
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
For a good explanation of 911 see:
https://en.m.wikipedia.org/wiki/911_(number)
Especially since Quantum Computing only breaks current public key encryption, not even some current shared key algorithms, and keys are much easier to exchange than giant pads.
OK. First off, "giant pads" is at best a clumsy phrase, so let's not beat around the bush, just call them MaxiPads.
Once that is done it should be no problem getting replenishment from a 7-11 "Flirtey drone".
You have the right to remain sentient. If you give up the right to remain sentient, you will be elected to public office
Also, to avoid pad exhaustion, the pad would probably be used to generate temporary/ephemeral symmetric keys and for some other things like the initial setup of the communication. The actual "meat" of the communication would be encrypted with the ephemeral, symmetric keys.
And oops! It's no longer a one-time pad. As soon as you start using an algorithm, by its very nature, you're now leaking a very slight amount of information, because the output is no longer actually random either. This exactly why a one-time pad isn't practical for most applications. It's only effective if it's the same length as the message being encrypted. Any attempt to "cheat" and you compromise the encryption integrity.
Besides, modern ciphers actually DO use true random numbers to generate the initial symmetric keys, typically using Diffie-Hellman key exchange, in which it's impossible for anyone to intercept the key even if they listen to the entire exchange. So you might as well skip the one-time pad, and you get the exact same effect.
Irony: Agile development has too much intertia to be abandoned now.
Ffs..
So.. You will personally go and visit each and every web site you want to access privately?
Physically visit every inline store you want to deal with?
Then secure all that data carefully! Remember.. If anyone gets a copy.. All security is give.. At either end!
You need to think about things for more than 30 seconds.
Or perhaps you should accept that armchair 'experts' like you who think this is so easy are actually a big part of the problem?
Good crypto is hard.. QC proof crypto will be harder.. Such is life.
The major historical mistake to avoid is over complex 'standards' that are therefore never implemented or used correctly (I am looking at you ipsec..)
Of course not. You build an infrastructure based on the premise of physical distribution of one-time pads. That doesn't mean you personally visit every web site you interact with; it means you assume that encryption of a website is breakable and you make the important sites uncrackable by using one-time pads. There are lots of ways to play around with the model and lots of weak points in bad implementations, but fundamentally any encryption algorithm other than that is breakable eventually. It's a much better and more reliable solution for many points of vulnerability than we have today. It is also entirely practical to implement in many cases because of the relatively cheap price of storage media these days.
Just because it's not hard doesn't mean it's trivial. :)
Real lawyers write in C++
It was WOPR, not WPOR.
The point is, that it's the Diffie-Hellman which is going to be broken by quantum computing, presumably. So you might want to be careful with that 'impossible' - this is exactly what the article is about.
Religion is what happens when nature strikes and groupthink goes wrong.
Solution: One time pad; "mathematically unbreakable encryption",
A concept born in 1882, and yet NIST is still looking for a solution in 2017.
Hmmm...
You are extremely ignorant of modern encryption. Ciphers like AES have existed for 15+ years and never had any significant attacks against them. To brute force AES-256 you would exhaust all the energy in the universe. AES is also not vulnerable to attacks by quantum computers. You act like the sky is falling when in reality there have been very few fundamental breaks on cryptographic primitives. Every significant attack in the last decade has been on implementations and protocols, which would be equally vulnerable in your imagined scheme. Even against quantum computers, we already have public key encryption schemes to replace the vulnerable ones. This NIST request is more about standardizing than coming up with something new from whole cloth. Cryptography is working.
Check out the Logjam paper from CCS '15. The authors show an improved attack on 512-1024 bit TLS that would allow for decryption of traffic, then estimate how much money it would cost to implement and show that based on public and leaked information it is likely that the NSA is already doing this.
Your post belies a significant misunderstanding of complexity theory. If we could do what we do today, only faster, then the world would be quite a different place than it is now. If we could constructively show that P = NP, we could make strong AI, cure most if not all diseases and revolutionize every field of science for a start. Quantum computers are able to solve problems in polynomial time (denoted QP) that classical computers are not known to be able to (good ol' P). That is a much bigger deal than you are making it out to be. It is not the difference between 10 minutes and two hours, it is the difference between 10 minutes and the age of the universe.
Having said that, QP is not thought to be equal to NP. We still have encryption schemes which are resistant to attack by quantum computers. The world is not going to end, encryption will still work fine, we just have to do a little bit of planning ahead.
The reason the D-Wave doesn't "break" RSA is that it can only do quantum annealing, which as you say is basically a search algorithm. It does not give exponential increases in efficiency like a theoretical "complete" quantum processor would. For instance, using Shor's algorithm one can factor an N bit number in time something like O(log^2 N), compared to the best algorithm on a classical computer which is something like O(N^(1/3)). In the best case, quantum annealing allows one to do a search which would normally take O(N) time on a classical computer instead in O(sqrt(N)) = O(N^(1/2)). It does not break any "complexity barriers" like a real quantum computer would, just lets you solve certain problems a bit faster.
This is a really big increase in efficiency, say going from a month worth of computation to solve a problem down to just an hour. But it is not anywhere near enough to break factoring since it would hypothetically take thousands of years to break on a classical computer. In fact, the best classical algorithm is actually slightly faster than quantum annealing because we happen to know that factoring is a problem that requires sub-exponential time to solve, O(N^(1/3)) on a classical computer vs O(N^(1/2)) on a D-Wave.
People have already tried this, they called it 2DES. It is a classical example you learn in an intro to cryptography course because it actually does not add any security at all. You can do something called a "meet-in-the-middle" attack where you try to decrypt from the right side and encrypt from the left side at the same time, looking for collisions in the middle. This means that even though you use two keys, you don't have to attack them in conjunction you can attack them separately giving you only one extra bit of security.
https://en.wikipedia.org/wiki/Meet-in-the-middle_attack
This is called deniable encryption and there are information theoretic lower bounds on what you can actually accomplish with this unfortunately. Each ciphertext has to be carefully coded with full knowledge of what "domain" it comes from in order to produce other, plausible messages. It is incredibly cumbersome and not usable for real-world applications. For simple "spy games" it could be useful, but given the incredibly diversity of data that is encrypted on an average persons computer it is not practical.
The one-time pad DOES NOT replace Diffie-Hellman though. It replaces symmetric encryption, for which we have perfectly good existing solutions. AES is not vulnerable to quantum attacks. Any discussion of the one-time pad in relation to quantum-secure encryption is pointless. We need new asymmetric encryption schemes like lattice-based encryption, not some half-cocked one-time pad bullshit.
1) Because of Grover's algorithm, even encryption which is "secure" against quantum computers still needs twice the key length to have the same level of security as against classical computers. This is because Grover's algorithm lets you brute force a space of N possibilities in time O(sqrt(N)) instead of O(N). So if 90 bits is secure today, you would want 180 bits to be secure against quantum attacks.
2) They can. AES goes up to 256 bits and there is no reason we couldn't make larger block ciphers if we needed to. Currently AES-256 would be secure even against a fully-functioning quantum computer.
3) You are confusing NIST and the NSA, and also AES with DES. The S-box for DES was recommended by the NSA because they had advanced knowledge of differential cryptanalysis that was not widely known at the time. It was not a backdoor. And they had no input into the design of AES, which was proposed by Belgian cryptographers and vetted in a mult-year open contest between academics. The Dual_EC_DRBG scheme with the backdoor that you are referencing was entirely designed by the NSA, not NIST, and academics were immediately suspicious of it. The open contests that NIST has done, including AES and SHA-3, have been widely lauded as the "right" way to do standardization and have had significant buy in from academics, in contrast to the top-down approach that lead to weak standards like Dual_EC_DRBG.
Yes let us now compare the packed files you have seen personally vs the entire volume of HTTPS traffic that goes across the internet every day. I am betting that the second one is a teensy bit bigger. And yes TrueCrypt and VeraCrypt don't use enclave chips, but only a handful of enthusiasts use those programs. You know what programs do use enclaves and therefore uniformly random keys? iOS encryption (over 1 billion iOS devices), Android encryption (lots of those too), Microsoft BitLocker, Apple Filevault. The problem is that you think the stuff you use is the main problem when in reality it is not. It is the mainstream stuff, and surprise billion dollar companies like Google, Apple and Microsoft don't rely on offline password security. And if the stuff you use is broken, that is YOUR fault. Make a better version of TrueCrypt that doesn't rely on password security. It is not the fault of the encryption scheme.
Also, the one-time pad is conceptually a very large password that both parties know. If you assume that you can get a long one-time pad, then you could have just as easily made a good password in the first place. It is intellectually dishonest to pretend otherwise. The ONLY reason you would ever use the one-time pad is if you do not trust the core security of symmetric encryption schemes.