Results 1 to 3 of 3

Thread: Can an MD5 sum be 0000-0000-0000-0000?

  1. #1
    Matt Thomas
    Guest

    Can an MD5 sum be 0000-0000-0000-0000?

    This is more a theoretical question and I apologize in advance if this
    is the wrong place. As the subjects states, my question is if it's
    possible for an MD5 sum to be 0 or more accurately 0-0-0-0? I believe
    to answer this you will have to dig into the RFC 1321 and associated
    hashing algorithm.

    A few of my own comments. The RFC plainly states that there are
    constants added into each phase of the algorithm. Based on this, the
    easy answer is no. What has blurred the lines is the fact that MAX
    (unsigned int)+1 is 0. Thus, is the algorithm made such this condition
    is not possible?

    http://www.faqs.org/rfcs/rfc1321.html

    From the RFC..

    /* Process each 16-word block. */
    For i = 0 to N/16-1 do

    /* Copy block i into X. */
    For j = 0 to 15 do
    Set X[j] to M[i*16+j].
    end /* of loop on j */

    /* Save A as AA, B as BB, C as CC, and D as DD. */
    AA = A
    BB = B

    CC = C
    DD = D

    /* Round 1. */
    /* Let [abcd k s i] denote the operation
    a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
    /* Do the following 16 operations. */
    [ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22
    4]
    [ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22
    8]
    [ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22
    12]
    [ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22
    16]

    /* Round 2. */
    /* Let [abcd k s i] denote the operation
    a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
    /* Do the following 16 operations. */
    [ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20
    20]
    [ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20
    24]
    [ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20
    28]
    [ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20
    32]

    /* Round 3. */
    /* Let [abcd k s t] denote the operation
    a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
    /* Do the following 16 operations. */
    [ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23
    36]
    [ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23
    40]
    [ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23
    44]
    [ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23
    48]

    /* Round 4. */
    /* Let [abcd k s t] denote the operation
    a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
    /* Do the following 16 operations. */
    [ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21
    52]
    [ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21
    56]
    [ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21
    60]
    [ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21
    64]

    /* Then perform the following additions. (That is increment each
    of the four registers by the value it had before this block
    was started.) */
    A = A + AA
    B = B + BB
    C = C + CC
    D = D + DD

  2. #2
    unruh
    Guest

    Re: Can an MD5 sum be 0000-0000-0000-0000?

    On 2010-01-08, Matt Thomas <matthomas@gmail.com> wrote:
    > This is more a theoretical question and I apologize in advance if this
    > is the wrong place. As the subjects states, my question is if it's
    > possible for an MD5 sum to be 0 or more accurately 0-0-0-0? I believe
    > to answer this you will have to dig into the RFC 1321 and associated
    > hashing algorithm.


    In principle the answer should be yes. Since a hash is supposed to act
    like a random mapping from input to output, any restriction on the types
    of output are a "weakness" of the hash. ( instead of 2^128 possible
    outputs there are only 2^128-1)
    >
    > A few of my own comments. The RFC plainly states that there are
    > constants added into each phase of the algorithm. Based on this, the

    But the arithmetic is modular, so those constants can add to 0 just as
    likely as anything else.

    > easy answer is no. What has blurred the lines is the fact that MAX
    > (unsigned int)+1 is 0. Thus, is the algorithm made such this condition
    > is not possible?
    >
    > http://www.faqs.org/rfcs/rfc1321.html
    >
    > From the RFC..
    >
    > /* Process each 16-word block. */
    > For i = 0 to N/16-1 do
    >
    > /* Copy block i into X. */
    > For j = 0 to 15 do
    > Set X[j] to M[i*16+j].
    > end /* of loop on j */
    >
    > /* Save A as AA, B as BB, C as CC, and D as DD. */
    > AA = A
    > BB = B
    >
    > CC = C
    > DD = D
    >
    > /* Round 1. */
    > /* Let [abcd k s i] denote the operation
    > a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
    > /* Do the following 16 operations. */
    > [ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22
    > 4]
    > [ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22
    > 8]
    > [ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22
    > 12]
    > [ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22
    > 16]
    >
    > /* Round 2. */
    > /* Let [abcd k s i] denote the operation
    > a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
    > /* Do the following 16 operations. */
    > [ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20
    > 20]
    > [ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20
    > 24]
    > [ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20
    > 28]
    > [ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20
    > 32]
    >
    > /* Round 3. */
    > /* Let [abcd k s t] denote the operation
    > a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
    > /* Do the following 16 operations. */
    > [ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23
    > 36]
    > [ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23
    > 40]
    > [ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23
    > 44]
    > [ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23
    > 48]
    >
    > /* Round 4. */
    > /* Let [abcd k s t] denote the operation
    > a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
    > /* Do the following 16 operations. */
    > [ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21
    > 52]
    > [ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21
    > 56]
    > [ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21
    > 60]
    > [ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21
    > 64]
    >
    > /* Then perform the following additions. (That is increment each
    > of the four registers by the value it had before this block
    > was started.) */
    > A = A + AA
    > B = B + BB
    > C = C + CC
    > D = D + DD


  3. #3
    Maarten Bodewes
    Guest

    Re: Can an MD5 sum be 0000-0000-0000-0000?

    Matt Thomas wrote:
    > This is more a theoretical question and I apologize in advance if this
    > is the wrong place. As the subjects states, my question is if it's
    > possible for an MD5 sum to be 0 or more accurately 0-0-0-0? I believe
    > to answer this you will have to dig into the RFC 1321 and associated
    > hashing algorithm.
    >
    > A few of my own comments. The RFC plainly states that there are
    > constants added into each phase of the algorithm. Based on this, the
    > easy answer is no. What has blurred the lines is the fact that MAX
    > (unsigned int)+1 is 0. Thus, is the algorithm made such this condition
    > is not possible?
    >


    It is theoretically possible, but all alarms should go off if you
    encounter one because you either have encountered a 1/2^64 chance or
    (just slightly more likely) the returned hash value is trap.

    Comparing the value with all zeros and issuing a serious warning or
    error when all zeros is encountered might make sense if you mistrust the
    values returned.

    Regards,
    Maarten

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •