SHA-2
Encyclopedia
In cryptography, SHA-2 is a set of cryptographic hash function
s (SHA-224, SHA-256, SHA-384, SHA-512) designed by the National Security Agency
(NSA) and published in 2001 by the NIST
as a U.S. Federal Information Processing Standard
. SHA stands for Secure Hash Algorithm
. SHA-2 includes a significant number of changes from its predecessor, SHA-1. SHA-2 consists of a set of four hash functions with digests that are 224, 256, 384 or 512 bits.
In 2005, security flaws were identified in SHA-1, namely that a mathematical weakness might exist, indicating that a stronger hash function would be desirable. Although SHA-2 bears some similarity to the SHA-1 algorithm, these attacks have not been successfully extended to SHA-2.
A new hash standard, SHA-3, is currently under development; an ongoing NIST hash function competition
is scheduled to end with the selection of a winning function in 2012. The SHA-3 algorithm will not be derived from SHA-2.
NIST published four additional hash functions in the SHA family, named after their digest lengths (in bits): SHA-224, SHA-256, SHA-384, and SHA-512. The algorithms are collectively known as SHA-2.
The algorithms were first published in 2001 in the draft FIPS PUB 180-2, at which time review and comments were accepted. FIPS PUB 180-2, which also includes SHA-1, was released as an official standard in 2002. In February 2004, a change notice was published for FIPS PUB 180-2, specifying an additional variant, SHA-224, defined to match the key length of two-key Triple DES
. These variants are patented in . The United States
has released the patent under a royalty free license.
SHA-256 and SHA-512 are novel hash functions computed with 32- and 64-bit words, respectively. They use different shift amounts and additive constants, but their structures are otherwise virtually identical, differing only in the number of rounds. SHA-224 and SHA-384 are simply truncated versions of the first two, computed with different initial values.
The SHA-2 functions are not as widely used as SHA-1, despite their better security. Reasons might include lack of support for SHA-2 on systems running Windows XP SP2 or older, a lack of perceived urgency since SHA-1 collisions have not yet been found, or a desire to wait until SHA-3
is standardized. SHA-256 is used to authenticate Debian
Linux software packages and in the DKIM message signing standard; SHA-512 is part of a system to authenticate archival video from the International Criminal Tribunal of the Rwandan genocide
. SHA-256 and SHA-512 are proposed for use in DNSSEC
. Unix and Linux vendors are moving to using 256- and 512-bit SHA-2 for secure password hashing. NIST's directive that U.S. government agencies must stop uses of SHA-1 after 2010, and the completion of SHA-3, may accelerate migration away from SHA-1.
Currently, the best public attacks break 41 of the 64 rounds of SHA-256 or 46 of the 80 rounds of SHA-512, as discussed in the "Cryptanalysis and Validation" section below.
The performance numbers above were for a single-threaded implementation on an Intel Core 2 1.83 GHz processor under Windows Vista in 32-bit mode, and serve only as a rough point for general comparison. On 64-bit machines, SHA-512 is significantly faster than SHA-256.
and SSL, PGP
, SSH
, S/MIME
, Bitcoin
and IPsec
.
SHA-1 and SHA-2 are the secure hash algorithms required by law for use in certain U.S. Government applications, including use within other cryptographic algorithms and protocols, for the protection of sensitive unclassified information. FIPS PUB 180-1 also encouraged adoption and use of SHA-1 by private and commercial organizations. SHA-1 is being retired for most government uses; the U.S. National Institute of Standards and Technology says, "Federal agencies should stop using SHA-1 for...applications that require collision resistance as soon as practical, and must use the SHA-2 family of hash functions for these applications after 2010" (emphasis in original).
in the message digest, finding a message that corresponds to a given message digest can always be done using a brute force search in 2L evaluations. This is called a preimage attack
and may or may not be practical depending on L and the particular computing environment. The second criterion, finding two different messages that produce the same message digest, known as a collision, requires on average only 2L/2 evaluations using a birthday attack
.
In terms of practical security, a major concern about these new attacks is that they might pave the way to more efficient ones. Whether this is the case has yet to be seen, but a migration to stronger hashes is believed to be prudent. Some of the applications that use cryptographic hashes, such as password storage, are only minimally affected by a collision attack
. Constructing a password that works for a given account requires a preimage attack, as well as access to the hash of the original password (typically in the shadow
file) which may or may not be trivial. Reversing password encryption (e.g., to obtain a password to try against a user's account elsewhere) is not made possible by the attacks. (However, even a secure password hash cannot prevent brute-force attacks on weak passwords
.)
In the case of document signing, an attacker could not simply fake a signature from an existing document—the attacker would have to produce a pair of documents, one innocuous and one damaging, and get the private key holder to sign the innocuous document. There are practical circumstances in which this is possible; until the end of 2008, it was possible to create forged SSL
certificates using an MD5
collision.
There are two meet-in-the-middle
preimage attack
s against SHA-2 with a reduced number of rounds. The first one attacks 41-round SHA-256 out of 64 rounds with time complexity of 2253.5 and space complexity of 216, and 46-round SHA-512 out of 80 rounds with time 2511.5 and space 23. The second one attacks 42-round SHA-256 with time complexity of 2251.7 and space complexity of 212, and 42-round SHA-512 with time 2502 and space 222.
, jointly run by the National Institute of Standards and Technology
(NIST) and the Communications Security Establishment
(CSE). For informal verification, a package to generate a high number of test vectors is made available for download on the NIST site; the resulting verification however does not replace in any way the formal CMVP validation, which is required by law for certain applications..
SHA224("")
0x d14a028c2a3a2bc9476102bb288234c415a2b01f828ea62ac5b3e42f
SHA256("")
0x e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
SHA384("")
0x 38b060a751ac96384cd9327eb1b1e36a21fdb71114be07434c0cc7bf63f6e1da274edebfe76f65fbd51ad2f14898b95b
SHA512("")
0x cf83e1357eefb8bdf1542850d66d8007d620e4050b5715dc83f4a921d36ce9ce47d0d13c5d85f2b0ff8318d2877eec2f63b931bd47417a81a538327af927da3e
Even a small change in the message will (with overwhelming probability) result in a mostly different hash, due to the avalanche effect
. For example, adding a period to the end of the sentence:
SHA224("The quick brown fox jumps over the lazy dog")
0x 730e109bd7a8a32b1cb9d9a09aa2325d2430587ddbc0c38bad911525
SHA224("The quick brown fox jumps over the lazy dog.")
0x 619cba8e8e05826e9b8c519c0a5c68f4fb653e8a3d8aa04bb2c8cd4c
SHA256("The quick brown fox jumps over the lazy dog")
0x d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592
SHA256("The quick brown fox jumps over the lazy dog.")
0x ef537f25c895bfa782526529a9b63d97aa631564d5d789c2b765448c8635fb6c
SHA384("The quick brown fox jumps over the lazy dog")
0x ca737f1014a48f4c0b6dd43cb177b0afd9e5169367544c494011e3317dbf9a509cb1e5dc1e85a941bbee3d7f2afbc9b1
SHA384("The quick brown fox jumps over the lazy dog.")
0x ed892481d8272ca6df370bf706e4d7bc1b5739fa2177aae6c50e946678718fc67a7af2819a021c2fc34e91bdb63409d7
SHA512("The quick brown fox jumps over the lazy dog")
0x 07e547d9586f6a73f73fbac0435ed76951218fb7d0c8d788a309d785436bbb642e93a252a954f23912547d1e8a3b5ed6e1bfd7097821233fa0538f3db854fee6
SHA512("The quick brown fox jumps over the lazy dog.")
0x 91ea1245f20d46ae9a037a989f54f1f790f0a47607eeb8a14d12890cea77a1bbc6c7ed9cf205e67b7f2b8fd4c7dfd3a7a8617e45f3c463d481c7e586c39ac1ed
for the SHA-256 algorithm follows. Note the great increase in mixing between bits of the
Note 1: All variables are unsigned 32 bits and wrap modulo 232 when calculating
Note 2: All constants in this pseudo code are in big endian
Initialize variables
(first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19):
h[0..7] :=
0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
Initialize table of round constants
(first 32 bits of the fractional parts of the cube roots of the first 64 primes 2..311):
k[0..63] :=
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
Pre-processing:
append the bit '1' to the message
append k bits '0', where k is the minimum number >= 0 such that the resulting message
length (in bits) is congruent
to 448 (mod 512)
append length of message (before pre-processing), in bits, as 64-bit big-endian integer
Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
break chunk into sixteen 32-bit big-endian words w[0..15]
Extend the sixteen 32-bit words into sixty-four 32-bit words:
for i from 16 to 63
s0 := (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3)
s1 := (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor (w[i-2] rightshift 10)
w[i] := w[i-16] + s0 + w[i-7] + s1
Initialize hash value for this chunk:
a := h0
b := h1
c := h2
d := h3
e := h4
f := h5
g := h6
h := h7
Main loop:
for i from 0 to 63
s0 := (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
maj := (a and b) xor (a and c) xor (b and c)
t2 := s0 + maj
s1 := (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
ch := (e and f) xor ((not e) and g)
t1 := h + s1 + ch + k[i] + w[i]
h := g
g := f
f := e
e := d + t1
d := c
c := b
b := a
a := t1 + t2
Add this chunk's hash to result so far:
h0 := h0 + a
h1 := h1 + b
h2 := h2 + c
h3 := h3 + d
h4 := h4 + e
h5 := h5 + f
h6 := h6 + g
h7 := h7 + h
Produce the final hash value (big-endian):
digest = hash = h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7
The computation of the
SHA-224 is identical to SHA-256, except that:
Here the initial values for the variables (in big endian):
(The second 32 bits of the fractional parts of the square roots of the 9th through 16th primes 23..53)
h[0..7] :=
0xc1059ed8, 0x367cd507, 0x3070dd17, 0xf70e5939, 0xffc00b31, 0x68581511, 0x64f98fa7, 0xbefa4fa4
SHA-512 is identical in structure, but:
SHA-384 is identical to SHA-512, except that:
, Python
, PHP
, and Perl
: A general purpose cryptographic library based on the code from GNU Privacy Guard
.
OpenSSL
: The widely used OpenSSL
, open-source
– implementations of SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512
cryptlib
: an open source
cross-platform software security toolkit library
Crypto++
: A public domain C++ class library of cryptographic schemes, including implementations of the SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512 algorithms.
Bouncy Castle
: The Bouncy Castle Library is a free Java and C# class library that contains implementations of the SHA-1, SHA-224, SHA-256, SHA-384 and SHA-512 algorithms as well as other algorithms like Whirlpool, Tiger
, RIPEMD
, GOST-3411, MD2, MD4
and MD5
.
jsSHA: A cross-browser JavaScript
library for client-side calculation of SHA digests, despite the fact that JavaScript does not natively support the 64-bit operations required for SHA-384 and SHA-512.
LibTomCrypt: A portable ISO C cryptographic toolkit, Public Domain.
md5deep
: A set of programs to compute MD5, SHA-1, SHA-256, Tiger, or Whirlpool cryptographic message digests on an arbitrary number of files. It is used in computer security, system administration and computer forensics communities for purposes of running large numbers of files through any of several different cryptographic digests. It is similar to sha1sum
from GNU Core Utilities
and md5sum
.
sphlib: A free, open-source
library which implements many hash functions, including SHA-1 and SHA-2, both in portable (but optimized) C and in Java.
VHDL: A free, open-source
collection of hardware implementations of hash functions (including SHA-1 and SHA-2) in portable (but optimized) VHDL.
Cryptographic hash function
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 change the hash value...
s (SHA-224, SHA-256, SHA-384, SHA-512) designed by the National Security Agency
National Security Agency
The National Security Agency/Central Security Service is a cryptologic intelligence agency of the United States Department of Defense responsible for the collection and analysis of foreign communications and foreign signals intelligence, as well as protecting U.S...
(NSA) and published in 2001 by the NIST
National Institute of Standards and Technology
The National Institute of Standards and Technology , known between 1901 and 1988 as the National Bureau of Standards , is a measurement standards laboratory, otherwise known as a National Metrological Institute , which is a non-regulatory agency of the United States Department of Commerce...
as a U.S. Federal Information Processing Standard
Federal Information Processing Standard
A Federal Information Processing Standard is a publicly announced standardization developed by the United States federal government for use in computer systems by all non-military government agencies and by government contractors, when properly invoked and tailored on a contract...
. SHA stands for Secure Hash Algorithm
Secure Hash Algorithm
The Secure Hash Algorithm is one of a number of cryptographic hash functions published by the National Institute of Standards and Technology as a U.S. Federal Information Processing Standard :...
. SHA-2 includes a significant number of changes from its predecessor, SHA-1. SHA-2 consists of a set of four hash functions with digests that are 224, 256, 384 or 512 bits.
In 2005, security flaws were identified in SHA-1, namely that a mathematical weakness might exist, indicating that a stronger hash function would be desirable. Although SHA-2 bears some similarity to the SHA-1 algorithm, these attacks have not been successfully extended to SHA-2.
A new hash standard, SHA-3, is currently under development; an ongoing NIST hash function competition
NIST hash function competition
The NIST hash function competition is an open competition held by the US National Institute of Standards and Technology for a new SHA-3 function to replace the older SHA-1 and SHA-2, which was formally announced in the Federal Register on November 2, 2007...
is scheduled to end with the selection of a winning function in 2012. The SHA-3 algorithm will not be derived from SHA-2.
Hash function
The algorithms were first published in 2001 in the draft FIPS PUB 180-2, at which time review and comments were accepted. FIPS PUB 180-2, which also includes SHA-1, was released as an official standard in 2002. In February 2004, a change notice was published for FIPS PUB 180-2, specifying an additional variant, SHA-224, defined to match the key length of two-key Triple DES
Triple DES
In cryptography, Triple DES is the common name for the Triple Data Encryption Algorithm block cipher, which applies the Data Encryption Standard cipher algorithm three times to each data block....
. These variants are patented in . The United States
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
has released the patent under a royalty free license.
SHA-256 and SHA-512 are novel hash functions computed with 32- and 64-bit words, respectively. They use different shift amounts and additive constants, but their structures are otherwise virtually identical, differing only in the number of rounds. SHA-224 and SHA-384 are simply truncated versions of the first two, computed with different initial values.
The SHA-2 functions are not as widely used as SHA-1, despite their better security. Reasons might include lack of support for SHA-2 on systems running Windows XP SP2 or older, a lack of perceived urgency since SHA-1 collisions have not yet been found, or a desire to wait until SHA-3
NIST hash function competition
The NIST hash function competition is an open competition held by the US National Institute of Standards and Technology for a new SHA-3 function to replace the older SHA-1 and SHA-2, which was formally announced in the Federal Register on November 2, 2007...
is standardized. SHA-256 is used to authenticate Debian
Debian
Debian is a computer operating system composed of software packages released as free and open source software primarily under the GNU General Public License along with other free software licenses. Debian GNU/Linux, which includes the GNU OS tools and Linux kernel, is a popular and influential...
Linux software packages and in the DKIM message signing standard; SHA-512 is part of a system to authenticate archival video from the International Criminal Tribunal of the Rwandan genocide
International Criminal Tribunal for Rwanda
The International Criminal Tribunal for Rwanda is an international court established in November 1994 by the United Nations Security Council in Resolution 955 in order to judge people responsible for the Rwandan Genocide and other serious violations of international law in Rwanda, or by Rwandan...
. SHA-256 and SHA-512 are proposed for use in DNSSEC
DNSSEC
The Domain Name System Security Extensions is a suite of Internet Engineering Task Force specifications for securing certain kinds of information provided by the Domain Name System as used on Internet Protocol networks...
. Unix and Linux vendors are moving to using 256- and 512-bit SHA-2 for secure password hashing. NIST's directive that U.S. government agencies must stop uses of SHA-1 after 2010, and the completion of SHA-3, may accelerate migration away from SHA-1.
Currently, the best public attacks break 41 of the 64 rounds of SHA-256 or 46 of the 80 rounds of SHA-512, as discussed in the "Cryptanalysis and Validation" section below.
Comparison of SHA functions
In the table below, internal state means the "internal hash sum" after each compression of a data block.| Algorithm and variant |
Output size (bits) | Internal state size (bits) | Block size (bits) | Max message size (bits) | Word size (bits) | Rounds | Operations | Collisions Hash collision Not to be confused with wireless packet collision.In computer science, a collision or clash is a situation that occurs when two distinct pieces of data have the same hash value, checksum, fingerprint, or cryptographic digest.... found |
Example Performance (MiB/s) | |
|---|---|---|---|---|---|---|---|---|---|---|
| MD5 (as reference) | 128 | 128 | 512 | 264 − 1 | 32 | 64 | and,or,xor,rot | Yes | 255 | |
| SHA-0 | 160 | 160 | 512 | 264 − 1 | 32 | 80 | +,and,or,xor,rot | Yes | - | |
| SHA-1 | 160 | 160 | 512 | 264 − 1 | 32 | 80 | +,and,or,xor,rot | Theoretical attack (251) | 153 | |
| SHA-2 | SHA-256/224 | 256/224 | 256 | 512 | 264 − 1 | 32 | 64 | +,and,or,xor,shr,rot | None | 111 |
| SHA-512/384 | 512/384 | 512 | 1024 | 2128 − 1 | 64 | 80 | +,and,or,xor,shr,rot | None | 99 | |
The performance numbers above were for a single-threaded implementation on an Intel Core 2 1.83 GHz processor under Windows Vista in 32-bit mode, and serve only as a rough point for general comparison. On 64-bit machines, SHA-512 is significantly faster than SHA-256.
Applications
The SHA-2 hash function is implemented in some widely-used security applications and protocols, including TLSTransport Layer Security
Transport Layer Security and its predecessor, Secure Sockets Layer , are cryptographic protocols that provide communication security over the Internet...
and SSL, PGP
Pretty Good Privacy
Pretty Good Privacy is a data encryption and decryption computer program that provides cryptographic privacy and authentication for data communication. PGP is often used for signing, encrypting and decrypting texts, E-mails, files, directories and whole disk partitions to increase the security...
, SSH
Secure Shell
Secure Shell is a network protocol for secure data communication, remote shell services or command execution and other secure network services between two networked computers that it connects via a secure channel over an insecure network: a server and a client...
, S/MIME
S/MIME
S/MIME is a standard for public key encryption and signing of MIME data. S/MIME is on an IETF standards track and defined in a number of documents, most importantly RFCs. S/MIME was originally developed by RSA Data Security Inc...
, Bitcoin
Bitcoin
Bitcoin is a decentralized, peer-to-peer network over which users make transactions that are tracked and verified through this network. The word Bitcoin also refers to the digital currency implemented as the currency medium for user transactions over this network...
and IPsec
IPsec
Internet Protocol Security is a protocol suite for securing Internet Protocol communications by authenticating and encrypting each IP packet of a communication session...
.
SHA-1 and SHA-2 are the secure hash algorithms required by law for use in certain U.S. Government applications, including use within other cryptographic algorithms and protocols, for the protection of sensitive unclassified information. FIPS PUB 180-1 also encouraged adoption and use of SHA-1 by private and commercial organizations. SHA-1 is being retired for most government uses; the U.S. National Institute of Standards and Technology says, "Federal agencies should stop using SHA-1 for...applications that require collision resistance as soon as practical, and must use the SHA-2 family of hash functions for these applications after 2010" (emphasis in original).
Cryptanalysis and validation
For a hash function for which L is the number of bitsBITS
BITS or bits may refer to:* Plural of bit* Background Intelligent Transfer Service, a file transfer protocol* Birla Institute of Technology and Science, a technology school in Pilani, Rajasthan, India, with campuses in Goa, Hyderabad, and Dubai...
in the message digest, finding a message that corresponds to a given message digest can always be done using a brute force search in 2L evaluations. This is called a preimage attack
Preimage attack
In cryptography, the preimage attack is a classification of attacks on hash functions for finding a message that has a specific hash value.There are two types of preimage attacks:...
and may or may not be practical depending on L and the particular computing environment. The second criterion, finding two different messages that produce the same message digest, known as a collision, requires on average only 2L/2 evaluations using a birthday attack
Birthday attack
A birthday attack is a type of cryptographic attack that exploits the mathematics behind the birthday problem in probability theory. This attack can be used to abuse communication between two or more parties...
.
In terms of practical security, a major concern about these new attacks is that they might pave the way to more efficient ones. Whether this is the case has yet to be seen, but a migration to stronger hashes is believed to be prudent. Some of the applications that use cryptographic hashes, such as password storage, are only minimally affected by a collision attack
Collision attack
In cryptography, a collision attack on a cryptographic hash tries to find two arbitrary inputs that will produce the same hash value, i.e. a hash collision...
. Constructing a password that works for a given account requires a preimage attack, as well as access to the hash of the original password (typically in the shadow
Shadow password
In computing, Unix-like operating systems use the shadow password database mechanism to increase the security level of passwords by restricting all but highly privileged users' access to encrypted password data...
file) which may or may not be trivial. Reversing password encryption (e.g., to obtain a password to try against a user's account elsewhere) is not made possible by the attacks. (However, even a secure password hash cannot prevent brute-force attacks on weak passwords
Password strength
Password strength is a measure of the effectiveness of a password in resisting guessing and brute-force attacks. In its usual form, it estimates how many trials an attacker who does not have direct access to the password would need, on average, to guess it correctly...
.)
In the case of document signing, an attacker could not simply fake a signature from an existing document—the attacker would have to produce a pair of documents, one innocuous and one damaging, and get the private key holder to sign the innocuous document. There are practical circumstances in which this is possible; until the end of 2008, it was possible to create forged SSL
Transport Layer Security
Transport Layer Security and its predecessor, Secure Sockets Layer , are cryptographic protocols that provide communication security over the Internet...
certificates using an MD5
MD5
The MD5 Message-Digest Algorithm is a widely used cryptographic hash function that produces a 128-bit hash value. Specified in RFC 1321, MD5 has been employed in a wide variety of security applications, and is also commonly used to check data integrity...
collision.
There are two meet-in-the-middle
Meet-in-the-middle attack
The meet-in-the-middle attack is a cryptographic attack which, like the birthday attack, makes use of a space-time tradeoff. While the birthday attack attempts to find two values in the domain of a function that map to the same value in its range, the meet-in-the-middle attack attempts to find a...
preimage attack
Preimage attack
In cryptography, the preimage attack is a classification of attacks on hash functions for finding a message that has a specific hash value.There are two types of preimage attacks:...
s against SHA-2 with a reduced number of rounds. The first one attacks 41-round SHA-256 out of 64 rounds with time complexity of 2253.5 and space complexity of 216, and 46-round SHA-512 out of 80 rounds with time 2511.5 and space 23. The second one attacks 42-round SHA-256 with time complexity of 2251.7 and space complexity of 212, and 42-round SHA-512 with time 2502 and space 222.
Official validation
Implementations of all FIPS-approved security functions can be officially validated through the CMVP programCMVP
The Cryptographic Module Validation Program is a joint American and Canadian security accreditation program for cryptographic modules. The program is available to any vendors who seek to have their products certified for use by the U.S...
, jointly run by the National Institute of Standards and Technology
National Institute of Standards and Technology
The National Institute of Standards and Technology , known between 1901 and 1988 as the National Bureau of Standards , is a measurement standards laboratory, otherwise known as a National Metrological Institute , which is a non-regulatory agency of the United States Department of Commerce...
(NIST) and the Communications Security Establishment
Communications Security Establishment
The Communications Security Establishment Canada is the Canadian government's national cryptologic agency. Administered under the Department of National Defence , it is charged with the duty of keeping track of foreign signals intelligence , and protecting Canadian government electronic...
(CSE). For informal verification, a package to generate a high number of test vectors is made available for download on the NIST site; the resulting verification however does not replace in any way the formal CMVP validation, which is required by law for certain applications..
Examples of SHA-2 variants (SHA224, SHA256, SHA384 and SHA512)
Hash values of empty string.SHA224("")
0x d14a028c2a3a2bc9476102bb288234c415a2b01f828ea62ac5b3e42f
SHA256("")
0x e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
SHA384("")
0x 38b060a751ac96384cd9327eb1b1e36a21fdb71114be07434c0cc7bf63f6e1da274edebfe76f65fbd51ad2f14898b95b
SHA512("")
0x cf83e1357eefb8bdf1542850d66d8007d620e4050b5715dc83f4a921d36ce9ce47d0d13c5d85f2b0ff8318d2877eec2f63b931bd47417a81a538327af927da3e
Even a small change in the message will (with overwhelming probability) result in a mostly different hash, due to the avalanche effect
Avalanche effect
In cryptography, the avalanche effect refers to a desirable property of cryptographic algorithms, typically block ciphers and cryptographic hash functions. The avalanche effect is evident if, when an input is changed slightly the output changes significantly...
. For example, adding a period to the end of the sentence:
SHA224("The quick brown fox jumps over the lazy dog")
0x 730e109bd7a8a32b1cb9d9a09aa2325d2430587ddbc0c38bad911525
SHA224("The quick brown fox jumps over the lazy dog.")
0x 619cba8e8e05826e9b8c519c0a5c68f4fb653e8a3d8aa04bb2c8cd4c
SHA256("The quick brown fox jumps over the lazy dog")
0x d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592
SHA256("The quick brown fox jumps over the lazy dog.")
0x ef537f25c895bfa782526529a9b63d97aa631564d5d789c2b765448c8635fb6c
SHA384("The quick brown fox jumps over the lazy dog")
0x ca737f1014a48f4c0b6dd43cb177b0afd9e5169367544c494011e3317dbf9a509cb1e5dc1e85a941bbee3d7f2afbc9b1
SHA384("The quick brown fox jumps over the lazy dog.")
0x ed892481d8272ca6df370bf706e4d7bc1b5739fa2177aae6c50e946678718fc67a7af2819a021c2fc34e91bdb63409d7
SHA512("The quick brown fox jumps over the lazy dog")
0x 07e547d9586f6a73f73fbac0435ed76951218fb7d0c8d788a309d785436bbb642e93a252a954f23912547d1e8a3b5ed6e1bfd7097821233fa0538f3db854fee6
SHA512("The quick brown fox jumps over the lazy dog.")
0x 91ea1245f20d46ae9a037a989f54f1f790f0a47607eeb8a14d12890cea77a1bbc6c7ed9cf205e67b7f2b8fd4c7dfd3a7a8617e45f3c463d481c7e586c39ac1ed
SHA-256 (a SHA-2 variant) pseudocode
PseudocodePseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
for the SHA-256 algorithm follows. Note the great increase in mixing between bits of the
w[16..63] words compared to SHA-1.Note 1: All variables are unsigned 32 bits and wrap modulo 232 when calculating
Note 2: All constants in this pseudo code are in big endian
Initialize variables
(first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19):
h[0..7] :=
0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
Initialize table of round constants
(first 32 bits of the fractional parts of the cube roots of the first 64 primes 2..311):
k[0..63] :=
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
Pre-processing:
append the bit '1' to the message
append k bits '0', where k is the minimum number >= 0 such that the resulting message
length (in bits) is congruent
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
to 448 (mod 512)
append length of message (before pre-processing), in bits, as 64-bit big-endian integer
Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
break chunk into sixteen 32-bit big-endian words w[0..15]
Extend the sixteen 32-bit words into sixty-four 32-bit words:
for i from 16 to 63
s0 := (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3)
s1 := (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor (w[i-2] rightshift 10)
w[i] := w[i-16] + s0 + w[i-7] + s1
Initialize hash value for this chunk:
a := h0
b := h1
c := h2
d := h3
e := h4
f := h5
g := h6
h := h7
Main loop:
for i from 0 to 63
s0 := (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
maj := (a and b) xor (a and c) xor (b and c)
t2 := s0 + maj
s1 := (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
ch := (e and f) xor ((not e) and g)
t1 := h + s1 + ch + k[i] + w[i]
h := g
g := f
f := e
e := d + t1
d := c
c := b
b := a
a := t1 + t2
Add this chunk's hash to result so far:
h0 := h0 + a
h1 := h1 + b
h2 := h2 + c
h3 := h3 + d
h4 := h4 + e
h5 := h5 + f
h6 := h6 + g
h7 := h7 + h
Produce the final hash value (big-endian):
digest = hash = h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7
The computation of the
ch and maj values can be optimized the same way as described for SHA-1.SHA-224 is identical to SHA-256, except that:
- the initial variable values
h0throughh7are different, and - the output is constructed by omitting
h7.
Here the initial values for the variables (in big endian):
(The second 32 bits of the fractional parts of the square roots of the 9th through 16th primes 23..53)
h[0..7] :=
0xc1059ed8, 0x367cd507, 0x3070dd17, 0xf70e5939, 0xffc00b31, 0x68581511, 0x64f98fa7, 0xbefa4fa4
SHA-512 is identical in structure, but:
- the message is broken into 1024-bit chunks,
- all numbers are 64 bits long,
- there are 80 rounds instead of 64,
- the appended length of the message (before pre-processing), in bits, is a 128-bit big-endian integer
- the initial values and additive constants are extended to 64 bits, and
- the shift and rotate amounts used are different.
SHA-384 is identical to SHA-512, except that:
- the initial values
h0throughh7are different (taken from the 9th through 16th primes), and - the output is constructed by omitting
h6andh7.
See also
- Comparison of cryptographic hash functionsComparison of cryptographic hash functionsThe following tables compare general and technical information for a number of cryptographic hash functions.- General information :Basic general information about the cryptographic hash functions: year, designer, references, etc.- Compression function :...
- Digital timestamping
- Hash based Message Authentication Code (HMAC) or Keyed HashHMACIn cryptography, HMAC is a specific construction for calculating a message authentication code involving a cryptographic hash function in combination with a secret key. As with any MAC, it may be used to simultaneously verify both the data integrity and the authenticity of a message...
- Hash collisionHash collisionNot to be confused with wireless packet collision.In computer science, a collision or clash is a situation that occurs when two distinct pieces of data have the same hash value, checksum, fingerprint, or cryptographic digest....
- HashcashHashcashHashcash is a proof-of-work system designed to limit email spam and denial-of-service attacks. It was proposed in March 1997 by Adam Back.-How it works:...
- International Association for Cryptologic ResearchInternational Association for Cryptologic ResearchThe International Association for Cryptologic Research is a non-profit scientific organization whose purpose is to further research in cryptology and related fields...
(IACR) - Secure Hash StandardSecure Hash StandardThe Secure Hash Standard is a set of cryptographically secure hash algorithms specified by the National Institute of Standards and Technology .The SHS standard specifies a number of Secure Hash Algorithms, for example SHA-1, SHA-256 and SHA-512....
- sha1sumSha1sumsha1sum is a computer program that calculates and verifies SHA-1 hashes. It is commonly used to verify the integrity of files. It is installed by default in most Unix-like operating systems...
(sha224sum, sha256sum, sha384sum and sha512sum) commands
Standards: SHA-1, SHA-2
- Specifications for a Secure Hash Standard (SHS) – Draft for proposed SHS (SHA-0)
- Secure Hash Standard (SHS) – Proposed SHS (SHA-0)
- CSRC Cryptographic Toolkit – Official NISTNational Institute of Standards and TechnologyThe National Institute of Standards and Technology , known between 1901 and 1988 as the National Bureau of Standards , is a measurement standards laboratory, otherwise known as a National Metrological Institute , which is a non-regulatory agency of the United States Department of Commerce...
site for the Secure Hash Standard- FIPS 180-3: Secure Hash Standard (SHS) (PDFPortable Document FormatPortable Document Format is an open standard for document exchange. This file format, created by Adobe Systems in 1993, is used for representing documents in a manner independent of application software, hardware, and operating systems....
, 236 kB) – Current version of the Secure Hash Standard (SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512), October 2008
- FIPS 180-3: Secure Hash Standard (SHS) (PDF
- Test vectors for SHA-256/384/512 from the NESSIENESSIENESSIE was a European research project funded from 2000–2003 to identify secure cryptographic primitives. The project was comparable to the NIST AES process and the Japanese Government-sponsored CRYPTREC project, but with notable differences from both...
project - Test vectors for SHA-1, SHA-2 from NISTNational Institute of Standards and TechnologyThe National Institute of Standards and Technology , known between 1901 and 1988 as the National Bureau of Standards , is a measurement standards laboratory, otherwise known as a National Metrological Institute , which is a non-regulatory agency of the United States Department of Commerce...
site - NIST Cryptographic Hash Project SHA-3 competition
- RFC 3874: A 224-bit One-way Hash Function: SHA-224.
- RFC 6234: US Secure Hash Algorithms SHA and SHA-based HMAC and HKDF). Contains sample C implementation.
Implementations in common languages
SHA hashing functions are found in many modern programming languages, such as JavaJava (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
, Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
, PHP
PHP
PHP is a general-purpose server-side scripting language originally designed for web development to produce dynamic web pages. For this purpose, PHP code is embedded into the HTML source document and interpreted by a web server with a PHP processor module, which generates the web page document...
, and Perl
Perl
Perl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...
Other implementations
LibgcryptLibgcrypt
libgcrypt is a cryptographic library developed as a separated module of GnuPG . It can also be used independently of GnuPG, although it requires its error-reporting library....
: A general purpose cryptographic library based on the code from GNU Privacy Guard
GNU Privacy Guard
GNU Privacy Guard is a GPL Licensed alternative to the PGP suite of cryptographic software. GnuPG is compliant with RFC 4880, which is the current IETF standards track specification of OpenPGP...
.
OpenSSL
OpenSSL
OpenSSL is an open source implementation of the SSL and TLS protocols. The core library implements the basic cryptographic functions and provides various utility functions...
: The widely used OpenSSL
crypto library includes freeFree software
Free software, software libre or libre software is software that can be used, studied, and modified without restriction, and which can be copied and redistributed in modified or unmodified form either without restriction, or with restrictions that only ensure that further recipients can also do...
, open-source
Open source
The term open source describes practices in production and development that promote access to the end product's source materials. Some consider open source a philosophy, others consider it a pragmatic methodology...
– implementations of SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512
cryptlib
Cryptlib
cryptlib is an open source cross-platform software security toolkit library. It is distributed under the Sleepycat License, a free software license compatible with the GNU General Public License...
: an open source
Open source
The term open source describes practices in production and development that promote access to the end product's source materials. Some consider open source a philosophy, others consider it a pragmatic methodology...
cross-platform software security toolkit library
Crypto++
Crypto++
Crypto++ is a free and open source C++ class library of cryptographic algorithms and schemes written by Wei Dai. Crypto++ has been widely used in academia, student projects, open source and non-commercial projects, as well as businesses...
: A public domain C++ class library of cryptographic schemes, including implementations of the SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512 algorithms.
Bouncy Castle
Bouncy castle (cryptography)
Bouncy Castle is a collection of APIs used in cryptography. It includes APIs for both the Java and the C# programming languages.Bouncy Castle is Australian in origin and thus American restrictions on the export of cryptographic software do not apply to it....
: The Bouncy Castle Library is a free Java and C# class library that contains implementations of the SHA-1, SHA-224, SHA-256, SHA-384 and SHA-512 algorithms as well as other algorithms like Whirlpool, Tiger
Tiger (hash)
In cryptography, Tiger is a cryptographic hash function designed by Ross Anderson and Eli Biham in 1995 for efficiency on 64-bit platforms. The size of a Tiger hash value is 192 bits. Truncated versions can be used for compatibility with protocols assuming a particular hash size...
, RIPEMD
RIPEMD
RIPEMD-160 is a 160-bit message digest algorithm developed in Leuven, Belgium, by Hans Dobbertin, Antoon Bosselaers and Bart Preneel at the COSIC research group at the Katholieke Universiteit Leuven, and first published in 1996...
, GOST-3411, MD2, MD4
MD4
The MD4 Message-Digest Algorithm is a cryptographic hash function developed by Ronald Rivest in 1990. The digest length is 128 bits. The algorithm has influenced later designs, such as the MD5, SHA-1 and RIPEMD algorithms....
and MD5
MD5
The MD5 Message-Digest Algorithm is a widely used cryptographic hash function that produces a 128-bit hash value. Specified in RFC 1321, MD5 has been employed in a wide variety of security applications, and is also commonly used to check data integrity...
.
jsSHA: A cross-browser JavaScript
JavaScript
JavaScript is a prototype-based scripting language that is dynamic, weakly typed and has first-class functions. It is a multi-paradigm language, supporting object-oriented, imperative, and functional programming styles....
library for client-side calculation of SHA digests, despite the fact that JavaScript does not natively support the 64-bit operations required for SHA-384 and SHA-512.
LibTomCrypt: A portable ISO C cryptographic toolkit, Public Domain.
md5deep
Md5deep
md5deep is a software package used in the computer security, system administration and computer forensics communities for purposes of running large numbers of files through any of several different cryptographic digests...
: A set of programs to compute MD5, SHA-1, SHA-256, Tiger, or Whirlpool cryptographic message digests on an arbitrary number of files. It is used in computer security, system administration and computer forensics communities for purposes of running large numbers of files through any of several different cryptographic digests. It is similar to sha1sum
Sha1sum
sha1sum is a computer program that calculates and verifies SHA-1 hashes. It is commonly used to verify the integrity of files. It is installed by default in most Unix-like operating systems...
from GNU Core Utilities
GNU Core Utilities
The GNU Core Utilities or coreutils is a package of GNU software containing many of the basic tools, such as cat, ls, and rm, needed for Unix-like operating systems...
and md5sum
Md5sum
md5sum is a computer program that calculates and verifies 128-bit MD5 hashes, as described in RFC 1321. The MD5 hash functions as a compact digital fingerprint of a file. As with all such hashing algorithms, there is theoretically an unlimited number of files that will have any given MD5 hash...
.
sphlib: A free, open-source
Open source
The term open source describes practices in production and development that promote access to the end product's source materials. Some consider open source a philosophy, others consider it a pragmatic methodology...
library which implements many hash functions, including SHA-1 and SHA-2, both in portable (but optimized) C and in Java.
VHDL: A free, open-source
Open source
The term open source describes practices in production and development that promote access to the end product's source materials. Some consider open source a philosophy, others consider it a pragmatic methodology...
collection of hardware implementations of hash functions (including SHA-1 and SHA-2) in portable (but optimized) VHDL.