1
$\begingroup$

I was told that a hash function (mostly looking at the SHA-* family) should have input strings of variant length provided first, and those of fixed length after (ie salt), in order to avoid some kind of collision attacks.

I haven't seen this explained anywhere, so I was wondering whether this holds and how so.


What I'm describing seems to be related to the length extension attack (also see Understanding the length extension attack) (thanks to Dan Anderson for bringing this up)

$\endgroup$
  • $\begingroup$ Where were you told? $\endgroup$ – kelalaka Mar 28 at 18:52
  • $\begingroup$ how does "where" add any value to the question or is of any interest to an answer? $\endgroup$ – c00kiemon5ter Mar 28 at 22:25
  • 1
    $\begingroup$ @c00kiemon5ter dubious claims such as "salt prevents length-extension attacks" are insensible in the context of cryptographic common knowledge, therefore we need some context to understand why such claims are made. $\endgroup$ – DannyNiu Mar 29 at 2:27
  • $\begingroup$ @DannyNiu and kelalaka, sorry; "where" implies locality in my native language, so I felt the answer should be "in the office" or "in a meeting", I didn't translate this as "in what context". $\endgroup$ – c00kiemon5ter Mar 29 at 11:18
3
$\begingroup$

Suppose you want to hash a pair of bit strings $(m, r)$ with a hash function $H_0$ defined on bit strings, where $m$ is variable-length and $r$ is fixed-length—maybe a unique salt, or a secret key, or an unpredictable randomization. We will consider possible functions $H(m, r) := H_0(\operatorname{encode}(m, r))$ for some encoding function (although there are other possible ways to hash tuples using an iterated hash function).

First, what security properties are you hoping for when you say ‘hash’? Here are some possibilities:

  • Independence. If $r \ne r'$, then the functions $m \mapsto H(m, r)$ and $m \mapsto H(m, r')$ are (effectively) independent functions.

    Here we are modeling $H_0$ as a uniform random choice of functions with quirks like the length extension attack below; we are interested not in how $H$ behaves on different messages with the same $r$, but rather how $H$ behaves with different $r$.

    This is important for password hashing, because techniques like rainbow tables provide a batch advantage trying to find inputs $m_1, \dots, m_n$ given the outputs $h_1 = f(m_1), \dots, h_n = f(m_n)$ of the same function[1][2]. However, you should use a serious password hash like scrypt or argon2 if you're hashing passwords, and they are already defined in terms of separate password and salt parameters.

  • Collision resistance. It is hard for the adversary to find $(m, r) \ne (m', r')$ such that $H(m, r) = H(m', r')$. This is a standard property of functions like SHA-256 and BLAKE2b; if it holds for $H_0$ we might hope that it holds for $H$.

    This is important for commitments: you can prove to someone that you have a message $m$ without revealing it by picking $r$ uniformly at random and revealing $h = H(m, r)$; then when you want to reveal what the message was, you can give them $(m, r)$ and they can verify $h = H(m, r)$.

  • (Enhanced) target collision resistance. It is hard for the adversary to find a message $m$ such that, given uniform random $r$ after choosing $m$, they can find $m' \ne m$ and $r'$ with $H(m, r) = H(m', r')$.

    With mere TCR[3] (first introduced to the literature as the less-pronounceable UOWHF[4]), the adversary is restricted to $r' = r$; with eTCR[5], the adversary is allowed to choose $r'$, so eTCR is a stronger requirement.

    (e)TCR is important for randomized signature schemes like RSA-PSS and Ed25519. The first secure signature scheme in history, Rabin's, used a randomized hash. Even if $H_0$ turns out to have collisions like MD5, there are choices for $H$ that remain eTCR to the best of our knowledge. Using a TCR construction would have thwarted MD5 certificate forgery, including a particular attack used by the governments of the United States and Israel to sabotage Iran's nuclear program—but RSA, Inc., and the IEEE adopted $H_0(r \mathbin\| H_0(m))$ instead of $H_0(r \mathbin\| m)$ in the standards[6][7] for PSS signatures. (More history.)

  • Pseudorandomness. It is hard for an anyone who doesn't know $r$ to distinguish the function $m \mapsto H(m, r)$ from a uniform random function of the same shape.

    Pseudorandomness is useful for many things including deterministic key derivation and message authentication codes.

These properties aren't exhaustive, but they're likely to be relevant in a wide variety of applications.

