0

With regards to resistance against dictionary and brute-force attacks to "crack" hashes containing passwords, what determines the resistance of a cryptographic hash function? Since collision resistance is not important for password storing, and, as far as I know, all the popular hash functions are resistant enough to pre-image and second pre-image attacks to make it an infeasible approach, I guess those factors don't really matter.

The first thing that crosses my mind is the amount of computation needed to calculate the hash (is there a word for this?) - the higher amount the longer it's going to take. Is there anything else? Bit-length? Is bit-length and "computation amount" somehow correlated?

Improve this question
1
  • Far from a complete answer: an additional measure can be the amount of memory needed to compute the hash (to prevent parallelization to some extent). The number of bits is theoretically relevant if your goal is to find a matching plaintext (more bits, more possible outputs: on average more attempts to find a matching plaintext), but not that relevant if your goal is to find the plaintext initially used (more bits increase the chances that a matching plaintext is in fact the one initially used). This is, however, only relevant if the attacker can check many hashes -- thus "theortically".
    – dst
    Sep 13 '15 at 12:15
2

Since the context of this appears to be password cracking, and cryptographic hashes are unsuitable for storing passwords, the simple answer is just "your question is irrelevant".

A good cryptographic hash function has a number of basic design goals:

  • It should be computationally feasible to compute a hash H(x) for some input value x.
  • Changing one bit of the input should change all output bits with a probability of 50%.
  • Given only the hash output, it should not be computationally feasible to recover any information about the input (aside from generic attacks like rainbow tables).
  • Given an input x1, it should not be computationally feasible to find another input x2 which satisfies the condition H(x1) == H(x2), i.e. it should be hard to find collisions.

While these basic goals are certainly useful, they don't really cover the full requirements of a good password storage function. To answer your question more specifically: large or controllable computational cost is most certainly not a feature of most "ordinary" cryptographic hash functions.

A good password storage function, alongside all of the above, should have these additional design goals:

  • It should not be deterministic, i.e. two equal passwords for different users (or other entities) should not result in the same output hash.
  • It should implement some form of defense against precomputation attacks (e.g. rainbow tables)
  • It should be computationally expensive to brute-force the original input for all but trivial and common dictionary inputs. This is usually controlled by implementing a cost value, which allows for scaling of performance.
  • There should not be a way to produce more than negligible performance gains using time/space tradeoffs.
  • The performance of the function should be roughly linear across all architectures, to avoid acceleration by GPUs, FPGAs, etc. perhaps excluding specifically-designed silicon.

Some of these goals are similar to those implemented by key-derivation functions (KDFs) such as PBKDF2, but again these functions are not designed for password storage, and have instead been appropriated for such uses.

While there are currently only a few designs that implement all of the above, it is a relatively new field, so future works is expected. As a matter of interest, the current state-of-the-art for password storage, as per PHC, is Argon.

Improve this answer
5
  • "... cryptographic hashes are unsuitable for storing passwords.. " But in practice it's the most common thing to use, no?
    – tsorn
    Sep 13 '15 at 16:26
  • @tsorn There are lots of people using bad security practices out there. It's the whole reason I have a job in the first place.
    – Polynomial
    Sep 13 '15 at 17:00
  • Well then, what are you really saying? Ignoring the requirement of a salt (a password storage function has to be deterministic, no?), the difference between a "password storage function" and a cryptographic hash function is higher or controlled computational cost and a implementation that avoids architecture-specific acceleration?
    – tsorn
    Sep 13 '15 at 18:14
  • 1
    @tsorn Yes, essentially, which is something that cryptographic hash functions do not provide.
    – Polynomial
    Sep 13 '15 at 18:50
  • Nitpick in the last bullet of your cryptographic hash design goals: What you describe is a second preimage, not a collision. For a collision, the attacker is not given an input x, instead the attacker finds any such x and x' where h(x)==h(x').
    – nobody
    May 26 at 10:00

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.