Block Cipher Structures: Ranked

If you’re like most people, you don’t have strong opinions about the internal structures of block ciphers. You’re likely perfectly happy using something standard in a standard construction, offered through a standard cryptography library, without ever giving too much thought to what’s going on under the hood.

If the fursona wasn’t a dead give-away, I’ve long since embraced abnormality.

Before we get started, let me give you a bit of my background and a standard disclaimer:

At multiple points in my career, I’ve had to implement cryptographic primitives–usually due to either a lack of availability in the programming language in question, or I looked at the existing implementations and side-channels fell out (which at one point prompted my team to jokingly prohibit me from looking at code on Fridays, lest I find a security issue and ruin everyone’s weekend plans).

Howevear, I am not a designer of cryptography primitives. There are cryptographers who specialize in this, who might have a more correct opinion than mine. If your cryptographer tells you I’m wrong, listen to them. I’m (almost certainly) not your cryptography expert.

Block Cipher Structures

Feistel Ciphers

Examples: DES (and Triple-DES), Blowfish, Lucifer, Camellia, Twofish

Anyone who has tried to study cryptography will be familiar with Feistel ciphers. The most commonly used Feistel ciphers today are Triple-DES and Blowfish (unfortunately).

Feistel ciphers have a lot going for them. A three-round Feistel network with a secure pseudorandom function seeded by distinct round keys is sufficient to build a pseudorandom permutation (and thus, a block cipher). A fourth round gives you a *strong* pseudorandom permutation.

They’re also rather simple constructions, too:

1. Take your input, cut it in half. Call one half L, the other R.
2. For each round: Apply the PRF to R (without overwriting R) with the key for this round, then XOR the PRF output with L.
3. Swap the L and R after each round.

However, most Feistel networks in use today operate on 64-bit blocks (where the left and right values are each 32-bit integers, which was convenient for the processors of the day). Block ciphers with 64-bit block ciphers are not secure by modern standards.

Notable exceptions to this disqualification, which use 128-bit blocks:

• TwoFish (AES finalist)
• Camellia (Japan/EU approved AES-alternative cipher)

Soatok’s Ranking: C-Tier

Substitution-Permutation Networks

Examples: AES (Rijndael)

I’ve complained about AES before. My complaints about AES are generalizable for the entire class of ciphers that AES belongs to:

There are other SPN ciphers besides AES, but it’s the only one in widespread use in 2021. So that’s the one I’m going to talk about here.

The existence of an S-Box invites programmers to implement a table look-up, and thereby introduce cache-timing vulnerabilities in their cipher.

AES usually gets around this by being implemented in hardware. Intel calls this AES-NI, but the same general idea applies everywhere.

If your CPU doesn’t have dedicated AES instruction sets, you can either be insecure and fast, or you can be secure but slow.

However, if you can bypass this implementation foot-gun, the underlying math works out and SPNs are really neat. After 20 years of protecting most of the traffic on the Internet, most of the cryptanalysis advances against AES (aside from side-channels) fail to keep cryptographers up at night.

Soatok’s Ranking: B-Tier

Add-Rotate-XOR Ciphers

Examples: Salsa20, ChaCha, XXTEA

Strictly speaking: ARX gives you a pseudorandom function, which leads to them normally being used for hash functions (e.g. SHA-2, BLAKE).

However, if you designate a part of the internal ARX structure to hold a key, nonce, and internal counter, you can turn a fast PRF into a stream cipher (where the underlying block is successive PRF outputs).

Because ARX ciphers only use the Add, Rotate, and XOR operations (where Rotate can be implemented with bit-shifts and bitwise OR), it’s very easy to implement ARX constructions in constant-time.

As an implementor, I feel 100x more confident working with an ARX design than a Substitution-Permutation Network (SPN).

Soatok’s Ranking: A-Tier

Permutation-based Ciphers

Examples: Gimli, Xoodoo

Despite the name that search engines confuse for transposition ciphers (which belong in classical cryptography, not modern cryptography), permutations are really cool. (They’re not, strictly speaking, block ciphers, but they bear mentioning because of how cool they are.)

To wit, here’s the entire reference implementation of Gimli:

#include <stdint.h>

uint32_t rotate(uint32_t x, int bits)
{
  if (bits == 0) return x;
  return (x << bits) | (x >> (32 - bits));
}

extern void gimli(uint32_t *state)
{
  int round;
  int column;
  uint32_t x;
  uint32_t y;
  uint32_t z;

  for (round = 24; round > 0; −−round)
  {
    for (column = 0; column < 4; ++column)
    {
      x = rotate(state[    column], 24);
      y = rotate(state[4 + column],  9);
      z =        state[8 + column];

      state[8 + column] = x ^ (z << 1) ^ ((y&z) << 2);
      state[4 + column] = y ^ x        ^ ((x|z) << 1);
      state[column]     = z ^ y        ^ ((x&y) << 3);
    }

    if ((round & 3) == 0) { // small swap: pattern s...s...s... etc.
      x = state[0];
      state[0] = state[1];
      state[1] = x;
      x = state[2];
      state[2] = state[3];
      state[3] = x;
    }
    if ((round & 3) == 2) { // big swap: pattern ..S...S...S. etc.
      x = state[0];
      state[0] = state[2];
      state[2] = x;
      x = state[1];
      state[1] = state[3];
      state[3] = x;
    }

    if ((round & 3) == 0) { // add constant: pattern c...c...c... etc.
      state[0] ^= (0x9e377900 | round);
    }
  }
}

Permutations like Gimli and Xoodoo are fast, secure, obviously constant-time, and have a small code footprint–which makes them attractive for lightweight cryptography. (See also: NIST’s lightweight cryptography project.)

However, permutations are still relatively new to cryptography. The only standard permutation-based construction available today is SHA-3 (which, more specifically, uses a sponge construction–which is based on a large permutation).

The only common complaint levied against SHA-3 today is that they set the security requirements too high, so it’s slower than it needed to be (although there appears to be some interest in hardware-accelerating SHA-3 in the future).

Because the internal state for permutations can be secure at relatively small sizes (for lightweight cryptography), and can be safely implemented at relatively large sizes (e.g. for encrypting practically unlimited data under a single key), modern symmetric cryptography research is likely to focus on permutations.

Soatok’s Ranking: S-Tier (or A+ Tier if that’s easier to understand)

Closing Thoughts

There are probably significant classes of ciphers I’ve omitted in this ranking. For example, dedicated stream ciphers like RC4 that don’t have an underlying block cipher. (But you shouldn’t use RC4!)

If you’re interested in something more practical than this post, you might want to read my comparison of symmetric encryption modes.

Correction: @erincandescent points out that Salsa20 and ChaCha (from the ARX section above) are also permutations:

Mea culpa! We were talking about general-purpose permutations in the latter section, but I didn’t delineate the two clearly enough.