Re: compare-by-hash (was Re: sharing /etc/passwd)

From: David Schultz (das_at_FreeBSD.ORG)
Date: 09/29/04

  • Next message: Deepak Jain: "Re: Kernel-loadable Root Kits" 
    Date: Tue, 28 Sep 2004 18:19:04 -0400
To: Jason Stone <freebsd-security@dfmm.org>

    On Tue, Sep 28, 2004, Jason Stone wrote:
    > -----BEGIN PGP SIGNED MESSAGE-----
    > Hash: SHA1
    >
    >
    > > One thing to keep in mind is that the collision-resistance of SHA-1 is
    > > an unproven conjecture.
    >
    > sure, I was going to mention that - indeed, md4 is the algorithm used in
    > rsync, and it _has_ been shown to be less collision-resistant than the
    > full 128-bits would imply.
    >
    > which means that instead of finding only one collision in the entire
    > lifetime of the universe, you'll find four.

    No, md4 and md5 are broken, in the sense that it's known how to
    feasibly generate collisions. For example:

    das@VARK:~> cmp md4*
    md4c_1 md4c_2 differ: char 8, line 1
    das@VARK:~> cmp md5*
    md5c_1 md5c_2 differ: char 20, line 1
    das@VARK:~> openssl md4 md4*
    MD4(md4c_1)= 4d7e6a1defa93d2dde05b45d864c429b
    MD4(md4c_2)= 4d7e6a1defa93d2dde05b45d864c429b
    das@VARK:~> openssl md5 md5*
    MD5(md5c_1)= a4c0d35c95a63a805915367dcfe6b751
    MD5(md5c_2)= a4c0d35c95a63a805915367dcfe6b751
    das@VARK:~> hexdump md4c_1
    0000000 9c83 4d7a 927a 56cb a578 b9d5 a5ee 57a7
    0000010 8a3c de74 66b3 dcc3 a020 b683 5d9f 3b2a
    0000020 71b3 c69d 9198 f9e9 805e d79f b2e8 a63b
    0000030 8e31 45dd 1fe5 97e3 bf08 2794 c3e9 b9e8
    0000040
    das@VARK:~> hexdump md4c_2
    0000000 9c83 4d7a 927a d6cb a578 29d5 a5ee 57a7
    0000010 8a3c de74 66b3 dcc3 a020 b683 5d9f 3b2a
    0000020 71b3 c69d 9198 f9e9 805e d79f b2e8 a63b
    0000030 8e31 45dc 1fe5 97e3 bf08 2794 c3e9 b9e8
    0000040
    das@VARK:~> hexdump md5c_1
    0000000 31d1 02dd e6c5 c4ee 3d69 069a af98 5cf9
    0000010 ca2f 87b5 4612 ab7e 0440 3e58 fbb8 897f
    0000020 ad55 0634 f409 02b3 e483 8388 7125 5a41
    0000030 5108 e825 cdf7 9fc9 1dd9 f2bd 3780 5b3c
    0000040 0b96 d11d 41dc 9c7b d8e4 f497 655a d555
    0000050 7335 c79a ebf0 0cfd 2930 66f1 09d1 8fb1
    0000060 2775 797f d530 eb5c e822 baad cc79 5c15
    0000070 74ed ddcb c55f 6dd3 9bb1 d80a cc35 e3a7
    0000080
    das@VARK:~> hexdump md5c_2
    0000000 31d1 02dd e6c5 c4ee 3d69 069a af98 5cf9
    0000010 ca2f 07b5 4612 ab7e 0440 3e58 fbb8 897f
    0000020 ad55 0634 f409 02b3 e483 8388 f125 5a41
    0000030 5108 e825 cdf7 9fc9 1dd9 72bd 3780 5b3c
    0000040 0b96 d11d 41dc 9c7b d8e4 f497 655a d555
    0000050 7335 479a ebf0 0cfd 2930 66f1 09d1 8fb1
    0000060 2775 797f d530 eb5c e822 baad 4c79 5c15
    0000070 74ed ddcb c55f 6dd3 9bb1 580a cc35 e3a7
    0000080

    (Acknowledgement: The md5 data comes from the page
    http://www.freedom-to-tinker.com/archives/000663.html, and the md4
    data from an email.)
    _______________________________________________
    freebsd-security@freebsd.org mailing list
    http://lists.freebsd.org/mailman/listinfo/freebsd-security
    To unsubscribe, send any mail to "freebsd-security-unsubscribe@freebsd.org"

  • Next message: Deepak Jain: "Re: Kernel-loadable Root Kits"

    Relevant Pages

    • Re: This Weeks Finds in Mathematical Physics (Week 226)
      ... Schneier credits Rivest as the designer of MD4, saying Bert den Boer and Antoon Bosselaears successfully crpytanalysed the last of the algorithms three rounds, while Ralph Merkle successfully attacked the first two rounds. ... Schneier credits Rivest as strengthening MD4 with the result being MD5. ...
      (sci.physics.research)
    • Re: OT: MD4 encryption
      ... what is MD4 used for? ... and just replaced by MD5 and is no longer used? ... Shortly after MD4 was published a number of attacks were demonstrated against parts of it. ... SHA1 isn't without problems either and discussion rages on about what is the best cryptographic hash algorithm out there. ...
      (comp.sys.mac.system)
    • Re: Slow but secure has function for small data
      ... Of course they don't contradict each other. ... The assumption that MD4 or MD5 behave like a PRF is not true. ...
      (sci.crypt)
    • Re: Crypto Mini-FAQ
      ... Here's one thing Hans Dobbertin wrote about MD5: ... "would be unwise to assume that the attack could not be ... It is instructive to read the history of MD4. ...
      (sci.crypt)