Re: rsync and md4

-----BEGIN PGP SIGNED MESSAGE-----

> 
> "David F. Ogren" writes:
> > > I'm afraid you are totally wrong here. MD4 has been completely
> > > broken. I wouldn't trust it for anything. In fact, MD5 is no longer
> > > trustworthy, either -- it was broken recently. Stick to SHA.
> > > 
> > 
> > MD4 has had successful attacks on limited rounds.  It has _not_ been 
> > completely cracked.
> 
> Could you please quit spewing inaccurate information?
> 
> Dobbertin completely cracked MD4 already, and found MD5 collisions in
> a document circulated on May 2nd that mean it isn't far behind.
> 
> The comments you are making are dangerous because they encourage
> people who don't know better to think that hashes which are known
> unsafe are safe. Please quit posting until you start monitoring the
> field enough to have accurate sources of information.
> 

I stand by my statements.  I have followed the current developments 
regarding MD5 with interest, and am using SHA1 in the program that I am 
currently authoring because of its MD5's weaknesses.

However, MD5 (and MD4) have not been completely cracked.  The problems that 
you bring up have to do with situations where an active attacker develops a 
slightly different pair of documents with the same hash.

Although this is highly undesirable characteristic for a hash function, and 
shows a weakness in the function that may eventually lead to its being 
completely cracked, it does not mean that a fraudulent document can be 
created from an already signed document.  This is an old argument and I 
don't want to get into it here.  However, there a lots of people that who 
still think MD5 can be safely used to a) sign documents that you create 
yourself, and b) sign documents that you have made cosmetic changes to.

Irregardless, this argument is moot.  This thread is titled "rsync and 
md4".  It is a discussion about which hash function suits this particular 
purpose and he is not particularly concerned with resistance to deliberate 
attack.  In this case MD4 will function adequately.
- --
David F. Ogren                | 
ogren@concentric.net          | "A man without religion is like a fish
PGP Key ID: 0x6458EB29        |  without a bicycle"
- ------------------------------|----------------------------------------
Don't know what PGP is?       | Need my public key?  It's available
Send a message to me with the | by server or by sending me a message
subject GETPGPINFO            | with the subject GETPGPKEY
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQEVAwUBMddp3uSLhCBkWOspAQEI1Qf/VLg6ak6Y/VfbynFhCcA69RZKAQ/C6pCx
DMdz3OFitOwQM/csjTPBs7jue/3ArIQ+jevBOjp/NyAoJ4U8+Np4yv7ksmpEjTKq
EWq4DcvAB7MgpgJ72A92tO55vQo8AjYPmcZT2LhqeiTg+R6yL437T4gqS0ZSs7Ud
7e1anp7m72shSel6OKsxtfgiyVDlVi6mdtpXlLegWxcZhPaRYaZen3mHJ3JdxCpc
EsQupdrNVxBGMuxKeBwlkjCxD1TbqFpHTodh0oapEDScjpzTMmQeHYavmboI+Pys
32jt1PI9JEPIDracYcI3ovkgvR5VmMlKhAPDXcYbr2MWeBbVRDOaJw==
=9dqv
-----END PGP SIGNATURE-----

"David F. Ogren" writes:
> I stand by my statements.

Then you have lost all your reputation with me. If you don't even have
the integrity to admit that you are wrong, you are obviously not a
reasonable source of information.

> However, MD5 (and MD4) have not been completely cracked.  The problems that 
> you bring up have to do with situations where an active attacker develops a 
> slightly different pair of documents with the same hash.

I believe that is "cracked" under most definitions of cryptographic
hashes, Mr. Ogren. A cryptographic hash is supposed to be useable in a
signature precisely because it is supposed to be computationally
infeasable to find two documents with the same hash. Whether both
documents are chosen by the attacker or only one is immaterial -- the
property as stated is independant of that. As things stand, you can
get someone to sign a contract saying "I agree to pay David F. Ogren
$100" and turn it into one saying "I agree to pay David F. Ogren
$2395.39" or some such. If that isn't "cracked" what would be
"cracked"? Yes, it could be worse, but is this not far more than bad
enough?

> Although this is highly undesirable characteristic for a hash function, and 
> shows a weakness in the function that may eventually lead to its being 
> completely cracked, it does not mean that a fraudulent document can be 
> created from an already signed document.

Whatever you like, Mr. Ogren.

Perry

