What are my md5 bits?

Question

I'm trying to code an md5 hashing function in Python but it doesn't seem to work. I've isolated the problem to the message bits that are to be hashed. Yes, I'm actually converting each byte to bits and forming a bit message (I want to study the algorithm on a bit level). And this is where things are falling apart; my bit string is not correctly formed.

The simplest message would be "", it's 0 bytes long, padding would be a "1" followed (or not) by 511 "0"s (last 64 bits denote message length, which, as already said, is just 0).

10000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000

I'm feeding 32-bit chunks of data into the transform function at a time. I've tried to manually position the 1 in all the positions of in the first chunk, as well as the last chunk (little endian). Where should the "1" be?

Thank you.

Update: The correct position for the first 32-bit word fed into the transform should in fact be: 00000000000000000000000010000000 which int(x,2) is 128 this mess is due to my A = rotL((A+F(B,C,D)+int(messageBits[0],2)+sinList[0]), s11)+B transform format using int() to interpret the bit strings as integer data, int() takes little endian format binary, thus 100.... was a very huge number.

Answer 1

MD5 uses big-endian convention at bit level, then little-endian convention at byte level.

The input is an ordered sequence of bits. Eight consecutive bits are a byte. A byte has a numerical value between 0 and 255; each bit in a byte has value 128, 64, 32, 16, 8, 4, 2 or 1, in that order (that's what "big-endian at bit level" means).

Four consecutive bytes are a 32-bit word. The numerical value of the word is between 0 and 4294967295. The first byte is least significant in that word ("little-endian at byte level"). Hence, if the four bytes are a, b, c and d in that order, then the word numerical value is a+256*b+65536*c+16777216*d.

In software applications, input is almost always a sequence of bytes (its length, in bits, is a multiple of 8). The aggregation of bits into bytes is assumed to have already taken place. Thus, the extra '1' padding bit will be the first bit of the next byte, and, since the bit-level convention is big-endian, that next byte will have numerical value 128 (0x80).

For an empty message, the very first bit will be the '1' padding bit, followed by a whole bunch of zeros. The message length is also zero, which encodes yet other zeros. Therefore, the padded message block will be a single '1' followed by 511 '0', as you show. When bits are assembled into bytes, the first byte will have value 128, followed by 63 bytes of value 0. When bytes are grouped into 32-bit words, the first word (M₀) will have numerical value 128, and the 15 other words (M₁ to M₁₅) will have numerical value 0.

Refer to the MD5 specification for details. What I describe above is what is explained in the first paragraph of section 2 of RFC 1321. The same encoding is used for the message bit length (at the end of the padding), and for writing out the final hash result.