10 ms·
NIST’s Post-Quantum Cryptography Program Enters ‘Selection Round’
- deleted 6y ago[deleted]
- nabla9 6y ago40 year old Classic McEliece made into the second round. It's well proven but not fit to all uses due to it's large public key size. > Classic McEliece has a stable specification−−the only significant change in the second round is the addition of additional parameter sets. As such, NIST selected Classic McEliece as a finalist and believes it could be ready for standardization (should NIST choose to select it) at the end of the third round
- drummer 6y agoI hope it makes it through the selection. Either way i'll be using it.
- tialaramex 6y agoWhat application do you have where huge public keys are no problem, but you fear imminent (at least within a lifetime where you can't upgrade) availability of large quantum computers capable of Shor's algorithm?
- oconnore 6y agoHow about a web browser? The Nytimes.com front page is 4.66 MB. A Quantum McEliece key is 8373911 bits (per wikipedia) or almost exactly 1MB. Therefore if my connection to Nytimes.com was over McEliece based TLS -- it would be a 21% bandwidth increase. I doubt I would notice.
- fsociety 6y agoYou have to consider that web browsers run on IoT devices now and shouldn’t be excluded from security.
- dependenttypes 6y agoI honestly doubt that an IoT device capable of displaying a modern fancy site and running bloated things like webkit would have trouble using Classic McEliece.
- bawolff 6y agoHow much of that do you have to download before browser does first paint? With a key handshake you would have to do it before any content is displayed. In much of the modern web (for people blessed with fast connections) latency is much more important than bandwidth. An extra 1mb right upfront might be very different from an extra mb overall. Especially when tcp slow start is taken into account. Even more so if the webpage is loading stuff from many different domains
- dependenttypes 6y agoPretty much anything really. HTTPS, private communications, etc. I am using a computer, not an IoT device.
- nabla9 6y agoClassic McEliece is not good for HTTPS or anything where you need to download new public keys frequently.
- dependenttypes 6y agoYou do not need to download a new public key in HTTPS frequently (except if you use forward secrecy, in which case a mixed scheme could be used), most people visit only just a few specific sites. In addition public keys could be cached. Anyway, a lot of web pages are already much bigger than the McEliece public key.
- est31 6y ago> imminent The arrival of quantum computers doesn't have to be imminent for it to cause harm. The Utah datacenter (and likely others) store giant amounts of encrypted content, waiting for the key exchange to become decryptable. Currently almost all communication we consider to be encrypted is not safe from quantum computers. How great would it be in 30 years if you had great evidence that people who are in the prime of their careers have done embarrassing things in their youth. You could extort them or use it to get them out of the way if they turn out to be a problem. The value of such information in fact increases over time as those people rise to more important positions of society. So ideally, we'd switch to quantum confidential key exchange as soon as possible so that such an attack can't be done.
- tialaramex 6y ago> How great would it be in 30 years if you had great evidence that people who are in the prime of their careers have done embarrassing things in their youth. Yes, Facebook does exist. I've written about this before. People who don't have a past with vaguely embarrassing things they did and goofy photos and the wrong friends and so on are not future politicians, they are ghosts and their future is as foreign intelligence agents. Do you know what sank Prime Minister "Call me Dave" Cameron in the United Kingdom? Was it the unverified and likely fictitious stories about a pig - similar to events from a popular a TV show? The family tax scandal? Something he did at school or as a young man? Photographs of him dressed like someone from a different century? Nope. What sank Dave was assuming that voters wouldn't destroy their own country to spite people they don't like (including him). A depressingly ordinary political tale, that could come from any era in history.
- Google234 6y agoWow, that story is really irrelevant. Take the time to read about cancel culture.
- drummer 6y agoWith Classic McElice, at least right now, the computation time for a keypair is a bigger problem than the size of the public key. It will get faster with better implementations and hardware use. But now it takes many seconds on a Ryzen 9 3950 to generate a keypair. I had to build a system with background threads computing keys and having them ready for quick response when a connection is made. If anyone is interested see: https://github.com/kareldonk/QuantumGate https://github.com/kareldonk/QuantumGate
- dependenttypes 6y agoYou might want to check out https://groups.google.com/a/list.nist.gov/forum/#!topic/pqc-forum/koZWqTM714A https://groups.google.com/a/list.nist.gov/forum/#!topic/pqc-... This project that you linked seems quite nice. I especically like its Code of Conduct.
- drummer 6y agoThanks for the link. It seems the implementations are already improving. From the posted benchmarks it looks like it got twice as fast, which is still slow for some use cases (like ephemeral use for forward secrecy) and slower devices. The best solution will be hardware support.
- badrabbit 6y agoI have heard that too, but us it really a big deal to have 65KB+ keys these days?
- timerol 6y agoAs someone who works on embedded devices, yes. The whole system can have 256KB of flash or less. 1 or 2KB for keys hurts, but is manageable. 65KB means that much of the IoT will not be upgraded to post-quantum security.
- dependenttypes 6y agoIoT devices should be behind private networks rather than being directly accessible to the internet anyway. Said devices can use a "weaker" algorithm like NTRU.
- bsder 6y ago> IoT devices should be behind private networks rather than being directly accessible to the internet anyway. Hogwash. You just reduced my reliability by a dramatic amount. Not only does my IoT device have to be functional, but it now has to have a gateway that is functional at the same time in order to be useful. Uh, yeah, no. And, besides, a private network is only private until one of the devices gets compromised. Then it's not private anymore. Better to make your device capable of living on the real, hostile Internet.
- dependenttypes 6y ago> Not only does my IoT device have to be functional, but it now has to have a gateway that is functional at the same time in order to be useful Consider it differently. Your IoT stove, IoT coffee maker, IoT washing machine, IoT lights, etc do not need to be secure if they are behind a secure gateway. > And, besides, a private network is only private until one of the devices gets compromised. Then it's not private anymore. The gateway makes sure that nobody but you will be able to access (and thus compromise) your IoT freezer. > Better to make your device capable of living on the real, hostile Internet. Sure, but considering the amount of IoT botnet that is out there I do not think that this is going to happen.
- dependenttypes 6y agoThis is the 3rd round, not the second.
- nabla9 6y agoThis is the 2nd round that selected 3rd round finalists.
- dependenttypes 6y ago"made into the second round" means that it passed the 1st round and entered the second.
- BearsAreCool 6y agoOne thing that bothers me about most of these algorithms is how conceptually difficult they are for me to understand. I don't have that strong of a background in cryptography but there is something special about how with RSA you can do it at a small scale by hand. With very limited notes I can explain to a group of high schoolers almost exactly how this vital part of encryption functions and even vulnerabilities in it (small exponent values, etc). While rolling your own crypto is bad, with a bit of work I'd expect almost any programmer to be able to implement RSA without too much difficulty. I'm not sure how important being able to explain encryption algorithms in detail to high school students is, but I'll definitely be sad when RSA and other non-quantum resistant algorithms join the likes of the enigma machine and exist for demonstration process only. I'm hopeful in time less crypto minded people (like me) will better understand module learning with errors or lattice based cryptography and maybe we'll get better at explaining it. It would be a shame if even more of cryptography into an unintelligible black box to eke out performance gains.
- tptacek 6y agoYou can intuitively reduce RSA to model problems that you can do by hand, or trivially implement it in Python, but it's debatable how much your intuition is actually serving you; do you really have your head around why RSA works, what its limitations are, and how it can be applied? I think you have to get that through careful study, not from the kind of "machine sympathy" you often acquire through implementing algorithms and systems code. In reality, most programmers cannot implement RSA safely without much difficulty; the opposite thing is rather the case. There's a reason the term "schoolbook RSA" has the connotations it does.
- jacobr1 6y agoBut there still is value in "schoolbook RSA." The OP thinks we lose something if we don't have "schoolbook $NextGenCrypto." I would disagree, because we can still use "schoolbook RSA" for its primary purpose: education on the general concept. At the high-school, or even 101 uni level, either we are teaching basic, generalizable skills, or we are providing high-level surveys of general knowledge. The use case isn't "How do I implement and use RSA as a practitioner in the field," but rather it is "How does this thing, that seems like magic, work?" The risk is that the simplified model gives some kind of intuition that will provide a disservice later in life, but the benefits are just the opposite. Which is why showing how even small errors even in the toy-implementation can render it insecure is also a useful tool.
- HashThis 6y agoGood
- dependenttypes 6y agoHere is the documentation: https://nvlpubs.nist.gov/nistpubs/ir/2020/NIST.IR.8309.pdf https://nvlpubs.nist.gov/nistpubs/ir/2020/NIST.IR.8309.pdf All 15 the following are moving to the 3rd round. Third-Round Finalists: Public-Key Encryption/KEMs - Classic McEliece (Code) - CRYSTALS-KYBER (Lattice) - NTRU (Lattice) - SABER (Lattice) Digital Signatures - CRYSTALS-DILITHIUM (Lattice) - FALCON (Lattice) - Rainbow (Multivariate) Alternate Candidates: Public-Key Encryption/KEMs - BIKE (Code) - FrodoKEM (Lattice) - HQC (Code) - NTRU Prime (Lattice) - SIKE (Supersingular Elliptic Curve Isogeny) Digital Signatures: - GeMSS (Multivariate) - Picnic (Zero-knowledge) - SPHINCS+ (Hash) All of Bernstein's submissions (except the joke one) are in the finalist or in the alternative list. A note regarding the alternatives: > The alternate candidates are regarded as potential candidates for future standardization, most likely after another round of evaluation. Some of the alternate candidates have worse performance than the finalists but might be selected for standardization based on NIST’s high confidence in their security. Others have acceptable performance but require additional analysis or other work to inspire sufficient confidence in their security for NIST to standardize. In addition, some alternate candidates were selected based either on NIST’s desire for diversity in future post-quantum security standards or on their potential for further improvement. I am quite a big fan of SPHINCS+, Picnic (these two reduce their security to the one of their underlying hash functions), and Classic McEliece myself. SIKE is interesting too but as far as I know it needs to be used interactively. Rainbow is also interesting.
- hackcasual 6y agoThe problem with classic mceliece is the size of the public keys, which is measured in megabytes
- dependenttypes 6y ago1.3 MiB for the most secure parameter set (mceliece8192128). The other sets are less than 1 MiB.
- sgillen 6y agoWell, at least people are used to downloading Mb of junk when they browse the internet these days anyway...
- dependenttypes 6y agoIt should be noted that Bernstein was complaining about the lack of transparency and NSA involvement in https://twitter.com/hashbreaker/status/1285922808392908800 https://twitter.com/hashbreaker/status/1285922808392908800
- john_alan 6y agoOf course, NIST compliance is a circus. I use it as a list of what not to use. Once a senior cryptographer in Citi's R&D lab was grilling me on my use of 25519 being without NIST's blessing. I asked him what he would use, he said, "cryptographically speaking 25519", Ok.jpg.
- dependenttypes 6y ago> I use it as a list of what not to use. Bernstein's (the one that made 25519) own submissions passed to round 3 though. Do you also avoid AES/SHA3/BLAKE because they were NIST finalists?
- skissane 6y ago> Of course, NIST compliance is a circus. The problem is when customers start demanding it. Then you don't really have much of a choice. Especially when your competitors are offering it – what is the more successful sales strategy – try to convince the customer they don't really need what they think they need, or just give them what they want? You'll win more deals with the second approach than the first. That doesn't mean you can't use NIST-unapproved algorithms that are technically superior to the NIST-approved ones. You can just have some "NIST mode" (or "FIPS mode" to use the older terminology) that you can turn on for those customers that ask for it, and then only NIST-approved algorithms get used for those customers. (It is more than just the choice of algorithms, you also need to have a certified implementation – in Java, one can replace BouncyCastle with BouncyCastle FIPS, and then have a flag to turn on approved mode for the instance; once in approved mode, use of non-certified algorithms is blocked.)
- raincom 6y agoInteresting. Arjen Lenstra used to be at Citi's R&D Lab; his brother is Hendrik Lenstra, who was Bernstein's Ph.D advisor.
- upofadown 6y agoThis all seems premature. If someone manages to invent a computer that works on atomic effects then there will be a lot of development of new algorithms based on whatever that computer can do. There is a very good chance that regular classical computing would be greatly speeded up by such an invention. Just the ability to do things on atom scale would be a huge breakthrough.
- api 6y agoIt's entirely possible that QC will arrive but will be more of a special purpose accelerator for certain algorithms (think of the way custom ASICs can accelerate specific operations) rather than a general purpose thing. Some form of general purpose QC may happen eventually but that might take quite a bit longer, and it may take longer still for it to be commonplace. In the meantime there will be a strong need for classically computable cryptographic algorithms that are strong against attack by any known quantum computable algorithm. Symmetric encryption (AES, ChaCha) and hashing (SHA, Blake2) are mostly safe as long as at least 256 bit keys are used and the algorithm doesn't have weaknesses that QC might open wider. Asymmetric encryption based on conventional Diffie-Hellman, RSA, or elliptic curve methods is absolutely not safe. There are known quantum algorithms that on paper can crack them in reasonable amounts of time if you have the right type and size of quantum computer, and at this point we have reason to believe that such a quantum computer can probably be built. Post-quantum cryptography efforts are about developing asymmetric encryption (key exchange and signatures) that can be computed on a classical computer but for which there are no known quantum attacks. The biggest danger by far is that somebody figures something out and builds such a quantum computer in secret, allowing them to snoop on all kinds of secret communication and steal vast amounts of money before anyone figures out something funny is going on. Unlike an atomic bomb or a new kind of aircraft or satellite, such a quantum computer could be built and operated without creating physical effects that anyone could see at a distance. Unless somebody talks it could remain secret for quite a while.
- The_rationalist 6y agowe have reason to believe that such a quantum computer can probably What are those reasons? Quantum computers could as well be nonsensical bullshit funded since 40s years
- dependenttypes 6y agoDJB seems to have a disagreement regarding some statements that NIST made https://twitter.com/hashbreaker/status/1288039119805747200 https://twitter.com/hashbreaker/status/1288039119805747200 "Misrepresentations of security proofs are starting to cause serious damage. The embarrassingly wrong idea that there's a proof that the "security of NewHope is never better than that of KYBER" is the centerpiece of NIST removing NewHope from #NISTPQC. See https://nvlpubs.nist.gov/nistpubs/ir/2020/NIST.IR.8309.pdf https://nvlpubs.nist.gov/nistpubs/ir/2020/NIST.IR.8309.pdf Known hybrid attacks are faster against Kyber than against NewHope. (Kyber missed this because its security analysis was oversimplified; I'm writing a paper on this.) More to the point, it's clear that there isn't and won't be a proof that Kyber is at least as secure as NewHope. Cryptographers who condone exaggerations of what has been proven share responsibility for any resulting security failures. We cannot simply ignore the increased influence of dangerously oversimplified "provable security" claims upon standards and deployment. This is not a game."