Commonly used password hashing algorithms work like this today: Salt the password and feed it into a KDF. For example, using PBKDF2-HMAC-SHA1, the password hashing process is DK = PBKDF2(HMAC, Password, Salt, ...)
. Because HMAC is a 2-round hashing with padded keys, and SHA1 a series of permutations, shifts, rotations and bitwise operations, fundamentally, the whole process is some basic operations organized in a certain way. It's not obvious, fundamentally, how difficult they really are to compute. That's probably why one-way functions are still a belief and we have seen some historically important cryptographic hash functions became insecure and deprecated.
I was wondering if it's possible to leverage NP complete problems to hash passwords in a brand new way, hoping to give it a more solid theoretical foundation. The key idea is, suppose P != NP (if P == NP then no OWF so current schemes break as well), being an NPC problem means the answer is easy to verify but hard to compute. This property fits well with the requirements of password hashing. If we view the password as the answer to an NPC problem, then we can store the NPC problem as the hash of the password to counter offline attacks: It's easy to verify the password, but hard to crack.
Caveat is, the same password may be mapped to multiple instances of an NPC problem, probably not all of them are hard to solve. As a first step in this research, I was trying to interpret a binary string as an answer to a 3-SAT problem, and to construct an instance of 3-SAT problem to which the binary string is a solution. In its simplest form, the binary string has 3 bits: x_0, x_1, x_2. Then there are 2^3 == 8 clauses:
000 ( (x_0) v (x_1) v (x_2) )
--------------------------------------
001 ( (x_0) v (x_1) v NOT(x_2) )
010 ( (x_0) v NOT(x_1) v (x_2) )
011 ( (x_0) v NOT(x_1) v NOT(x_2) )
100 ( NOT(x_0) v (x_1) v (x_2) )
101 ( NOT(x_0) v (x_1) v NOT(x_2) )
110 ( NOT(x_0) v NOT(x_1) v (x_2) )
111 ( NOT(x_0) v NOT(x_1) v NOT(x_2) )
Suppose the binary string is 000. Then only 1 of 8 clause is false (the first one). If we discard the first clause and AND the remaining 7 clauses, then 000 is a solution of the resulting formula. So if we store the formula, then we can verify 000.
The problem is, for a 3-bit string, if you see 7 different clauses there, then you instantly know which one is missing, and that would reveal the bits.
So later I decided to discard 3 of them, only keeping the 4 marked by 001, 010, 100 and 111. This sometimes introduces collisions but makes solving the problem less trivial. The collisions don't always happen, but whether they would surely disappear when the input has more bits is not known yet.
Edit. In the general case where the binary string can be any of (000, 001, ..., 111), there are still 8 clauses where 7 are true and 1 is false. Pick the 4 clauses that give truth value (001, 010, 100, 111). This is reflected in the prototype implementation below.
Edit. As the answer shown by @D.W. below, this method of choosing clauses may still result in too many clauses on a given set of variables which makes it possible to quickly narrow down their values. There are alternate methods of choosing the clauses among the total 7 * C(n, 3) clauses. For example: Pick a different number of clauses from a given set of variables, and do that only for adjacent variables ( (x_0, x_1, x_2), (x_1, x_2, x_3), (x_2, x_3, x_4), ... ) and thus form a cycle instead of a clique. This method is likely not working as well because intuitively you can try assignments using induction to test whether all clauses can be satisfied. So to make it simple explaining the overall structure let's simply use the current method.
The number of clauses for an n-bit string is 4 * C(n, 3) = 4 * n * (n - 1) * (n - 2) / 6 = O(n^3), which means the size of hash is polynomial of the size of password.
There's a prototype implementation in Python here. It generates a 3-SAT problem instance from a user input binary string.
After this long introduction, finally my questions:
Does the above construction (as implemented in the prototype) work as secure password hashing, or at least look promising, can be revised, etc.? If not, where it fails?
Because we have 7 * C(n, 3) clauses to choose from, is it possible to find another way to construct a secure 3-SAT instance suitable for use as password hash, possibly with the help of randomization?
Are there any similar work trying to leverage NP completeness to design proven secure password hashing schemes, and already got some results (either positive or negative)? Some intros and links would be very welcome.
Edit. I'd accept the answer below by @D.W., who was the first to reply and gave great insights about the problem structure as well as useful resources. The naive clause selection scheme introduced here (as implemented in the Python prototype) didn't seem to work because it's possible to quickly narrow down variable assignments in small groups. However, the problem remains open because I haven't seen a formal proof showing such NPC-to-PasswordHashing reductions won't work at all. Even for this specific 3-SAT reduction problem, there might be different ways of choosing clauses that I don't want to enumerate here. So any updates and discussions are still very welcome.