How Do I Prove My Password, Without Giving You My Password?

We build systems which are often insecure and where we pass our passwords over channels which can contain sniffing agents, such as for man-in-the-middle ones, and which can discover our password. Often we use HTTPs as a tunnel, and where we only authenticate one side to the other. The method often used to authenticate Bob the Server to Alice the User is with a digital certificate. So how  do we authenicate each side, and password the proof of the password, without actually storing the password?

One method to improve the process is Secure Remote Password protocol (SRP). In this protocol the server does not contain any password-related data, and involves the client providing a proof that it knows the password, without giving away what the password is.

So we Alice has a password p, and wants define it with Bob the server.

Alice selects some salt (s) and computes a hash of s and p:

x = Hash (s,p)

Next she calculates v using a generator value (g):

v = g^x

Alice sends this (and s), and Bob the Server indexes (v,s) with a value of I. The password is now registered with Bob the Server.

Now Alice will prove she knows the password. First she generates a random number (a) and sends I and A:

I, A = g^a

Bob the Server sends the salt (s) and B:

s, B = kv + g^b

Alice and Bob the Server compute:

u = H(A, B)

Alice computes a hash of s, I and p, and then calculate a shared session key of K_c:

x = H(s, I, p)
S_c = pow(B - k * pow(g, x, N), a + u * x, N)
K_c = H(S_c)

Bob the Server computes a session key of K_s:

S_s = pow(A * pow(v, u, N), b, N)
K_s = H(S_s)

They should now have the same session key (K_s == K_c), and will send messages from Alice to Bob the Server:

Alice(cipher) = K_s("I am Alice")

and Bob the Server to Alice:

Bob(cipher) = K_c("I am Bob")

If the messages decode we authenticate Alice to Bob, and Bob to Alice.

Here is an example:

Conclusions

The threat of the insider means that if the hashed version of passwords is compromised, it can lead to a large-scale data leak. Organisations should do everything they can to protect the passwords of their user, and SRP is a major contender for this.

In 2012 Linkedin was hacked, and there was a leak of 6.5 million usernames and passwords, but this has risen to 117 million.  Now, a dark web market dealer - The Real Deal - has been offering these account details for 5 Bitcoins ($2,200). The passwords themselves are hashed version, but these are fairly easily to crack with rainbow tables, especially as users tend to pick weak passwords. Some think that 117 million seems a large amount for the hack, so it is unvalidated at the present time.

An analysis of the passwords used, shows the same old contenders, with "123456" right up there at the top, and someway behind we get "linkedin" and "password". In fact, these passwords make up about one million of all the passwords on the hashed database: