NIST’s Post-Quantum Cryptography Program Enters ‘Selection Round’

https://www.nist.gov/news-events/news/2020/07/nists-post-quantum-cryptography-program-enters-selection-round

by xoa • 6 years ago

107 75 6 years ago

nabla92• 6 years ago

40 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

drummer3• 6 years ago

I hope it makes it through the selection. Either way i'll be using it.

tialaramex5• 6 years ago

What 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?

badrabbit2• 6 years ago

I have heard that too, but us it really a big deal to have 65KB+ keys these days?

timerol• 6 years ago

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

dependenttypes20• 6 years ago

This is the 3rd round, not the second.

BearsAreCool• 6 years ago

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

tptacek2• 6 years ago

You 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• 6 years ago

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

amir734jj2• 6 years ago

Because post quantum crypto algorithm are based on completely different breed of hard problems. Lattice problems and they are not straightforward to visualize as we were with RSA. Visualizing a lattice of large dimension, calculate its shortest vector or various other properties is not straightforward.

My bachelors was in Math and my master thesis was about lattice problems and post quantum cryptography. For my Ph.D. I switched to completely different subject because I couldn't write good papers in this area. So I understand your concern.

hackcasual3• 6 years ago

2d lattices are easy to visualize though. I've given brown bags to general engineers on NTRU like systems, and have found that some find it even easier to understand than RSA as it's more graphical

remcob• 6 years ago

Would you consider elliptic curve cryptography conceptually difficult? It's certainly more complex than RSA, but over time great educational resources have been developed. The same will happen for these post-quantum schemes.

klyrs• 6 years ago

I second that. I've helped teach ECC to high schoolers (granted, it was a summer program for exceptionally mathematical students) and they found it quite approachable.

nullc5• 6 years ago

Personally, I don't think the ECC tutorials are very good-- they are mostly analogs of the RSA tutorials that are extremely mechanical and do not impart much to any useful intuition about the system.

Someone versed in the monthly HN "how ECC works" submissions will find themselves able to implement a completely naive sidechannel vulnerable and unusably slow implementation of pubkey generation and ECDH (and maybe ECDSA, if they cribbed from wikipedia while doing it). Yet they should on no account be doing this because there are already many excellent, well written (or at least battle hardened) implementations.

By contrast they are unable to:

1) recognize vulnerabilities, even trivial ones, in implementations (including their own)

2) Invent new useful applications (which would be the best reasons to not use an existing piece of code-- it doesn't do what you need)

3) Come up with or implement performance optimizations.

The reason I've found for that by focusing on a mechnical understanding of how to apply the group law gets in the way of an algebraic understanding of how the group can be used.

For all but (3) the specifics of the group law are irrelevant and even for (3) everything except for specialized cracking code uses projective coordinates so the procedure people learned for affine coordinates isn't useful.

If people are having fun they have my blessing :)... but it's my informed view that overwhelmingly ECC tutorials give a lot more "feeling of understanding" than useful understanding.

hannob• 6 years ago

I am actually not sure if this isn't more of a problem of RSA than a feature.

I have seen many simple introductions to some cryptography that try to explain RSA. The problem is: They're almost always wrong and explain some insecure variation of RSA. (Most of the time they talk about a "Message" as the input to the RSA function without ever explaining the concept of padding and why this is important in RSA.)

The thing is: Implementing some form of RSA is relatively easy. Implementing RSA in a secure way is far from trivial.

mdxn• 6 years ago

Lattice based cryptography can actually be made pretty accessible and can be taught to highschoolers and fresh undergraduates (I have done this with students at my job) as long as you give them a couple of math tools they may not have: matrix transforms, Gaussian distribution, vector dot product, and the one time pad. While this is a longish list, none of the topics are particularly hard and are accessible. I'll take a crack at an explanation (with schoolbook Regev-like LWE) and you can let me know how I did. It is better with pictures and probably can be shaped over the years, but I do think that people can adapt this explanation to turn it into something as easy, if not easier, than RSA.

1. Start with a random (secret) n-dimensional vector, s, that lives on a lattice (a square grid like pattern). This is your (small) secret key.