-----BEGIN PRIVACY-ENHANCED MESSAGE-----
Proc-Type: 4,MIC-CLEAR
Content-Domain: RFC822
Originator-Certificate:
 MIIBvzCCAWkCEFmOln6ip0w49CuyWr9vDVUwDQYJKoZIhvcNAQECBQAwWTELMAkG
 A1UEBhMCVVMxGDAWBgNVBAoTD1NlY3VyZVdhcmUgSW5jLjEXMBUGA1UECxMOU2Vj
 dXJlV2FyZSBQQ0ExFzAVBgNVBAsTDkVuZ2luZWVyaW5nIENBMB4XDTk1MDUwODIw
 MjMzNVoXDTk3MDUwNzIwMjMzNVowcDELMAkGA1UEBhMCVVMxGDAWBgNVBAoTD1Nl
 Y3VyZVdhcmUgSW5jLjEXMBUGA1UECxMOU2VjdXJlV2FyZSBQQ0ExFzAVBgNVBAsT
 DkVuZ2luZWVyaW5nIENBMRUwEwYDVQQDEwxDaGFybGVzIFdhdHQwWTAKBgRVCAEB
 AgICBANLADBIAkEM2ZSp7b6eqDqK5RbPFpd6DGSLjbpHOZU07pUcdgJXiduj9Ytf
 1rsmf/adaplQr+X5FeoIdT/bVSv2MUi3gY0eFwIDAQABMA0GCSqGSIb3DQEBAgUA
 A0EApEjzeBjiSnGImJXgeY1K8HWSufpJ2DpLBF7DYqqIVAX9H7gmfOJhfeGEYVjK
 aTxjgASxqHhzkx7PkOnL4JrN+Q==
MIC-Info: RSA-MD5,RSA,
 AUgiTVoKIzYpT3U2b5lxqGU6+uLTb+C+hivLsd0PxXH993pdEwRJ3rvJtAPSIacX
 +G7fosR46YQw+F9wxr955fI=

> "David F. Ogren" writes:
> > I stand by my statements.
> 
> Then you have lost all your reputation with me. If you don't even have
> the integrity to admit that you are wrong, you are obviously not a
> reasonable source of information.

How typically Perry.  

> 
> > However, MD5 (and MD4) have not been completely cracked.  The problems that 
> > you bring up have to do with situations where an active attacker develops a 
> > slightly different pair of documents with the same hash.
> 
> I believe that is "cracked" under most definitions of cryptographic
> hashes, Mr. Ogren. A cryptographic hash is supposed to be useable in a
> signature precisely because it is supposed to be computationally
> infeasable to find two documents with the same hash. Whether both
> documents are chosen by the attacker or only one is immaterial -- the
> property as stated is independant of that. As things stand, you can
> get someone to sign a contract saying "I agree to pay David F. Ogren
> $100" and turn it into one saying "I agree to pay David F. Ogren
> $2395.39" or some such. If that isn't "cracked" what would be
> "cracked"? Yes, it could be worse, but is this not far more than bad
> enough?
> 
> > Although this is highly undesirable characteristic for a hash function, and 
> > shows a weakness in the function that may eventually lead to its being 
> > completely cracked, it does not mean that a fraudulent document can be 
> > created from an already signed document.
> 
> Whatever you like, Mr. Ogren.
> 
> Perry

Perry, as you are so fond of quoting Dobbertin, let me forward once again to 
the list Hans' analysis of the "crack" that he discovered.  He explicitly 
agrees with Mr. Ogren's analysis.  Yes it is prudent to move away from MD5.
But there are still plenty of uses where it is more than sufficient.

Charlie Watt
SecureWare

- -----------------------------------------------------------------------

