Can the hash of one message be used to make it easier to find the hash of a very similar message?

Question

Background:

I am trying to get an understanding of using a hash of a passphrase as a secret.

Example:

sha256("EasyToRememberPassphrase") -> secret.

I am assuming a properly designed hash function used this way above will yield a secret with the same or fairly similar entropy as the input passphrase (or the size of the hash, whatever is smaller), thus as far as being used as a secret goes, the passphrase and secret are equally hard to guess.

On to the question:

Say I generate two secrets, secretA and secretB in the following way:

passphrase = "EasyToRememberPassphrase"
sha256(passphrase + "a") -> secretA
sha256(passphrase + "b") -> secretB

Assuming an attacker gets access to two pieces of information:

• secretA
• the fact that secretB was hashed from data very similar to secretA

Does this give the attacker an easier time figuring out secretB? And if so, to what degree? Or are good hash functions immune/sufficiently resistant to an attack using this particular set of information?

Answer 1

Knowing secretA; that it what obtained as sha256(passphrase + "a") -> secretA; and that passphrase is easy to remember; is enough for a password cracker to find passphrase. From that, secretB succumbs.

Thus yes, what's known gives the attacker an easy time figuring out secretB. If there are $n$ bits of entropy in the passphrase, the attacker's work is on average $2^{n-1}$ SHA-256 hashes. For many definitions of an easy to remember passphrase, that's feasible with readily available hardware and software, and technical progress is making that easier every year (by perhaps 0.2 to 2 bit of entropy, depending on what one thinks the state of Moore's law is). Morality: hashing something a human can remember does not turn it into a key. For this, use scrypt (or another Key Derivation Function intended for passwords, such as the lesser bcrypt or PBKDF2); and add salt at the KDF input, if at all possible.

---

No weakness in SHA-256 was involved in the above, only its excessive speed for the application. As far as we know (we have no proof), SHA-256 has properties close enough to a random function that in the application, a practical adversary (unable to perform work comparable to $2^{256}$ hashes) can not exploit that SHA-256 was used for producing both secretA and secretB with only 2 bits different in the input (assuming ASCII), other than by guessing that input.

That property of SHA-256 (that nearly equal input induce no exploitable similarity in outputs) was not one of SHA-256's primary design goals, and does not follow from these goals, stated as: "The hash algorithms specified in this Standard are called secure because, for a given algorithm, it is computationally infeasible 1) to find a message that corresponds to a given message digest, or 2) to find two different messages that produce the same message digest").

If we wanted something with that property, and a strong argument (which would be useful if passphrase was replaced by a true key), we could use a MAC of an arbitrary constant for each desired secret. That could be HMAC with SHA-256 rather than just SHA-256, used as HMAC(key,"a") -> secretA and HMAC(key,"b") -> secretB.

Update: on second thought, in the setup in the question, and given the internals of SHA-256, we can argument in favor of that property (which is better than having no known evidence of the contrary): the two inputs to SHA-256 differ in the same block, thus any relation between the two outputs would amount to a related-key attack on the cipher from which the round function of SHA-256 is built. This argument is still much weaker than the modern argument for HMAC using SHA-256.

Answer 2

If the passphrase has enough entropy to resist exhaustive attack (which a human-memorable passphrase almost certainly won't), then no, an attacker who learns H(passphrase + 'a') can't deduce the value of H(passphrase + 'b').

To prevent exhaustive search, you should not be using SHA256 as your hash function. Instead, you should use PBKDF2 or scrypt or bcrypt, to make the hashing as slow as possible. If you do that, and your passphrase has enough entropy, then the scheme should have the security property you are looking for.