SHA-0 and SHA- 1 can convert a 64-bit message with a maximum of 2 into a series of 160-bit message digests; Its design principle is similar to the encryption hash algorithms MD4 and MD5 designed by MIT professor Ronald L. Rivest. On CRYPTO 98, two French researchers proposed an attack method on SHA-0: within the computational complexity of 26 1, a collision can be found (that is, two different messages correspond to the same message digest); This number is less than the 80th power of 2 required by the birthday attack method, that is, there is an algorithm that makes its security less than the computational complexity of an ideal hash function to resist attacks.
In 2004, Biham and Chen also found the approximate collision of SHA-0, that is, two messages can hash out almost the same value; Where 142 bits are the same. They also found the complete collision of SHA-0 (relative to the approximate collision), which reduced the complexity from 80 to 62.
On August 12, 2004, Joux, Carribault, Lemuet and Jalby published a method to find the complete collision of SHA-0 algorithm, which is the result of summarizing Chabaud and Joux attacks. Finding a complete collision requires only 25 1 computational complexity. They used a supercomputer with 256 Itanium2 processors, which consumed about 80,000 CPU man-hours.
On August 17, 2004, Feng Dengguo, Lai and Li announced the preliminary results of attacking MD5, SHA-0 and other hash functions at the Rump meeting of CRYPTO 2004. The computational complexity of their attack on SHA-0 is 2 to the 40th power, which means that their attack results are better than those of Joux and others. See MD5 security. In February, 2005, Wang Xiaoyun, Yin Yiqun and Yu Hongbo once again published an algorithm to crack the SHA-0 secret, which can find collisions within the computational complexity of 2 to the 39th power. In view of SHA-0' s secret breaking achievements, experts suggest that those who intend to use SHA- 1 to implement the cryptographic system should also reconsider. After the results of the 2004 password conference were announced, NIST announced that they would gradually reduce the use of SHA- 1 and replace it with SHA-2.
In 2005, Rijmen and Oswald published an attack on the weaker version of SHA- 1 (53 encryption cycles instead of 80): collisions were found within the computational complexity of 2 to the 80th power.
In February 2005, Wang Xiaoyun, Yin Yiqun and Yu Hongbo published an attack on SHA- 1 full version. A set of collisions can be found with computational complexity less than 2 to the 69th power. (Using birthday attacks to find collisions requires a computational complexity of 2 to the 80th power. )
The author of this paper wrote: "Our secret cracking analysis is based on differential cryptanalysis, approximate collision, multi-block collision technology to deal with SHA-0, and information change technology to find collision from MD5 algorithm. Without these powerful analysis tools, SHA- 1 cannot be cracked. " In addition, the author also shows a 58th encryption cycle SHA- 1, and finds a group of collisions in the 33rd unit operation of 2. The paper on the complete attack method was published at the CRYPTO conference in August 2005.
Yin Yiqun stated in the interview: "Overall, we found two weaknesses: one is that the pretreatment is not complicated enough; The second is that some mathematical operations in the first 20 cycles will cause unpredictable security problems. "
Wang Xiaoyun, Yao Qizhi and Yao Chufeng once again published a more efficient SHA- 1 attack method at the end of the CRYPTO meeting on August 7th, 2005, which can find collisions within the 63rd power of 2.
At the CRYPTO conference in 2006, Christian Rechberger and Christophe De Cannière announced that they could find the collision of SHA- 1 if attackers were allowed to decide part of the original message.
In the academic theory of cryptography, if the computational complexity of any attack method is less than that of the brute force search method, it can be considered as a method to break the password system; But this does not mean that the secret cracking method can already enter the practical application stage.
As far as the application level is concerned, there are new ways to break secrets, suggesting that there may be more efficient and practical improved versions in the future. Although these practical versions of secret cracking have not yet been born, it is necessary to develop stronger hash algorithms to replace the old ones. In addition to the "collision" attack method, there is also a pre-image attack method, which is to reverse the original message from the hashed string; Anti-translation attack is more serious than collision attack, but it is also more difficult. In many cases, it will be applied to password hashing (such as storage of user passwords, digital signature of files, etc.). ), the impact of collision attack is not great. For example, an attacker may not only want to forge an identical document, but also want to transform the original document and attach a legal signature to deceive the verifier who holds the private key. On the other hand, if the user's password before encryption can be deduced from the ciphertext, the attacker can use the obtained password to log in other users' accounts, which is not allowed in the password system. However, if there is a reverse translation attack, as long as the hash string of the specified user password can be obtained (usually in the shadow file, the original password information may not be revealed), it is possible to obtain the user password. The following is the pseudo code of SHA- 1 algorithm:
Initialize variables:
h0 := 0x6745230 1
h 1 := 0xEFCDAB89
h2 := 0x98BADCFE
h3 := 0x 10325476
h4 := 0xC3D2E 1F0
Pretreatment:
Append the bit "1" to the message.
Add k bit "0", where k is the minimum number > = 0, and the message thus obtained.
Length (bit) is equal to 448 (mod 5 12)
Additional message length (before preprocessing), in bits, is a 64-bit big-endian integer.
Processing messages in consecutive 5 12 bit blocks:
Divide the message into blocks of 5 12 bits.
For each block
Divide the block into 16 32-bit big word w[i], 0 ≤ i ≤ 15.
Expand 16 32-bit words to 80 32-bit words:
From 16 to 79
w[I]:=(w[I-3]xor w[I-8]xor w[I- 14]xor w[I- 16])left rotate 1
Initialize the hash value of this block:
Answer: = h0
b := h 1
c := h2
d := h3
e := h4
Main loop:
From 0 to 79 for I
If 0 ≤ i ≤ 19, then
F := (b and c) or ((not b and d)
k := 0x5A827999
Otherwise, if 20 ≤ i ≤ 39
F := b XOR c XOR d
k := 0x6ED9EBA 1
Otherwise, if 40 ≤ i ≤ 59
F := (b and c) or (b and d) or (c and d)
k := 0x8F 1BBCDC
Otherwise, if 60 ≤ i ≤ 79
F := b XOR c XOR d
k := 0xCA62C 1D6
temp:=(a left rotate 5)+f+e+k+w[I]
e := d
d := c
C := b rotate 30 to the left.
B: = A.
Answer: = temperature
Add the hash of this block to the current result:
h0 := h0 + a
h 1 := h 1 + b
h2 := h2 + c
h3 := h3 + d
h4 := h4 + e
Generate the final hash value (big endian):
digest = hash = h0 append h 1 append H2 append H3 append H4