What encoding might we use to define $H$ in terms of $H_0$, and what properties does the resulting $H$ provide? Let's assume $H_0$ is an iterated hash function, like essentially all of them, and let's assume for simplicity that $m$ an integral number of blocks long.

  1. Suffix-MAC: $H(m, r) := H_0(m \mathbin\| r)$, putting $r$ at the end.

    • provides independence
    • provides exactly as much collision resistance as $H_0$: a collision in $H$ is a collision in $H_0$ and vice versa
    • provides at most as much (e)TCR as $H_0$ provides collision resistance: finding a collision in $H_0$ is enough to break (e)TCR of $H$—so, no (e)TCR for MD5 or SHA-1!
    • provides at most as much pseudorandomness as $H_0$ provides collision resistance, for iterated Merkle–Damgård functions with no output filter like MD5 or SHA-256: finding a collision in $H_0$ is enough to distinguish $H$ from uniform random—so, no pseudorandomness at all for MD5 or SHA-1!
  2. Prefix-MAC: $H(m, r) := H_0(r \mathbin\| m)$, putting $r$ at the beginning.

    • provides independence
    • provides exactly as much collision resistance as $H_0$: a collision in $H$ is a collision in $H_0$ and vice versa
    • provides at least as much (e)TCR as $H_0$ provides collision resistance: an (e)TCR break of $H$ implies a collision in $H_0$, but finding a collision in $H_0$ does not necessarily help to find a collision in $H$e.g., nobody has broken eTCR for MD5 in this form
    • provides no pseudorandomness for for iterated Merkle–Damgård functions with no output filter like MD5, SHA-256, and SHA-512, for which length extension attacks apply: given $H(m)$ but not $m$, it is easy to find $H(\operatorname{pad}(m) \mathbin\| m')$ for any suffix $m'$, which a uniform random function exhibits with negligible probability—so, no pseudorandomness for MD5, SHA-1, SHA-256, SHA-512!
      • Exception: If $m$ is fixed-length, then prefix-MAC provides pseudorandomness under reasonable assumptions about $H_0$ even when $H_0$ is MD5, SHA-256, or SHA-512.
      • Note that SHA-3, BLAKE2, SHA-512/256, and essentially all new designs in the past decade do not have this weakness, so $H(r \mathbin\| m)$ is pseudorandom—but they usually also provide separate keyed hashes like KMAC128 or keyed BLAKE2, which are better to use because they are effectively independent even if you happen to hash the message $r \mathbin\| m$ with SHA-3 or unkeyed BLAKE2.
  3. Envelope-MAC or sandwich-MAC: $H(m, r) := H_0(r \mathbin\| m \mathbin\| r)$, putting $r$ at the beginning and the end.

    • provides independence
    • provides exactly as much collision resistance as $H_0$
    • provides at least as much (e)TCR as $H_0$ provides collision resistance
    • provides pseudorandomness under reasonable assumptions about $H_0$

    This is a predecessor to HMAC and actually it provides about the same security as HMAC with less complexity, as long as $m$ is padded so that the $r$ keys appear in their own blocks; it was left in the dustbin of history mainly because someone noticed that it does not provide security if the trailing $r$ straddles a block boundary[8] and thereby gave it a bad reputation, but it has since been proved that with appropriate padding it is a perfectly good choice[9] (paywall-free).

  4. HMAC: $H(m, r) := H_0\bigl((r \oplus \mathrm{opad}) \mathbin\| H_0((r \oplus \mathrm{ipad}) \mathbin\| m)\bigr)$, using prefix-MAC first to compress the message and then as an output filter, with two keys derived by a simple key schedule.

    • provides independence
    • provides probably about the same collision resistance as $H_0$
    • provides at least as much (e)TCR as $H_0$ provides collision resistance
    • provides pseudorandomness under mostly reasonable assumptions about $H_0$
$\endgroup$
  • $\begingroup$ This is an outstanding answer - far more analytical than anything I expected. Thank you for taking the time to write this. I need to go through this a couple more times. And I also need to think more about the properties we expect to get from this function and express them with your given meanings. $\endgroup$ – c00kiemon5ter Mar 29 at 11:14
1
$\begingroup$

I've seen that urban myth in the context of passwords and salt. The saying goes it's better to append than prepend salt, to avoid length extension attacks (similar to SHA-1 append attacks). However, it really doesn't matter as the salt, prepended or appended, totally changes everything. The same password (or other input) cannot be correlated with different salt, no matter if it's prepended or appended.

In other words, the salt completely protects against length extension attacks no matter where it is inserted. Salt also protects against building databases (rainbow tables) that reverse lookup hashed passwords (assuming the salt is long enough to make having every salt value in the database impractical).

$\endgroup$
  • $\begingroup$ hello and thanks ;) I think you are correct and my colleague was actually referring to the length extension attack. I'll read up on it. $\endgroup$ – c00kiemon5ter Mar 28 at 23:31
  • $\begingroup$ I think you could be clearer about whether you think length-extension attacks don't apply to password scenarios (which I agree with) or if you think in general length-extension attacks are not impacted by the decision to append/prepend (which I don't think is true). $\endgroup$ – bmm6o Mar 29 at 15:29
  • $\begingroup$ Neither password scenarios or digests in general are impacted by the decision of prepending or appending salt. The salt provides randomization on the original input and is equally effective whether it is prepended or appended. It's true that hashes can be computed sequentially in blocks and the intermediate results are the same in the case of appending salt. But we don't have those intermediate results to play with. $\endgroup$ – Dan Anderson Mar 29 at 20:56

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.