Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to understand to padding process of MD5 from the link: http://www.ietf.org/rfc/rfc1321.txt

In this link I have found the following description of padding:

The message is "padded" (extended) so that its length (in bits) is congruent to $448$, modulo $512$. That is, the message is extended so that it is just $64$ bits shy of being a multiple of $512$ bits long. Padding is always performed, even if the length of the message is already congruent to $448$, modulo $512$.

I have tried to understand the sentence "That is, the message is extended so that it is just $64$ bits shy of being a multiple of $512$ bits long." with my utmost effort. But I've failed.

Can anyone explain the sentence with better clarity?

share|improve this question
    
It means "the message is extended so that it is just 64 bits shorter than it would need to be to make it a multiple of 512 bits long." – immibis Jan 11 at 9:54
    
If it's the phrase "just shy of" which is puzzling you, you might be better off asking at english.stackexchange.com. – TRiG Jan 11 at 11:18

Let's say our message is b bits long. When we're done padding it, it should look like this:

P = [  Message   |     Padding     |  Message length ]
    |<- b  bits->|<-- ??? bits --->|<--- 64 bits --->|

Where the message length is just b encoded as a 64-bit integer, and the middle padding section looks like this:

Padding = 1 0 0 0 0 ... 0 0 0 0 0

(Those are actual 1 and 0 bits).

So how many zero bits do we include in the padding? Enough to make P a multiple of 512 bits long (so 512 bits, 1024 bits, 1536 bits, etc.). This allows us to break P up into a complete number of 512-bit chunks for the next step.

For example, let's say the message is 128 bits long (16 bytes). We need 64 bits for the message length. That brings us to 192 bits. In order to get to a multiple of 512 bits, we'll need to add 512 - 192 = 320 bits of padding: a single one followed by 319 zeroes:

P = [  Message   |     Padding     |  Message length ]
    |<-128 bits->|<-- 320 bits --->|<--- 64 bits --->|

Note that the first two sections take up 128 + 320 = 448 bits. In general, once we break the message up into 512-bit blocks, the last block will contain 64 bits for the message length and 512 - 64 = 448 bits for the end of the message and the padding combined. This is where the 448 number in the RFC comes from.

share|improve this answer
    
... and the reason that padding is always performed is that you would get the same hashes for some messages as a padded message and another unpadded message with a message size of $512 \times x + 448$ bits may end up with the same encoded value - and thus the same hash value. – Maarten Bodewes Jan 11 at 8:38
    
@MaartenBodewes Actually the message length field would protect against that. So the specific padding rule is just an extra precaution. – kasperd Jan 11 at 10:34
1  
@kasperd interesting observation - if slightly annoying for persons that need to hash a lot of 448 sized messages :) – Maarten Bodewes Jan 11 at 10:37
    
If the message is $b$ bits, there are exactly $512-((b+64)\bmod512)$ bits of padding, the first of which being a 1, all the others 0; and then there's the 64-bit length (little-endian). – fgrieu Jan 11 at 14:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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