In the SHA hash algorithm the message is always padded, even if initially the correct length without padding; the padding is of the form "1" followed by the necessary number of 0s.
Why is it necessary that the message always be padded?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ I edited your question to make it look better, but it was unclear if you were only asking why padding is always added or if you were also asking why the particular form of padding was chosen. Feel free to roll back changes if necessary. $\endgroup$– mikeazoCommented May 31, 2012 at 18:04
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
Well, the entire point of a cryptographical hash function is that no one can practically devise two messages that hash to the same value.
Now, the SHA family of hashes use the Merkle–Damgård construction; that is, they have an iterated hash function, and each invocation of the hash function takes as input a fixed block size (either 512 or 1024 bits in the case of the SHA family).
However, we're interested in hashing messages that don't happen to be an exact multiple of 512 or 1024 bits in length. So, what we do is define a padding function that takes a message, and converts it into a form that's a multiple of the block size in length; we then run the hash compression function on this padded message.
Now, there are a couple of requirements on this padding function; one of the most critical that if we had two different messages, then they must still be different after padding; if not, then the hash compression functions will work identically, and so those two messages would hash to the same value.
That really is the answer to your question (a); if our padding function didn't modify (pad) messages that happened to be the correct length, then that would immediately lead to a collision. For example, if we take any message $M$ that's not a multiple of the block size, we could compute $Pad(M)$. Now, $Pad(M)$ will be a multiple of the block size, and so we'd know that $Hash(M) = Hash(Pad(M))$.
As for the answer to your question (b), well, if our padding function was simply adding zero bits until the padded message was of the correct length, well, that would lead to a collision of the form $Hash(M) = Hash(M || 0)$ (assuming postpending the 0 doesn't cause us to cross a block boundary). On the other hand, the SHA padding function isn't just appending 0 and 1 bits; it also involves adding a bitlength of the entire message at the very end. If the question is "why do they add a 100...000 pattern and add a message length', well, I rather suspect that's a belt-and-suspenders approach. Either would be sufficient in itself (as either would prevent two messages from padding into a common value); both are cheap, and so the designers decided to do both.
-
1$\begingroup$ As to why two padding techniques are used: If padding was only with a 1 and enough 0 to reach the next block frontier, then an authority arbitrarily deciding the 160-bit magic value used as initialization vector could use that power to introduce a backdoor, by computing the magic value from an arbitrary 512-bit secret, that could be prefixed to messages to cause a collision. While the magic value in SHA-1 (
67452301EFCDAB8998BADCFE10325476C3D2E1F0) is regular enough to show this is not the case, this is a nice reason to use the other padding technique (appending the length). $\endgroup$– fgrieu ♦Commented Jun 4, 2012 at 11:42 -
$\begingroup$ This explanation is evidently demonstrating something very obvious and yet I sadly fail to grasp it....."if our padding function didn't modify (pad) messages that happened to be the correct length, then that would immediately lead to a collision. " Why would it lead to a collision? The example in the subsequent sentence makes no sense to me unfortunately. Why do we know Hash(M) = Hash(Pad(M))? And why does that tell us anything? I'm completely missing the point :( $\endgroup$ Commented Jan 14, 2017 at 3:26
$\begingroup$
$\endgroup$
3
In many existing padding schemes, without padding always being added there is a trivial second preimage attack. For simplicity let's assume a 10 bit hash function $h_{10}$ (extending this to other size hash functions is trivial).
Let $m_1=101$ and $m_2=1011000000$. I claim that $h_{10}(m_1)=h_{10}(m_2)$.
Since $m_2$ is 10 bits, no padding is needed. Since $m_1$ is smaller, padding is needed. What padding will be added? The padded version of $m_1$ will be equal to $m_2$, which is why the claim is true. Thus, there are two message $m_1\neq m_2$ and yet $h_{10}(m_1)=h_{10}(m_2)$.
NOTE: This attack applies to many hash functions including SHA-1 and the SHA-2 family.
-
$\begingroup$ This is not true. One could imagine a padding algorithm that doesn't always add padding and has no trivial second preimage attacks. For example, one could devise a padding algorithm such that if the input was a perfect fit for an even number of blocks, it isn't padded at all and in every other case, it is padded so that the padded result contains an odd number of blocks. $\endgroup$ Commented Jun 1, 2012 at 15:35
-
$\begingroup$ @DavidSchwartz, good point. I was more referring to SHA1's padding scheme and why it specifically always needs to add padding. $\endgroup$– mikeazoCommented Jun 1, 2012 at 16:16
-
$\begingroup$ This is missing a comment about the inclusion of the length indication, which is present in the answer of poncho. $\endgroup$– Maarten Bodewes ♦Commented Jun 18, 2016 at 11:58
$\begingroup$
$\endgroup$
Strictly speaking, it's not. But you wind up with either very complex or very ugly padding algorithms.
For example, say you were designing a padding algorithm such that there exists one string of length M that is "padded" by adding no padding at all. Clearly, it would be a disaster if any string of length less than M could be padded so as to produce a string that, if input, wouldn't be padded.
So this leaves you two painful options:
1) You can look at the contents of the string to decide how to pad it. This makes streaming implementations difficult, and is confusing and prone to error.
2) You can reserve some lengths for unpadded strings. But this means that some lengths will have to be padded with at least two extra blocks.
Basically, if you try designing an algorithm that leaves any inputs unpadded, you will find that every one you design is either broken (allowing two inputs to pad to the same output) or horrible.
