Jump to content

Cryptographic hash function

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Rabbler (talk | contribs) at 09:59, 25 February 2009 (→‎External links). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

For the Wikipedia article teaching users how to create a cryptographic hash on Wikipedia, see Template:User committed identity.

A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will almost certainly change the hash value. In many contexts, especially telecommunications, the data to be encoded are often called the "message", and the hash value is also called the message digest or simply digest.

The ideal hash function has four main properties:

  • it is easy to compute the hash for any given data,
  • it is extremely difficult to construct a text that has a given hash,
  • it is extremely difficult to modify a given text without changing its hash,
  • it is extremely unlikely that two different messages will have the same hash.

These requirements call for the use of advanced cryptography techniques, hence the name.

Cryptographic hash functions have many applications, such as message integrity checks, digital signatures, authentication, and various information security applications. Their hash values can also be used as fingerprints for detecting duplicate data files, file version changes, and similar applications, or as checksums to guard against accidental data corruption. Indeed, cryptographic hash values are often called (digital) fingerprints or checksums, although these are somewhat different concepts. Cryptographic hash functions should not be confused with plain hash functions which are used to map data to indices into a hash table.

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. The function SHA-256 seems as of 2006 free from those weaknesses. 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.[1]

Overview

A cryptographic hash function (specifically, SHA-1) at work. Note that even small changes in the source input drastically change the resulting output, by the so-called avalanche effect.

Most cryptographic hash functions are designed to take a string of any length as input and produce a fixed-length hash value. The four basic properties listed above imply that not even a malicious adversary can replace or modify the input data without changing its digest. Thus, if two strings have the same digest, one can be very confident that they are identical.

Ideally, one may wish for even stronger conditions. It should be impossible for an adversary to find two messages with substantially similar digests; or infer any useful information about the data, given only its digest. Therefore, a cryptographic hash function should behave as much as possible like a random function while still being deterministic and efficiently computable.

Related algorithms

Checksums and cyclic redundancy checks (CRCs) are quite distinct from cryptographic hash functions, and are used for different applications. If used for security, they are vulnerable to attack; for example, a CRC was used for message integrity in the WEP encryption standard, but an attack was readily discovered which exploited the linearity of the checksum specified.

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.

Cryptographic properties

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:

This property is implied by collision-resistance. Second preimage resistance is sometimes referred to as weak collision resistance.

  • Collision-resistant: it should be hard to find two different messages m1 and m2 such that hash(m1) = hash(m2). Due to a possible birthday attack, this means the hash function output must be at least twice as large as what is required for preimage-resistance. This property is sometimes referred to as strong collision resistance.

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.

Applications

A typical use of a cryptographic hash would be as follows: Alice poses a tough math problem to Bob, and claims she has solved it. Bob would like to try it himself, but would yet like to be sure that Alice is not bluffing. Therefore, Alice writes down her solution, appends a random nonce, computes its hash and tells Bob the hash value (whilst keeping the solution and nonce secret). This way, when Bob comes up with the solution himself a few days later, Alice can prove that she had the solution earlier by revealing the nonce to Bob. (This is an example of a simple commitment scheme; in actual practice, Alice and Bob will often be computer programs, and the secret would be something less easily spoofed than a claimed puzzle solution).

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.

Merkle-Damgård construction

Main article: Merkle-Damgård construction
The Merkle-Damgård hash construction.

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.

Hash functions based on block ciphers

Main article: One-way compression function

There are several methods to use a block cipher to build a cryptographic hash function. The methods resemble the block cipher modes of operation usually used for encryption. All well-known hash functions, including MD4, MD5, SHA-1 and SHA-2 are built from block-cipher-like components designed for the purpose, with feedback to ensure that the resulting function is not bijective.

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.

Methods to make hash functions from block ciphers

See one-way compression function for details.

  • Davies-Meyer
  • Matyas-Meyer-Oseas
  • Miyaguchi-Preneel
  • MDC-2
  • MDC-4

Use in building other cryptographic primitives

Hash functions can be used to build other cryptographic primitives. For these other primitives to be cryptographically secure, care must be taken to build them correctly.

Message authentication codes (MACs) are often built from hash functions. HMAC is such a MAC.

Just as block ciphers can be used to build hash functions, hash functions can be used to build block ciphers. Luby-Rackoff constructions using hash functions can be provably secure if the underlying hash function is secure. Also, many hash functions (including the SHA hash functions) are built by using a special-purpose block cipher in a Davies-Meyer or other construction; that cipher can also be used in a conventional mode of operation, without the same security guarantees. See SHACAL, BEAR and LION.

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.

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. SEAL is a stream cipher that uses SHA-1 to generate internal tables, which are then used in a keystream generator more or less unrelated to the hash algorithm; SEAL is not guaranteed to be as strong (or weak) as SHA-1.

Concatenation of cryptographic hash functions

Concatening outputs from multiple hash functions provides security at least as good as the strongest of the algorithms included in the concatenated result [citation needed]. For example, SSL uses concatenated MD5 and SHA-1 sums to ensure the protocol will remain secure even if one function is broken.

However, when the component hash functions follow the Merkle-Damgård model, the concatenated function is only as strong as the best component, not stronger. Joux[2] 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.

List of cryptographic hash functions

Some of the following algorithms are known to be insecure; consult the article for each specific algorithm for more information on the status of each algorithm. Note that this list doesn't include candidates in the current NIST hash function competition. For even more hash functions see the box at the bottom of the page.

Algorithm Output size (bits) Internal state size Block size Length size Word size Collision attack (complexity) Pre-image attack (complexity)
HAVAL 256/224/192/160/128 256 1024 64 32 Yes
MD2 128 384 128 No 8 Almost
MD4 128 128 512 64 32 Yes (2^8)[3] With flaws (2^102)[4]
MD5 128 128 512 64 32 Yes (2^5) No
PANAMA 256 8736 256 No 32 Yes
RadioGatún Arbitrarily long 58 words 3 words No 1-64 No
RIPEMD 128 128 512 64 32 Yes
RIPEMD-128/256 128/256 128/256 512 64 32 No
RIPEMD-160/320 160/320 160/320 512 64 32 No
SHA-0 160 160 512 64 32 Yes (2^39)[5]
SHA-1 160 160 512 64 32 With flaws (2^63)[6] No
SHA-256/224 256/224 256 512 64 32 No No
SHA-512/384 512/384 512 1024 128 64 No No
Tiger(2)-192/160/128 192/160/128 192 512 64 64 No
WHIRLPOOL 512 512 512 256 8 No

The SHA hash functions are a series of functions developed by the NSA: SHA, also known as SHA-0, SHA-1 and four flavours of a function known as SHA-2.

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.

See also

References

  1. ^ NIST.gov - Computer Security Division - Computer Security Resource Center
  2. ^ Joux, Antoine. Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions. LNCS 3152/2004, pages 306-316 Full text.
  3. ^ http://www.infosec.sdu.edu.cn/uploadfile/papers/Cryptanalysis%20of%20the%20Hash%20Functions%20MD4%20and%20RIPEMD.pdf
  4. ^ http://www.nis-summer-school.eu/presentations/bart_preneel_lecture.pdf
  5. ^ http://www.infosec.sdu.edu.cn/paper/sha0-crypto-author-new.pdf
  6. ^ Schneier on Security: New Cryptanalytic Results Against SHA-1

Further reading

  • Bruce Schneier. Applied Cryptography. John Wiley & Sons, 1996. ISBN 0-471-11709-9.

External links

Retrieved from "https://en.wikipedia.org/w/index.php?title=Cryptographic_hash_function&oldid=273160673"