NationMaster - Encyclopedia: Hash collision

In computer science, a hash collision or hash clash is a situation that occurs when two distinct inputs into a hash function produce identical outputs. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... A hash function is a reproducible method of turning some kind of data into a (relatively) small number that may serve as a digital fingerprint of the data. ...

All hash functions have potential collisions, though with a well-designed hash function, collisions should occur less often (compared with a poorly designed function) or be more difficult to find. In certain specialized applications where a relatively small number of possible inputs are all known ahead of time it is possible to construct a perfect hash function which maps all inputs to different outputs. However, many hash functions, including most cryptographic hash functions, produce a fixed size output from an arbitrarily long message. In such a design, there will always be collisions, because any given hash has to correspond to a very large number of possible inputs. Perfect hash functions are hash functions which guarantee O(1) operations complexity when used in a hash table. ... In cryptography, a cryptographic hash function is a hash function with certain additional security properties to make it suitable for use as a primitive in various information security applications, such as authentication and message integrity. ...

In searching

An efficient method of searching can be to process a lookup key using a hash function, then take the resulting hash value and then use it as an index into an array of data. The resulting data structure is called a hash table. As long as different keys map to different indices, lookup can be performed in constant time. When multiple lookup keys are mapped to identical indices, however, a hash collision occurs. The most popular ways of dealing with this are chaining (building a linked list of values for each array index), and open addressing (searching other array indices nearby for an empty space). Both of these, however, degrade the worst-case lookup complexity to linear time of the number of elements. In computer science, a hash table is a data structure that speeds up searching for information by a particular aspect of that information, called a key. ... In computer science, a hash table is a data structure that speeds up searching for information by a particular aspect of that information, called a key. ... In computational complexity theory, constant time refers to the computation time of a problem when the time needed to solve that problem doesnt depend on the size of the data it is given as input. ... In computer science, a linked list is one of the fundamental data structures, and can be used to implement other data structures. ... In computational complexity, an algorithm is said to take linear time, or O(n) time, if the time it requires is proportional to the size of the input, which is usually denoted n. ...

Collision resistance

Weak collision resistance: for a given

x

, it is hard to find a $y neq x$ such that

H (x) = H (y)

. A user inputs a value, in this example a password, called initial value (

x

). If the hash function

H

is weakly collision resistant, the probability of finding a second password with the same hash value as the initial one is negligible in the output length of the hash function. In mathematics, the Colombeau algebra is an algebra introduced with the aim of constructing an improved theory of distributions, in which multiplication is not problematic. ...

Strong collision resistance: it is hard to find any

x

and

y

such that

H (x) = H (y)

. If the hash function

H

is strongly collision resistant, the probability of finding any two passwords with the same hash value is negligible in the output length of the hash function. In mathematics, the Colombeau algebra is an algebra introduced with the aim of constructing an improved theory of distributions, in which multiplication is not problematic. ...

In cryptography

One desirable property of cryptographic hash functions is that it is computationally infeasible to find a collision. The value of a hash function can be used to certify an input is unchanged by publishing the signed value of the hash if it is not feasible to produce a collision. Feasible in this context refers to any algorithm with an asymptotic running time polynomial in the output length of the hash function, which is usually much faster than a brute-force birthday attack. The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek ÎºÏÏ…Ï€Ï„ÏŒÏ‚ kryptÃ³s hidden, and the verb Î³ÏÎ¬Ï†Ï‰ grÃ¡fo write or Î»ÎµÎ³ÎµÎ¹Î½ legein to speak) is the study of message secrecy. ... In cryptography, a cryptographic hash function is a hash function with certain additional security properties to make it suitable for use as a primitive in various information security applications, such as authentication and message integrity. ... A digital signature or digital signature scheme is a type of asymmetric cryptography used to simulate the security properties of a signature in digital, rather than written, form. ... A birthday attack is a type of cryptographic attack which exploits the mathematics behind the birthday paradox, making use of a space-time tradeoff. ...

The process of finding two arbitrary values whose hashes collide is called a collision attack; the process of finding one arbitrary value whose hash collides with another, given hash is called a preimage attack. A successful preimage attack is a much more serious break than a successful collision attack. In cryptography, a preimage attack on a cryptographic hash differs from a collision attack. ...

See also

References

External links

v • d • e

Cryptographic hash functions and Message authentication codes (MACs)

Hash algorithms: Gost-Hash | HAS-160 | HAVAL | MDC-2 | MD2 | MD4 | MD5 | N-Hash | RadioGatún | RIPEMD | SHA family | Snefru | Tiger | WHIRLPOOL | crypt(3) DES In cryptography, a cryptographic hash function is a hash function with certain additional security properties to make it suitable for use as a primitive in various information security applications, such as authentication and message integrity. ... A cryptographic message authentication code (MAC) is a short piece of information used to authenticate a message. ... GOST R 34. ... HAS-160 is a cryptographic hash function designed for use with the Korean KCDSA digital signature algorithm. ... HAVAL is a variable-length cryptographic hash function. ... In cryptography, MDC-2 (Modification Detection Code 2, sometimes called Meyer-Schilling) is a cryptographic hash function with a 128-bit hash value. ... Message Digest Algorithm 2 (MD2) is a cryptographic hash function developed by Ronald Rivest in 1989. ... MD4 is a message digest algorithm (the fourth in a series) designed by Professor Ronald Rivest of MIT in 1990. ... In cryptography, MD5 (Message-Digest algorithm 5) is a widely used cryptographic hash function with a 128-bit hash value. ... In cryptography, N-Hash is a cryptographic hash function based on the FEAL round function, and is now considered insecure. ... PANAMA is a cryptographic primitive which can be used both as a hash function and a stream cipher. ... RIPEMD-160 (RACE Integrity Primitives Evaluation Message Digest) is a 160-bit message digest algorithm (and cryptographic hash function) developed in Europe by Hans Dobbertin, Antoon Bosselaers and Bart Preneel, and first published in 1996. ... SHA redirects here. ... Snefru is a cryptographic hash function invented by Ralph Merkle which supports 128-bit and 256-bit output. ... In cryptography, Tiger is a cryptographic hash function designed by Ross Anderson and Eli Biham in 1996 with a view for efficiency on 64-bit platforms. ... crypt(1) is a Unix utility command while crypt(3) is an unrelated standard library function. ...

