Password hashing using NP complete problems

Question

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:

1. 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?

2. 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?

3. 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.

Answer 1

Unfortunately, this doesn't seem to work (see below for details), and it seems hard to find a way to make this kind of idea yield a provably secure scheme.

The problem with your general idea

You're not the first to think of the idea of trying to base cryptography on NP-complete problems. The problem is that NP-hardness only ensures worst-case hardness, but cryptography requires average-case hardness. There have been multiple attempts to base cryptography on NP-complete problems (e.g., knapsack cryptosystems), but they have not fared well. Typically what happens is that people discover algorithms that are often effective on average (or with non-trivial probability), even though in the worst case they are exponential; this is enough to break the crypto, even though it doesn't contradict the NP-hardness.

The point of relying on a NP-hard problem is presumably to ensure some kind of provable security for your scheme (e.g., if P $\ne$ NP then your cryptosystem is secure), but because of the difference between worst-case vs average-case hardness, that kind of result doesn't actually follow, and it's not clear how to build a cryptosystem where we do obtain such a result.

I suggest reading more about the subject. You can find some useful starting points at The significance of NP-Hard Problems in Cryptography, Average-case complexity open problems other than one-way functions, Status of Impagliazzo's Worlds?, Worst case to average case reductions.

The problem with your particular scheme

Your specific proposal isn't fully specified. To analyze a scheme, you need to fully specify how the scheme works. In your case, it's not clear how you select 4 out of the 7 clauses in the general example. (And a single example is not a substitute for a specification that describes how you do it in general.)

That said, it appears your scheme will be easy to break no matter how you instantitate those details. Intuitively, 3SAT instances with so many clauses are usually easy. More specifically, I will describe an attack that solves the type of 3SAT instances generated by your scheme. First, let's try to recover $x_0,x_1,x_2,x_3,x_4$. Focus on just the clauses that mention only those variables (and not any other). There should be 40 such clauses, because there are 10 ways to choose a subset of 3 of the variables. There are $2^5$ possible assignments to those 5 variables, so try them all and discard any assignment that is violated by any of the 40 clauses. I predict that this will leave you with only about one assignment that is consistent with all clauses.

(Why? For each subset of 3 variables, the 4 clauses narrow us down so only $1/2$ of the assignments are consistent with those 4 clauses. We have 10 such subsets, so heuristically we expect the chances that an incorrect assignment will be consistent with all 10 subsets to be about $1/2^{10}$, and since there are only $2^5-1$ possible incorrect assignments, probably approximately none of them will survive these tests. Or, to try a different set of heuristic: any incorrect assignment will satisfy a single clause with probability $7/8$, so heuristically the probability that it satisfies all 40 clauses is about $(7/8)^{40} \approx 2^{-7.7}$. Therefore, the expected number of incorrect assignments that are consistent with all 40 clauses is about $(2^5-1) \times 2^{-7.7} \approx 0.15$. So usually all incorrect assignments are eliminated, leaving only the correct assignment.)

This can be repeated for each group of 5 variables, uniquely recovering the unique satisfying assignment for each. If there is any ambiguity, the candidate assignments can be checked against other clauses.

In this way, we see that there is an efficient algorithm that will typically solve the class of 3SAT instances generated by your procedure. It won't solve all 3SAT instances, but the instances you generate have a special structure, and it does solve instances with that special structure effectively. This illustrates the point well: some instances of 3SAT are easier than others, and the hardness of 3SAT (in worst-case complexity) says little or nothing about the hardness of the special instances you generate or the hardness of an average 3SAT instance.