CypheRix       

Report of SHA-1 Broken and the CypheRix Evidence Gatherer System

Manfred von Willich
CypheRix (Pty) Ltd
2005-02-22

Summary

The recently reported SHA-1 weakness presents a threat only to those systems that rely on the algorithm’s resistance to birthday attacks – in which the attacker provides both the original and substitute text.

The CypheRix Evidence Gatherer System relies only on a different property – that a collision with a given hash cannot be found – and is hence not affected by the weakness.

Further in the new USB Evidence Enrolment Devices we place a 160 bit chaining value ahead of the data being signed. In the case of the first segment of data being signed a 160 bit nonce (random number) generated by the Device is inserted. This will protect our solution from all similar attacks of this genre.

It should be noted that more than three years after the initial publication of the attack no practical attacks have yet to be published. 

The following additional information should be noted than assisted us in our decision to remain with SHA1 for now:

1. SHA1 has had far more extensive pier review than SHA2.

2. The computation effort required from SHA256 is significantly higher than that required for SHA1.

3. Many other major players have not moved away from SHA1 in spite of a lot of talk.

The Report

Bruce Schneier reported on 15 February 2005 that SHA-1 has been broken – specifically, that an unpublished paper has claimed that collisions should be expected in 2⁶⁹ SHA-1 operations.

What does “broken” mean?

For symmetric ciphers and hash functions, the cryptographer’s definition of “broken” is finding an attack (even if only theoretical) that requires less work than a brute force search to circumvent an intended cryptographic property.  Use of other resources (e.g. the need for large amounts of data storage) is often ignored.  This is definition is generally not applied to public key algorithms, since every known public key algorithm is broken by this definition.

By way of clarifying the concept, a symmetric cipher that has a 16-bit key is not broken if the easiest method (in terms of required computing power) involves testing each of the possible keys to determine the correct key given plaintext/ciphertext pairs (i.e. a brute force search).  Yet a brute force search is easy (a maximum of 2¹⁶ applications of the cipher will be necessary, which would be very quick on a PC).  From this example it should be clear that “broken” and “insecure” are not synonymous.

The concept of whether an algorithm is broken or not is nevertheless useful.  It gives us a sense of whether we can directly gauge a lower limit on the security of the algorithm against applicable attacks from its visible parameters (such as key size, block size and cost applying the algorithm).

What cryptographic property of SHA-1 is broken?

The desired properties of a cryptographic hash function are that it should be secure with respect to:

(a)           Finding the plaintext from the output hash value (known as the message digest),

(b)          Finding a second text for which the hashes collide (are equal) given an input text, and

(c)           Finding an arbitrary pair of input texts for which the hashes collide.

These properties may be described respectively as (a) one-way function, (b) known text collision-free, and (c) birthday attack collision-free.

The published attack is a birthday attack, i.e. on property (c).  In such an attack, it is assumed that a system may be attacked if the attacker can find a collision of two arbitrary texts (i.e. he does not get to choose either), get the system to accept the one, and then exploits the collision to substitute the other.  The key point is that this is an applicable attack only when the attacker can get the system to accept and sign an arbitrary text.

Note that in contexts where the diversity of the inputs is known and restricted, hash functions are inherently insecure with regard to property (a) – the one-way property.  For example, if it is known that the input text is no more than say 32 bits long, it is a simple matter to locate the correct input text by a brute force search.

What properties of SHA-1 does the CypheRix Token System and Certified Recorder rely upon?

The CypheRix Certified Recorder uses the cryptographic strength of SHA-1 in digital signatures for authenticating key exchanges and for signing audio.  The security of this relies specifically on property (b).

The report of a theoretical birthday attack does suggest that the other properties for which SHA-1 is used could be broken.  This is definitely not a cause for immediate concern, since the work factor of brute force is very high (2¹⁶⁰), and a work factor in excess of 2¹⁰⁰ is acceptable for the near future.  When an attack suggests a work factor for locating collisions (for a birthday attack) of below 2⁵⁰ we may have cause for concern in this regard.

The weakest link

A system may use cryptography to enhance the security of a system.  The security of the system will always also rely on many factors that lie outside the field of interest of cryptographers, which is primarily the “black box” properties of the algorithms used.  Placing too much emphasis on the exact strength of the (very strong) algorithms tends to divert attention from the weakest points against attack – such as the implementation and operational procedures.

Note too that the security of the system relies crucially upon the strength of the RSA system.  Not only RSA is seriously broken is the sense defined above (for which we compensate by using enormous key sizes), number factoring algorithm are being intensively investigated.  Breakthroughs in this area may be a more immediate threat than threats to the hash functions involved.

Putting it into context…

DES has been broken for a long time using differential and linear cryptanalysis.  However, the only attack on this cipher that anyone is known to have implemented is a brute force attack, despite its extensive use commercially.  Thus, a cipher known to have been broken is not necessarily as insecure as a “break” may suggest, primarily because the typical skill requirement and cost of implementing such an attack is high (generally ignored in estimations), whereas a brute force attack is simple.

Even AES may theoretically be broken (http://www.schneier.com/crypto-gram-0209.html).  Yet there is little concern.

To date, no actual collisions have been found on SHA-1 – meaning that the attack is strictly theoretical and no practical implementation exists yet.  It is doubtful whether anyone will mount a serious birthday attack on this algorithm in the next decade unless the attack is substantially improved.  Until a collision is found, no one can mount a birthday attack on a system – and then only on systems where such an attack is applicable.

Conclusion

No immediate cryptographic threat exists to the security of the CypheRix Evidence Gatherer System.  As a treat becomes significant, it should be possible to update the system to counter the threat.