Thread: State of the Art of Password Hashing

Originally Posted by laserlight

It might not be a fluke, but I wonder if you're solving the right problem:

I get the impression that you've come up with your own cryptographic hash function, except that it is intended specifically for password hashing, to address "the inherent weaknesses (and flaws) of the very algorithms that we rely on". The thing is, when we're talking about hashing a password for storage, we're talking about preimage resistance, but (as far as we non-NSA people know) the algorithms commonly used for password hashing these days are preimage resistant, even if it is just plain MD5 applied once with no salt.

Consequently, the algorithms that build on these for better password hashing don't address preimage resistance since attackers are unlikely to approach the problem from that angle anyway. From what I understand, they just assume that if the password is random and sufficiently long, it really is computationally infeasible to find the password given the hash and the algorithm, thus the problem to solve is how to protect passwords that are not so random and/or not sufficiently long.

Do you disagree with this assessment? What are the "inherent weaknesses (and flaws)" that your algorithm fixes?

There are a variety of functions in common use today; some provably broken (MD5, SHA-1), others theoretically so or at least in just limited circumstances (SHA-2, for example), and then a handful with few-to-none known "major" issues (AES, SHA-3).

Preimage resistance is obviously one the most important properties of a good hash function, but there are other points to consider as well. MD5, SHA-1, and SHA-2 are all susceptible to length extension attacks and so cannot be safely used as message authentication codes. MD5 is prone to bit-flipping attacks. Few (including the venerable SHA-3) produce remarkably high entropy density output (which ultimately opens the door to more efficient cryptanalysis). Most are based on what amounts to "complex shuffling routines" (to broadly simplify things, of course), a fact which severely complicates the ability to *prove* the assumption of security of the system. Finally, ALL of the algorithms are generally designed in a very rigid, non-scalable manner; complex initialization constants seem to be the rule, meaning that a change from say 256-bit to 512-bit keys can be problematic and hazard-prone at best.

In contrast, what I am proposing instead focuses on a very fundamental number theory question, one which is many orders of magnitude easier to prove than such "smoke and mirror" techniques (the well-understood Diffie-Hellman problem is a good example of what I am striving for here) and as a result should be much more resilient to the types of vulnerabilities seen today (of course, whether or not it is prone to some other kind of attack remains to be seen). Incidentally, the randomness produced by the algorithm which provides such a high degree of collision resistance isn't even forced by the design - it just arises naturally from the normal course of operation. Last but not least, the whole scheme is easily scalable (so easy that one just has to modify the size parameter of a function call to produce a hash of arbitrary width).

So yes, I do feel quite justified in saying that this is the right problem to be working on.

Originally Posted by Sebastiani

There are a variety of functions in common use today; some provably broken (MD5, SHA-1)

They are provably broken for collision attacks, but collision resistance is not necessary for the security of password storage as long as there is second preimage resistance.

Originally Posted by Sebastiani

Preimage resistance is obviously one the most important properties of a good hash function, but there are other points to consider as well. MD5, SHA-1, and SHA-2 are all susceptible to length extension attacks and so cannot be safely used as message authentication codes.
(...)
In contrast, what I am proposing instead focuses on a very fundamental number theory question, one which is many orders of magnitude easier to prove than such "smoke and mirror" techniques (the well-understood Diffie-Hellman problem is a good example of what I am striving for here) and as a result should be much more resilient to the types of vulnerabilities seen today (of course, whether or not it is prone to some other kind of attack remains to be seen).

In other words, the title of and introduction to this thread is inaccurate. You're not aiming for the state of the art for password hashing in particular, but rather you're aiming for something somewhat grander: the state of the art for cryptographic hash functions (as in a new crytographic primitive).

Originally Posted by laserlight

They are provably broken for collision attacks, but collision resistance is not necessary for the security of password storage as long as there is second preimage resistance.

Sure, preimage resistance is important. It certainly isn't the sole consideration though.

Originally Posted by laserlight

In other words, the title of and introduction to this thread is inaccurate. You're not aiming for the state of the art for password hashing in particular, but rather you're aiming for something somewhat grander: the state of the art for cryptographic hash functions (as in a new crytographic primitive).

Maybe not so much "inaccurate" as "inconcise", but yes, the implication here is more specifically a generic cryptographic primitive.

Moreover, this isn't just a single algorithm we're talking about but rather a whole new class of them to draw from. There is a reason why number theory has been called the "Queen of Mathematics" - it's perhaps the most inexhaustible wellspring of potential available to us.