Functions with these properties are used as hash functions for a variety of purposes, both within and outside cryptography. Practical applications include message integrity checks, digital signatures, authentication, and various information security applications. A hash can also act as a concise representation of the message or document from which it was computed, and allows easy indexing of duplicate or unique data files.
In various standards and applications, the two most commonly used hash functions are MD5 and SHA-1 (other well known hash functions are listed below). In 2005, security flaws were identified in both of these, namely that a possible mathematical weakness might exist, indicating that a stronger hash function would be desirable. In 2007 the National Institute of Standards and Technology announced a contest to design a hash function which will be given the name SHA-3 and be the subject of a FIPS standard.
A hash function takes a string of any length as input and produces a fixed length string which acts as a kind of "signature" for the data provided. In this way, a person knowing the hash is unable to work out the original message, but someone knowing the original message can prove the hash is created from that message, and none other. A cryptographic hash function should behave as much as possible like a random function while still being deterministic and efficiently computable.
A cryptographic hash function is considered "insecure" from a cryptographic point of view, if either of the following is computationally feasible:
An attacker who can do either of these things might, for example, use them to substitute an authorized message with an unauthorized one.
Ideally, it should not even be feasible to find two messages whose digests are substantially similar; nor would one want an attacker to be able to learn anything useful about a message given only its digest. Of course the attacker learns at least one piece of information, the digest itself, which for instance gives the attacker the ability to recognise the same message should it occur again.
A message authentication code (MAC) takes a message and a secret key and generates a "MAC tag", such that it is difficult for an attacker to generate a valid pair (message, tag) that doesn't match one they've already seen; they are used to prevent attackers forging messages, among other uses. Though it is sometimes referred to as a "keyed hash function", a MAC serves a very different purpose and has very different security properties than a cryptographic hash function; for example, it is not considered a flaw if it is easy for someone who knows the MAC key to generate two messages that have the same MAC. Hash functions can be used to create MAC functions; see for example HMAC.
There is no formal definition which captures all of the properties considered desirable for a cryptographic hash function. These properties below are generally considered prerequisites:
A hash function meeting these criteria may still have undesirable properties. For instance, many popular hash functions are vulnerable to length-extension attacks: given h(m) and len(m) but not m, by choosing a suitable m' an attacker can calculate h (m || m'), where || denotes concatenation. This property can be used to break naive authentication schemes based on hash functions. The HMAC construction works around these problems.
It is however, a common misconception that "one-wayness" of a cryptographic hash function means irreversibility of processing of the hash state, and that it somehow contradicts the principles used to construct block ciphers. Such "irreversibility" in fact means presence of local collisions that could facilitate attacks. The hash function must be a permutation processing its state bijectively to be cryptographically secure. It must be irreversible regarding the data block just like any block cipher must be irreversible regarding the key (it should be impossible to find the key that can encrypt a block A into a block B faster than the brute-force). This makes iterated block ciphers and hash functions processing blocks of the same size as secret keys of those block ciphers virtually identical, except the roles of key and data blocks are swapped. All the attacks against the MDx and SHA families of hash functions exploit local collisions in the processing of the data block. The local collisions caused by the final addition operation can also be exploited by these attacks.
Another important application of secure hashes is verification of message integrity. Determining whether any changes have been made to a message (or a file), for example, can be accomplished by comparing message digests calculated before, and after, transmission (or any other event).
A message digest can also serve as a means of reliably identifying a file; several source code management systems, including Git, Mercurial and Monotone, use the sha1sum of various types of content (file content, directory trees, ancestry information, etc) to uniquely identify them. A related application is password verification. Passwords are usually not stored in cleartext, for obvious reasons, but instead in digest form. To authenticate a user, the password presented by the user is hashed and compared with the stored hash. This is sometimes referred to as one-way encryption.
For both security and performance reasons, most digital signature algorithms specify that only the digest of the message be "signed", not the entire message. Hash functions can also be used in the generation of pseudorandom bits.
SHA-1, MD5, and RIPEMD-160 are among the most commonly-used message digest algorithms as of 2005. In August 2004, researchers found weaknesses in a number of hash functions, including MD5, SHA-0 and RIPEMD. This has called into question the long-term security of later algorithms which are derived from these hash functions — in particular, SHA-1 (a strengthened version of SHA-0), RIPEMD-128, and RIPEMD-160 (both strengthened versions of RIPEMD). Neither SHA-0 nor RIPEMD are widely used since they were replaced by their strengthened versions. In February 2005, an attack on SHA-1 was reported, finding collisions in about 269 hashing operations, rather than the 280 expected for a 160-bit hash function. In August 2005, another attack on SHA-1 was reported, finding collisions in 263 operations.
Hashes are used to identify files on peer-to-peer filesharing networks. For example, in an ed2k link, an MD4-variant hash is combined with the file size, providing sufficient information for locating file sources, downloading the file and verifying its contents. Magnet links are another example. Such file hashes are often the top hash of a hash list or a hash tree which allows for additional benefits.
A hash function must be able to process an arbitrary-length message into a fixed-length output. This can be achieved by breaking the input up into a series of equal-sized blocks, and operating on them in sequence using a one-way compression function. The compression function can either be specially designed for hashing or be built from a block cipher. A hash function built with the Merkle-Damgård construction is as resistant to collisions as is its compression function; any collision for the full hash function can be traced back to a collision in the compression function.
The last block processed should also be unambiguously length padded; this is crucial to the security of this construction. This construction is called the Merkle-Damgård construction. Most widely used hash functions, including SHA-1 and MD5, take this form.
A standard block cipher such as AES can be used in place of these custom block ciphers; this generally carries a cost in performance, but can be advantageous where a system needs to perform hashing and another cryptographic function such as encryption that might use a block cipher, but is constrained in the code size or hardware area it must fit into, such as in some embedded systems like smart cards.
Pseudorandom number generators (PRNGs) can be built using hash functions. This is done by combining a (secret) random seed with a counter and hashing it. If the counter is a bignum (allowed to count to any size) then the PRNG can have an infinite period.
Stream ciphers can be built using hash functions. Often this is done by first building a cryptographically secure pseudorandom number generator and then using its stream of random bytes as keystream and XOR that onto the cleartext to get the ciphertext. SEAL is such a stream cipher which is based on SHA-1.
Concatening multiple hash functions could produce a new hash function that is more secure than its component parts. For example, one might concatenate the output of SHA-1 and RIPEMD-160 to produce a new function H(x) = SHA-1(x) || RIPEMD-160(x).
However, the new function is still no more secure than each of its component parts in isolation. Joux noted that the iterative nature of cryptographic hash functions introduces a weakness. n-collisions (n different messages that hash to the same value) are effectively no more difficult to find than 2-collisions. If an n-collision can be found for RIPEMD, it is likely that amongst the n different messages there will be a collision in SHA-1. The time needed to find the SHA-1 collision is polynomial. This argument is summarized by Finney
Concatenated hash functions are used within SSL and the Debian Advanced Packaging Tool system, both of which currently use concatenated MD5 and SHA-1 sums. This does not increase security, but provides redundancy in case one is broken: a valid reason for using multiple hash functions.
|Algorithm||Output size (bits)||Internal state size||Block size||Length size||Word size||Collision|
|RadioGatún||Arbitrarily long||58 words||3 words||No||1-64||No|
Note: The internal state here means the "internal hash sum" after each compression of a data block. Most hash algorithms also internally use some additional variables such as length of the data compressed so far since that is needed for the length padding in the end. See the Merkle-Damgård construction for details.
WIPO ASSIGNS PATENT TO CERTICOM FOR "DEVICE AND METHOD FOR IMPLEMENTING A CRYPTOGRAPHIC HASH FUNCTION" (CANADIAN INVENTOR)
Aug 23, 2011; GENEVA, Aug. 23 -- Publication No. WO/2011/097702 was published on Aug. 18. Title of the invention: "DEVICE AND METHOD FOR...
Wipo Publishes Patent of Irdeto Canada, Jonathan Emmett, Philip Allan Eisen, James Muir, Daniel Murdock for "Method and System for Protecting Execution of Cryptographic Hash Functions" (Canadian Inventors)
Oct 11, 2012; GENEVA, Oct. 11 -- Publication No. WO/2012/129638 was published on Oct. 4. Title of the invention: "METHOD AND SYSTEM FOR...
US Patent Issued to SAP on Feb. 22 for "System and Method for Generating Pseudo-Random Numbers" (German Inventors)
Feb 24, 2011; ALEXANDRIA, Va., Feb. 24 -- United States Patent no. 7,894,602, issued on Feb. 22, was assigned to SAP AG (Walldorf, Germany)....