Key clustering

Key clustering, in cryptography, is two different keys that generate the same ciphertext from the same plaintext by using the same cipher algorithm. A good cipher algorithm, using different keys on the same plaintext, should generate a different ciphertext irrespective of the key length.

If there is a plaintext P, two different keys K1 and K2, and an algorithm A, the two key generate ciphertexts C1 and C2 as follows:

P → A(K1) → C1

P → A(K2) → C2

Key clustering has occurred if C1 and C2 are the same, which should not occur.

Importance

If an 'attacker' tries to break a cipher by brute-force (trying all possible keys until it finds the correct key) then key clustering will result in an easier attack on a particular cipher text. If there are N possible keys without any key clustering then the attacker will on average need to try N/2 keys to decrypt it and a worst case of trying all N keys. If there are two keys that are clustered then the average number of keys to try is reduced to N/4 (worst case is N-1 keys). If three keys cluster than average attempt is only N/6 attempts.