12
$\begingroup$

If you hash a string using SHA-256 on your computer, and I hash the same string using SHA-256 on my computer, will we generate the same value? Does the algorithm depend on a seed (so we'd both need the same seed) or some other such parameter?

edit: To clarify, by 'string' I meant 'the same byte input', which as the comments and @ispiro's answer point out, may be different for the same character string depending on the encoding.

$\endgroup$
  • 16
    $\begingroup$ You have to be careful what you mean by "string". A string is a sequence of characters, while hash function usually process byte sequences. If you use different encodings to map strings to byte sequences this can give you different hashvalues. $\endgroup$ – Drunix Feb 5 '18 at 12:05
  • 2
    $\begingroup$ No, it will depend on encoding. The selected answer is misleading. Maybe take a look at this: stackoverflow.com/questions/47963143/… $\endgroup$ – Koray Tugay Feb 5 '18 at 12:57
  • $\begingroup$ Also, while there is no "seed" (aka "salt") in pure hash functions, some libraries include the generation of the salt as part of the function they call "hash" (even though, strictly speaking, hashing is the part after you've integrated the input and the salt and done the encoding). So the accepted answer isn't wrong, if you are talking about pure hashing, but other readers may be mislead if they think their libraries "hash" function only hashes the input string. $\endgroup$ – Guy Schalnat Feb 5 '18 at 16:09
  • 1
    $\begingroup$ Even beyond the fact text is not a bytestring without encoding, if the character strings "look the same", may even compare the same, there's a variety characters that look identical, aren't printable, or are zero-width. $\endgroup$ – Nick T Feb 5 '18 at 17:50
  • 5
    $\begingroup$ OP can confirm but I think the question is assuming the same byte sequence and asking more about how the algorithm behaves given the same input. $\endgroup$ – xdhmoore Feb 5 '18 at 19:25
29
$\begingroup$

Yes, if you hash the same input with the same function, you will always get the same result.

This follows from the fact that it is a hash-function. By definition a function is a relation between a set of inputs and a set of permissible outputs with the property that each input is related to exactly one output.

In practice there is no seed involved in evaluating a hash-function.

Now, this is how things work in practice. On the theoretical side of things, we often talk about families of hash-functions. In that case there does exist a key that selects which member of the family we are using. The reason for this is a technical problem with the definition of collision resistance.

The naive definition of collision resistance for a single hash function $H : \{0,1\}^* \to \{0,1\}^n$ would be that for all efficient algorithms $\mathcal{A}$ the following probability is negligible $$\Pr[(x_1,x_2)\gets\mathcal{A}(1^n): H(x_1)=H(x_2)]$$

The problem with that is, that it is impossible to achieve. Given that $H$ is compressing, collisions necessarily exist. So an algorithm $\mathcal{A}$ that simply has one of those collision hardcoded and outputs it, has $$\Pr[(x_1,x_2)\gets\mathcal{A}(1^n): H(x_1)=H(x_2)] = 1.$$ So the definition is not achievable, since this $\mathcal{A}$ by definition exists even though nobody might know what it is.

To solve this problem, we define collision resistance for a family of hash-functions $\{H_k : \{0,1\}^* \to \{0,1\}^n\}_k$. We then define that such a family is collision resistant if it holds that the following probability is negligible $$\Pr_{k\gets\{0,1\}^n}[(x_1,x_2)\gets\mathcal{A}(k): H_k(x_1)=H_k(x_2)].$$

Here we do not run into the same problem, because the exact function $\mathcal{A}$ needs to find a collision for is chosen uniformly at random from an exponentially large family. Since $\mathcal{A}$ could have hardcoded collisions for at most a polynomial number of functions in the family, such hash-function families are not trivially impossible.

Note that this means that there somewhat of a disconnect between the theoretical treatment of hash-functions and their practical use.

$\endgroup$
  • $\begingroup$ Would you mind telling me where I could read up on the syntax for those formulae? $\endgroup$ – SwiftsNamesake Feb 5 '18 at 16:43
  • $\begingroup$ @SwiftsNamesake Would you mind being slightly more specific about which parts are confusing to you? $\endgroup$ – Maeher Feb 5 '18 at 16:46
  • $\begingroup$ I'm just generally curious about how I should interpret those expressions. They remind me a bit of list comprehensions, though. $\endgroup$ – SwiftsNamesake Feb 5 '18 at 17:06
  • 2
    $\begingroup$ @SwiftsNamesake: $1^n$ means (here) a bitstring of $n$ bits at 1. It belongs to $\{0,1\}^n$, the set of exactly $n$-bit bitstrings, having $2^n$ elements (where that's a number!). $\{0,1\}^∗$ is, in principle, the (infinite) set of all bitstrings (of finite but unbounded length), although that often in practice ends to be the (immense but finite) set of all bitstrings less than $2^{64}$ or $2^{128}$ bits. $\displaystyle\Pr_{k\gets\{0,1\}^n}[\operatorname{foo}(k)]$ is the probability that $\operatorname{foo}(k)$ holds for a uniformly random $k$-bit bitstring. $\endgroup$ – fgrieu Feb 5 '18 at 17:46
  • 2
    $\begingroup$ @SwiftsNamesake: $\{H_k : \{0,1\}^* \to \{0,1\}^n\}_k$ is a set of functions from $\{0,1\}^*$ to $\{0,1\}^n$ parametrized by $k$, each noted $H_k$. And $\displaystyle\Pr_{k\gets\{0,1\}^n}[(x_1,x_2)\gets\mathcal{A}(k): H_k(x_1)=H_k(x_2)]$ is the probability that for a uniformly random $k$-bit bitstring, algorithm $\mathcal{A}$, when fed $k$ as input, outputs a pair of (implicitly: distinct) bitstrings such that the member $H_k$ of the hash family collides for these bitstrings. $\endgroup$ – fgrieu Feb 5 '18 at 18:05
9
$\begingroup$

Strings aren't byte arrays.

The accepted answer deals with the question of whether SHA256 includes a seed. (Though the proof from the word "function" is arguable, since we call password-to-key functions "functions" though they can include "salt and pepper".) But strings still need to be encoded into bytes to be hashed.

Expounding on Drunix's comment, a quick search has revealed that it's quite likely that identical strings return different hash values owing to the strings being encoded in different encodings.

Here's a highly upvoted answer on StackOverflow suggesting using either UTF8 or UTF16 ("unicode" in the answer), which would nominally return different bytes and therefore different hashes.

And here's an answer using ASCII. Which "uses replacement fallback to replace each string that it cannot encode and each byte that it cannot decode with a question mark ("?") character." (MSDN) Again, returning a different hash than a UTF8 encoded string.

Additionally, take the following answer on StackOverflow. It mentions how macOS (Apple's Mac operating system) stores file names in a specific (unexpected?) way so that certain strings will "change" (at least in their byte representation).

And, of course, if your string comes from a text file, it will depend on the file's encoding. Notepad defaults (at least on my computer) to ANSI.

$\endgroup$
  • 1
    $\begingroup$ Why didn't you also mention EBCDIC? Or computers with non-8-bit bytes ;) $\endgroup$ – Hagen von Eitzen Feb 5 '18 at 20:58
  • $\begingroup$ @HagenvonEitzen I was going for hieroglyphs, but felt under qualified :) But seriously, I meant to point out likely problems. $\endgroup$ – ispiro Feb 5 '18 at 21:03
  • 2
    $\begingroup$ @HagenvonEitzen I actually implemented SHA-256 on a 6-bit IBM 1401 mainframe so it could mine Bitcoin. Unfortunately, at the rate of 80 seconds per hash it would take this 1960s punch card business computer much more than the universe's lifetime to mine a block so it wasn't cost-effective. $\endgroup$ – Ken Shirriff Feb 5 '18 at 22:09
  • $\begingroup$ I've edited my question to address your point and the comments. @Maeher correctly interpreted what I had meant by my question. $\endgroup$ – conor Feb 6 '18 at 0:06
  • $\begingroup$ This answer makes essentially the same mistake that it's trying to correct. The reality is that the term "string" is ambiguous: it often refers to a sequence of bytes (typically octets), occasionally to a sequence of characters (such as Unicode characters), frequently to something approximating a sequence of characters (such as 16-bit unsigned integers intended for interpretation as UTF-16 code units), and sometimes to more than one of these (such as when the only character encoding available is a single-byte encoding). $\endgroup$ – ruakh Feb 6 '18 at 8:22

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.