Key clustering: Difference between revisions
Content deleted Content added
Key clustering was wrong described as key/hash collision. The correct of clustering can be find here: https://en.wikipedia.org/wiki/Hash_table |
|||
| Line 1: | Line 1: | ||
{{Unreferenced|date=July 2017}}{{Orphan|date=February 2009}} |
{{Unreferenced|date=July 2017}}{{Orphan|date=February 2009}} |
||
Key or hash function should avoid ''[[Hash table|clustering]]'', the mapping of two or more keys to consecutive slots. Such clustering may cause the lookup cost to skyrocket, even if the load factor is low and collisions are infrequent. The popular multiplicative hash<sup>[[Hash table#cite%20note-knuth-3|[3]]]</sup> is claimed to have particularly poor clustering behaviour.<sup>[[Hash table#cite%20note-%3A0-9|[9]]]</sup> |
|||
'''Key clustering''', in [[cryptography]], is two different [[key (cryptography)|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 a [[brute-force attack]], trying all possible keys until it finds the correct key, key clustering makes it easier to attack a particular cipher text. If there are ''n'' possible keys without any key clustering, the attacker needs to try an average of ''n''/2 keys to decrypt it and no more than ''n'' keys. If there are two keys that are clustered, the average number of keys is reduced to ''n''/4 and the maximum is ''n''-1 keys. If three keys cluster, the average attempt is only ''n''/6 attempts. |
|||
reference: CISSP Common Body of Knowledge Review by Alfred Ouyang, 2012 retrieved from site ://opensecuritytraining.info/CISSP-5-C_files/5-Cryptography-Part1.pdf |
|||
[[Category:Key management]] |
[[Category:Key management]] |
||
Revision as of 02:20, 21 June 2019
 |
Key or hash function should avoid clustering, the mapping of two or more keys to consecutive slots. Such clustering may cause the lookup cost to skyrocket, even if the load factor is low and collisions are infrequent. The popular multiplicative hash[3] is claimed to have particularly poor clustering behaviour.[9]
 | This cryptography-related article is a stub. You can help Wikipedia by expanding it. |