> Some of you may have seen this, but I think it's worth reposting here.
>   --Rob
> 
> Forward from sci.crypt on 11 Jun 1996 14:22:03 GMT
>   <dobbertin@skom.rhein.de> wrote (Re: "MD5 discussion"):
> 
> >In view of the continuing discussion about MD5, I want to make a few comments,
> >which hopefully can help to avoid some misunderstandings and misinterpretations:
> 
> >1. In February 1996 my paper "Cryptanalysis of MD4" appeared (Fast Software
> >Encryption, Cambridge Proceedings, Lecture Notes in Computer Sciences, 
> >vol. 1039, Springer-Verlag, 1996, pp. 71-82). In this paper, as an example two
> >versions of a contract are given with the same MD4 hash value. Alf sells his
> >house to Ann, in the first version the price is $176,495 and in the second it is
> >$276,495. The contracts have been prepared by Alf. Now if Ann signs the first
> >version with $176,495 then Alf can altered to price to $276.495 ...
> >In principle this risk occurs, if you use a hash function for which (senseful) collisions
> >can be found,  whenever you allow another person to have influence on the 
> >contents of a document you are signing. Certainly this does not happen
> >very often in practical applications. But sometimes you *must* have an agreement
> >about a text (contract) which is then signed by two or more parties. And these are
> >often just the most important applications!
> 
> >2. I suspect that the recent attack on MD5 compress can be refined and extended
> >such that it might lead to MD5 collisions (matching the right IV) and perhaps then
> >even to similar results as already obtained for MD4. Certainly this requires a lot of 
> >hard additional work.  
> 
> >3. If you write a message for your own (nobody else has influence on it) and sign
> >it using MD5 (and a strong public key algorithm, of course) then there is no danger 
> >that it can be altered (at least according to our knowledge today)! Thus it is true
> >that I guess almost all of you will have no risk using MD5, for instance in PGP.
> >However, if you accept 2., then in some cases there could be problems ... 
> 
> >4. After all I have reservations against keeping MD5 as a (de facto) standard, 
> >because 2. might indicate that there is a serious security problem with MD5.
> 
> >5. My conclusions are: no reason for panic, but in future implementations better
> >move away from MD5.
> 
> >6. Presently a paper discussion the status of MD5 in detail is in preparation.
> 
> >  -   Hans Dobbertin      
-----END PRIVACY-ENHANCED MESSAGE-----

Charles Watt writes:
> How typically Perry.  

Thank you for the compliment. I know that you think my comments are
evidence that I am nasty and that you think this is an insult, but my
clients seem to think this sort of thing is evidence that I'm
uncompromising in trying to maintain the security of their
systems. Everyone here knows my reputation. I may have a rough edge to
me, but people by now know that my advice is generally right on the
money. The fact that I have a reputation pleases me -- it does not
disturb me.

> Perry, as you are so fond of quoting Dobbertin, let me forward once again to 
> the list Hans' analysis of the "crack" that he discovered.  He explicitly 
> agrees with Mr. Ogren's analysis.

No, he doesn't. Dobbertin's privately circulated document is entitled
"Cryptanalysis of MD5", not "Possible weaknesses in MD5". The MD4
results were even more damning. It is true that the attacks aren't
general, but they are bad enough that the key property of
cryptographic hashes -- that it is computationally infeasable to
produce two documents with the same hash (note that the property is
NOT that you cannot produce a document with the same hash as a
document selected by the opponent), has been broken. Chosen plaintext,
in particular, is completely broken.

Dobbertin explicitly says that although there is no reason to panic,
that MD5 is not to be trusted.

I quote from your quote of Dobbertin:

      5. My conclusions are: no reason for panic, but in future
      implementations better move away from MD5.

> Yes it is prudent to move away from MD5.  But there are still plenty
> of uses where it is more than sufficient.

Yeah, like if you are looking for a wacky checksum and not a
cryptographic hash.

Look the point is that Ogren seems to think this is some sort of a
minor technicality and that we can safely ignore it most of the
time. Thats simply not prudent. Once you find that the key properties
of your cryptographic hash have fallen and you have to be
exceptionally careful about what you put through the hash lest an
attacker somehow influence it, you've lost the game. MD5 is no longer
trustworthy. I agree that one needn't run screaming in the streets,
but Ogren made it sound as though this wasn't a matter of
concern. Thats simply wrong. Saying that leads people to a completely
incorrect conclusion.

Perry

"Perry E. Metzger" <perry@piermont.com> writes:

 > From cypherpunks-errors@toad.com  Wed Jul 10 14:43:28 1996
 > Subject: Re: rsync and md4
 > Date: Mon, 01 Jul 1996 10:19:27 -0400

I think I've seen this message before.  Perry must be in reruns
for the summer.

Stay tuned for more of "The Best of Perry." :)

--
     Mike Duvos         $    PGP 2.6 Public Key available     $
     mpd@netcom.com     $    via Finger.                      $

Mike Duvos writes:
> "Perry E. Metzger" <perry@piermont.com> writes:
> 
>  > From cypherpunks-errors@toad.com  Wed Jul 10 14:43:28 1996
>  > Subject: Re: rsync and md4
>  > Date: Mon, 01 Jul 1996 10:19:27 -0400
> 
> I think I've seen this message before.  Perry must be in reruns
> for the summer.
> 
> Stay tuned for more of "The Best of Perry." :)

Some host out there is reposting cypherpunks mail. I haven't tracked
it down yet.

.pm

