SHA-0/SHA-1 Reduced Operation Digest Collision Weakness

Bugtraq ID:	12577
Class:	Design Error
CVE:	CVE-2005-4900
Remote:	Yes
Local:	No
Published:	Feb 15 2005 12:00AM
Updated:	May 28 2018 11:00AM
Credit:	Discovery is credited to Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu.
Vulnerable:	NSA SHA-1 Algorithm NSA SHA-0 Algorithm Fortinet Fortios 5.6 Fortinet Fortios 5.4.8 Fortinet Fortios 5.4.7 Fortinet Fortios 5.4.6 Fortinet Fortios 5.4.5 Fortinet Fortios 5.4.4 Fortinet Fortios 5.4.3 Fortinet Fortios 5.4.2 Fortinet Fortios 5.4.1 Fortinet Fortios 5.2.12 Fortinet Fortios 5.2.11 Fortinet Fortios 5.2.8 Fortinet Fortios 5.2.6 Fortinet Fortios 5.2.5 Fortinet Fortios 5.2.4 Fortinet Fortios 5.2.3 Fortinet Fortios 5.2.2 Fortinet Fortios 5.2.1 Fortinet Fortios 5.0.13 Fortinet Fortios 5.0.9 Fortinet Fortios 5.0.8 Fortinet Fortios 5.0.7 Fortinet FortiOS 5.0.3 Fortinet FortiOS 5.0.2 Fortinet FortiOS 5.0.1 Fortinet Fortios 4.7.7 Fortinet Fortios 4.3.19 Fortinet Fortios 4.3.17 Fortinet Fortios 4.3.15 Fortinet FortiOS 4.3.10 Fortinet Fortios 4.3.9 Fortinet FortiOS 4.3.8 Fortinet Fortios 4.3 Fortinet Fortios 4.2.13 Fortinet Fortios 4.2.12 Fortinet Fortios 4.1.11 Fortinet Fortios 4.1.10 Fortinet FortiOS 3.0 Fortinet FortiOS 2.80 Fortinet FortiOS 2.50 Fortinet FortiOS 2.36 Fortinet Fortios 5.4.0 Fortinet Fortios 5.4 Fortinet Fortios 5.2.9 Fortinet Fortios 5.2.10 Fortinet Fortios 5.2.0 Fortinet Fortios 5.2 Fortinet Fortios 5.0.6 Fortinet FortiOS 5.0.5 Fortinet Fortios 5.0.4 Fortinet Fortios 5.0.12 Fortinet Fortios 5.0.11 Fortinet Fortios 5.0.0 Fortinet FortiOS 5.0 Fortinet Fortios 4.3.18 Fortinet Fortios 4.3.16 Fortinet FortiOS 4.3.14 Fortinet FortiOS 4.3.13 Fortinet FortiOS 4.3.12
Not Vulnerable:	Fortinet Fortios 5.6.1

SHA-0/SHA-1 Reduced Operation Digest Collision Weakness

Researchers Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu have allegedly devised attacks that will reduce the number of operations required to compute an input that generates a collision in SHA-0/SHA-1 digests. This weakness may threaten the integrity of digital signatures that are generated using these algorithms, since it may be possible to create identical signatures using different input data.

The research paper describing these attacks is not publicly available at this time; the results have not been vetted by others in the field. We will update this BID as more information emerges.

UPDATE (June 11, 2009): Further investigation by other researchers (Cameron McDonald Philip Hawkes and Josef Pieprzyk) has reduced SHA-1 collisions to 2**52 hash operations.

SHA-0/SHA-1 Reduced Operation Digest Collision Weakness

Currently we are not aware of any working exploits. If you feel we are in error or if you are aware of more recent information, please mail us at: [email protected].

SHA-0/SHA-1 Reduced Operation Digest Collision Weakness

Solution:
Currently we are not aware of any vendor-supplied patches. If you feel we are in error or if you are aware of more recent information, please mail us at: [email protected].

SHA-0/SHA-1 Reduced Operation Digest Collision Weakness

References:

• Crypto attack puts digital sig hash on collision course (Dan Goodin)
  
• Differential Path for SHA-1 with complexity O(252) (Cameron McDonald Philip Hawkes and Josef Pieprzyk)
  
• SHA-1 Broken (Bruce Schneier)