8
$\begingroup$

Appending the length of the message when padding of a SHA-2 message is sufficient to satisfy the Merkle-Damgård construction. However the padding in SHA-2 also pads with 10* between the end of the message and the message length data. I know that 10* padding lets one turn non-block-aligned length messages into block-aligned length messages in a reversible way. However, because the padding already encodes the bit length of the original message, this 10* padding is redundant. Using the bit length data we can already determine where the original message ends and 0* padding would be sufficient. In fact, in "One Way Hash Functions and DES. Advances in Cryptology" in Crypto’89, Merkle uses 0* padding followed by the length.

So my question, why does SHA-2 call for doing 10* padding in addition to appending the message length?

$\endgroup$
5
$\begingroup$

As rightly pointed in the question, 0*+length padding would work just as well as 10*+length padding, with the benefit of simplicity and requiring one less block in some cases, like SHA-256 for a message of 56 bytes.

I guess SHA-2 does this because SHA-1 did, and before that SHA, MD5, and Ronald Rivest's MD4 (1990), which is the earliest reference that I can point, and already had:

  Step 1. Append padding bits

     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 (in
     which case 512 bits of padding are added).

     Padding is performed as follows: a single "1" bit is appended
     to the message, and then enough zero bits are appended so that
     the length in bits of the padded message becomes congruent to
     448, modulo 512.

  Step 2. Append length

     A 64-bit representation of b (the length of the message before
     the padding bits were added) is appended to the result of the
     previous step.  In the unlikely event that b is greater than
     2^64, then only the low-order 64 bits of b are used.  (These
     bits are appended as two 32-bit words and appended low-order
     word first in accordance with the previous conventions.)

Perhaps earlier block-cipher based MACs used 10* padding without length strengthening, where 10* prevents some trivial attacks 0* allows. In particular, 10* padding was used for variants of the so-called "CBC-MAC", which became ISO/IEC 9797-1 MAC Algorithm 1 padding method 2 (approved 1999). It would then be plausible that the 10* padding was kept, and length-strengthening as suggested by Merkle added, because 10* padding alone would not be as safe.


Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography, in section 9, mentions both padding with 0* (algorithm 9.29) and 10* (algorithm 9.30) and note:

The padding method of Algorithms 9.29 and 9.30 originated from ISO/IEC 10118-4 “Information technology – Security techniques – Hash-functions – Part 4: Hash-functions using modular arithmetic”, draft (CD), 1996.

but I doubt this is the true origin.

$\endgroup$
  • $\begingroup$ This seems like speculation. Is the true origin just unknown and the reasons may be lost to time? $\endgroup$ – forest Feb 14 '18 at 13:57
  • $\begingroup$ It seems like very informed speculation in my opinion. Considering this is the best answer in over a year, I'd accept the answer unless you are expecting Ron Rivest to chime in. $\endgroup$ – rmalayter Apr 23 at 16:14

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.