-----BEGIN PRIVACY-ENHANCED MESSAGE-----
Proc-Type: 4,MIC-CLEAR
Content-Domain: RFC822
Originator-Certificate:
 MIIBvzCCAWkCEFmOln6ip0w49CuyWr9vDVUwDQYJKoZIhvcNAQECBQAwWTELMAkG
 A1UEBhMCVVMxGDAWBgNVBAoTD1NlY3VyZVdhcmUgSW5jLjEXMBUGA1UECxMOU2Vj
 dXJlV2FyZSBQQ0ExFzAVBgNVBAsTDkVuZ2luZWVyaW5nIENBMB4XDTk1MDUwODIw
 MjMzNVoXDTk3MDUwNzIwMjMzNVowcDELMAkGA1UEBhMCVVMxGDAWBgNVBAoTD1Nl
 Y3VyZVdhcmUgSW5jLjEXMBUGA1UECxMOU2VjdXJlV2FyZSBQQ0ExFzAVBgNVBAsT
 DkVuZ2luZWVyaW5nIENBMRUwEwYDVQQDEwxDaGFybGVzIFdhdHQwWTAKBgRVCAEB
 AgICBANLADBIAkEM2ZSp7b6eqDqK5RbPFpd6DGSLjbpHOZU07pUcdgJXiduj9Ytf
 1rsmf/adaplQr+X5FeoIdT/bVSv2MUi3gY0eFwIDAQABMA0GCSqGSIb3DQEBAgUA
 A0EApEjzeBjiSnGImJXgeY1K8HWSufpJ2DpLBF7DYqqIVAX9H7gmfOJhfeGEYVjK
 aTxjgASxqHhzkx7PkOnL4JrN+Q==
MIC-Info: RSA-MD5,RSA,
 BmSwniu8gUasZa1TjPkW32wDQoVcczj8fKdr0iBciiZtHKyz1xXgeHgBI9V0oV8h
 dwcOLMC8bbAL39VVNkGHlxw=

> > Perry, as you are so fond of quoting Dobbertin, let me forward once again to 
> > the list Hans' analysis of the "crack" that he discovered.  He explicitly 
> > agrees with Mr. Ogren's analysis.
> 
> No, he doesn't. Dobbertin's privately circulated document is entitled
> "Cryptanalysis of MD5", not "Possible weaknesses in MD5". The MD4
> results were even more damning. It is true that the attacks aren't
> general, but they are bad enough that the key property of
> cryptographic hashes -- that it is computationally infeasable to
> produce two documents with the same hash (note that the property is
> NOT that you cannot produce a document with the same hash as a
> document selected by the opponent), has been broken. Chosen plaintext,
> in particular, is completely broken.
> 
> Dobbertin explicitly says that although there is no reason to panic,
> that MD5 is not to be trusted.
> 
> I quote from your quote of Dobbertin:
> 
>       5. My conclusions are: no reason for panic, but in future
>       implementations better move away from MD5.
> 
> > Yes it is prudent to move away from MD5.  But there are still plenty
> > of uses where it is more than sufficient.
> 
> Yeah, like if you are looking for a wacky checksum and not a
> cryptographic hash.
> 
> Look the point is that Ogren seems to think this is some sort of a
> minor technicality and that we can safely ignore it most of the
> time. Thats simply not prudent. Once you find that the key properties
> of your cryptographic hash have fallen and you have to be
> exceptionally careful about what you put through the hash lest an
> attacker somehow influence it, you've lost the game. MD5 is no longer
> trustworthy. I agree that one needn't run screaming in the streets,
> but Ogren made it sound as though this wasn't a matter of
> concern. Thats simply wrong. Saying that leads people to a completely
> incorrect conclusion.

I admit I am at a disadvantage having deleted the first few messages on this 
thread without actually reading them -- but when I am out one day and come 
back to 200+ cypherpunk messages of which perhaps 10 are relevant to 
cryptography, I get a little quick with the delete.  However, I am assuming
from the stated speed requirement that the original query was intended for 
just such a hashing scheme.  I interpretted Ogren's comments along the lines
of "choose an algorithm based upon a best fit for the requirements, where
security is just one of the requirements (although the most important)" 
(quotes used to indicate paraphrasing rather than actual quote).  If these
assumptions are valid, then he is quite correct, for a blanket condemnation
of MD5 is unwarranted.  If the intended application is for use with 
signatures, then I too would be quite leary of MD5 -- but only if I am
signing a document that I did not originate OR I need to ensure the
validity of the signature for longer than 12 months.  Condemning an 
application of MD5 without understanding the specific requirements placed 
upon the hashing algorithm is unjustified.  Complacently accepting the 
strength of the algorithm for all applications based upon recent findings 
is foolish.

Charles Watt
SecureWare

-----END PRIVACY-ENHANCED MESSAGE-----