SRP: Logging In with a Password Without Sending It

SRP: Logging In with a Password Without Sending It

Introduction

A password is a poor secret. People choose short ones, they reuse them, and a server that stores them becomes a target. The usual fix is to send the password over a TLS connection and let the server hash it. This works only if the server really is the server. A user who types the password into a fake site has given it away.

The Secure Remote Password protocol, SRP, takes another path. The password never crosses the network, not even in a hashed form. The two sides run a Diffie-Hellman style exchange in which the password decides whether they end up with the same key. If the password is wrong, they get different keys, and the login fails. The server stores only a verifier, a value that cannot be used to log in.

SRP is an example of a password-authenticated key exchange, or PAKE. This guide builds SRP-6 from RFC 5054, with the proofs and the session key of RFC 2945. It reproduces the test vector of RFC 5054 value by value. It also shows with real runs what an attacker can and cannot do, including an attack that works against a server that skips one required check. A newer design with a stronger guarantee is the subject of the OPAQUE guide. For the key exchange that SRP resembles, see the Diffie-Hellman guide.

Table of Contents

• History and Standards
• The Idea: a Verifier Instead of a Password
• The Mathematics of SRP-6
• The Session Key and the Proofs
• The Groups
• What an Attacker Can Do
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Where It Stands
• Limitations
• Security Status
• FAQ
• References

History and Standards

RFC 2945, published in September 2000 by Wu of Stanford University as a standards track document, describes the mechanism called SRP-SHA1. The RFC says that the protocol is sometimes called SRP-3. It places SRP among the non-disclosing authentication methods of RFC 1704, and it stresses two advantages. An eavesdropper who records a login cannot use the record to test guessed passwords. The server can store passwords in a form that is not directly useful to an attacker.

RFC 5054 appeared in November 2007 with the title “Using the Secure Remote Password (SRP) Protocol for TLS Authentication”. It is an informational document. It specifies SRP-6, which the RFC calls a slight improvement over SRP-3, and it adds new cipher suites to TLS. One of them is TLS_SRP_SHA_WITH_AES_128_CBC_SHA, with the code 0xC01D. The RFC also includes a table of group parameters and a test vector. Both are used in this guide.

The two documents divide the work. RFC 5054 gives the group parameters, the way to compute the verifier, k, u, B, and the shared secret. RFC 2945 gives the session key function and the two proofs that the parties exchange at the end. In RFC 5054, the finished messages of TLS take the place of those proofs.

The Idea: a Verifier Instead of a Password

Registration takes place once. The user picks a name I and a password P. A random salt s is drawn, and the user computes two values, the private key x and the verifier v:

x = SHA1(s | SHA1(I | ":" | P))        v = g^x mod N

The server stores the triple (I, s, v) and forgets the password. The number x is the private key of the user, derived from the password, and v is the matching public key. The group parameters N and g are public, with N a large prime.

At login, the client and the server run a Diffie-Hellman exchange in which the public key v takes part. The client picks a random a and sends A = g^a. The server picks a random b and sends the salt and B. Each side then computes a secret. The client uses the password it has just typed, and the server uses the stored verifier. The two secrets are equal only when the typed password is the registered one.

The Mathematics of SRP-6

The exchange has these steps, in the notation of RFC 5054.

1. The client sends the user name I and the value A = g^a mod N. The server must abort if A mod N = 0.
2. The server sends s and B = (k * v + g^b) mod N, where k = SHA1(N | PAD(g)). The client must abort if B mod N = 0.
3. Both compute the scrambler u from the two public values, as u = SHA1(PAD(A) | PAD(B)).
4. The client computes S = (B - k * g^x)^(a + u * x) mod N, using x from the password it typed.
5. The server computes the secret S from the verifier, as S = (A * v^u)^b mod N.

The function PAD writes an integer as bytes with the most significant byte first, and it adds zero bytes on the left until the string is as long as N. For a group of 1,024 bits that is 128 bytes.

