An important detail you really want to understand before reading this is that NIST (and NSA) didn't come up with these algorithms; they refereed a competition, in which most of the analysis was done by competitors and other academics. The Kyber team was Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Gregor Seiler, Damien Stehlé, and also Peter Schwabe, a collaborator of Bernstein's.
Absolutely, but NIST ultimately choose the winners, giving them the option to pick (non-obviously) weak/weaker algorithms. Historically only the winners are adopted. Look at the AES competition - how often do you see Serpent being mentioned, despite it having a larger security margin than Rijndael by most accounts?
> Historically only the winners are adopted. Look at the AES competition
Often, yes. But also consider the SHA-3 competition.
BLAKE2 seems more widely used than what was chosen for SHA-3 (Keccak). What was submitted for the SHA-3 competition was BLAKE1 (it didn't have a number back then but I think this is clearer) so it's not like NIST said that Keccak is better than BLAKE2, they only said it's better than BLAKE1 (per their requirements, which are unlikely to align with your requirements because of the heavy weighing of speed-in-hardware), but still this is an example of a widely used algorithm that is not standardized.
> how often do you see Serpent being mentioned, despite it having a larger security margin than Rijndael
The goal of an encryption algorithm is not only to be secure. Sure, that has to be a given: nobody is going to use a broken algorithm when given a choice. But when you have two secure options, the more efficient one is the one to choose. You could use a 32k RSA key just to be sure, or a 4k RSA key which (to the best of my knowledge) everyone considers safe until quantum. (After quantum, you need something like a 1TB key, as djb humorously proposed.)
Wikipedia article on Serpent: "The 32 rounds mean that Serpent has a higher security margin than Rijndael; however, Rijndael with 10 rounds is faster and easier to implement for small blocks."
I don't know that nobody talks about Serpent solely because it was not chosen as winner. It may just be that Rijndael with 256-bit keys is universally considered secure and is more efficient at doing its job.
Re: BLAKE2, I'm not sure it's fair to say that BLAKE2 is more widely used overall. But I do agree BLAKE2 is a bit of an outlier in terms of adoption. I think part of the reason is that SHA2 remains the go-to option, else I'd expect the ecosystem to consolidate around SHA3.
Re: Serpent, there are many things to unpack here but, in summary, you don't know a priori how large of a security margin you need (given the primary function of a cipher, you want to pick the conservative option), efficiency concerns become much less relevant with hardware-accelerated implementations and years of Moore's law performance uplifts, low-power devices can take advantage of much lighter algorithms than Rijndael OR Serpent, ease of implementation does not equal ease of correct/secure implementation vis-a-vis side channel attacks, and certainly if Serpent was chosen you wouldn't see Rijndael talked about much.
Blake2 also uses a very SHA2-like construction (a HAIFA construction, which is based on Merkle-Damgard). I believe this was the main reason SHA3 was chosen to be something completely different (a sponge construction). If SHA2 was found to be insecure, Blake2 would be at more risk of also being broken than Keccak.
Speculatively, if SHA2 is broken without breaking Merkle-Damgard hashes in general, Blake2/3 could well become SHA4.
> I'm not sure it's fair to say that BLAKE2 is more widely used overall
Ah, maybe my experience is biased then. I keep coming across BLAKE2 implementations, but rarely hear so much as people considering to use SHA-3 somewhere. If anyone has actual numbers on this, that would be interesting.
It would be good if SHA-3 is being used because then chip makers have a reason to bake it into their hardware, which is exactly where the biggest gain over SHA-2 is expected. If that happens, and all else being equal (no cracks appear in Keccak), I'd be surprised if BLAKE2 remains as popular!
> you don't know a priori how large of a security margin you need
True, so this can be argued to be an educated guess at first. But then confidence increases over time. It seems to be expected that, more than 20 years later, people aren't considering Serpent anymore. Is it because it wasn't chosen as AES? Certainly partially, but BLAKE2 (I'll admit it does seem like an outlier) likely will still be talked about in the future so standardization is not the only factor.
I didn't see actual benchmarks, but Serpent sounds at least three times slower than Rijndael for, by now, no tangible benefit. What would be interesting is if there were AES competitors that are also fully unbroken and are more efficient than Rijndael, or easier to implement, etc.
To save you some time, one software evaluation is on page 531. Serpent performs worse in software than Rijndael (AES) just about everywhere (note they use categories rather than precise metrics, but you can dig into that if you want). By contrast, one hardware evaluation is on page 539. Serpent has the highest throughput for the lowest "area" i.e. required. These results repeat on p541.
So it depends on whether you are comparing a software or hardware implementation.
I wish chip makers would bake the elliptic curve used in Bitcoin and Ethereum (secp256k) as well, instead of the entire industry coalescing around secp256r, which many suspect was somehow weaker (since its parameters are some weird large number X instead of a hard-to-game number like 15, leading some to believe that the first X-1 candidates were tried and X was found to be weaker).
The real reason I would have liked that to be the case is so that one could use WebAuthn and Subtle Web Crypto to sign things and have the blockchain natively verify the signature.
As it is, I am hoping that EVM will roll out a precompiled signature verifier for secp256r, which is on the roadmap — they say!
There are a few different on-chain implementations of secp256r1 signature verification for use with passkeys, my favorite of which is demoed at https://p256.alembic.tech
Work is also being done on SNARK-based cross-curve signature verification
But I fully agree, especially with the growing popularity of account abstraction, the EVM desperately needs a secp256r1 precompile!
I fully admit to having a weak spot for Serpent - it is self-bitslicing (see the submission package or the linux kernel tree), which in hindsight makes constant time software easier to write, and it was faster in hardware even when measured at the time, which is where we have ended up putting AES anyway (e.g. AES-NI etc).
BUT. On security margins, you could argue the Serpent designers were too conservative: https://eprint.iacr.org/2019/1492
It is also true that cryptanalytic attacks appear to fare slightly better against AES than Serpent. What does this mean? A brute force attack has the same number of operations as the claimed security level, say, 2^128 for 128-bit. An attack is something better than this: fewer operations. All of the attacks we know about achieve slightly less than this security level - which is nonetheless still impossible to do - but that comes at a cost: they need an infeasible amount of memory. In terms of numbers: 9000 TB to reduce 2^128 to 2^126 against full-round AES according to a quick check of wikipedia. For reference, the lightweight crypto competition considered 2^112 to be sufficient margin. 2^126 is still impossible.
In practice, the difference between Serpent and AES in terms of cryptanalytic security is meaningless. It is not an example of NIST picking a weaker algorithm deliberately, or I would argue, even unintentionally. It (AES) was faster when implemented in software for the 32-bit world that seemed to be the PC market at the time.
Implemented correctly, I agree the difference in security margin may not be too important. Otherwise, Serpent is more resistant to timing attacks. Weaknesses in implementation are as important as weaknesses in design.
Regardless, the comparison wasn't intended to argue for a meaningful difference in security margin, but to show that that the winner of the competition, well, wins (in adoption).
Thanks for digging that paper out again. It is really telling that AES only gets a bit of a bump (10-30%) while the other ones gain like 2x or more.
I was about to comment that the competitors to AES were definitely too conservative, and it bit them because of how much slower it made them in software and larger in hardware.
The Blowfish key-schedule algorithm is equivalent to encrypting 4kB of data with it. This isn't a problem for some use-cases (e.g. transferring a large file over HTTPS), but terrible for others e.g. a encrypting lots of short messages using different keys without being able to cache > 30x larger result of the key-schedule result. To make it worse the cipher uses four large 256 x 32bit S-boxes with data (key and plaintext) dependent indexes making it very hard to implement fast without adding a timing side-channel on anything more complex than a simple microcontroller. It also does very little computation per memory access. Blowfish is a fast cipher on a very simple 32bit CPU with >= 4kiB of fast memory, but modern CPUs offer a lot more compute throughput than memory throughput. There is also very little opportunity to exploit for even the most expensive OoO CPUs because almost every depends on a data dependent memory access within a few instructions. For these reasons it's also expensive and relatively slow to implement in hardware.
Almost all of these downsides are helpful for password has validation function like bcrypt() because there is nothing to an attacker can to guess much faster than a desktop CPU.
Blowfish was a good cipher at a time when CPUs lacked dedicated trustworthy crypto engines, wide and deep OoO execution capability, and packed-SIMD support. AES and SHA1/2 are commonly implemented in hardware on modern server, desktop and mobile CPUs. Where hardware offloading isn't available ciphers can take advantage of OoO and SIMD to perform vastly more useful work per cycle than stalling on memory accesses.
Correct me if I'm wrong, everything is also being done out in the open for everyone to see. The NIST aren't using some secret analysis to make any recommendations.
Teams of cryptographers submit several proposals (and break each other's proposals). These people are well respected, largely independent, and assumed honest. Some of the mailing lists provided by NIST where cryptographers collaborated to review each other's work are public
NIST may or may not consort with your friendly local neighborhood NSA people, who are bright and talented contributors in their own right. That's simply in addition to reading the same mailing lists
At the end, NIST gets to pick a winner and explain their reasonning. What influenced the decision is surely a combination of things, some of which may be internal or private discussions
> NIST may or may not consort with your friendly local neighborhood NSA people
It is worth noting that while breaking codes is a big part of the NSA's job, they also have a massive organization (NSA Cybersecurity, but I prefer the old name Information Assurance) that works to protect US and allied systems and cryptographic applications.
In the balance, weakening American standards does little to help with foreign collection. Their efforts would be much better spent injecting into the GOST process (Russia and friends) or State Cryptography Administration (China and friends).
> In the balance, weakening American standards does little to help with foreign collection.
While that makes logical sense, the previous actions of the NSA has demonstrated they're not a logical actor in regards to this stuff, or that there's more going on.
> In the balance, weakening American standards does little to help with foreign collection.
Though it can be greatly beneficial for domestic collection. Further, so long as the US remains a dominant player in Tech and Tech-influenced fields like finance, odds are a lot of the world is going to be at least de facto using US standards.
> I filed a FOIA request "NSA, NIST, and post-quantum cryptography" in March 2022. NIST stonewalled, in violation of the law. Civil-rights firm Loevy & Loevy filed a lawsuit on my behalf.
> That lawsuit has been gradually revealing secret NIST documents, shedding some light on what was actually going on behind the scenes, including much heavier NSA involvement than indicated by NIST's public narrative.
even if I had never heard of DUAL_EC_whatsit, there's enough here to make me mistrust NIST.
He/she means that there have been good things coming out of the NSA/NIST collaborations (another example is SHA0->SHA1, introducing a "mysterious" left shift that made SHA1 much stronger), and the bad ones are caught quickly.
How so? Or rather, taking change for a given, what are believable indicators that a secret organization outside normal systems of law and publicity has changed _for the better_? After all, the Snowden relevations lead not to the NSA deciding that creating a global panopticon for a super-surveillance state would be a bad idea, but rather them doing their damnedest that never again the American public would be informed of the true scale of their dystopian actions.
I'm sure the NSA 9-5ers justify weakening standards processes by the fact it's still secure enough to be useful for citizens and some gov orgs but flawed enough to help themselves when it matters at x point in the future.
No one can say they pushed some useless or overtly backdoored encryption. That's rarely how Intel agencies work. It's also not how they need to work to maintain their effectiveness indefinitely.
When the CIA is trying to recruit for HUMINT if they can get claws into anything whether it's a business conference that has a 0.1% chance they'll meet some pliable young but likely future industry insider that may or may not turn into a valuable source then they'll show up to every single year to that conference. It's a matter of working every angle you can get.
They aren't short of people, time, or money. And in security tiny holes in a dam turn into torrents of water all the time.
The fact NIST is having non public backroom meetings with NSA, concealing NSA employee paper authors, generating a long series of coincidental situations preferencing one system, and stonewalling FIOAs from reputable individuals. IDK, if was a counter intelligence officer in charge of detecting foreign IC work I'd be super suspicious of anything sold as safe and open from that org.
> everything is also being done out in the open for everyone to see
Well, everything apart from the secret stuff:
"I filed a FOIA request "NSA, NIST, and post-quantum cryptography" in March 2022. NIST stonewalled, in violation of the law. Civil-rights firm Loevy & Loevy filed a lawsuit on my behalf.
That lawsuit has been gradually revealing secret NIST documents, shedding some light on what was actually going on behind the scenes, including much heavier NSA involvement than indicated by NIST's public narrative"
Thing is... no lawsuit will ever reveal documents directly against the USA's national interest.
Every single document will be reviewed by a court before being opened up, and any which say "We did this so we can hoodwink the public and snoop on russia and china" won't be included.
There is a final standardization step where NIST selects constants, and this is done without always consulting with the research team. Presumably, these are usually random, but the ones chosen for the Dual-EC DRBG algorithm seem to have been compromised. SHA-3 also had some suspicious constants/padding, but that wasn't shown to be vulnerable yet.
The problem with Dual EC isn't the sketchy "constants", but rather the structure of the construction, which is a random number generator that works by doing a public key transformation on its state. Imagine CTR-DRBG, but standardized with a constant AES key. You don't so much wonder about the provenance of the key so much as wonder why the fuck there's a key there at all.
I don't know of any cryptographer or cryptography engineer that takes the SHA3 innuendo seriously. Do you?
Additional backstory that might be helpful here: about 10 years ago, Bernstein invested a pretty significant amount of time on a research project designed to illustrate that "nothing up my sleeves" numbers, like constants formed from digits of pi, e, etc, could be used to backdoor standards. When we're talking about people's ability to cast doubt on standards, we should keep in mind that the paragon of that idea believes it to be true of pi.
I'm fine with that, for what it's worth. Cryptography standards are a force for evil. You can just reject the whole enterprise of standardizing cryptography of any sort, and instead work directly from reference designs from cryptographers. That's more or less how Chapoly came to be, though it's standardized now.
I do know a few cryptographers who were suspicious of SHA-3 when it came out, but after some napkin math and no obvious hole was found, they were fine with it. The actual goal of that extra padding was to get extra one bits in the input to avoid possible pathological cases.
My understanding of the Dual-EC problem may be different than yours. As I understand it, the construction is such that if you choose the two constants randomly, it's fine, but if you derived them from a known secret, the output was predictable for anyone who knows the secret. The NIST did not provide proof that the constants used were chosen randomly.
Random choice would be equivalent to encrypting with a public key corresponding to an unknown private key, while the current situation has some doubt about whether the private key is known or not.
Even with a verifiably random key, Dual EC is still unacceptable.
First, because its output has unacceptable biases [1,2].
Second, because its presence allows an attacker to create a difficult-to-detect backdoor simply by replacing the key, as apparently happened with Juniper NetScreen devices [3,4].
[2] Berry Schoenmakers and Andrey Sidorenko, Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator, May 2006. Online: https://eprint.iacr.org/2006/190.pdf
[3] Stephen Checkoway, Jacob Maskiewicz, Christina Garman, Joshua Fried, Shaanan Cohney, Matthew Green, Nadia Heninger, Ralf-Philipp Weinmann, Eric Rescorla, and Hovav Shacham, A Systematic Analysis of the Juniper Dual EC Incident, October 2016. Online: https://www.cs.utexas.edu/~hovav/dist/juniper.pdf
[4] Ben Buchanan, The Hacker and the State, chapter 3, Building a Backdoor. Harvard University Press, February 2020.
"Verifiably random" means produced using a process where it isn't possible for you to know the outcome. In this case, saying "the key is [X], which is the SHA-2 hash of [Y]" would allow you to know that they couldn't choose [X] without breaking SHA-2.