2. Hit that vector with a randomly generated matrix A (written As for multiplying matrix A with vector s), which basically just scales, skews, rotates, and projects that lattice into m-dimensional space (we want m to be much bigger than n). For those in the know, the new vector, As, is almost a "psuedorandom", "random looking", or hard to predict value. This is a way of taking your small key and turning it into a large key.

Intuition: Note that each component of As is basically an individual dot product. On a simple level, you can think of the dot product as a generalization of XOR, parity, or something that creates a checkerboard pattern using that lattice. This basically creates a high dimensional grid (lattice) with many colors that alternate. The end goal is to get some samples of these colors and reconstruct what the grid pattern looks like. If you have tried to learn a checkerboard (XOR, parity) pattern with a linear classifier, you know that this is hard. Here, we are generalizing this concept into something even harder.

3. Add (Discrete) Gaussian noise to As to get As + e. This is just adding "small" random noise to each of the components. You do this is to turn the almost "random looking" large key into an actually "random looking" large key.

Intuition: The reason for doing this is that if you have A and y where As = y, you can solve for s using Gaussian elimination. This is equivalent to the process that gradeschoolers use to solve systems of equations with multiple variables (where they subtract one row from another or solve then substitute variables).

Turns out that Gaussian elimination and other algorithms suck bad at getting the right answer if you have noise or small sources of error. The process gets thrown off wildly and gets no where close to s. The situation is so bad that even quantum computers are assumed to not be able to do it. This is what makes your large key resistant to being reverse engineered by powerful computers.

4. Use your As + e as a one time pad. To encrypt a message m, your ciphertext is the pair A and As + e + m. To decrypt, someone takes the key, s, computes As, then subtracts that off. This leaves you with m + e.

5. Decryption in (4) is bad because the small error, e, is leftover. This makes the process noisy and makes you lose a little information when you encrypt or decrypt. You fix this by using a noise correction encoding that makes the e go away.

Your new ciphertext is (A, As + e + encode(m))

EDIT: Note that to make this actually secure you need to pick good parameters for your lattices and your noise distributions. If your error is too small, it wont fool attacks and is easy to solve. If your error is too large you cant decrypt. The problem is easy unless you are in high enough dimensions (for instance, LWE is easy in 2 dimensions, which is what we use to visualize things).

f38zf5vdt• 6 years ago

Do you have any YouTube videos of your lectures? If not, consider making one and uploading it. As lattice based cryptography comes into maturity ELI15 for us non-mathematicians on the ground floor will be essential.

SAI_Peregrinus2• 6 years ago

RSA isn't that easy to understand. It's a trap: it seems simple on the surface because the core mathematical operation is easy, but the actual complexity (padding) often gets omitted.

RSA-KEM (key encapsulation mode) is easy. There's no padding, the only thing is you can't encrypt a message, only a random number < the modulus. Then you run that number through a Key Derivation Function (KDF) and use it with an Authenticated Encryption with Associate Data (AEAD) cipher. That's just simple enough I'd teach it to high-school students.

RSA encryption is hard. It requires OAEP padding, which is by no means simple. I'd not try to teach it to high-school students.

RSA signing is hard. It requires PSS padding, which is by no means simple. I'd also not try to teach it to high-school students.

Every other use of RSA is insecure, often in very subtle and hard to understand ways. Using RSA as a teaching tool about public-key cryptography does a disservice to students, since they (like you) tend to think that RSA alone is useful for cryptography.

And if you can treat an operation like the padding as a "black box" and ignore understanding, then you can understand code-based cryptography the same way: treat the code as a black box, and the math is very simple.

tialaramex5• 6 years ago

I sympathize but don't entirely agree.

The old version 1.5 signature padding remains widespread. Unlike PSS it doesn't have a security proof reducing to RSA but it does have decades of successful use in practice in one of the harshest environments (the Web because the clients merrily run code written by a potential adversary).

"Prepend this fixed data to your hash" which is the central idea of v1.5 padding is definitely something you could teach to high school students. You can even show them why it's necessary pretty easily for a small exponent.

