Cryptographic hash function

) at work. A small change in the input (in the word "over") drastically changes the output (digest). This is called the avalanche effect. A cryptographic hash function (CHF) is a hash algorithm (a map of an arbitrary binary string to a binary string with a fixed size of n bits) that has special properties desirable for cryptographic applications. Hashing is a one-directional mathematical operation which is quick to calculate, yet hard to reverse. Common uses include password storage and digital signatures. Even a small change in the input results in a very different hash, meaning that it functions as an efficient and consistent way to check if two copies of data or software match. Typically, the operation works on a block of input data; the hash output is then hashed with the next block, creating a new hash reflecting everything to that point; this action is repeated until the hash reflects everything through the final block. More technically: * the probability of a particular n -bit output result (hash value) for a random input string ("message") is 2^{-n} (as for any good hash), so the hash value can be used as a representative of the message; * finding an input string that matches a given hash value (a pre-image) is infeasible, assuming all input strings are equally likely.…

) at work. A small change in the input (in the word "over") drastically changes the output (digest). This is called the avalanche effect. A cryptographic hash function (CHF) is a hash algorithm (a map of an arbitrary binary string to a binary string with a fixed size of n bits) that has special properties desirable for cryptographic applications. Hashing is a one-directional mathematical operation which is quick to calculate, yet hard to reverse. Common uses include password storage and digital signatures. Even a small change in the input results in a very different hash, meaning that it functions as an efficient and consistent way to check if two copies of data or software match. Typically, the operation works on a block of input data; the hash output is then hashed with the next block, creating a new hash reflecting everything to that point; this action is repeated until the hash reflects everything through the final block. More technically: the probability of a particular n -bit output result (hash value) for a random input string ("message") is 2^{-n} (as for any good hash), so the hash value can be used as a representative of the message; finding an input string that matches a given hash value (a pre-image) is infeasible, assuming all input strings are equally likely. The resistance to such search is quantified as security strength: a cryptographic hash with n bits of hash value is expected to have a preimage resistance strength of n bits, unless the space of possible input values is significantly smaller than 2^{n} (a practical example can be found in ); a second preimage resistance strength, with the same expectations, refers to a similar problem of finding a second message that matches the given hash value when one message is already known; finding any pair of different messages that yield the same hash value (a collision) is also infeasible: a cryptographic hash is expected to have a collision resistance strength of n/2 bits (lower because of the birthday paradox). Cryptographic hash functions have many information-security applications, notably in digital signatures, message authentication codes (MACs), and other forms of authentication. They can also be used as ordinary hash functions, to index data in hash tables, for fingerprinting, to detect duplicate data or uniquely identify files, and as checksums to detect accidental data corruption. Indeed, in information-security contexts, cryptographic hash values are sometimes called (digital) fingerprints, checksums, (message) digests, or just hash values, even though all these terms stand for more general functions with rather different properties and purposes. Non-cryptographic hash functions are used in hash tables and to detect accidental errors; their constructions frequently provide no resistance to a deliberate attack. For example, a denial-of-service attack on hash tables is possible if the collisions are easy to find, as in the case of linear cyclic redundancy check (CRC) functions. === Wide pipe versus narrow pipe === A straightforward application of the Merkle–Damgård construction, where the size of hash output is equal to the internal state size (between each compression step), results in a narrow-pipe hash design. This design causes many inherent flaws, including length-extension, multicollisions, long message attacks, generate-and-paste attacks, and also cannot be parallelized. As a result, modern hash functions are built on wide-pipe constructions that have a larger internal state size – which range from tweaks of the Merkle–Damgård construction to new constructions such as the sponge construction and HAIFA construction. None of the entrants in the NIST hash function competition use a classical Merkle–Damgård construction. Meanwhile, truncating the output of a longer hash, such as used in SHA-512/256, also defeats many of these attacks.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1376147393 under CC BY-SA 4.0; modifications have been made.