Although they are omnipresent in constrained environments and lightweight protocols, small (32-bit, 64-bit) block ciphers have a bad reputation. They are perceived as something antiquated, insecure, and to stay away from for any new application, especially in software implementations.
To some extent, thinking that way is safe, and as a general building block, larger block ciphers are more versatile and provide improved security and usage limits than small block ciphers. In fact, due to modern applications and protocols, the trend in some contexts is to realize that 128 bits are not enough, and shift to large block ciphers such as Rijndael-256 and Vistrutah (NIST submission), part of NIST’s wide-block standardization effort, or public permutations such as Keccak.
The main problem with small block ciphers is that well… they are small. Generally, we want the set of possible inputs and outputs to be large enough that it’s practically impossible to enumerate. If that set is small, that doesn’t hold true. Generally, we also want the output of a cipher to be indistinguishable from random for an adversary. But with a 32-bit block cipher, collisions become likely around 216 blocks for a given key, and the distinguishing advantage only grows from there, which is ridiculously low. Using them securely is possible, but requires very careful design of application-specific protocols.
Nonetheless, small block ciphers can remain very useful, even in modern applications because in spite of their limitations, they remain block ciphers.
Block ciphers
A block cipher is a fundamental building block in symmetric cryptography.
Imagine a list of N elements. Then, you put them all in a bag, shake the bag really well, and randomly grab all the elements one by one, to form a new list. There are still N elements, just in a completely different order. The first one may now be the 23948234th one, etc. We just applied a random-looking permutation.
If we know what the permutation is, we can easily invert the process, and map element 23948234 back to the first one.
A block cipher is a set of two functions:
A function P(k, x) -> x' that takes a secret key k , generates a random-looking permutation from it, and returns the image of x under that permutation.
... continue reading