Why do the two secrets agree? Use the relation v = g^x first. On the client side, B - k * g^x equals k * v + g^b - k * v, which is g^b. The secret of the client is then:

S = (g^b)^(a + u x) = g^(b a + b u x)

On the server side, A * v^u equals g^a * g^(x u), which is g^(a + u x). The secret of the server is then:

S = (g^(a + u x))^b = g^(b a + b u x)

The two values are the same. If the client used another password, its x would differ, B - k * g^x would no longer be g^b, and the secrets would be unrelated. This is the whole trick.

The roles of the new values are listed in RFC 5054. The scrambler u prevents an attacker who has learned a verifier from authenticating as that user. The multiplier k prevents an attacker who can choose the group parameters from running a 2-for-1 guessing attack, in which one session would test two passwords. The value x mixes the password with the salt.

The Session Key and the Proofs

The secret S is a large integer, and the parties need a key of a fixed size and a proof that they hold it. RFC 2945 supplies both.

The key is the value K = SHA_Interleave(S). Write S as bytes, drop leading zero bytes, and drop one more byte if the length is odd. Call the result T. The bytes at even positions form E, and the bytes at odd positions form F. Hash both with SHA-1, and interleave the two digests byte by byte. The result always has 40 bytes, two 20-byte digests woven together, with nothing truncated.

The proofs are the following two hashes:

M1 = H( H(N) xor H(g) | H(I) | s | A | B | K )        sent by the client
M2 = H( A | M1 | K )                                  sent by the server

The server computes M1 with its own key and compares. If the values differ, it must abort with an error before it sends M2, because answering could compromise the password. If they match, the server sends M2, and the client checks it in the same way. After this, each side knows that the other holds the same key, which means that the password was right.

RFC 2945 says that it does not fix the format of the messages, including the padding. My code writes A and B in M1 as plain integers without padding, and I wrote this choice into the code as a comment. This is the one place where I follow a convention and not a test vector. A library that pads A and B to the length of N computes a different M1 from the same login. That is why two independent SRP implementations can agree on K and still reject each other’s proofs.

The Groups

RFC 5054 lists seven groups, and a client should accept only groups from a trusted list such as this one. Every N is a safe prime, which means that N = 2q + 1 with q also prime. The generator g must generate the whole group.

Size of N	Bytes	Generator
1,024 bits	128	2
1,536 bits	192	2
2,048 bits	256	2
3,072 bits	384	5
4,096 bits	512	5
6,144 bits	768	5
8,192 bits	1,024	19

I checked these claims. The text of the RFC gives each prime in hexadecimal, and my script reads them from the text. For every group, both N and (N - 1) / 2 pass a Miller-Rabin test, and the generator has the full order N - 1. The 1,024-bit group is the one of the test vector. It is the smallest, and the RFC says that clients must make sure that N is large enough to make discrete logarithms infeasible. The RFC also warns about a prime of a special form that makes discrete logarithms easy, which is the reason to accept only known groups. A 1,024-bit group gives only about 80 bits of security by NIST’s estimates, so a new deployment should use the 2,048-bit group or a larger one.

What an Attacker Can Do

RFC 5054 lists the weak points of the protocol. My tests run each of them.

A passive observer. The observer sees A, B, the salt, and the proofs. Every one of these values depends on a secret exponent, either a or b. A guessed password gives a guessed x, but the observer cannot compute S without a or b, so there is nothing to compare the guess against. This is the advantage over a challenge-response scheme in which the transcript contains a hash of the password.

An active attacker who knows nothing. The attacker can contact the server and try one password for each attempt. The RFC says that servers should limit the rate of attempts for a user name and for an address. A failed attempt reveals only that one guess was wrong.

An attacker who skips the checks. The RFC calls the checks on A and B crucial. Suppose that the server accepts A = 0, or A = N. Then A * v^u is a multiple of N, so the server computes S = 0 whatever the verifier and b are. The attacker knows that S = 0, computes the same key and a valid M1, and logs in as the user without the password. In my test, a server without the check accepted both values, and a server with the check rejected both. The value A = 2N cannot be sent in the format of the protocol, because A must fit in as many bytes as N.

