4 ms·

> Append a single 1: Just begs the question, why?

by stigz 4y ago

trinovantes 4y ago
If your input ends with a 0 and you don't append the 1, you have no idea if that 0 is part of the padding or input
- edflsafoiewq 4y ago
  Yes you do, since you still have the length field.
  - oconnor663 4y ago
    Good point, I never thought about it that way. The reverse is also true: The length is probably unnecessary, since the "1" is there. I suppose the length makes it harder to produce collisions with inputs of different lengths, but in practice I don't think anyone actually tries to do that. If I had to take a wild guess, I'd guess that some early design in the family used only the "1", and that the length was added later?
    - edflsafoiewq 4y ago
      Padding without the length isn't suffix-free, ie. there's two different messages x and y with pad(x) a suffix of pad(y). You want that basically because if there's ever a collision part-way through the loop on two inputs, if there's a common suffix, the rest of the loop will be the same so there's no chance to "escape" the collision. Being some kind of artifact seems plausible.
      - trinovantes 4y ago
        > Padding without the length isn't suffix-free Can you give a more concrete example? Specifically with padding with 1 then all 0s without length. Appending the 1 then all 0s is supposed to prevent collisions. The length suffix is used as an early attempt to avoid length extension attacks on MACs of the form H(secret|M). However, we've later seen that it's not sufficient as it's easy to determine length of the secret by trial and error. This eventually led to the creation of HMAC H(H(secret^opad)|H(secret^ipad|M)). In theory, the length suffix is no longer needed (or the "1" suffix but we save more space by removing the length). Maybe a cryptographer with more history knowledge can explain this but personally I think it's now one of those "don't fix what's not broken" things. It doesn't hurt security and it's already been thoroughly analyzed (and hardware optimized) so we just leave it.
        edflsafoiewq 4y ago
        Of it not being suffix-free? Just stick a full block on the front of the message. Length padding isn't just for MACs, its used in the first place to prove Merkle-Damgard works at all, ie. is collision-preserving. If you have a hash collision with two messages with the same length, you can run through the Merkle-Damgard loop in parallel and find a collision in the compression function. For different lengths that doesn't work but if you just insert the length into the last block, you know you'll always have a collision in the final block in that case. There's a proof here that being suffix-free is necessary and sufficient for a padding rule to make Merkle-Damgard collision-preserving: https://eprint.iacr.org/2009/325.pdf https://eprint.iacr.org/2009/325.pdf
        trinovantes 4y ago
        > stick a full block on the front of the message Yes, this will give you the same intermediate state in the hash function but if m1!=m2, then the final output H(pad'(x|m1)) != H(pad'(x|m2)) where pad' is just appending 1 then all 0s. Maybe it's due to the years since my crypto class or maybe I'm just dense but I'm not following your logic at all. I'm asking for an actual example of m1 and m2 that will result in the same hash if they are not padded with their lengths. I made the assertion that for all m1,m2 if m1!=m2 then H(pad'(m1))!=H(pad'(m2)). Disproving it is simply giving a counter example m1,m2. EDIT: I took some time to skim through the paper you've linked and it supports my assertion: > We also have shown that the simplest padding such as padding 10^d only can be sufficient for collision preserving property if we restrict collision resistant assumption of the underlying compression function for the first (t − 1) bits. Since we know (or at least believe) the SHA2 compression function is collision resistant, then length padding is redundant.
        edflsafoiewq 4y ago
        Oh, we're talking about different things. I'm only talking about proving collision-preservation, not something as spectacular as generating collisions.
edflsafoiewq 4y ago
AFAIK the 1 bit does nothing. Padding with 1+(number of 0s)+(length of message) is traditional though and used by MD4/MD5/SHA1/SHA2. You can read in a few places that this is the padding proposed by Merkle, but I looked it up and in my reading of One Way Hash Functions and DES he does not use the 1 > As an aside, we note that x is padded with 0's until its size is an integral multiple of the size of the convenientlySizedChunks. Note that padding with 0s might introduce some ambiguity about the exact value of x that is being authenticated, as discussed by Juenernan[4]. The message "010110" padded to 8 bits would be "01011000" and it is now unclear how many trailing 0's were present in the original message. Several methods are available to resolve this ambiguity. We select a method that will also be useful in resolving a further problem: we append the length of x, in bits, at the end of x. To make this additional "length" field easy to find. we shall right justify it in the final block. If the length field won't fit, we add additional blocks to the end of x.

> Append a single 1: Just begs the question, why?

by stigz 4y ago

> Append a single 1: Just begs the question, why?

trinovantes 4y ago

If your input ends with a 0 and you don't append the 1, you have no idea if that 0 is part of the padding or input

edflsafoiewq 4y ago
Yes you do, since you still have the length field.
- oconnor663 4y ago
  Good point, I never thought about it that way. The reverse is also true: The length is probably unnecessary, since the "1" is there. I suppose the length makes it harder to produce collisions with inputs of different lengths, but in practice I don't think anyone actually tries to do that. If I had to take a wild guess, I'd guess that some early design in the family used only the "1", and that the length was added later?
  - edflsafoiewq 4y ago
    Padding without the length isn't suffix-free, ie. there's two different messages x and y with pad(x) a suffix of pad(y). You want that basically because if there's ever a collision part-way through the loop on two inputs, if there's a common suffix, the rest of the loop will be the same so there's no chance to "escape" the collision. Being some kind of artifact seems plausible.
    - trinovantes 4y ago
      > Padding without the length isn't suffix-free Can you give a more concrete example? Specifically with padding with 1 then all 0s without length. Appending the 1 then all 0s is supposed to prevent collisions. The length suffix is used as an early attempt to avoid length extension attacks on MACs of the form H(secret|M). However, we've later seen that it's not sufficient as it's easy to determine length of the secret by trial and error. This eventually led to the creation of HMAC H(H(secret^opad)|H(secret^ipad|M)). In theory, the length suffix is no longer needed (or the "1" suffix but we save more space by removing the length). Maybe a cryptographer with more history knowledge can explain this but personally I think it's now one of those "don't fix what's not broken" things. It doesn't hurt security and it's already been thoroughly analyzed (and hardware optimized) so we just leave it.
      - edflsafoiewq 4y ago
        Of it not being suffix-free? Just stick a full block on the front of the message. Length padding isn't just for MACs, its used in the first place to prove Merkle-Damgard works at all, ie. is collision-preserving. If you have a hash collision with two messages with the same length, you can run through the Merkle-Damgard loop in parallel and find a collision in the compression function. For different lengths that doesn't work but if you just insert the length into the last block, you know you'll always have a collision in the final block in that case. There's a proof here that being suffix-free is necessary and sufficient for a padding rule to make Merkle-Damgard collision-preserving: https://eprint.iacr.org/2009/325.pdf https://eprint.iacr.org/2009/325.pdf
        trinovantes 4y ago
        > stick a full block on the front of the message Yes, this will give you the same intermediate state in the hash function but if m1!=m2, then the final output H(pad'(x|m1)) != H(pad'(x|m2)) where pad' is just appending 1 then all 0s. Maybe it's due to the years since my crypto class or maybe I'm just dense but I'm not following your logic at all. I'm asking for an actual example of m1 and m2 that will result in the same hash if they are not padded with their lengths. I made the assertion that for all m1,m2 if m1!=m2 then H(pad'(m1))!=H(pad'(m2)). Disproving it is simply giving a counter example m1,m2. EDIT: I took some time to skim through the paper you've linked and it supports my assertion: > We also have shown that the simplest padding such as padding 10^d only can be sufficient for collision preserving property if we restrict collision resistant assumption of the underlying compression function for the first (t − 1) bits. Since we know (or at least believe) the SHA2 compression function is collision resistant, then length padding is redundant.
        edflsafoiewq 4y ago
        Oh, we're talking about different things. I'm only talking about proving collision-preservation, not something as spectacular as generating collisions.

edflsafoiewq 4y ago

AFAIK the 1 bit does nothing. Padding with 1+(number of 0s)+(length of message) is traditional though and used by MD4/MD5/SHA1/SHA2. You can read in a few places that this is the padding proposed by Merkle, but I looked it up and in my reading of One Way Hash Functions and DES he does not use the 1 > As an aside, we note that x is padded with 0's until its size is an integral multiple of the size of the convenientlySizedChunks. Note that padding with 0s might introduce some ambiguity about the exact value of x that is being authenticated, as discussed by Juenernan[4]. The message "010110" padded to 8 bits would be "01011000" and it is now unclear how many trailing 0's were present in the original message. Several methods are available to resolve this ambiguity. We select a method that will also be useful in resolving a further problem: we append the length of x, in bits, at the end of x. To make this additional "length" field easy to find. we shall right justify it in the final block. If the length field won't fit, we add additional blocks to the end of x.