Just a week or two before the SHA-1 news from Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu, I wrote a paper on what it means to be secure. In a flash of inspiration, I hit on applying the methodology of Pareto-efficiency to security.
In brief, I define a Pareto-secure improvement to be one where a change made to a component results in a measurable and useful improvement in security results, at no commensurate loss of security elsewhere. And a component is Pareto-secure if there is no further improvement to be made. I further go on to say that a component is Pareto-complete if it is Pareto-secure under all reasonable assumptions and in all reasonable systems. See the draft for more details!
SHA-1 used to be Pareto-complete. I fear this treasured status was cast in doubt when Wang's team of champions squared up against it at Crypto2004 last year; the damaging note, 'Collision Search Attacks on SHA1,' of a week or two back has dealt a further blow.
Here's the before and after. I wrote this before the new information, but I haven't felt the need to change it yet.
| Before Crypto 2004 | After Crypto 2004 | |||
|---|---|---|---|---|
| Pareto-secure (signatures) |
Pareto-complete | Pareto-secure (signatures) |
Pareto-complete | |
| MD5 | ? | No | No | No |
| SHA0 | Yes | ? | No | No |
| SHA1 | Yes | Yes | ? | No |
| SHA256 | Yes | Yes | Yes | ? |
To be Pareto-complete, the algorithm must be good for all uses. To be Pareto-secure, the algorithm must be good - offer no Pareto-improvement - for a given application and set of assumptions. In order to stake that claim, I considered above the digital signature, in the sense of for example DSA.
Posted by iang at February 26, 2005 09:21 PM | TrackBack