Block Ciphers and (Non-)Generic Attacks

Question

I am currently reading through Cryptography Engineering and came across this definition of block cipher security:

Definition 2 An attack on a block cipher is a non-generic method of distinguishing the block cipher from an ideal block cipher.

Reading further, I find myself struggling to understand what the authors mean by a "non-generic attack" (and, conversely, a "generic attack"), which may be explained by what they say near the end of the relevant section:

That's why nobody has been able to formalise a definition of generic attacks and block cipher security.

Would anyone like a shot at attempting a definition of a generic attack and of a non-generic attack, particularly with respect to block ciphers?

Answer 1

As explained in a comment: A generic attack is one that works against all block-ciphers (with a given block and key size), without consideration about the structure of the block-cipher.

One generic attack for a block cipher of a given block size $b$ bits builds a dictionary of input/output pairs (e.g. from past plaintext/ciphertext), for a fixed key. When an input or output in that dictionary gets reused, the adversary gains an advantage. In many scenarios, that's expected after about $2^{b/2}$ blocks (less in ECB mode, more in CTR mode). Such attack works for any block cipher, including an hypothetical one implemented as a random permutation.

If we in addition consider the key size of $k$ bits, another generic attack, brute force key search, enumerates the keys. With at least $k/b+1$ input/output pairs, that's likely to find the key after about $2^{k-1}$ attempts.

Sometime we have a generic attack against a whole category of block ciphers sharing a common characteristic. For example, there's a generic attack against all Feistel ciphers, based on the fact that for any key, they implement an even permutation; this allows an adversary having built a dictionary of all input/output pairs except two of these, to deduce the remaining two with certainty. Another example (given in that answer) is an enhanced brute force key search removing most of the work associated to the first and/or last round in a Feistel cipher.

Answer 2

By a generic attack we also understand an attack that with minimal corrections would apply to every block cipher.

For example, suppose you have a (plaintext,ciphertext) pair and test keys by exhaustive search: you apply the keyed cipher $E_K$ to plaintext $P$ for every $K$ and check if you get ciphertext $C$ in response.

Quite often, the ciphertext bits are not a result of an atomary operation, but are obtained in portions: first 32 bits, then the next 32 bits etc. Then you could speed up your exhaustive search by checking the first 32 bits only, and do the rest only if those bits match. Here you may get an improvement up to 20-30%, depending on the cipher.

Clearly, such principle would apply to almost every cipher, so it is not called an attack, but if it is, then we say ``generic attack''.