Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Computing > Computer Security > Can an MD5 sum be 0000-0000-0000-0000?

Reply
Thread Tools

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

 
 
Matt Thomas
Guest
Posts: n/a
 
      01-08-2010
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
 
Reply With Quote
 
 
 
 
unruh
Guest
Posts: n/a
 
      01-08-2010
On 2010-01-08, Matt Thomas <(E-Mail Removed)> 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

 
Reply With Quote
 
 
 
 
Maarten Bodewes
Guest
Posts: n/a
 
      01-10-2010
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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
create a md5 / md5 passwd with a salt Peter Woodsky Ruby 6 11-21-2008 09:08 AM
Can base class have the net sum of all the interfaces of its derived classes? Vj C++ 4 12-19-2006 06:32 PM
Upload, duplicated files, MD5 Sum Check, Federated Search =?Utf-8?B?QW5k?= ASP .Net 0 08-02-2006 05:44 AM
md5 from python different then md5 from command line ursache.marius@gmail.com Python 9 05-07-2006 11:49 PM
I remember someone asking about an MD5 javascript: http://pajhome.org.uk/crypt/md5/ Mozzie \( v \) Javascript 0 07-12-2004 01:06 PM



Advertisments