Collision (computer science)

Collision (computer science)

Not to be confused with wireless packet collision.

In computer science, a collision or clash is a situation that occurs when two distinct pieces of data have the same hash value, checksum, fingerprint, or cryptographic digest.[1]

Collisions are unavoidable whenever members of a very large set (such as all possible person names, or all possible computer files) are mapped to a relatively short bit string. This is merely an instance of the pigeonhole principle.[1]

The impact of collisions depends on the application. When hash functions and fingerprints are used to identify similar data, such as homologous DNA sequences or similar audio files, the functions are designed so as to maximize the probability of collision between distinct but similar data. Checksums, on the other hand, are designed to minimize the probability of collisions between similar inputs, without regard for collisions between very different inputs.[citation needed]

In most other applications, however, collisions of any kind are equally undesirable. Any collision in a hash table increases the average cost of lookup operations. When fingerprints are used to avoid unnecessary file storage or transfer, e.g. in a proxy server or backup system, a collision may cause incorrect operation and even permanent data loss. A successful collision attack on a cryptographic hash function may compromise the security of computer and communication systems. Therefore, much effort is devoted to the design of algorithms that minimize the occurrence of collisions for various applications.

In the context of cryptographic hash functions, the inability of an adversary to compute collisions efficiently is often essential to the security of the protocol. A collision-free hash function is a type of one-way function that formalizes this property: it is not possible for a randomized polynomial-time algorithm to locate a collision of a collision-free hash function with non-negligible probability. It is unknown whether such a function exists.

References

  1. ^ a b Jered Floyd (2008-07-18). "What do Hash Collisions Really Mean?". http://permabit.wordpress.com/: Permabits and Petabytes. http://permabit.wordpress.com/2008/07/18/what-do-hash-collisions-really-mean/. Retrieved 2011-03-24. "For the long explanation on cryptographic hashes and hash collisions, I wrote a column a bit back for SNW Online, “What you need to know about cryptographic hashes and enterprise storage”. The short version is that deduplicating systems that use cryptographic hashes use those hashes to generate shorter “fingerprints” to uniquely identify each piece of data, and determine if that data already exists in the system. The trouble is, by a mathematical rule called the “pigeonhole principle”, you can’t uniquely map any possible files or file chunk to a shorter fingerprint. Statistically, there are multiple possible files that have the same hash." 

See also


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Lock (computer science) — In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies. Contents 1 Types 2… …   Wikipedia

  • Namespace (computer science) — For namespaces in general, see Namespace. A namespace (sometimes also called a name scope) is an abstract container or environment created to hold a logical grouping of unique identifiers or symbols (i.e., names). An identifier defined in a… …   Wikipedia

  • Computer network — Computer networks redirects here. For the periodical, see Computer Networks (journal). Datacom redirects here. For other uses, see Datacom (disambiguation). Internet map. The Internet is a global system of interconnected computer networks that… …   Wikipedia

  • Collision resolution — may refer to Hash table implementations in computer science Collision response in classical mechanics This disambiguation page lists articles associated with the same title. If an internal lin …   Wikipedia

  • computer — computerlike, adj. /keuhm pyooh teuhr/, n. 1. Also called processor. an electronic device designed to accept data, perform prescribed mathematical and logical operations at high speed, and display the results of these operations. Cf. analog… …   Universalium

  • Collision avoidance (networking) — In computer networking and telecommunication, collision avoidance methods try to avoid resource contention by attempting to avoid simultaneous attempts to access the same resource. Collision avoidance methods include prior scheduling of timeslots …   Wikipedia

  • Computer Go — Part of a series of articles on Go (board game) Game specifics Go rules Go handicaps Go proverbs Go terms Go strategy and tactics Fuseki (whole board openings) Joseki (corner based openings) Life and death Tsumego …   Wikipedia

  • Collision Course (Space: 1999) — Collision Course Space: 1999 episode Episode no. Season 1 Episode 13 Directed by Ray Austin Written by …   Wikipedia

  • Collision cascade — A classical molecular dynamics computer simulation of a collision cascade in Au induced by a 10 keV Au self recoil. This is a typical case of a collision cascade in the heat spike regime. Each small sphere illustrates the position of an atom, in… …   Wikipedia

  • Collision detection — For collision detection on networks see CSMA/CD Collision detection typically refers to the computational problem of detecting the intersection of two or more objects. While the topic is most often associated with its use in video games and other …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”