What is SHA-1 (Encryption)

SHA-1 (Secure Hash Algorithm) is a cryptographic hash function designed by the National Security Agency of the United States (NSA) and published by the U.S. government as a standard Federal Information Processing (Federal Information Processing Standard NIST). It produces a result (called a "hash") of 160 bits.

Origin of SHA-0 and SHA-1

SHA-1 is the successor of SHA-0, which was quickly set aside by NIST for security reasons. SHA-0 was legitimately suspected to contain loopholes that would quickly lead to collisions (two different documents that generate the same hash). Given the controversy surrounding the operation of SHA-0 and some findings that attributed to NSA, the SHA-0 was amended shortly after its release (1993) and this led to getting SHA-1 (1995) . A collision on the full SHA-0 was recently discovered by Antoine Joux et al. (August 2004) and suggests that the SHA-1 could also suffer an attack.

Attacks

An attack based on the paradox of anniversaries to find a collision on the full SHA-1 with a number of operations of about 280.

In 2005, Rijmen and Oswald published an attack on a simplified version of SHA-1 (53 laps), their attack was to find a collision with fewer than 280 transactions.

In February 2005, Bruce Schneier reported an attack on the full version of SHA-1 by the Chinese team of Wang, Yin and Yu Their method found:

* A collision in SHA-1 full 128-bit operations with 269 instead of 280 by the paradox of anniversaries

* A collision in SHA-0 with only 239 full operations

* A collision in a simplified version of SHA-1 (58 laps) with 233 operations

The description of the attack was published in June 2005.

On 17 August 2005, an improvement of the attack was announced by Wang et al. CRYPTO conference in 2005, the complexity rises from 269 to 263, and is a division by 64 of the original complexity.

Consequences

Even if a gain of 217 operations can divide the search time by a factor of 131,072, the attack with 263 operations is at the limit of what is achievable. Adi Shamir, however suggested that the attack could probably be addressed through distributed computing on a global scale.

Moreover, with 263 operations, the attack is below the 264 needed for an exhaustive search on a MD5 (no longer recommended for new applications). Having lost a step ahead after the announcement of the attack by Wang et al., SHA-1 was phased out of cryptographic applications in favor of SHA-256 or other hash functions like Whirlpool or Tiger. The voices are already calling for a new hash standard, as was the case some years ago, symmetric encryption with AES.

The attack occurred by Wang et al. That is to say that we can find two messages using random content producing the same signature. However, this type of attack that could endanger applications like PGP and authenticity methods.

It was originally proposed by Apple that the i-phone have native SHA encryption. However, it was dropped as it was found that the cell phone processor was not efficient enough to calculate the hash within a reasonable time frame.