An attacker who steals the verifier. The RFC says that this attacker can masquerade as the real server to that user, and can attempt a dictionary attack to recover the password. My test shows the first part: with v, N, g, and s, the attacker builds B = k * v + g^b, and the client accepts it, because the secret is the same on both sides. The attacker cannot log in as the user without the password, because u prevents the use of v in place of x. For the second part, I ran a dictionary of 6-digit PINs against a verifier of a 1,024-bit group. The PIN 481074 was found after 13,003 guesses in 5.3 seconds, which is 2,434 guesses per second in plain Python. All 1,000,000 PINs would take about 411 seconds. The cost of a guess is one modular exponentiation with a 160-bit exponent and two hashes. This is why a verifier must be protected like a hash of a password, and why PAKE protocols that resist this attack are an active research topic.

Interactive Visualizer

The visualizer above runs the whole login with the real values. Choose the size of the group, enter the user name, the registered password, the password typed at the login, the salt, and the two secret exponents. The log shows each step: the verifier, A, k and B, u, the two secrets, the key K, and the two proofs.

• Right password. Both secrets agree, the server accepts M1, the client accepts M2, and the result is the 40-byte key.
• Wrong password. The two secrets differ, the server rejects M1, and the log stops there.
• The attack variant. It runs the attacker who sends A = 0 or A = N to a server that checks or does not check. You can see that S = 0 and that the server accepts.

The defaults are the test vector of RFC 5054, with the user alice and the password password123. The page uses its own SHA-1 and big-integer arithmetic.

A Worked Example

The test vector of RFC 5054 uses the 1,024-bit group, the user alice, the password password123, and the salt beb25379d1a8581eb5a727673a2441ee. Every value below matches the RFC.

Value	Result
k = SHA1(N | PAD(g))	7556aa045aef2cdd07abaf0f665c3e818913186f
x = SHA1(s | SHA1(I:P))	94b7555aabe9127cc58ccf4993db6cf84d16c124
v = g^x mod N, first bytes	7e273de8696ffc4f...
A = g^a mod N, first bytes	61d5e490f6f1b795...
B = k v + g^b mod N, first bytes	bd0c61512c692c0c...
u = SHA1(PAD(A) | PAD(B))	ce38b9593487da98554ed47d70a7ae5f462ef019
S of the client and of the server, first bytes	b0dc82babcf30674...

The RFC gives no values for K, M1, and M2, so these come from my code:

K  = 2b8cabcede81b9765a37fc68fbde512326a156512bc0dac5fd64d2c7c3bf857a56b0c0a8ceed18c0
M1 = 8b5fdb7db0346e353689d2edfacec647a813e6d0
M2 = e8149a44a9d5bf552a4cc9120c545301a537f227

If the client types password124 instead, its secret starts with 9cdc51416907c671 and no longer equals the secret of the server, so the proofs fail.

Python Implementation

This is SRP-6 with SHA-1. The groups are read from a file that a script produces from the text of RFC 5054. After the code comes the script, and then its output for the test vector.

# srp.py
# SRP-6 as in RFC 5054 (group parameters, x, v, k, B, u and the shared secret) with the proofs M1 and M2 and
# the interleaved session key of RFC 2945. SHA-1 is the hash, as in both RFCs.
# Teaching code. It is not constant time, and the random values must come from a secure source in real use.
import hashlib
import json
import os

_groups = json.load(open(os.path.join(os.path.dirname(__file__), "srp_groups.json")))
GROUPS = {int(bits): (int(n, 16), g) for bits, (n, g) in _groups.items()}


def sha1(*parts):
    h = hashlib.sha1()
    for part in parts:
        h.update(part)
    return h.digest()


