Archived

This topic is now archived and is closed to further replies.

krumms

MD5/SHA - Message Padding

Recommended Posts

I''m having problems implementing both MD5 and SHA-1 - well, for most part its going great - its just the whole message padding thing (http://www.ietf.org/rfc/rfc1321.txt, sections 3.1 & 3.2, and http://www.faqs.org/rfcs/rfc3174.html, section 4): From what I understand, the following statement is true: ** NO MATTER WHAT, if the message length (in bits) L is less than 2^64 (that''s the size of two MD5/SHA words), then a _single_ ''1'' bit is appended. Immediately after this, 448 mod (L+1) zeroes are appended. Following that, two words (representing the length of the original message) are concatenated to the message in the remaining 64 bits. ** Now, the problem I have with this is as follows: What happens if L == (2^64)-1 ? The 1 bit is appended to give L = (2^64). Then there is the matter of the 64 bits that represent the length of the message. Wouldn''t the addition of these 64 bits result in an L == (2^64)+64 ? Which would be invalid, because the length of L can''t exceed (2^64) - or so I understand. If somebody could clear this up for me I''d be very grateful - I''ve probably just misinterpreted something from the RFCs. Again, thanks very much. Tom L

Share this post


Link to post
Share on other sites
I recently implemented MD5 so I think I know what you are talking about (don't know if any of this applies to SHA1). I had to read the specification a couple of times before I figured out how padding was supposed to be made. The "congruent to 448, modulo 512" can be a bit confusing - it's easier to simply think of the 64-bit message length as part of the padding. So, padding is done to the next 512-bit boundary using first a single "1" bit, then "0" bits up to 64 bits less than the next 512-bit boundary, and finally the two 32-bit words representing the message length.

Anyway, the way you do padding is not significantly changed if the message length is 2^64 bits or more - when the original message length is larger than 2^64 bits, you only use the low-order 64 bits when appending the length. You always add padding before calculating the digest, though.

Edit: RFC3174 seems to imply that SHA1 is limited to messages less than 2^64 bits in length. MD5 does not appear to have this restriction. This shouldn't affect your implementation, since it is the ORIGINAL message length you append, not the padded length.


[edited by - spock on September 30, 2002 6:56:50 PM]

Share this post


Link to post
Share on other sites
Thanks for your reply spock,

quote:
if the original message length is larger than 2^64 bits, you only use the low-order 64 bits when appending the length.


Okay, so ... even if my message length is already a multiple of 512, I still add the padding ? I understand that the 64-bit value representing the message length is considered to be part of the padding, but say I had my final block Mn, which was filled up with 450-bits from the message. The 64-bit value won''t fit (its too large by two bits) - does it just overflow into the next block? I doubt it, because that would break the whole idea of giving the final block a length of a multiple of 512 (512*n) since the next block would now have a length of 2. This is what I''m having trouble getting my head around

Dunno - maybe I''m misunderstanding something. Perhaps you could set me on the right trail?

Thanks very much,

Tom

Share this post


Link to post
Share on other sites
quote:
Original post by krumms
Okay, so ... even if my message length is already a multiple of 512, I still add the padding?


Yes, padding is ALWAYS performed.

quote:

say I had my final block Mn, which was filled up with 450-bits from the message. The 64-bit value won''t fit (its too large by two bits) - does it just overflow into the next block?


If the last block of the original message was 450 bits, you''d pad by adding one "1" bit, then 509 "0" bits, and finally the 64-bit original message length. You end up with one extra 512-bit block.

Share this post


Link to post
Share on other sites