Making people check padding is again not too hard for high school students, and I think "Do all the things on the checklist. All of them" is a worthwhile lesson not just in cryptography.

dependenttypes20• 6 years ago

Not to mention the most difficult issue that even mainstream libraries (like libgcrypt which is used by gpg) get wrong: implementing rsa in constant time as to avoid timing side channel attacks. I would argue that understanding and implementing elliptic curves (the modern ones especically) correctly is much easier.

nullc5• 6 years ago

I think it's likely that your understanding of RSA is mostly fake. E.g. You could do some totally insecure 'RSA' on paper, but it would be insecure.

Eventually people will write intuitive explanations of other algorithms (it's fairly easy to do them for sphincs+ and mceliece, for example) and you'll feel you understand them too. (and, in fact, I think those understandings will actually be less dangerous than the RSA ones!)

with a bit of work I'd expect almost any programmer to be able to implement RSA without too much difficulty.

Implement RSA incorrectly without too much difficulty.

You should be dubious that even world class cryptographers will get it totally right, as many RSA implementations -- even ones written by experts-- have had serious flaws.

HashThis• 6 years ago

Good

dependenttypes20• 6 years ago

Here is the documentation: 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.

hackcasual3• 6 years ago

The problem with classic mceliece is the size of the public keys, which is measured in megabytes

dependenttypes20• 6 years ago

1.3 MiB for the most secure parameter set (mceliece8192128). The other sets are less than 1 MiB.

sgillen2• 6 years ago

Well, at least people are used to downloading Mb of junk when they browse the internet these days anyway...

skissane2• 6 years ago

All of Bernstein's submissions (except the joke one) are in the finalist or in the alternative list.

What was the joke one?

rainworld• 6 years ago

Post-quantum RSA, 1-terabyte keys: https://eprint.iacr.org/2017/351.pdf

nullc5• 6 years ago

I think McEliece and Sphincs+ are both excellent applications for typical PGP use cases-- and have great security properties. Their weaknesses don't matter as much in low throughput applications.

(e.g. McEliece's slow key generation is a big problem when you're creating 1000 connections per second and want good perfect forward secrecy. It's a non-issue for a long term key that is rotated at most once a year.)

I'm sad that sphincs+ is only an alternate.

Things like software signing and human scale communication don't care if signing is somewhat slow and the signatures are long-- but they do have extremely long lived keys that are difficult to rotate.

dependenttypes20• 6 years ago

Signing/verification speed are both important on things like TLS/SSH/etc and sadly SPHINCS+ can not compete in either, see page 55 in https://sphincs.org/data/sphincs+-round2-specification.pdf

But I agree that it can be used in the OpenPGP use-case. Anyway, Rainbow seems quite solid for TLS.

McEliece's slow key generation is a big problem when you're creating 1000 connections per second and want good perfect forward secrecy

I personally think that if you want forward secrecy you should derive the session key from both the static McEliece key and the ephemeral ntru/whatever key.

dependenttypes20• 6 years ago

It should be noted that Bernstein was complaining about the lack of transparency and NSA involvement in https://twitter.com/hashbreaker/status/1285922808392908800

john_alan• 6 years ago

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

dependenttypes20• 6 years 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?

skissane2• 6 years 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• 6 years ago

Interesting. Arjen Lenstra used to be at Citi's R&D Lab; his brother is Hendrik Lenstra, who was Bernstein's Ph.D advisor.

upofadown3• 6 years ago

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

api2• 6 years ago

It'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_rationalist2• 6 years ago

we 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

nullc5• 6 years ago

be a lot of development of new algorithms based on whatever that computer can do.

This whatever should only change the performance by constant factors.

In theory, cryptographic algorithms give the defender an exponential advantage against the attacker, so any small constant factor can be overcome by adding a few bits of security margin.

dependenttypes20• 6 years ago

DJB seems to have a disagreement regarding some statements that NIST made 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

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

NIST’s Post-Quantum Cryptography Program Enters ‘Selection Round’

Related Stories