APPLICATION NOTE 3522

Abstract: In 2005, a group of Chinese researchers attacked the strength of the Secure Hash Algorithm (SHA-1). This white paper discusses that attack and shows that, although the algorithm is slightly less collision-resistant than previously thought, the security of the SHA-1 memory devices from Maxim is not affected. Thus, the company's SHA-1 memory devices (DS1963S, DS1961S, DS2460, DS28CN01, DS28E01-100 and DS2432), will continue to provide a low-cost, effective solution for accessory/peripheral authentication and tamper-proof, verifiable memory applications.

Ultimately, the utility of these devices depends on the robustness and security of the Secure Hash Algorithm, as defined by the U.S. National Institute of Standards and Technology (NIST) in Federal Information Processing Standards Publication 180-1 (FIPS PUB 180-1) and ISO/IEC 10118-3. In 2005, a group of Chinese researchers published a report showing how they had attacked the strength of this algorithm (see Note 1). This application note shows that, although some applications which use SHA-1 might need to reevaluate the security provided, the security of Maxim SHA-1 memory devices is not compromised by this research claim.

The theoretical bound for the number of hash operations required to find a collision (a pair of messages which share the same digest) is 2

Although the second SHA-1 algorithm assertion is weakened by this new Chinese research, there is no reason to suspect that the research will lead to any attacks on the first SHA-1 claim. Thus in summary,

A successful attack on the algorithm of this MAC-based security system would require discovery of the secret key. In most of the available SHA-1 memory devices, this key is a 64-bit write-only value. (Newer devices may soon be available with an even larger key.) An attacker could issue a challenge to a device, read the resulting MAC, and then execute a brute-force search of the full 64-bit value until it found a MAC that matched. This action would require 2

Finding a message, which matches the digest of any given input message, requires 2

Note that although the complexity of 2

- X. Wang, Y.L. Yin, and H. Yu., Finding Collisions in the Full SHA-1, Advances in Cryptology—Crypto'05 at: http://www.infosec.sdu.edu.cn/paper/sha1-crypto-auth-new-2-yao.pdf (PDF)
- Finding collisions in SHA-1 has an upper bound of 2
^{80}because of the "birthday paradox." Basically, this paradox says that if you are attempting to match any two elements with n-bits of output, you only have to consider 2^{(n/2)}elements, not 2^{(n)}elements, to have an extremely high probability of finding a match. This is a well-known cryptographic property of all hashes and is determined only by the number of bits in the output. - The SHA-1 algorithm performs about 1740 basic arithmetic operations on the message block elements. Assuming 20% overhead for additional manipulation, a complete turn of the algorithm will run in 2100 clock cycles. Using a Cray X1 supercomputer with 64 CPUs (Cray's largest scale, single-cabinet configuration as of year 2005) operating at peak performance of 819 gigaflops, it would require 12.4 years of continuous operation to generate a complete look-up table. Cray's largest advertised X1 system, with 64 cabinets, would take over two months. That much computing power makes this type of attack cost-prohibitive.