Sep 16, 2013

Update to Partial Passwords


A few weeks back I exchanged a few emails with Tom (aka bananalol). We had a good discussion about the security of the partial password scheme you can find here.

I was able to show that his initial suspicion of a security hole in the scheme was unfounded.

Category: General
Posted by: dc352

The initial argument was whether it was possible the solve the system of linear equations. However, the scheme is based on the fact that these systems of equations have always infinitely many solutions.

The same holds for Shamir's secret sharing that inspired our solution for storing and verifying partial passwords.

The discussion actually continued and Tom showed that storing the constant K in plaintext allows for an attack. I have initially suggested that one can store this constant in plaintext or a hash value of it. Currently, we have to recommend using the hash value.

For those interested in detail, here is an excerpt from Tom's email. (It assumes password letters come from a set of 100 characters - hence the magic constant of 100.)

 

For match (p1p2..pN) I think you can compute the whole password in "constant" time O(100*k), by using the function again for each next unknown password character pN+1..pk, as an equation with 1 variable. E.g. we've got a match (p1p2...pN), then to reveal pN+1 we solve the equation for set 1,2,...,N-1, N+1 with just discovered (y1, y2, ..., yN-1), and with an unknown yN+1:

K' = \sum_i [ yi * [ (\PI_j (j) ) / (\PI_j (i-j)) ] ] would be like

K' = yN+1 * [ (\PI_j (j) ) / (\PI_j (N+1-j)) ] ] + C

where C is constant (computed).

If K is in plain text, then it is a simple equation with 1 variable and can be solved in O(1). If K is stored as a hash, then iterate through every character again and compare hash(K') with stored hash(K). Note, that in this case, computing each next character requires O(100) operations, in total of O(100*k) rather than O(100^k).

10^12/16!*10! was suggested as if you brute force N=6 characters with plain K (if using the trick with modulo it is be better to brute force last N chars than first N, due to the lower charset for p16 than p1).