10
$\begingroup$

I always assumed that a hash function allows input of arbitrary length, since that's what all the hash functions I was aware of did. Wikipedia's definition of a hash function is as follows:

A hash function is any function that can be used to map data of arbitrary size to fixed-size values.

However, some functions like bcrypt, which label themselves as password hash functions, define a maximum size input length (in the case of bcrypt, 72 bytes). This seems like a contradiction, and has lead me to come up with two possible explanations:

  1. Password hash functions, although similar in name, are not hash functions.
  2. Arbitrary length inputs is not a strict requirement for hash functions, merely a common feature.

As such, I would like to know how to resolve this apparent contradiction. Is it necessary for a hash function to allow arbitrary length inputs or not?

$\endgroup$
  • $\begingroup$ That is a password hash function, not exactly a hash function, and can change according to the designer, Argon2i has $2^{32}-1$. This can allow the designer to control the structure $\endgroup$ – kelalaka Jan 11 at 14:03
  • 5
    $\begingroup$ I think the meaning of "arbitrary length" may be up for debate - does it mean "any length", or just "a variety of lengths", with the key feature being that different lengths of input do not produce different lengths of output. I note that further down that Wikipedia article (under "Applicability") is this sentence which implies limits are possible, but undesirable: "A hash function that allows ... strings only up to a certain length ... isn't as useful as one that does." Neither sentence has a direct citation, though, so a clearer and more authoritative definition would certainly be possible. $\endgroup$ – IMSoP Jan 11 at 14:15
  • $\begingroup$ @kelalaka Right, but the question being debated is whether such functions can still be considered "hash functions"; i.e. is "password hash function" a sub-type of "hash function"? In the case of bcrypt, its creators seem to use the terms somewhat interchangeably, so is there consensus that this is incorrect usage? $\endgroup$ – IMSoP Jan 11 at 14:24
  • 2
    $\begingroup$ @IMSoP So yeah, turns out I was wrong, which is good - means I learned something today. $\endgroup$ – MechMK1 Jan 11 at 14:45
  • $\begingroup$ @MechMK1 Just an observation: Wikipedia is notoriously inaccurate when it comes to cryptographic information. I would be very, very careful trusting what you read there. $\endgroup$ – forest Jan 11 at 23:40
18
$\begingroup$

Is it necessary for a hash function to allow arbitrary length inputs or not?

Of course not. SHA-256 is limited to inputs of 18,446,744,073,709,551,615 bits or less; it is not defined for larger inputs; SHA-256 is not disqualified from being considered a hash function because of this limitation.

$\endgroup$
  • $\begingroup$ So the claim that hash function allow arbitrary-length inputs is not technically accurate - just accurate in most use cases? $\endgroup$ – MechMK1 Jan 11 at 14:44
  • 4
    $\begingroup$ @MechMK1: correct; in practice, we'll never have to compute a hash on a $2^{61}$ byte string (if nothing else, it'd take years to actually compute, given that we have to do it serially), and so it's considered irrelevant if a function can't handle that size. $\endgroup$ – poncho Jan 11 at 14:51
  • $\begingroup$ I was just very surprised to hear that something could be considered a "real" hash function and have a very small "practical" limit like 72 bytes $\endgroup$ – MechMK1 Jan 11 at 15:04
  • $\begingroup$ I believe MD5 has an unlimited input limit because the Merkle–Damgård padding's message length wraps rather than becoming undefined. $\endgroup$ – forest Jan 11 at 23:08
13
$\begingroup$

Is it necessary for a hash function to allow arbitrary length inputs or not?

Although one can design a hash function that can hash arbitrary size there is no need since one can not easily pass the $2^{64}-1$ limit for SHA-1, SHA-224, and SHA-256 series, and $2^{128}-1$ limit for the SHA-384, SHA-512, SHA-512/224 and SHA-512/256 series. During the standardization, NIST put the limits NIST FIPS 180 due to the below MOV attack (Handbook of Applied Cryptography; Chapter 9, Example 9.23);

Those are based on the Merkle–Damgård construction and padding the message length at the end is necessary for security (also called MD-strengthening). If the message size is not padded at the end, an internal collision ( on the compression functions ) can be turned into a full collision in the hash function. Therefore, different sized files will have different hashes due to the length padding ( see the the MOV attack). Interestingly the longer the file you hash ( just change the padding ) the more chance of internal collision you will have, See

