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

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


• 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?

-

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.

-
Nitpick: The passphrase jog doom motto gripe carat (which I just generated with Diceware) is fairly easy to remember, but your password cracker is going take a while looking for it, even if it's hashed with plain SHA-256. See also the obligatory xkcd reference. –  Ilmari Karonen Feb 11 '13 at 6:40
@IlmariKaronen: The XKCD reference estimates 44 bits of entropy, and $2^{43}$ SHA-256 is within feasibility of FPGA password crackers like the one in my first reference, or GPU-based ones. Your 5-words diceware password has $25\log_2 6\approx64.6$ bits of entropy, and indeed is reasonably safe. But it would take a lot of effort for me to remember it. –  fgrieu Feb 11 '13 at 7:17
There's certainly some personal variation involved here, but you might be surprised by how easy passphrases like these really are to memorize. Try it: can you recall the xkcd passphrase without looking at the comic? Try spending a minute or so coming up with a similar mnemonic for the one above (or just thinking about it, or retyping and erasing it, or whatever works best for you) and see if you can still remember it tomorrow. –  Ilmari Karonen Feb 11 '13 at 7:59
@IlmariKaronen: I did as suggested; I had seen this comic like 5 times (including yesterday and few weeks ago), and I only remembered "horse". I looked at it again, and I was not even close for the other three words, much less the order. Granted, I never tried to memorize it, and I'm confident that I could (my memory works well on things that "make sense" to me; I can memorize >8 arbitrary words, short term, by mentally placing them in a familiar corridor). Also, for long term use, it seems much easier to pick a fair passphrase, than it is to memorize one imposed on you by dices. –  fgrieu Feb 11 '13 at 13:24
Thanks for a good answer that really goes into several things I was wondering. The advice to use HMAC for this kind of situation seems like a substantial improvement. The way I understand your answer (and the abstract from the linked paper) is that using HMAC makes exploiting any correlation harder/impossible. Is this correct? –  mingleplough Feb 11 '13 at 22:39

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.

-