Given a root hash
root = H(plaintext)
and two (or more) derived hashes
h1 = H(salt1 + root)
h2 = H(salt2 + root)
would the knowledge of h1 and h2 alone increase the chances of finding the root hash or even the plaintext? I'm using SHA256.
$\begingroup$
$\endgroup$
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
7
To the best of our knowledge, SHA256 does not leak any additional information from related hashes.
On the other hand, the state of "our knowledge" might not be that comprehensive; this security property of SHA256 cannot be derived from the base security assumptions of a hash function (preimage resistance, second preimage resistance and collision resistance), and as far as I know, no one has studied it. While it may be (and likely is) secure, no one has really studied it, and so there there might be a semiobvious leakage that no one happened to find yet.
Now, there is an obvious variation on this which has been studied: HMAC. HMAC is a Message Authentication Code, that is, it has a security assumption that if you give someone (who doesn't know the key) a large number of MAC outputs based on known texts, they still cannot derive the key, or any information about MAC outputs for texts they haven't seen. That is precisely the security assumption that you are looking for; and so HMAC has been analyzed against the exact problem you're looking for. HMAC uses a hash function (for example, SHA256) as an underlying primitive, and it does have a small additional cost over the underlying hash; if you can do some precomputation, this additional cost is just one more hash compression evaluation.
As for how you would use HMAC; well, HMAC has two inputs, a "key" and a "message". You would make your "root" the key and the "salt" the message, and use the output of the MAC as your derived hash.
-
$\begingroup$ Contrary to what you say, I'm sure that the security property can be derived from the preimage resistance of the hash function. If you can find "root" from the results of the hash of concatenating it with arbitrary "saltN" values faster than brute force then the hash is not preimage resistant. $\endgroup$– ByteCoinCommented Feb 22, 2012 at 18:13
-
$\begingroup$ @ByteCoin: I disagree. Preimage resistance says "given a single hash, you can't find a string that hashes to that value". It doesn't say anything about what happens if you're given a large number of hashes. Your reasoning about "concatinating it with an arbitrary saltN" doesn't work, as in a preimage attack, you don't know "it" (the original preimage). It's not difficult (assuming there is a preimage resistant hash function) to put together a hash function that is preimage resistant but not "group" preimage resistant (that is, from a set of related preimages, you can find the preimages). $\endgroup$– ponchoCommented Feb 22, 2012 at 18:31
-
$\begingroup$ We seem to differ in our understanding of what preimage resistance is. After reading [Rogaway and Shrimpton's "Hash Function Basics"](www.cs.ucdavis.edu/~rogaway/papers/relates.pdf) it seems understandable that we might have different ideas of what it means. They rigorously specify three different variants, "Pre" "aPre" and "ePre". In order to save time, I would contend that no hash function that is not group preimage resistant in your definition would ever be considered "secure" and that the security property we were originally discussing can certainly be guaranteed from collision resistance. $\endgroup$– ByteCoinCommented Feb 22, 2012 at 20:46
-
1$\begingroup$ @fgrieu: I would contend that your public function H is not preimage resistant as the relevant preimages can now be found with 2^128 work instead of the normal 2^256. $\endgroup$– ByteCoinCommented Feb 22, 2012 at 23:53
-
1$\begingroup$ @fgrieu: Here is the construction I was thinking of; we would take a preimage-resistant function H, and create another hash function $J(m) = H(m) + BitSelect( H(m), m )$, where $BitSelect$ is a function that selects one bit out of the message (where that bit is selected depending on the value of H(m)). J is almost as preimage resistant as H (if you can find a preimage for J in time X, you can find a reimage for H in time 2X); however given a large number of related messages hashed by J, it is quite likely that all the bits of the messages will be leaked. $\endgroup$– ponchoCommented Feb 23, 2012 at 1:23
$\begingroup$
$\endgroup$
Given just h1 and h2, if the salts are of any significant length then it will be impossible to uniquely determine "root" even if the hash function is very weak so long as it performs enough "compression". If both salts are known as well as h1 and h2 then the value of root is impractical to determine as long as the hash function is secure.
Recovery of root or plaintext given the above construction given only the derived values would constitute as serious break of the security of SHA256. However, you may not have considered all the relevant threats and the system as a whole may be vulnerable to a length-extension attack. It's worth using the HMAC construction mentioned in poncho's answer rather than trying to do it yourself.
$\begingroup$
$\endgroup$
4
The answer depends on assumptions on plaintext.
If an adversary can enumerate the possible plaintext (e.g. if plaintext is a password, mediocre passphrase, or a published file) then yes: knowledge of h1 or h2 allows finding what plaintext is, by verifying beyond reasonable doubt an hypothesis made. For some level of protection against that, use a Password-Based Key Derivation Function such as PBKDF2, or better scrypt.
If plaintext can't be guessed (e.g has 128 bits of entropy), then no: root and plaintext will not leak, from a practical standpoint. More precisely, we are safe, for some strong enough hypothesis on H, that SHA-256 may meet (and meets in practice as far as we know).. or perhaps not (since we have no proof). A suitable hypothesis on H is being computationally indistinguishable from a random function (aside from the length-extension property, and being a particular public function).
As pointed in another answer, we'd have the HMAC security argument if we used
h1 = HMAC( Hash=SHA-256, Key=root, Message=salt1 )
h2 = HMAC( Hash=SHA-256, Key=root, Message=salt2 )
-
$\begingroup$ This is incorrect. Knowledge of h1 or h2 only allows an adversary to verify that their guess of plaintext is correct if salt1 or salt2 respectively are published. The original question is careful to ask whether knowledge of h1 and h2 ALONE increase the chances of finding root or the plaintext. $\endgroup$– ByteCoinCommented Feb 23, 2012 at 0:28
-
$\begingroup$ @Bytecoin: Indeed I assume salt is public, that's the standard assumption. $\endgroup$– fgrieu ♦Commented Feb 23, 2012 at 6:31
-
$\begingroup$ Although the salts are not exactly public, they are not strongly secured either. Plaintext represents pre-hashed credentials. So do I get it right that, in this case, a PBKDF or at least HMAC should be used for that? $\endgroup$ Commented Feb 24, 2012 at 5:16
-
$\begingroup$ @MichaelKlaus: Yes, if Plaintext has moderate entropy, feeding it (or better, whatever it is obtained from) to a PBKDF is a good option. If something (salts) is not strongly secured, the simple and safe option is to consider it public. Also beware that credentials can often be guessed. Using HMAC rather than H is inteanded to guard against a (very hypothetical) weakness in SHA-256, nothing else. $\endgroup$– fgrieu ♦Commented Feb 24, 2012 at 17:22
$\begingroup$
$\endgroup$
Presuming root contains enough entropy to make a brute force search infeasible given only $h1$ and $salt1$, the (presumed) preimage resistance of SHA256 means that finding root would still be infeasible even if the attacker also knows the value $h2$ and $salt2$.
Update: First order preimage resistance is usually defined as, for a random value $h$, it is hard to find a message $m$ such that $h = H(m)$. Given the debate this definition has caused in the comment field of another answer, one might argue that this definition is too imprecise and doesn't fully capture the intuitive notion of preimage resistance. Other definitions are of course possible:
Let $n$ be the output length of the hash function $h$ and let $N$ be the maximum input length. Let $r:\{0,1\}^N\mapsto\{0,1\}^N$ be a random function that maps any valid input to another valid input. This function is unknown to adversary but a parameter of the game. Let $BitSelect:\{0,1\}^N\mapsto\{0,1\}$ be such that $BitSelect(m)$ selects a single bit from $m$ based on the value of $h(m)$. Let $f_r:\{0,1\}^N\mapsto\{0,1\}^n\times\{0,1\}$ be such that $f_r(x) = h(r(x)),BitSelect(r(x))$. Define first order preimage resistance such that $h$ is first order preimage restistant if and only if an adversary has less than $2^{-(n-1)}$ advantage distinguishing $f_r$ from the corresponding random function.
Arguably, this definition captures the intuitive notion that first order preimage resistance is about the inability to derive a hash input you didn't get to choose from a hash output you didn't get to choose. Also, if $h$ is not preimage resistant in the common sense, then $f_r$ as defined above will not be IND-CPA.
answered Feb 22, 2012 at 11:09