11
$\begingroup$

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 (<1% increase in time for a longer string), or it might be twice as slow (100% increase), or it might be more.

$\endgroup$
4
  • 7
    $\begingroup$ Could you give some example of "the popular hashing algorithms"? Are they of the MD5, SHA-1, SHA-256 kind; or of the PBKDF2, BCrypt, Scrypt kind? Both are usable as part of a password generation method. Only the second kind should be used for password validation; but their interface typically includes at least three parameters: password, salt, workfactor; for secure parametrization and the order of magnitude of size of other inputs that you consider, only the workfactor has a sizable influence on execution time. $\endgroup$
    – fgrieu
    Feb 12, 2016 at 13:47
  • $\begingroup$ I assumed that they'd mostly be the same in terms of speed vs input length scaling but with .NET it is common to use SHA256 so that is probably as good an example as any. It's unclear what the difference between the password and the salt is as I thought they were simply concatenated within the function, but for the purposes of the question the salt would be fixed length. I'm not familiar with workfactor though. $\endgroup$
    – NibblyPig
    Feb 12, 2016 at 14:20
  • $\begingroup$ with PBKDF2-SHA256, an extra hash iteration due to a very long input is inconsequential when you have an iteration count of a quarter million $\endgroup$ Feb 12, 2016 at 21:20
  • $\begingroup$ @SLC To reiterate fgrieu's point, SHA-256 is not a suitable function for storing and verifying passwords, precisely because it is fast. Use a dedicated password hashing function like bcrypt, scrypt, or PBKDF2. $\endgroup$ Feb 16, 2016 at 23:17

2 Answers 2

15
$\begingroup$

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))&\text{if }|P|\le64\text{ octets}\\ \operatorname{HMAC}(H(P),m)&\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

  1. replace $P$ with $\operatorname{SHA-256}(P)$ if $P$ is more than 64 octets;
  2. pad $P$ to 64 octets by appending zeroes to the right and pre-compute $P\oplus\text{ipad}$ and $P\oplus\text{opad}$
  3. 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})$
  4. 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.

$\endgroup$
6
  • 1
    $\begingroup$ Thanks that is quite interesting. You make it sound like password and salt length are trivial, which I suppose is true for a single hash, but by increasing the password length by one character (from say, 6>7) you would have to perform several billion additional iterations to brute force. Is that correct? I was wondering initially if increasing the minimum password length by e.g. 1 character vs increasing the salt length by say, 10 characters, would be equivalent in terms of the speed to brute force a database of passwords (longer pw = more iterations, longer salt = slower iterations). $\endgroup$
    – NibblyPig
    Feb 15, 2016 at 13:42
  • $\begingroup$ Sorry, I don't follow, which part isn't correct? $\endgroup$
    – NibblyPig
    Feb 15, 2016 at 13:48
  • 1
    $\begingroup$ @SLC: oups I has misread your comment; apologies. Your comment is about the time it takes to find a password by brute force (when your original question, and my answer, is about the time it takes to compute the hash knowing the password and salt). Adding 10 characters to the salt length leaves hardness of a brute force attack essentially unchanged, except if the earlier salt was common to many users, and the new one improves on that. Increasing the password length (or the parameter controlling the minimum password length) even by 1 considerably increases the hardness of a brute force attack. $\endgroup$
    – fgrieu
    Feb 15, 2016 at 14:04
  • 1
    $\begingroup$ Isn't for PBKDF2 the password actually repeatedly used as input for the PRF? In that case the size of the password may indeed influence the speed of this slightly unfortunate function (twice for each HMAC even). Of course it would not matter for anything below - eh - $32 - 8 - 4 = 20$ bytes or so... $\endgroup$
    – Maarten Bodewes
    Feb 16, 2016 at 1:30
  • $\begingroup$ Sheesh that should be 192 bits or 24 bytes of course for SHA-256....one block 448 minus one output size of 256 bit. $\endgroup$
    – Maarten Bodewes
    Feb 16, 2016 at 1:40
7
$\begingroup$

All hashes I know of are block oriented. The time required to calculate the hash scales with the number of blocks to be hashed. There is a small constant overhead dealing with the IV and, possibly, a finalization function.

$\endgroup$
1
  • 8
    $\begingroup$ I think you should say "scales linearly". That seems important from the OP's question. $\endgroup$
    – mikeazo
    Feb 12, 2016 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.