 |
|
| ||||||||||||||||||||||||||
|
|
| ||||||||||||||||||||||||||
|
|
|
|
|
| ||||||||
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 hash function takes a long string (or message) of any length as input and produces a fixed length string as output, sometimes termed a message digest or a digital fingerprint.
Broadly speaking, the security properties are required to ensure that the digest is "random" to prospective attackers, and does not leak any information about the message itself, and that other messages cannot be found that produce the same digest. Any change to the message, even a single bit, should result in a dramatically different message digest when re-generated from the received message. A cryptographic hash function is considered secure if
In the first case, an insecure message digest might be used to reconstruct a message which had been encrypted, thus defeating the encryption. In the second case, being able to find a different message which produces a given message digest allows substitution of messages by an attacker; this is a dangerous insecurity.
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.
In the sense in which cryptographic hash functions are discussed in this article, they take only one input - the message. No key is required to compute them before sending or after receiving. In contrast, message authentication codes are keyed hash functions; only the owner of a secret key can compute hashes with that key. Properly employed, a MAC avoids potential attacks against unkeyed hashes and can be used to provide sender authentication as well as message integrity checks.
Mathematically, a cryptographic hash function is a hash function that is:
Note that in the criteria above, 'hard' is used in an unusual way. It means provably hard (as for instance, 'in NP'), or in the less than equivalent alternative, so hard that all expert and informed observers see no prospect of ever achieving the result.
An idealized, imaginary cryptographic hash often used in theoretical studies is the random oracle. This is an oracle which keeps a list of every input it receives. When it receives an input it has never seen before, it generates a random number which it records in its table as the output for that input, then returns that output to the caller. When it receives an input it has seen, it returns the output recorded in its table. Since the mapping from inputs to outputs is random, it is easy to see that random oracles are preimage and collision resistant given a sufficiently large set of possible outputs.
It is important to note that most real cryptographic hashes fail to approximate random oracles in significant ways. For example, they are subject to length-extension: given h(m), it is possible to compute h(m+m'), where + denotes concatenation. The HMAC construction was designed to avoid the attacks that result from length-extension. It is often the case that protocols using cryptographic hashes cannot be proved secure using only the 3 properties that are required of them; however, on making the assumption that the hash function is a random oracle, it is possible prove the protocol secure. This is the canonical use of the random oracle model.
A typical use of a cryptographic hash would be as follows: Alice poses to Bob a tough math problem 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, computes its hash and tells Bob the hash value (whilst keeping the solution secret). This way, when Bob comes up with the solution himself a few days later, Alice can verify his solution but still be able to prove that she had the solution earlier.
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. The above application is called a commitment scheme. Another important application of secure hashes is verification of message integrity. Determination of whether or not 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) (see Tripwire, a system using this property as a defense against malware and malfeasance). A message digest can also serve as a means of reliably identifying a file. 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.
To decrease computational delays, 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, if they meet some additional, statistical, tests.
SHA-1, MD5, and RIPEMD-160 are among the most commonly-used message digest algorithms as of 2004. 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 (strengthened versions of RIPEMD). Neither SHA-0 nor RIPEMD are widely used since they were replaced by their strengthened versions.
A hash function must be able to process an arbitrary-length message into a fixed-length output. In practice, this can be achieved by breaking the input up into a series of equal-size blocks, and operating on them in sequence using a compression function. This design is known as an iterated hash function, or alternatively, the Merkle-Damgård structure; most widely-used hash functions take this form:
In the diagram, the compression function is denoted by f, and transforms a fixed-length input to an output of the same size. The algorithm starts with an initial value, the initialisation vector (IV). For each message block, the compression function f takes the result so far, combines it with the block, and produces an intermediate result. The value after the last block is taken to be the hash value for the entire message.
The popularity of this construction is due to the fact, proved by Merkle and Damgård, that if the compression function f is collision-resistant, then so is the hash function constructed using it.
HAVAL, MD2, MD4, MD5, N-Hash, RIPEMD-160, SHA, Snefru, Tiger, Whirlpool
|
||||
| View Live Article | This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License | |
||
