How does hash speed vary based on string length? Surprisingly I have not been able to find an answer to this question on Google.

If I have a function that is based on any of the popular hashing algorithms used for password generation, by what percentage/magnitude does the speed change when the string length increases? Assuming the salt is retrieved from the function.

Function GetHash("CAT")

Function GetHash("I like cats, cats are great, I am a longer string")


I am looking only for the most approximate of answers, for example the difference might be tiny (&lt;1% increase in time for a longer string), or it might be twice as slow (100% increase), or it might be more.
Contrary to the other answer, I'll be assuming the hash function is of the password-oriented kind; and my answer will be: input size has almost no influence on speed in good practice, even for much longer input than in the question.

Password-oriented (or entropy-stretching, key-stretching) hash functions are, for example, suitable to transform a (password, salt) pair into a hash, with (salt, hash) then stored in a database, allowing later checking a (password, salt) pair by recomputing hash and comparing it against the one found in the database along salt, without allowing to directly extract password from a (salt, hash) pair.

Such hashes actually have three inputs: password, salt, and a workfactor which controls the effort required to compute the hash output. Said effort is parameterized to make testing a list of (say) the 10 million most common choices of password somewhat costly. For example, with a workfactor such that computing one hash requires 0.1s on the CPU normally used, the 10 million passwords are tested in 12 days with that CPU, hours with a server having many CPUs, perhaps a fraction of hour for a well-equipped adversary using ASICs or FPGAs (example publicly for sale). Choice of workfactor is a compromise between effort for legitimate use (translating into delay and power spent at each password use, capital investment for more powerful hardware); and security: the lower the effort to compute a hash, the cheaper it will be to find a common password from a leaked (salt, hash) pair.

An example of password-oriented hash is PBKDF2 with PRF an HMAC with (e.g.) SHA-256 as the hash, as standardized by NIST Special Publication 800-132. A safer one is Bcrypt. An arguably even safer one is Scrypt with HMAC−SHA-256, which can leverage multiple CPUs and ample RAM on the legitimate user's machine as a mean to dramatically raise the investment cost necessary for a parallel attack in a reasonable timeframe. The recent state of the art is captured by the results of the Password Hashing Competition.

For all these functions, a choice of the workfactor giving even minimal security, and password and salt inputs even orders of magnitude larger than in the question, the execution time overwhelmingly depends on workfactor; somewhat on code quality and CPU used; and very marginally on the size of password and salt (up to a limit of perhaps 1MB for each second of the execution time as controlled by workfactor). In a nutshell, that's because the password and salt inputs, when long (typically: more than about 64 bytes) are only processed once and reduced to something of fixed small size (using a hash such as SHA-1 or SHA-256), which is then repeatedly processed, with the repetition count controlled by workfactor.



Update: Maarten Bodewes pointed in comment that things might be different for the common PBKDF2 using HMAC-SHA-256 as the PRF. My analysis (below) is that timing dependency w.r.t. the size of the password won't happen for software implementations offering good security, but only for those sub-optimal from a security standpoint by a factor of about 2 or more.

The bulk of the execution time for PBKDF2 using HMAC-SHA-256 as the PRF is spent iterating $m_j=\operatorname{HMAC}(P,m_{j-1})$, where $P$ is the password input, and (with $H=\operatorname{SHA-256}$):
$$\operatorname{HMAC}(P,m)=\begin{cases}
H((P\oplus\text{opad})\|H((P\oplus\text{ipad})\|m))&amp;\text{if }|P|\le64\text{ octets}\\
\operatorname{HMAC}(H(P),m)&amp;\text{otherwise}  
\end{cases}$$
where the $x\text{pad}$ are 64-octet constants, and the $P\oplus x\text{pad}$ are with $P$ right-padded with zeroes to 64 octets. When $|P|\le64$ and $|m|=32$, computing $\operatorname{HMAC}(P,m)$ involves 2 invocations of SHA-256 each with 96 octets of data, thus a total of 4 invocations of the round function of SHA-256.

A good implementation of PBKDF2 should maximize the security obtained for a given execution delay, thus should be speed-optimized. Therefore, a good implementation of PBKDF2 using HMAC-SHA-256 as the PRF should


replace $P$ with $\operatorname{SHA-256}(P)$ if $P$ is more than 64 octets;
pad $P$ to 64 octets by appending zeroes to the right and pre-compute $P\oplus\text{ipad}$ and $P\oplus\text{opad}$
apply the round function $R$ of $\operatorname{SHA-256}$ to these, obtaining the 32-octet $h_\text{in}=R(\text{IV},P\oplus\text{ipad})$ and $h_\text{out}=R(\text{IV},P\oplus\text{opad})$
in the core loop dominating the execution time, compute $m_j=R(h_\text{out},R(h_\text{in},\operatorname{pad}(m_{j-1})))$ using 2 invocations of $R$, and combine that $m_j$ by XOR into a separate 32-octet value.


Only steps (1) and (2) can have a timing dependency w.r.t. to $|P|$. All steps of PBKDF2 conceivably movable in the core loop 4 are shown.

If the implementation uses SHA-256 as a black box, but still performs (1) and (2) out of the core loop, it is bound to have 4 invocations of $R$ in the core loop, rather than 2. This is not best practice at least in software, because it lowers the protection against password search by a factor of about 2; but it does not introduce any dependency of the execution time of the core loop w.r.t. to $|P|$.

If the implementation moves (2) in the core loop, but not (1), it is likely that it will have some time dependency w.r.t. $|P|$ in the core loop (about linear, with some slope likely positive up to and including $64$ octets; then stable at the value obtained for $|P|=32$ afterwards). There will however be a fixed 4 invocations $R$ per core loop, and in any half-decent software implementation using a compiled language that will dominate the execution time, making the time dependency w.r.t. $|P|$ small.

If the implementation fails to perform (1) out of the core loop, then likely its core loop will exhibit a time dependency w.r.t. $|P|$, with a stiff steps at $|P|=65$ octets corresponding to going from 4 to 6 $R$, then steps about half as stiff at $|P|=120+k\cdot64$ octets for each additional $R$. That's a strong time dependency w.r.t. $|P|$, but only for implementations seriously inadequate from a security standpoint for the range of $|P|$ considered.



Hashes optimized for speed (like MD5, SHA-1, or SHA-256) should not be used alone for password storage and validation, because their very speed is a devastating weakness; worse, that weakness increases as time passes, for even nowadays Moore's law significantly speeds-up tasks which run well on parallel engines.