Why should symmetric block cyphers be efficient?

Question

If I remember well, AES (then named Rijndael) won the competition because it was slightly faster to implement as one of its competitors, Serpent, which erred on the side of caution, using 32 rounds as where most probably, 16 rounds would have been sufficient. In a way, the competition was rewarding "highest security per clock cycle" (way of speaking). That was almost 2 decades ago, when computers were still much slower than today, so clock cycles were still expensive, and too heavy cryptographic burdens might make it hard to use on home computers. However, today the problems of encryption are rather the large amounts of brute force that one can apply. This is why one uses "inefficient" key derivation functions, to slow down brute force.

My question is: why doesn't this apply to block cyphers ? Wouldn't it be a good idea to have "inefficient" and slow block cyphers ? Wouldn't something like Serpent, but even with say, 4096 rounds, be preferable over an efficient algorithm like AES, so that it takes much more time to use in a brute force attack ?

Answer 1

Slowing block ciphers by increasing the number of rounds is an idea that does not catch because

• Compared to 15 years ago, the volume of data routinely enciphered by a computer has grown much more than the frequency of its CPU (even multiplied by number of cores and IPC improvements). Hence speed of ciphers is more important than it ever was. Correspondingly, we see AES implemented in hardware (giving a huge speedup) or faster ciphers (like Chacha) increasingly used.

• Increasing the number of rounds would only give the equivalent of a few bits more key in term of resistance to brute force; so if we want more resistance to brute force, we just use a wider key, and avoid a huge performance drop. For illustration: 4096 rounds instead of the regular 32 in Serpent makes brute force about 128 times harder, that's the equivalent of 7 extra bits of key (since 128 is 2⁷); these few bits are negligible when AES candidates came in 128, 192 and 256-bit key size variants (going from 128 to 192 bits is an extra 64 bits, that is about 16 million million million times harder by brute force).

There are applications for slow cryptography: in particular password-based encryption, where a password is used as key of a cipher. In that application, we need something slow to mitigate the risk of brute force password search. But using a block cipher with many rounds would be very misguided, because for legitimate use one needs to make all the rounds for each block encrypted, when the attacker only needs to make all the rounds for the first block during most of the attack. Instead, what works best is making many rounds in an initial transformation from password to key (key streching), then using a regular (fast) cipher.

_{Rant: Sadly, many programs implement that poorly. For example, 7zip's AES encryption uses a fixed 1000 iterations of hashing (line 27 of WzAes.cpp there), leaving it needlessly vulnerable to brute force password search. Even GPG 1.x comes out of the box with insufficient settings for passphrase-to-key transformation as used to protect private keys at rest, and the following arcane settings beefing it up to the max are not entirely satisfying:}

s2k-mode 3               # iterated hashing (that's the default)
s2k-count 65011712       # maximum supported number of iterations
s2k-digest-algo SHA512   # one of the slowest/widest hash supported
s2k-cipher-algo AES256   # no incentive to use a narrower key

Answer 2

This question can be generalized to the question why ciphers should be quick. There are several reason why encryption/decryption needs to be quick even today:

• Faster to implement aka (easier to implement): the easier it is to implement, the less likely it is for an developer to make an mistake when implementing the cipher for a given system and thus decreasing the risk of a faulty encryption.

• Embedded devices: Embedded devices are still heavily resource bound. A ciphers needs to be quick even on those system, specially when they are operating with real-time criteria.

• Increased encrypted data: Nowadays a good developer will encrypt the whole traffic, even if it may not be sensitive data. The amount of data rose with the increase of available computing power. Same goes for data that isn't send over a channel even. Nobody wants to wait till his/her 200GB backup is encrypted on the disk.

In the end it all comes down to user experience. Nobody wants to wait for a website to load, so nobody wants to wait for data to be encrypted. Also if wen can cut off cycles for encryption, we can use the available cycles for something else.

EDIT: KDFs itself have nothing to do with block ciphers. While KDFs create from a low entropy source a higher entropy source, ciphers encrypt data given a key. Both are building blocks in a crypto system. DKFs are usually used to generate more secure passwords and prevent an attacker from brute forcing it due the higher amount of computing time they take.

See it this way: Chipers such as AES are fast, because they work with the assumption that the key used is of high enough entropy. KDFs are slow because they work with the assumption that the key used is of low entropy. Together both can be used to create a strong crypto system:

Low Entropy Key --- KDF ---> High Entropy Key (one time; slow)

High Entropy Key + Data --- AES Encrypt ---> Encrypted Data (many times; fast)

High Entropy Key + Encrypted Data --- AES Decrypt ---> Data (many times; fast)

All a user now has to do is to remember his low entropy key. Or if he needs performance his high entropy key.