2
$\begingroup$

From FIPS 180-4 § 5.1.1, the padding used for the SHA family of hashes begins with a binary 1, followed by a number of 0s, and finally a 64-bit representation of the message length:

Suppose that the length of the message, M, is 𝓁 bits. Append the bit "1" to the
end of the message, followed by k zero bits, where k is the smallest, non-
negative solution to the equation 𝓁 + 1 + k ≡ 448 mod 512. Then append the 64-bit
block that is equal to the number 𝓁 expressed using a binary representation.

A form of this question has already been asked before, and the answer seems to be that it's likely because MD5 did that, and MD4 before that. But while that explains why MD5, SHA-1, and SHA-2 do it, it leaves the initial question unanswered. What is the purpose of starting the padding with a 1? If the correct answer for the SHS is "because that's how MD4 did it", then why did MD4 do it?

For SHA-3 which does not use length encoding, the purpose is to eliminate ambiguity:

The initial 1 bit is required so messages differing only in a few additional 0 bits at the end do not produce the same hash.

MD4, which has always employed length encoding, still seems to use this padding.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
2
$\begingroup$

If you don't start the padding with a $1$ it is not completely obvious where the padding starts.

If the message ends in

$...011010$

and you pad it to

$...01101000000$

which zeros were part of the message and which part of the padding?

If the padding is $1000...$ you know it started at the last $1$ in the padded string.

$...011010$

$...01101010000$

Edit: Considering Why does the padding in Merkle–Damgård hash functions like MD5 contain the message length? This looks a bit like $10000...$ was used in the beginning and then the length was added for weaker assumptions on the compression function. In which case implementers probably complained that there are no real problems and that they didn't want to do any work, and that changes would require new certifications of products, etc. pp. and they ended up with this compromise which allows simply ignoring the last 64-bit block and using the old algorithms.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I can't see how this is correct. For your rhetorical question, the answer is that the parts of the message is everything from the first bit to the nth bit, where n is the length specified in the last 64 bit block. The 1 is completely unnecessary from the point of view of acting as a delimiter. Not to mention, the final 64 bits will contain some 1s. $\endgroup$
    – forest
    Commented Feb 14, 2018 at 8:13
  • 1
    $\begingroup$ I'm SORRY! I haven't had enough coffee yet and misread the question. Although, I still believe this is the original reason why the $1$ is there. ;) $\endgroup$
    – Elias
    Commented Feb 14, 2018 at 8:28
  • 2
    $\begingroup$ @forest: Elias's point can be reworded as: without the 64 or 128 length bits, the 1 is required to avoid collisions. It is plausible that initially there was the 1 for this reason, but not the length; and the length was added as an afterthought to simplify and strengthen the security argument, see this; and the 1 stuck. I thought that is plausible when I wrote that other answer, but could not find a reference. The compatibility argument seems dubious, since lengths other than 0 change the hash. $\endgroup$
    – fgrieu ♦
    Commented Feb 14, 2018 at 9:40
  • $\begingroup$ @fgrieu I was talking only about the code that processes the message after the hash has been verified, of course. The code compatibility argument is pretty weak in this case but that never stops developers from using it. After all, if you want to use only the length you have to do MODULAR ARITHMETIC! $\endgroup$
    – Elias
    Commented Feb 14, 2018 at 9:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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