How Do I Prove My Password, Without Giving You It? The Magic of SRP

How Do I Prove My Password, Without Giving You It? The Magic of SRP

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

SRP

A demo of this method is defined here.

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ˣ

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ᵃ

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

s, B = kv + gᵇ

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:

#. H, N, g, and k are known beforehand to both client and server:
N = 0xc037c37588b4329887e61c2da3324b1ba4b81a63f9748fed2d8a410c2fc21b1232f0d3bfa024276cfd88448197aae486a63bfca7b8bf7754dfb327c7201f6fd17fd7fd74158bd31ce772c9f5f8ab584548a99a759b5a2c0532162b7b6218e8f142bce2c30d7784689a483e095e701618437913a8c39c3dd0d4ca3c500b885fe3
g = 0x2
k = 0xb317ec553cb1a52201d79b7c12d4b665d0dc234fdbfd5a06894c1a194f818c4a

0. server stores (I, s, v) in its password database
I = fred
p = qwerty1234
s = 0xfda947a1b1427048
x = 0x37ba469993c0bd2586d3e68807f2edb1da08806da80c26bc732c989bf7a2613c
v = 0x125e2b6c236a0522937e14bd5cdc3d10fb4f1c8ec893ded30a2db82e05915cfbdff570e1458d1779b112ea76e2c4a0e832eea11111c9e60b874ba8640186d9ec756db9be4145822c57b760abceeded039558b6643259319277cc12784a620e104f931523c9069aa4a13694c5629e37a699062edaca30a75324180360a433942b

1. client sends username I and public ephemeral value A to the server
I = fred
A = 0x252776843ccfcd4e319d507812cc001973cb1cceec9856880b48325da3dd821e434c8747398b59ae2db57ee852474a5a092c8f4741ac6139400b3af9adb8c9463c718af927fea9a5f5d57a61fc73724359a7b6ce891b63c3d9b4b0ef2af33d6b422ce98905f290354ca70a825ed72538e8915f278abadeb3dacb5099301d5c2d

2. server sends user's salt s and public ephemeral value B to client
s = 0xfda947a1b1427048
B = 0x7c3ad37f8f313e30273685be6b714199f5e6ebf9774fe2fa7c91f995d78129fcaf5e52f919887e795ba181d7a016e21f4b0162c0a0048c6b0ef6e85b808b385fe40080043171f984ed7c7a6ea7b68feb04a738f5786aeb6447ad5f3f93ecabde575b10fe45cca7808083a45755d2d559dc6c84127544357c8ca38690f8a78a78

3. client and server calculate the random scrambling parameter
u = 0x6ed0183b75014de85e5f217e16e7e0b124e3458240558bbb0208da08739b9457

4. client computes session key
S_c = 0x8e05d1e97f065cd4ef226e249eaf1ab4798d4a731238b0888720d4ae99f1c809476cb55d39651c56eaa8233d1e0f1e23095120d230e98b1b40f29df62ec62ad5a961b6bea20e1fbe743f602bf05e5ee33b5498d076ccc34941ae58848514b8848d694c37623eb2c69f9659c244b0458053400a51ba9d3c74d6274f0b45faaca4
K_c = 0xd2871bb153ff765f4b95ea36a0272144ab26204f3e7128c12355dcb09a0e92d0

5. server computes session key
S_s = 0x8e05d1e97f065cd4ef226e249eaf1ab4798d4a731238b0888720d4ae99f1c809476cb55d39651c56eaa8233d1e0f1e23095120d230e98b1b40f29df62ec62ad5a961b6bea20e1fbe743f602bf05e5ee33b5498d076ccc34941ae58848514b8848d694c37623eb2c69f9659c244b0458053400a51ba9d3c74d6274f0b45faaca4
K_s = 0xd2871bb153ff765f4b95ea36a0272144ab26204f3e7128c12355dcb09a0e92d0

6. client sends proof of session key to server
M_c = 0x8f15bb59302a92aec68747f531e324608cfdd972a7d4b7ce8dc806af0326a00e

7. server sends proof of session key to client
M_s = 0x6bb87a337901bff9046e3d973c7957874e00a6bd4fb4785e10699ba178e4d1a1

An outline of the code used is:

# based on http://srp.stanford.edu/design.html
import hashlib
import random

def global_print(*names):
    x = lambda s: ["{}", "0x{:x}"] [hasattr(s, 'real')].format(s)
    print("".join("{} = {}\n".format(name, x(globals()[name])) for name in names))

# note: str converts as is, str( [1,2,3,4] ) will convert to "[1,2,3,4]"
def H(*args):  # a one-way hash function
    a = ':'.join(str(a) for a in args)
    return int(hashlib.sha256(a.encode('utf-8')).hexdigest(), 16)

def cryptrand(n=1024):
    return random.SystemRandom().getrandbits(n) % N

# A large safe prime (N = 2q+1, where q is prime)
# All arithmetic is done modulo N
# (generated using "openssl dhparam -text 1024")
N = '''00:c0:37:c3:75:88:b4:32:98:87:e6:1c:2d:a3:32:
       4b:1b:a4:b8:1a:63:f9:74:8f:ed:2d:8a:41:0c:2f:
       c2:1b:12:32:f0:d3:bf:a0:24:27:6c:fd:88:44:81:
       97:aa:e4:86:a6:3b:fc:a7:b8:bf:77:54:df:b3:27:
       c7:20:1f:6f:d1:7f:d7:fd:74:15:8b:d3:1c:e7:72:
       c9:f5:f8:ab:58:45:48:a9:9a:75:9b:5a:2c:05:32:
       16:2b:7b:62:18:e8:f1:42:bc:e2:c3:0d:77:84:68:
       9a:48:3e:09:5e:70:16:18:43:79:13:a8:c3:9c:3d:
       d0:d4:ca:3c:50:0b:88:5f:e3'''
N = int(''.join(N.split()).replace(':', ''), 16)
g = 2        # A generator modulo N

k = H(N, g)  # Multiplier parameter (k=3 in legacy SRP-6)

print("#. H, N, g, and k are known beforehand to both client and server:")
global_print("H", "N", "g", "k")

print("0. server stores (I, s, v) in its password database")

# the server must first generate the password verifier
I = "person"         # Username
p = "password1234"   # Password
s = cryptrand(64)    # Salt for the user
x = H(s, I, p)       # Private key
v = pow(g, x, N)     # Password verifier
global_print("I", "p", "s", "x", "v")

print("1. client sends username I and public ephemeral value A to the server")
a = cryptrand()
A = pow(g, a, N)
global_print("I", "A")  # client->server (I, A)

print("2. server sends user's salt s and public ephemeral value B to client")
b = cryptrand()
B = (k * v + pow(g, b, N)) % N
global_print("s", "B")  # server->client (s, B)

print("3. client and server calculate the random scrambling parameter")
u = H(A, B)  # Random scrambling parameter
global_print("u")

print("4. client computes session key")
x = H(s, I, p)
S_c = pow(B - k * pow(g, x, N), a + u * x, N)
K_c = H(S_c)
global_print("S_c", "K_c")

print("5. server computes session key")
S_s = pow(A * pow(v, u, N), b, N)
K_s = H(S_s)
global_print("S_s", "K_s")

print("6. client sends proof of session key to server")
M_c = H(H(N) ^ H(g), H(I), s, A, B, K_c)
global_print("M_c")
# client->server (M_c) ; server verifies M_c

print("7. server sends proof of session key to client")
M_s = H(A, M_c, K_s)
global_print("M_s")
# server->client (M_s) ;  client verifies M_s

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: