Re: MD6 withdrawn from SHA-3 competition

2009-07-07 Thread Josh Rubin
Paul Hoffman wrote:
> At 10:39 AM -0700 7/4/09, Hal Finney wrote:
>   
>> But how many other hash function candidates would also be excluded if
>> such a stringent criterion were applied? Or turning it around, if NIST
>> demanded a proof of immunity to differential attacks as Rivest proposed,
>> how many candidates have offered such a proof, in variants fast enough
>> to beat SHA-2?
>> 
>
> The more important question, and one that I hope gets dealt with, is
> what is a sufficient proof. We know what proofs are, but we don't have
> a precise definition. We know what a proof should look like, sort
> of. Ron and his crew have their own definition, and they can't make
> MD6 work within that definition. But that doesn't mean that NIST
> wouldn't have accepted the fast-enough MD6 with a proof from someone
> else. 

Mathematicians have a precise definition of what a proof is, thanks to
logicians like David Hilbert and Kurt Goedel. But people in all
disciplines have a terrible time formulating problems, and remembering
the conditions under which a statement was proved. They also quote
theorems incorrectly, and errors propagate through the less
well-reviewed parts of the literature.

--
Josh Rubin
jlru...@gmail.com

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com


Re: MD6 withdrawn from SHA-3 competition

2009-07-07 Thread Chen Ke-Fei Lin
At 10:39 AM -0700 7/4/09, Hal Finney wrote:
>But how many other hash function candidates would also be excluded if
>such a stringent criterion were applied? Or turning it around, if NIST
>demanded a proof of immunity to differential attacks as Rivest proposed,
>how many candidates have offered such a proof, in variants fast enough
>to beat SHA-2?

Several hash candidates have proofs against differential attacks but only
four with such proofs are faster than SHA-2 (Edon-R, Shabal, Cheetah and
Keccak).
But according to http://eprint.iacr.org/2008/511.pdf
Keccak and Cheetah in 32-bit mode are not actually faster than SHA-2.

C.K.F. Lin

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com


Re: MD6 withdrawn from SHA-3 competition

2009-07-06 Thread Ray Dillinger
On Sat, 2009-07-04 at 10:39 -0700, "Hal Finney" wrote:
> Rivest:
> > Thus, while MD6 appears to be a robust and secure cryptographic
> > hash algorithm, and has much merit for multi-core processors,
> > our inability to provide a proof of security for a
> > reduced-round (and possibly tweaked) version of MD6 against
> > differential attacks suggests that MD6 is not ready for
> > consideration for the next SHA-3 round.
> 
> But how many other hash function candidates would also be excluded if
> such a stringent criterion were applied? Or turning it around, if NIST
> demanded a proof of immunity to differential attacks as Rivest proposed,
> how many candidates have offered such a proof, in variants fast enough
> to beat SHA-2?

I think "resistance to attacks" (note absence of any restrictive
adjective such as "differential") is a very important property 
(indeed, one of the basic defining criteria) to demonstrate 
in a hash algorithm.  If someone can demonstrate an attack, 
differential or otherwise, or show reason to believe that such
an attack may exist, then that should be sufficient grounds 
to eliminate a vulnerable candidate from any standardization 
competition. 

In other words, the fact that MD6 can demonstrate resistance to 
a class of attacks, if other candidates cannot, should stand in 
its favor regardless of whether the competition administrators 
say anything about proving resistance to any particular *kind* 
of attacks.  If that does not stand in its favor then the 
competition is exposed as no more than a misguided effort to 
standardize on one of the many Wrong Solutions.  


Bear




-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com


Re: MD6 withdrawn from SHA-3 competition

2009-07-06 Thread Paul Hoffman
At 10:39 AM -0700 7/4/09, Hal Finney wrote:
>But how many other hash function candidates would also be excluded if
>such a stringent criterion were applied? Or turning it around, if NIST
>demanded a proof of immunity to differential attacks as Rivest proposed,
>how many candidates have offered such a proof, in variants fast enough
>to beat SHA-2?

The more important question, and one that I hope gets dealt with, is what is a 
sufficient proof. We know what proofs are, but we don't have a precise 
definition. We know what a proof should look like, sort of. Ron and his crew 
have their own definition, and they can't make MD6 work within that definition. 
But that doesn't mean that NIST wouldn't have accepted the fast-enough MD6 with 
a proof from someone else.

--Paul Hoffman, Director
--VPN Consortium

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com


Re: MD6 withdrawn from SHA-3 competition

2009-07-05 Thread "Hal Finney"
Rivest:
>   Thus, while MD6 appears to be a robust and secure cryptographic
>   hash algorithm, and has much merit for multi-core processors,
>   our inability to provide a proof of security for a
>   reduced-round (and possibly tweaked) version of MD6 against
>   differential attacks suggests that MD6 is not ready for
>   consideration for the next SHA-3 round.

But how many other hash function candidates would also be excluded if
such a stringent criterion were applied? Or turning it around, if NIST
demanded a proof of immunity to differential attacks as Rivest proposed,
how many candidates have offered such a proof, in variants fast enough
to beat SHA-2?

Hal Finney

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com


Re: MD6 withdrawn from SHA-3 competition

2009-07-05 Thread Paul Hoffman
At 11:49 PM -0400 7/3/09, Steven M. Bellovin wrote:
>Here's the essential paragraph:
>
>   Thus, while MD6 appears to be a robust and secure cryptographic
>   hash algorithm, and has much merit for multi-core processors,
>   our inability to provide a proof of security for a
>   reduced-round (and possibly tweaked) version of MD6 against
>   differential attacks suggests that MD6 is not ready for
>   consideration for the next SHA-3 round.