In contrast, SHA-3 (Keccak is the winner of the competition and it is based on Sponge Construction) doesn't have a limit ( though the SHA-3 competition call says; shall support a maximum message length of at least $2^{64}-1$ bits)

So, although some need a limit due to attack considerations and standards; NIST provides a better definition (NIST FIPS 202 #page9)

A hash function is a function on binary data (i.e., bit strings) for which the length of the output is fixed ( with footnote: For many hash functions, there is a (very large) bound on the length of the input data.)

And Menezes et. al definition;

More precisely, a hash function $h$ maps bit-strings of arbitrary finite length to strings of fixed length, say $n$ bits.

Therefore, limited or not, all are considered cryptographic hash functions as long as they have good pre-image resistance, second-preimage resistance, and collision resistance, with $\mathcal{O}(2^n)$, $\mathcal{O}(2^n)$, and $\mathcal{O}(2^{n/2})$ attack costs, respectively.

$\endgroup$
3
$\begingroup$

No, but yes, but you're asking the wrong question.

A hash function, formally speaking, is a function from some input set to a finite set. There is no general requirement that the input set have a particular size or form. The input is not necessarily the set of all bit-strings. It's very common to define hash functions on structured data, for example. However, in practice, the reason to use a hash function is to map a “large” set of potential inputs to a ”small“ set of hash values. The point of hash functions is to produce a value with a stringent size limit from a value that doesn't have this size limit. As a consequence, stating that a hash function “can be used to map data of arbitrary size to fixed-size values” is an adequate one-line summary.

Note that “hash function” on its own is not a cryptographic concept. There is a separate concept of cryptographic hash function. In contexts where cryptography is implicit, “hash function” means “cryptographic hash function”, but in a general context such as a generalist encyclopedia article, “hash function” has nothing to do with cryptography.

A cryptographic hash function is a kind of hash function that has some additional security-related properties. Like in the general case, the input doesn't have to be the set of all bit-strings. Unlike the general case, though, it's rather uncommon to consider hash functions on structured input. Usually, when we need to use a cryptographic hash on structured data, we start by encoding the data unambiguously as a bit-string. However, when the data has internal equivalences (for example if it's a sequence in which some elements can be reordered), the representation of the data can be a nontrivial issue and so sometimes it's necessary to analyze the security of the whole mapping from structured data to hash value, and not just the security of the mapping from an encoding of the data as a bit-string to a hash value.

In practice, most cryptographic hash functions take a bit-string as input, and accept input that is theoretically bounded, but practically unbounded. All common cryptographic hash functions accept at least two exabytes of input ($2^{64}$ bits). If a practical requirement for larger inputs was foreseen, the world would adopt new functions that accept longer inputs. So while it isn't mathematically correct that typical cryptographic hash functions accept inputs of any length, it's practically true in the sense that you won't be able to actually run the function on a counterexample.

But the most important part of the answer to your question is something you didn't ask.

A password hash function is not a hash function!

Beware of terminology, it's sometimes misleading. A password hash function shares some properties of a cryptographic hash function, and that's why it's called that way. However there are differences, both in terms of the interface and in terms of the security property. A password hash function does not fit the definition of “hash function” (cryptographic or not), and it shares some security properties with cryptographic hash functions but there are also crucial differences.

A cryptographic hash function is a function $F$ that takes one input (“message”, usually a bit-string) and returns one output (the hash value, usually a bit-string of a fixed size). It must have three security properties (which I'll express here in layman terms — some of the formal definitions are pretty tricky):

  • Preimage resistance (sometimes called first preimage resistance): given a “random” $h$, it's difficult to find $m$ such that $F(m) = h$.
  • Second preimage resistance: given $m_1$, it's difficult to find $m_2$ such that $F(m_1) = F(m_2)$.
  • Collision resistance: it's difficult to find $m_1 \ne m_2$ such that $F(m_1) = F(m_2)$.

A password hash function (for which there's no Wikipedia article that I can recommend, the closest being key stretching) is a function $G$ with two inputs: a password and a salt. Note that unlike a hash function, there are two inputs. The password has a similar role to the input of a hash function, but the salt is new. Like a hash function, a password hash function has an output which is generally a bit-string of a fixed size; however the very closely related concept of key stretching function can have variable-size output.

Given a password as input, to use a password hashing function, you need to provide a salt. There are two ways to do that: you can generate it, or you can read back a stored value (which is normally stored together with the expected output value).

The security properties of a password hash function $G$ have more differences than similarities with the security properties of a cryptographic hash function.

  • Password preimage resistance: given $s$ and $h$, it is difficult to find $p$ such that $G(p, s) = h$, even if $h$ is deliberately chosen such that $p$ exists, as long as $p$ is not revealed.
  • Input sensitivity: if $p_1 \ne p_2$ then knowing $G(p_1, s)$ does not give any information about $G(p_2, s)$. Likewise, if $s_1 \ne s_2$, then knowing $G(p, s_1)$ does not give any information about $G(p, s_2)$. In other words, the function erases any relationship between the inputs, since any two inputs map to unrelated outputs as long as the inputs are not identical.
  • Slowness: the fastest known method for calculating values of $G$ must be as slow as possible.

(Note that whereas cryptographic hash functions are a long-established concept and have a standard presentation and standard terminology, this is not the case for a password hash function. The names I give above are my own, and you're likely to find different presentations of the concept that might break the properties down differently.)

The preimage resistance property for passwords is kind of intermediate between first preimage resistance and second preimage resistance for ordinary (cryptographic) hashes. First preimage resistance would not be sufficient for passwords. First preimage resistance allows certain values of $h$ to be “easy”, because you can always enumerate $h(\mathtt{"a"}), h(\mathtt{"b"}), h(\mathtt{"c"}), \ldots$ and that gives you some hash values with known preimages. This is why finding a preimage is only difficult if $h$ is not deliberately chosen to make it easy. Another way to state preimage resistance is that inverting the function (calculating preimages) can only be done by guessing the input and verifying it. (Guessing includes knowing in advance.) With ordinary hashing, it's supplemented by second preimage resistance, which in some sense says that enumerating values of $h$ is the only way to break first preimage resistance. With password hashing, second preimage resistance and collision resistance are irrelevant. It doesn't really matter if there are multiple passwords for the same account. What matters is that it's difficult to find any of them. The more passwords there are, the more likely it is easy to find one, so in practice password hashing functions tend not to have collisions, but it isn't an absolute requirement.

Password hashing absolutely require that related inputs map to unrelated outputs. You wouldn't want to be able to tell that a password guess is one character off, for example. This property is mostly true of typical hash functions, but there tend to be corner cases where related inputs do map to related outputs (such as length extension attacks). This is not acceptable with key derivation, including key stretching.

Slowness is a specific property of key stretching and password hashing. As we saw above with first preimage resistance, inverting a hash function is prone to guessing. Guessing is very bad for password lookup because passwords are often chosen to be memorable, and that makes them easy to guess. Password hashing must be intrinsically slow to slow down guessing attempts.

$\endgroup$
  • $\begingroup$ I like this answer, but think it would be less contradictory with a small change: since you say a "hash function" (in the general case) can take structured input, and have a variety of properties, it seems reasonable to say that a "password hash function" is a "hash function" (it meets the definition you provide in the first paragraph), but is not a "cryptographic hash function". In other words, that they are two different sub-sets of the set of all "hash functions". This seems consistent with, for instance, the usage in the bcrypt paper I linked to in an earlier comment. $\endgroup$ – IMSoP Jan 13 at 17:35
  • $\begingroup$ @IMSoP A hash function takes a single parameter. It might be structured data, but it's still a single input. A password hash function takes two parameters with fundamentally different roles. So a password hash function doesn't fit the definition of a hash function, even a very general one. In programming terms, it doesn't have the right type. $\endgroup$ – Gilles 'SO- stop being evil' Jan 13 at 17:48
  • $\begingroup$ @IMSoP The input to a function like SHA-256 is theoretically bounded: the definition says no more than 2^64 bits minus change. But it's practically unbounded because you'll never attempt to pass that much attempt to it. (An annoying thing if you're maintaining an implementation of the function since you're supposed to have code to detect if the limit is reached, but you can't test this code on real data…) $\endgroup$ – Gilles 'SO- stop being evil' Jan 13 at 17:50
  • $\begingroup$ Ah, I see what you meant with the "bounded/unbounded" part now. $\endgroup$ – IMSoP Jan 13 at 18:01
2
$\begingroup$

There is no requirement that a hash function 'use' any or all of the bits of the value being hashed. Admittedly, a hash function that always returns 5 is not particularly useful, but it does map an input to a value.

More useful hash functions will involve more of the input value but not necessarily all of it.

Thus, it is sort of meaningless to ask if hash functions must take input values of arbitrary length.

New contributor
Jay Goldman is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

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.