MD5 Code Coverage

Question

I'm currently implementing an MD5 hash algorithm based RSA data security code, in the UpdateData method there is a section which reads:

mCount[0] += (length << 3);

if (mCount[0] < (length << 3))
{
    mCount[1]++;
}

I'm trying at the moment to understand how the if statement could ever evaluate to true (the mCount[0] value is initialised to 0). Any help would be greatly appreciated.

Thanks

Answer 1

It can happen if there is an overflow of the mCount[0] variable.

unsigned int i = 4294967295;//2^32-1
unsigned int j = 1;
i += j;
assert(i < j);

The block of code you mentioned is probably called multiple times, depending on how much data there is to process. So mCount[0] will eventually overflow.

Answer 2

This is for carry propagation, the sum of length*8 is stored in two 32-bit words (here, mCount is likely an array of unsigned int) mCount[1]:mCount[0].

lo += a
if (lo < a) hi++; // true if overflow occurs: lo + a >= 2^32

is equivalent to 64-bit operation:

(hi:lo) += (0:a)

Answer 3

This will happen whenever mCount[0] is negative before the addition and if the addition itself does not overflow.

Answer 4

I know this is not technically an answer to your programming question, but I honestly think the most valuable advice I can give you is that you should use a widely-used and well-vetted MD5 (or any other crypto) algorithm, DO NOT roll your own. How can I put this delicately... this advice is doubly true if you are asking questions about integer math. The road to hell is littered with the bodies of people who tried to implement tricky crypto themselves without fully understanding what they were doing, and ended up leaving gaping security holes in the process. Be smart, use somebody else's debugged implementation, use your own valuable time to implement parts of the system you can't get from someplace else.

Answer 5

As Eric and Brian point out, this happens has when mCount[0] overflows, which happens every 500mb (2^29), so if you hash files/data streams larger than 500mb you will see this code trigger.

Using two 32bit counters, allows for 2^61 bytes of input before the counter truly overflows.