def to_bytes(x):
    # most significant byte first, no leading zero byte (the implicit conversion of the RFCs)
    return x.to_bytes((x.bit_length() + 7) // 8, "big") if x else b""


def pad(x, n):
    # PAD(): the same conversion, left-padded with zero bytes to the length of N
    return x.to_bytes((n.bit_length() + 7) // 8, "big")


def from_bytes(b):
    return int.from_bytes(b, "big")


def multiplier(n, g):
    return from_bytes(sha1(to_bytes(n), pad(g, n)))                      # k = SHA1(N | PAD(g))


def private_key(salt, identity, password):
    inner = sha1(identity + b":" + password)
    return from_bytes(sha1(salt, inner))                                 # x = SHA1(s | SHA1(I | ":" | P))


def make_verifier(n, g, salt, identity, password):
    return pow(g, private_key(salt, identity, password), n)              # v = g^x mod N


def scramble(n, a_pub, b_pub):
    return from_bytes(sha1(pad(a_pub, n), pad(b_pub, n)))                # u = SHA1(PAD(A) | PAD(B))


def client_public(n, g, a):
    return pow(g, a, n)


def server_public(n, g, v, b):
    return (multiplier(n, g) * v + pow(g, b, n)) % n                     # B = k v + g^b mod N


def client_secret(n, g, salt, identity, password, a, b_pub):
    # S = (B - k g^x)^(a + u x) mod N; the client must stop if B mod N is 0
    if b_pub % n == 0:
        raise ValueError("B mod N is zero")
    a_pub = pow(g, a, n)
    u = scramble(n, a_pub, b_pub)
    x = private_key(salt, identity, password)
    return pow((b_pub - multiplier(n, g) * pow(g, x, n)) % n, a + u * x, n)


def server_secret(n, g, v, b, a_pub, check=True):
    # S = (A v^u)^b mod N; the server must stop if A mod N is 0
    if check and a_pub % n == 0:
        raise ValueError("A mod N is zero")
    b_pub = server_public(n, g, v, b)
    u = scramble(n, a_pub, b_pub)
    return pow(a_pub * pow(v, u, n) % n, b, n)


def interleave(secret):
    # SHA_Interleave of RFC 2945: a session key of 40 bytes
    t = to_bytes(secret)
    if len(t) % 2:
        t = t[1:]
    g, h = sha1(t[0::2]), sha1(t[1::2])
    return bytes(b for pair in zip(g, h) for b in pair)


def client_proof(n, g, identity, salt, a_pub, b_pub, key):
    # M1 = H(H(N) xor H(g) | H(I) | s | A | B | K)
    xor = bytes(p ^ q for p, q in zip(sha1(to_bytes(n)), sha1(to_bytes(g))))
    return sha1(xor, sha1(identity), salt, to_bytes(a_pub), to_bytes(b_pub), key)


def server_proof(a_pub, m1, key):
    return sha1(to_bytes(a_pub), m1, key)                                # M2 = H(A | M1 | K)


if __name__ == "__main__":
    # the values of the test vector in Appendix B of RFC 5054
    n, g = GROUPS[1024]
    identity, password = b"alice", b"password123"
    salt = bytes.fromhex("beb25379d1a8581eb5a727673a2441ee")
    a = 0x60975527035CF2AD1989806F0407210BC81EDC04E2762A56AFD529DDDA2D4393
    b = 0xE487CB59D31AC550471E81F00F6928E01DDA08E974A004F49E61F5D105284D20
    verifier = make_verifier(n, g, salt, identity, password)
    a_pub, b_pub = client_public(n, g, a), server_public(n, g, verifier, b)
    print("x =", "%x" % private_key(salt, identity, password))
    print("k =", "%x" % multiplier(n, g))
    print("u =", "%x" % scramble(n, a_pub, b_pub))
    secret_client = client_secret(n, g, salt, identity, password, a, b_pub)
    secret_server = server_secret(n, g, verifier, b, a_pub)
    print("S is the same on both sides:", secret_client == secret_server)
    print("S starts with", "%x" % (secret_client >> (1024 - 64)))
    key = interleave(secret_client)
    m1 = client_proof(n, g, identity, salt, a_pub, b_pub, key)
    m2 = server_proof(a_pub, m1, key)
    print("K =", key.hex())
    print("M1 =", m1.hex())
    print("M2 =", m2.hex())
    wrong = client_secret(n, g, salt, identity, b"password124", a, b_pub)
    print("a wrong password gives the same secret:", wrong == secret_server)
    try:
        server_secret(n, g, verifier, b, n)
    except ValueError as error:
        print("the server refuses A = N:", error)

# Reads the group parameters of Appendix A of RFC 5054 (the text file of the RFC) and writes srp_groups.json.
import json
import re
import sys

lines = open(sys.argv[1], encoding="utf-8").read().splitlines()
start = next(i for i, l in enumerate(lines) if l.startswith("Appendix A.  SRP Group Parameters"))
end = next(i for i, l in enumerate(lines) if l.startswith("Appendix B.  SRP Test Vectors"))
groups, bits, collecting, digits = {}, None, False, ""
for line in lines[start:end]:
    if line.startswith("Taylor, et al.") or line.startswith("RFC 5054"):
        continue
    m = re.match(r"\s+\d+\.\s+(\d+)-bit Group", line)
    if m:
        bits, digits, collecting = int(m.group(1)), "", False
        continue
    if "hexadecimal value for the prime is" in line or "Its hexadecimal value is" in line:
        collecting, digits = True, ""
        continue
    m = re.match(r"\s+The generator is: (\d+)", line)
    if m:
        groups[bits] = (digits, int(m.group(1)))
        collecting = False
        continue
    if collecting and re.fullmatch(r"\s*([0-9A-F]{8}\s*)+", line):
        digits += re.sub(r"\s", "", line)
assert sorted(groups) == [1024, 1536, 2048, 3072, 4096, 6144, 8192], sorted(groups)
for bits, (digits, g) in groups.items():
    assert len(digits) == bits // 4, (bits, len(digits))
json.dump({str(b): [d, g] for b, (d, g) in groups.items()}, open("srp_groups.json", "w"))
print({b: g for b, (d, g) in groups.items()})

Running the first file reproduces the test vector:

x = 94b7555aabe9127cc58ccf4993db6cf84d16c124
k = 7556aa045aef2cdd07abaf0f665c3e818913186f
u = ce38b9593487da98554ed47d70a7ae5f462ef019
S is the same on both sides: True
S starts with b0dc82babcf30674
K = 2b8cabcede81b9765a37fc68fbde512326a156512bc0dac5fd64d2c7c3bf857a56b0c0a8ceed18c0
M1 = 8b5fdb7db0346e353689d2edfacec647a813e6d0
M2 = e8149a44a9d5bf552a4cc9120c545301a537f227
a wrong password gives the same secret: False
the server refuses A = N: A mod N is zero

I checked the code against the RFC in several ways. The script that reads the test vector takes every value from the text of RFC 5054: the salt, k, x, v, a, b, A, B, u, and the premaster secret. My code reproduces all of them, for the client and for the server. The seven groups pass the primality tests described above, in 24 seconds.

The functions of RFC 2945 have no test vector. The function SHA_Interleave is checked by hand on small inputs: the bytes 01 02 03 04 give E = 01 03 and F = 02 04, an odd length drops the first byte, and leading zero bytes are ignored. The proofs M1 and M2 follow the formulas of the RFC, and I could not compare them with another implementation. I ran 30 random logins in groups of 1,024 to 4,096 bits. In each run, both sides computed the same secret and the same proofs, and a wrong password gave a different secret and a proof that the server rejects.

The page code has its own SHA-1, which matches OpenSSL for all input lengths from 0 to 300. It reproduces all 30 test vectors that the Python code produces, including wrong passwords and the attack variant. I ran its page in a simulated browser.

Where It Stands

• A published standard for TLS. RFC 5054 defines the use of SRP in TLS, as an informational document.
• Small footprint. The protocol needs one round trip and one modular exponentiation for each side, with no certificates.
• Superseded by newer designs. SRP gives a stored verifier that can be attacked with a dictionary after a breach. The OPAQUE guide covers a protocol that avoids this by hiding the salt behind an oblivious function.

Limitations

This is a teaching implementation, not a production one:

• Not constant time. The big-integer operations of Python depend on the values.
• SHA-1 only. RFC 5054 uses SHA-1 and notes that attacks on its collision resistance do not affect the three uses in SRP. If attacks on those uses appeared, new cipher suites would be needed.
• A fast hash for the password. The value x takes only two SHA-1 calls, and my dictionary test shows the effect. A real system should consider how a stolen verifier can be attacked.
• No rate limiting. The code does not count failed logins.
• No protection of the user name. The user name travels in the clear in the TLS extension of RFC 5054, and the RFC suggests a first connection to hide it.
• Random secrets. The functions take a and b as arguments. A real program must draw them from a secure source, with at least 256 bits.
• Unknown users. Section 2.5.1.3 of RFC 5054 describes how a server can hide that a user does not exist. It returns a stable fake salt from HMAC-SHA1(seed_key, "salt" | user_name) and a random B, ideally from a fake verifier so the timing matches. The code does not implement this.

Security Status

The protocol rests on the difficulty of the discrete logarithm in the chosen group and on properties of the hash function. The RFC states that the checks on A and B, the size of the secrets, and the choice of a trusted group are all required. If a client accepts a group chosen by an attacker, a special prime can make discrete logarithms easy and expose the password.

SRP does not hide the verifier problem. A breach of the server gives the attacker an offline attack on every user, and it lets the attacker impersonate the server to those users. The RFC also notes that a verifier can match several pairs of user name and password. My experiments show the speed of a dictionary attack against one verifier, and they show how a missing check destroys authentication.

FAQ

Is the password sent to the server?

The password never leaves the client. The server receives A, the proofs, and the user name. The password is used on the client only, to compute x.

What is the difference between SRP-3 and SRP-6?

RFC 5054 calls SRP-6 a slight improvement. It adds the multiplier k, so B is k * v + g^b and not v + g^b, and it computes u from A and B. The RFC says that k prevents a 2-for-1 guessing attack by an attacker who chooses the group, and that u prevents an attacker with the verifier from authenticating as the user.

Why does the server need a salt?

The salt makes the verifiers of two users with the same password different, and it prevents the use of tables prepared in advance. It is public, and the server sends it at the beginning of every login.

Can an eavesdropper guess the password offline?

Not from the transcript of a login. The values in it depend on the secret exponents. An attacker who has the verifier from the server can guess offline, as my experiment shows.

Why is SRP not used everywhere?

I did not study the adoption of SRP in practice, and I cannot answer from the sources I read. The design points are clear from the RFCs: the stored verifier can be attacked after a breach, the salt is sent to anyone who asks, and the exchange needs large-integer arithmetic.

What does the check on A protect?

It stops an attacker from forcing the secret to 0. Without it, a login without the password succeeds. The check is cheap, and the RFC calls it crucial.

References

1. RFC 2945, “The SRP Authentication and Key Exchange System,” by Wu, September 2000. Available at: https://www.rfc-editor.org/rfc/rfc2945

2. RFC 5054, “Using the Secure Remote Password (SRP) Protocol for TLS Authentication,” by Taylor, Wu, Mavrogiannopoulos, and Perrin, November 2007. Available at: https://www.rfc-editor.org/rfc/rfc5054

3. RFC 1704, “On Internet Authentication,” by Haller and Atkinson, October 1994.

4. Wu, Thomas. “SRP-6: Improvements and Refinements to the Secure Remote Password Protocol,” submission to the IEEE P1363.2 working group, October 2002. RFC 5054 cites it as its source for SRP-6 and for the roles of k and u.