At 10:12 AM + 7/4/09, Brandon Enright wrote:
>It wasn't entirely clear to me if it really was withdrawn.  Ron Rivest
>posted on behalf of the MD6 team some thoughts on MD6 performance and
>specifically suggested/requested that NIST ask for submitted algorithms
>to be "provably resistant to differential attacks".

I agree more with Brandon than with Steve, but who knows. I read Ron's message 
as a challenge to NIST about whether or not NIST would really rely on the 
proofs. It was clear they didn't want to withdraw MD6, but that they felt like 
they had to because of the speed requirement.




--Paul Hoffman, Director
--VPN Consortium

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com


Re: MD6 withdrawn from SHA-3 competition

2009-07-04 Thread Brandon Enright
On Thu, 2 Jul 2009 20:51:47 -0700 or thereabouts "Joseph Ashwood"
 wrote:

> Sent: Wednesday, July 01, 2009 4:05 PM
> Subject: MD6 withdrawn from SHA-3 competition
> 
> > Also from Bruce Schneier, a report that MD6 was withdrawn from the
> > SHA-3 competition because of performance considerations.
> 
> I find this disappointing. With the rate of destruction of primitives
> in any such competition I would've liked to see them let it stay
> until it is either broken or at least until the second round. A quick
> glance at the SHA-3 zoo and you won't see much left with no attacks.
> It would be different if it was yet another M-D, using AES as a
> foundation, blah, blah, blah, but MD6 is a truly unique and
> interesting design.
> 
> I hope the report is wrong, and in keeping that hope alive, the MD6
> page has no statement about the withdrawl.
> Joe 
> 

It wasn't entirely clear to me if it really was withdrawn.  Ron Rivest
posted on behalf of the MD6 team some thoughts on MD6 performance and
specifically suggested/requested that NIST ask for submitted algorithms
to be "provably resistant to differential attacks".

The logic was that MD6 is slow because the high number of rounds is
needed in their proof.  They won't tweak/submit a version that doesn't
meet this requirement of theirs and based on the current contest
requirements, they can't be competitive speed-wise without losing their
proof of resistance to differential attacks.  Unless the contest
changes to require such a proof, there is no point in moving MD6
forward.

Brandon

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com


Re: MD6 withdrawn from SHA-3 competition

2009-07-04 Thread Steven M. Bellovin
On Thu, 2 Jul 2009 20:51:47 -0700
"Joseph Ashwood"  wrote:

> --
> Sent: Wednesday, July 01, 2009 4:05 PM
> Subject: MD6 withdrawn from SHA-3 competition
> 
> > Also from Bruce Schneier, a report that MD6 was withdrawn from the
> > SHA-3 competition because of performance considerations.
> 
> I find this disappointing. With the rate of destruction of primitives
> in any such competition I would've liked to see them let it stay
> until it is either broken or at least until the second round. A quick
> glance at the SHA-3 zoo and you won't see much left with no attacks.
> It would be different if it was yet another M-D, using AES as a
> foundation, blah, blah, blah, but MD6 is a truly unique and
> interesting design.
> 
> I hope the report is wrong, and in keeping that hope alive, the MD6
> page has no statement about the withdrawl.

The report is quite correct.  Rivest sent a note to NIST's hash forum
mailing list (http://csrc.nist.gov/groups/ST/hash/email_list.html)
announcing the withdrawal.  Since a password is necessary to access the
archives (anti-spam?), I don't want to post the whole note, but Rivest
said that they couldn't improve MD6's performance to meet NIST's
criteria (at least as fast as SHA-2); the designers of MD6 felt that
they could not manage that and still achieve provable resistance to
differential attacks, and they regard the latter as very important.
Here's the essential paragraph:

Thus, while MD6 appears to be a robust and secure cryptographic
hash algorithm, and has much merit for multi-core processors,
our inability to provide a proof of security for a
reduced-round (and possibly tweaked) version of MD6 against
differential attacks suggests that MD6 is not ready for
consideration for the next SHA-3 round.


--Steve Bellovin, http://www.cs.columbia.edu/~smb

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com


Re: MD6 withdrawn from SHA-3 competition

2009-07-03 Thread Joseph Ashwood

--
Sent: Wednesday, July 01, 2009 4:05 PM
Subject: MD6 withdrawn from SHA-3 competition


Also from Bruce Schneier, a report that MD6 was withdrawn from the SHA-3
competition because of performance considerations.


I find this disappointing. With the rate of destruction of primitives in any 
such competition I would've liked to see them let it stay until it is either 
broken or at least until the second round. A quick glance at the SHA-3 zoo 
and you won't see much left with no attacks. It would be different if it was 
yet another M-D, using AES as a foundation, blah, blah, blah, but MD6 is a 
truly unique and interesting design.


I hope the report is wrong, and in keeping that hope alive, the MD6 page has 
no statement about the withdrawl.
   Joe 


-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com


MD6 withdrawn from SHA-3 competition

2009-07-01 Thread Perry E. Metzger

Also from Bruce Schneier, a report that MD6 was withdrawn from the SHA-3
competition because of performance considerations.

http://www.schneier.com/blog/archives/2009/07/md6.html

Perry
-- 
Perry E. Metzgerpe...@piermont.com

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com