Lesson plan
Hash collision
In computer science, a hash collision or hash clash is when two distinct pieces of data in a hash table share the same hash value. The hash value in this case is derived from a hash function which takes a data input and returns a fixed length of bits. Hash is typically used as a many-to-one function, with the number of potential inputs (size of input domain) much larger that the number of potential output values ("range"), making collisions inevitable ("pigeonhole principle"). For the cryptographic hash functions (CHFs), the output is a compact representative of particular input value used by data integrity algorithms to operate efficiently using this representative in place of the much larger input data. A collision violates the assumptions of integrity algorithms, so CHFs are designed to make finding a practical collision computationally infeasible (so-called collision resistance). The typical uses of non-cryptographic hash functions (NCHFs) – like bloom filters, hash tables, count sketches – are less sensitive to collisions, so NCHFs require just the uniform distribution and avalanche properties. Still, collision resistance is an additional feature that is useful against hash flooding attacks; simple NCHFs, like the cyclic redundancy check (CRC), have essentially no collision resistance and thus cannot be used with an input open to manipulation by an attacker.…
Article summary
In computer science, a hash collision or hash clash is when two distinct pieces of data in a hash table share the same hash value. The hash value in this case is derived from a hash function which takes a data input and returns a fixed length of bits. Hash is typically used as a many-to-one function, with the number of potential inputs (size of input domain) much larger that the number of potential output values ("range"), making collisions inevitable ("pigeonhole principle"). For the cryptographic hash functions (CHFs), the output is a compact representative of particular input value used by data integrity algorithms to operate efficiently using this representative in place of the much larger input data. A collision violates the assumptions of integrity algorithms, so CHFs are designed to make finding a practical collision computationally infeasible (so-called collision resistance). The typical uses of non-cryptographic hash functions (NCHFs) – like bloom filters, hash tables, count sketches – are less sensitive to collisions, so NCHFs require just the uniform distribution and avalanche properties. Still, collision resistance is an additional feature that is useful against hash flooding attacks; simple NCHFs, like the cyclic redundancy check (CRC), have essentially no collision resistance and thus cannot be used with an input open to manipulation by an attacker.…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.