February 26, 2005

Is SHA-1 Pareto-secure?

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-complete Pareto-secure
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
Post a comment

Remember personal info?

Hit preview to see your comment as it would be displayed.