Key clustering: Difference between revisions

Revision as of 20:19, 17 January 2007

Latest revision as of 17:58, 21 August 2021

(29 intermediate revisions by 23 users not shown)

Line 1:

{{Multiple issues|

{{Cleanup|April 2006}}

{{Refimprove|date=November 2019}}

{{expert}}

{{Confusing|date=June 2020}}

}}

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 [[hash collision|collisions]] are infrequent. The popular multiplicative hash<ref>{{cite book | first=Donald |last=Knuth |author1-link=Donald Knuth | title = The Art of Computer Programming | volume = 3: ''Sorting and Searching'' | edition = 2nd | publisher = Addison-Wesley | year = 1998 | isbn = 978-0-201-89685-5 | pages = 513–558 }} {{verify source |date=September 2019 |reason=This ref was deleted Special:Diff/902760856 by a bug in VisualEditor and later restored by a bot from the original cite located at Special:Permalink/895004660 cite #3 - verify the cite is accurate and delete this template. [[User:GreenC bot/Job 18]]}}</ref> is claimed to have particularly poor clustering behaviour.<ref>{{Cite web|title = Prime Double Hash Table|url = https://www.concentric.net/~Ttwang/tech/primehash.htm|date = March 1997|accessdate = 2015-05-10|last = Wang|first = Thomas|archiveurl = https://web.archive.org/web/19990903133921/http://www.concentric.net/~Ttwang/tech/primehash.htm|archivedate = 1999-09-03}} {{verify source |date=September 2019 |reason=This ref was deleted Special:Diff/902760856 by a bug in VisualEditor and later restored by a bot from the original cite located at Special:Permalink/895004660 cite #9 - verify the cite is accurate and delete this template. [[User:GreenC bot/Job 18]]}}</ref>

==References==

In [[cryptography]], '''key clustering''' is said to occur when two different [[key (cryptography)|keys]] generate the same [[ciphertext]] from the same [[plaintext]], using same [[cipher]] [[algorithm]]. A good cipher algorithm, using different keys on the same plaintext, should generate a different ciphertext, irrespective of the key length.

{{Reflist}}

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.

==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.

==External links==

*[http://ei.cs.vt.edu/~cs5604/cs5604cnCL/CL-illus.html Illustrations of Key-Clustering Concepts]

[[Category:Key management]]