Key clustering

From Wikipedia, the free encyclopedia

This article or section is in need of attention from an expert on the subject.
Please help recruit one or improve this article yourself. See the talk page for details.
Please consider using {{Expert-subject}} to associate this request with a WikiProject

In cryptography, key clustering is said to occur when two different keys generate the same ciphertext from the same plaintext, 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.

Assume that there is a plaintext P, two different keys, K1 and K2, and an algorithm A. Ciphertexts C1 and C2 with the two keys are generated as follows:

P → A(K1) → C1

P → A(K2) → C2

C1 should not equal C2, if they do then key clustering has occurred.

[edit] 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 with out 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.