MAC algorithms: DAA | CBC-MAC | HMAC | OMAC/CMAC | PMAC | UMAC | Poly1305-AES The Data Authentication Algorithm (DAA) is a former U.S. government standard for producing cryptographic message authentication codes. ... CBC-MAC stands for Cipher Block Chaining Message Authentication Code. ... A keyed-hash message authentication code, or HMAC, is a type of message authentication code (MAC) calculated using a cryptographic hash function in combination with a secret key. ... OMAC (One-key MAC) is a message authentication code constructed from a block cipher much like the PMAC algorithm. ... PMAC, which stands for Parallelizable MAC, is a message authentication code algorithm. ... UMAC - Wikipedia /**/ @import /skins-1. ... Poly1305-AES is a secure hash function written by Daniel J. Bernstein External links Poly1305-AES Categories: Cryptography stubs | Cryptographic hash functions ...

Authenticated encryption modes: CCM | CWC | EAX | GCM | OCB Authenticated Encryption (AE) is a term used to describe encryption systems which simultaneously protect confidentiality and authenticity (integrity) of communications. ... CCM mode (Counter with CBC-MAC) is a mode of operation for cryptographic block ciphers. ... In cryptography, CWC Mode (Carter-Wegman + CTR mode) is an AEAD block cipher mode of operation designed by Tadayoshi Kohno, John Viega and Doug Whiting. ... EAX mode is a mode of operation for cryptographic block ciphers. ... GCM mode (Galois/Counter Mode) is a mode of operation for symmetric key cryptographic block ciphers. ... OCB mode (Offset Codebook Mode) is a mode of operation for cryptographic block ciphers. ...

Attacks: Hash collision | Birthday attack | Preimage attack | Rainbow table | Brute force attack A birthday attack is a type of cryptographic attack which exploits the mathematics behind the birthday paradox, making use of a space-time tradeoff. ... In cryptography, a preimage attack on a cryptographic hash differs from a collision attack. ... Simplified rainbow table with 3 reduction functions A rainbow table is a lookup table offering a time-memory tradeoff used in recovering the plaintext password from a password hash generated by a hash function, often a cryptographic hash function. ... The EFFs US$250,000 DES cracking machine contained over 1,800 custom chips and could brute force a DES key in a matter of days â€” the photograph shows a DES Cracker circuit board fitted with several Deep Crack chips. ...

Misc: Avalanche effect | Hash collision | Merkle-Damgård construction Standardization: CRYPTREC | NESSIE This article is about cryptography; for other meanings, see snowball effect. ... In cryptography, the Merkle-DamgÃ¥rd hash function is a generic construction of a cryptographic hash function. ... CRYPTREC is the Cryptography Research and Evaluation Committee set up by the Japanese Government to evaluate and recommend cryptographic techniques for government and industrial use. ... For other uses, see nessie (disambiguation). ...

v • d • e

Cryptography

History of cryptography | Cryptanalysis | Cryptography portal | Topics in cryptography

The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek ÎºÏÏ…Ï€Ï„ÏŒÏ‚ kryptÃ³s hidden, and the verb Î³ÏÎ¬Ï†Ï‰ grÃ¡fo write or Î»ÎµÎ³ÎµÎ¹Î½ legein to speak) is the study of message secrecy. ... The history of cryptography begins thousands of years ago. ... Close-up of the rotors in a Fialka cipher machine Cryptanalysis (from the Greek kryptÃ³s, hidden, and analÃ½ein, to loosen or to untie) is the study of methods for obtaining the meaning of encrypted information, without access to the secret information which is normally required to do so. ... This article is intended to be an analytic glossary, or alternatively, an organized collection of annotated pointers. ... This article does not cite any references or sources. ... Encryption Decryption In cryptography, a block cipher is a symmetric key cipher which operates on fixed-length groups of bits, termed blocks, with an unvarying transformation. ... The operation of the keystream generator in A5/1, a LFSR-based stream cipher used to encrypt mobile phone conversations. ... A big random number is used to make a public-key/private-key pair. ... In cryptography, a cryptographic hash function is a hash function with certain additional security properties to make it suitable for use as a primitive in various information security applications, such as authentication and message integrity. ... A cryptographic message authentication code (MAC) is a short piece of information used to authenticate a message. ... A cryptographically secure pseudo-random number generator (CSPRNG) is a pseudo-random number generator (PRNG) with properties that make it suitable for use in cryptography. ... This article is about hidden messages. ...

Contents

In searching GA_googleFillSlot("encyclopedia_square");