2
$\begingroup$

Trying to settle a discussion at work. We are mostly concerned with pre-image resistance.

Suppose we have a common secure hash function $H$ (e.g. SHA-1/SHA-2) and some message $M$ we want to hash. The message has length $M_L$. For the message we provide the digest $D$ and the length of data digested $D_L$.

With regards to preimage-resistance, for which common hash functions is it more secure to check that

$H(M) = D$ $and$ $M_L = D_L$

rather than just checking

$H(M) = D$

?

$\endgroup$
  • $\begingroup$ When you have an incorrectly implemented Merkle tree hash (pretty common, e.g. Bitcoin and Amazon fell for that), you need to compare the size as well. $\endgroup$ – CodesInChaos Dec 3 '15 at 18:55
  • $\begingroup$ @CodesInChaos sounds interesting... Got a reference URL, especially for Amazon? Google is unhelpful (probably searching for wrong terms) $\endgroup$ – rmalayter Dec 15 '15 at 23:08
  • $\begingroup$ As all sane secure hash functions include the length as part of the algorithm, isn't the length has wholly redundant? $\endgroup$ – rmalayter Dec 15 '15 at 23:09
  • $\begingroup$ @rmalayter: Well, that's what I believe (there goes my attempt at an unbiased question through the window) but as the question popped up at work I thought I should ask here for some expert ruling. My take on it is also that the size could be seen as another (albeit very insecure) hash-function and then (I remember reading) that using several hash-functions in parallel is barely more secure than using only the strongest, which would render size redundant as well. $\endgroup$ – Andreas Magnusson Jan 20 '16 at 12:23
1
$\begingroup$

First the obvious; checking $M_L=D_L$:

  • is unnecessary from a security standpoint IF $H$ really is secure, by definition of that; but who knows what's really secure?
  • can't harm preimage resistance (first or/and second), nor collision resistance;
  • can greatly increase speed, if the hash is computed only after checking $M_L=D_L$; that's a common reason to perform this test in file de-duplication;
  • can harm the conceivable objective of hiding $D_L$ in some attack scenarios (such as timing or other side-channel attack);
  • harms even so slightly a common objective: simplicity.

It is possible to construct a devious $H$ that is collision resistant and second preimage resistant only if it is also checked $M_L=D_L$; e.g., a variant of SHA-256 that matches the original for messages of length $l\ge255$ bits; and for shorter messages outputs the original message, a one bit, and $255-l$ zero bit(s). That can be improved to a hash that is very secure from the standpoint of second preimage resistance if $M_L=D_L$ is checked, and less secure (according to some parameter) otherwise. That's indicative checking $M_L=D_L$ could help security for some otherwise insecure hashes.

If we take MD5 as an example: we know how to create collisions with little effort (including for messages with different and arbitrary beginning), but that's only if these messages have exactly the same length. Otherwise, the best known attack is brute force (feasible, but never performed publicly as of today for being too expensive). However that applies to collision-resistance, not to the question's preimage resistance (neither first nor second). Thus, in the case of MD5, we know that adding a check that $M_L=D_L$ does not significantly improves collision resistance, but MD5 remains preimage resistant without that check.


Definitions used:

  • first preimage resistance: given some arbitrary value the size of a hash, it is difficult to find a message with that hash.
  • second preimage resistance: given some arbitrary message, it is difficult to find a different message with the same hash.
  • collision resistance: it is difficult to find two distinct messages with the same hash.
$\endgroup$
  • $\begingroup$ So what you're saying is that with MD5 (at least) it doesn't help? $\endgroup$ – Andreas Magnusson Dec 2 '15 at 11:21
  • $\begingroup$ @Andreas Magnusson: see updated answer. $\endgroup$ – fgrieu Dec 2 '15 at 11:28
  • $\begingroup$ But if the messages have exactly the same length, the ML==DL is always true in the cases when it's easiest to create collisions, or is it something I'm not getting (quite likely ;))? $\endgroup$ – Andreas Magnusson Dec 2 '15 at 11:33
  • $\begingroup$ I still don't understand. All the collision examples here mscs.dal.ca/~selinger/md5collision have the exact same message/data size. So at least for those examples, checking ML==DL for MD5 does not improve collision resistance. The question then is whether it improves preimage resistance? $\endgroup$ – Andreas Magnusson Dec 3 '15 at 14:42
  • $\begingroup$ @Andreas Magnusson: oups, you are right; thanks for correcting me. And indeed, I do not (yet) answer the question. Perhaps it would be easier if you specified the question is about a certain common type of hash, and which (like, SHA-1), or for any abstract theoretical hash. $\endgroup$ – fgrieu Dec 3 '15 at 15:36

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.