4 ms·

Absolutely, but NIST ultimately choose the winners, giving them the option to pick (non-obviously) weak/weaker algorithms. Historically only the winners are ado

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?

zahllos 3y ago
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 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.
- kpdemetriou 3y ago
  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).
- bsder 3y ago
  > BUT. On security margins, you could argue the Serpent designers were too conservative: https://eprint.iacr.org/2019/1492 https://eprint.iacr.org/2019/1492 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.
lucb1e 3y ago
> 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.
- kpdemetriou 3y ago
  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.
kevin_thibedeau 3y ago
Blowfish has a continuing existence as the basis for bcrypt.
- tptacek 3y ago
  It works as a password hash for reasons having in part to do with why it isn’t a great general purpose cipher.
  - bonzini 3y ago
    Can you expand, or link to an explanation?
    - aidenn0 3y ago
      Blowfish has an unusually slow key-setup phase. Slowness is an advantage for password hashes, since it makes offline attacks harder.
    - crest 3y ago
      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.

zahllos 3y ago

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

kpdemetriou 3y ago
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).
bsder 3y ago
> BUT. On security margins, you could argue the Serpent designers were too conservative: https://eprint.iacr.org/2019/1492 https://eprint.iacr.org/2019/1492 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.

lucb1e 3y ago

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

kpdemetriou 3y ago
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.

kevin_thibedeau 3y ago

Blowfish has a continuing existence as the basis for bcrypt.

tptacek 3y ago
It works as a password hash for reasons having in part to do with why it isn’t a great general purpose cipher.
- bonzini 3y ago
  Can you expand, or link to an explanation?
  - aidenn0 3y ago
    Blowfish has an unusually slow key-setup phase. Slowness is an advantage for password hashes, since it makes offline attacks harder.
  - crest 3y ago
    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.