3
$\begingroup$

MD5 processes a 512-bit block and produces a 128-bit (16 byte) message digest often expressed as 32-digit hexadecimal value

For example if I hash the word "how" using MD5 , I get the following hash value

db88a0257c220dbfdd2e40f6152d6a8d

The word "how" is represented in 3 bytes which is 24 bits. How does MD5 process a 24 bit into a 512 bit block???

$\endgroup$
7
$\begingroup$

It's called padding.

MD5 fills the "not finished block" with exactly one "1" bit and a number of "0" bits until the length of the number is 64 bits away from being divisible be 512. It could happen that you don't need to add any "0" bits, that's okay, but never omit the "1" bit! After that, the length of the original message in bits is added, formatted with the fixed length of 64 bits in little-endian in words of 32 bit. Now the block is divisible by 512 and ready to be used in the "core" MD5 algorithm. The biggest message which can be processed in a single block is 417 bits long: 417 bits for the message, 1 bit for the mandatory "1" bit and 64 bits for the length: $417 + 1 + 64 = 512$. (We don't need any extra "0" bits for this message.)

The plaintext of "how" in ASCII is: $$ \text{01101000 01101111 01110111} $$ Now we concatenate a "1" bit: $$ \text{01101000 01101111 01110111 1} $$ That are 25 bits. Now we need the lowest number which is divisible by 512 and at least 64 higher than our current message length. 512 is this number for our example. 64 bits lower than 512 is $512 - 64 = 448$. We need to add $448 - 25 = 423$ "0" bits. $$ \text{01101000 01101111 01110111 10000000 [416 "0" bits]} $$ The length of the original string is 24. The binary representation of 24 as 64 bit number is this. (Little-endian, so the least-significant byte comes first!) $$ \text{00011000 [56 "0" bits]} $$ Now we concatenate this number to the block: $$ \text{01101000 01101111 01110111 10000000 [416 "0" bits] 00011000 [56 "0" bits]} $$ Now follows the full block, converted from little-endian and written (big-endian) as 32-bit integers, like MD5 will process them.

0x80776F68 0x00000000 0x00000000 0x00000000
0x00000000 0x00000000 0x00000000 0x00000000
0x00000000 0x00000000 0x00000000 0x00000000
0x00000000 0x00000000 0x00000018 0x00000000

If you want to hash more data, divide it into blocks. You still have to add the "1" bit and the length of the hashed message. If the last block is already under 64 bits away from being divisible by 512, than you have to add a new block, just for padding! Omitting the padding is very bad because the hash is even more susceptible for length extension attacks than it's normally the case for MD5.

$\endgroup$
  • 1
    $\begingroup$ @fgrieu: A: Small mistake, thanks. B: Ah, yeah, endianess always did confuse me, thanks. C: Forgot to mention the "64 bits away from" part, will have a look at it, thanks. $\endgroup$ – Nova Oct 10 '14 at 9:45
  • 1
    $\begingroup$ Take care that MD5's endianness is quite pervert. The encoding of bits in bytes is big-endian (as shown by the fact the padding byte is 0x80, not 0x01), but the encoding of bytes in 32-bit words is little-endian. $\;$ IIRC, in the landmark paper with the first MD5 collision there was some endianness issue in the first version, and that needed the collision search to be performed all over again. $\endgroup$ – fgrieu Oct 10 '14 at 11:29
  • 1
    $\begingroup$ @fgrieu: Well, alright, I just incorporated your comments into the answer. $\endgroup$ – Nova Oct 10 '14 at 15:21
  • 2
    $\begingroup$ Like all Merkle-Damgård hashes, MD5 is susceptible to length extension attacks even with padding. What proper padding prevents is trivially collisions between a message and a padded message. As an example of such trivial collisions, look at PBKDF-HMAC-x. $\endgroup$ – CodesInChaos Oct 10 '14 at 15:45
  • 1
    $\begingroup$ Changed my mind, you need to at least correct the last sentence, so I would edit the comment of Codes in in one form or another. $\endgroup$ – Maarten Bodewes Oct 11 '14 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.