SRP is Now Deprecated

by Steve on October 8th, 2021

Firstly I'm not able to declare the deprecation of SRP, but you should consider all versions of SRP to be deprecated.

Background Information

SRP is a password authenticated key exchanges (PAKE), and the current version is SRP6a. Like PAKE sounds, it's a key exchange that is authenticated by a password. Just think of it as Diffie-Hellman (DH) that is somehow protected with a password. Neither a passive attacker (sniffer) or an active one (MITM) can attack a PAKE to gain any knowledge besides whether the password was correct or incorrect.

There are balanced PAKEs and augmented PAKEs (aPAKE). A balanced PAKE is for peer-to-peer cases where everyone knows the password and no data is stored (please disregard what WiFi does they picked a known to be broken balanced PAKE instead of an augmented PAKE). An augmented PAKE, sometimes called an unbalanced PAKE, is for the more common client-server cases, where only the client knows the password; the server stores something like a password hash that can be used to verify password guesses and prove they have this data. If the server's data is stolen, an attacker can masquerade as the server but not as a client to the server. Equally importantly, only after stealing this server data can an attacker make offline password guesses.

PAKEs utilize public key cryptography. This can be multiplicative groups, elliptic curve cryptography (ECC), or post quantum (PQ). Multiplicative groups are simple math formulas modulo a safe prime and all the hard work is done by "power modulo". The primitives come for free in big int libraries (although they're rarely constant time, but don't worry about that now). ECC is also done modulo a prime, but the formulas are more complicated and harder to implement. There are a few methods for PQ but I'm going to ignore these as they are large, slow, complicated, and new.

The thing that makes multiplicative groups and ECC safe is the (elliptic curve) discrete logarithm problem (DLP or ECDLP) is hard for classical computers. Quantum computers can solve these and I've seen time estimates from seconds to a month for common sizes. It takes longer for larger sizes, O(n^3) for bit length for factoring RSA and ECDLP (page 26 has a nice table). The more DLPs an attacker needs to solve to break a PAKE, the more it is resistant to quantum computers.

The main key exchanges used in PAKEs are standard DH, Noise-KN, and "other". Standard DH is used in balanced PAKEs. Noise-KN is used in aPAKEs. "Other" key exchanges are more complicated and usually in aPAKEs. Noise-KN is similar to 3DH ("Triple Diffie Hellman") but with only one identity public key. 3DH is what Signal used before switching to X3DH, which has better properties for non-interactive key exchanges.

An oblivious pseudorandom function (oblivious PRF or OPRF) is a way to combine secrets without revealing either secret. It works like DH, but without revealing the public keys. An OPRF protects the salt by combining and obscuring the password (the client's secret) and the salt (the server's secret). The password is hashed into a public key, the client blinds it, the server applies the salt, and the client unblinds it. As a result, the salt applied to the password.

Protecting the salt with an OPRF prevents an important precomputation attack. Assume an attacker knows once they breach the server, there is a limited amount of time before passwords are changed. The attacker makes a bunch of guesses to the password, runs them through the password KDF, stores the results, and once they obtain the server data they can very quickly check if any of those guesses were correct. This shortens the window a user needs to change their password after a breach from weeks to instantly.

Key stretching is applying work to a low entropy secret, such as a password, to increase its strength. When one says "password hash" or "password key derivation function (KDF)" this implies that it is doing key stretching. Similarly, saying "hash" or "KDF" implies that it is not doing key stretching.

Good libraries are misuse resistant. This means the functions that a programmer can call will try to prevent them from messing up. Older APIs would ask for salts, IVs, and nonces. Newer APIs don't and instead use a cryptographic random source. Also algorithms can be misuse resistant. Such as with a PAKE if you send a message before you're suppose to, it doesn't break. If the algorithm isn't misuse resistant, this can be prevented with a misuse resistant library.

Blog Starts at Here

SRP6a is very popular because it's only defined on multiplicative groups. If you have big ints in your language or a library, then you can follow the short formulas and implement it. It's just a few additions, multiplications, and exponentiations (which is just more multiplication or "power modulo") modulo a safe prime. What if I told you there's a better, simpler, and older augmented PAKE (aPAKE) than SRP6a? You might be thinking, "why isn't that in use everywhere?" The algorithm was patented, but the good news is that the patent expired March 2017. So it's fair game.

The original algorithm is called SPEKE. There are a few flavors of SPEKE. There's balanced and augmented and with and without an OPRF, but more on these later. SPEKE-based PAKEs are better than SRP6a because they are misuse resistant. With SRP6a, if the server sends their verifier first (or sends encrypted data without first verifying the client), then anyone can connect to the server and receive data necessary to make offline password guesses. A lot of SRP6a implementations don't prevent this misuse.

The basic idea of a PAKE is to hide something. The three main things one can hide are the ephemeral public key[s] (like SRP6a), the generator, and/or (for aPAKEs) the salt. The idea behind SPEKE is "hiding the generator". If you know how Diffie-Hellman (DH) works, then you know how SPEKE works. The generator is a hash of the password, squared modulo the prime. Now SPEKE just does DH with that generator. An augmented version uses Noise-KN and the identity private key is a hash of the password (ie sqrtGenerator || identityPrivateKey = passwordKdf(password, salt, settings)). The server received the identity public key and generator during registration which is then kept secret.

(There's an older augmented version of SPEKE, B-SPEKE. It's a little different because Noise-KN hadn't been invented. It's suboptimal and not worth diving into.)

SPEKE also has a property called "Quantum Annoyance", where an attacker needs to solve a DLP for every password guess. PAKEs without this property require solving one or two DLPs then can make password guesses. The augmented SPEKEs have a slightly stronger version of Quantum Annoyance: an attacker needs to first observe a successful exchange before they can use a quantum computer (which might never exist).

Which flavor of SPEKE should you use: SPEKE, B-SPEKE, modified B-SPEKE, BS-SPEKE, CPace, AuCPace, and (strong) AuCPace? SPEKE and CPace are balanced PAKEs and the rest are aPAKEs. The two good ones are CPace for a balanced PAKE and BS-SPEKE for an aPAKE. CPace is better than SPEKE because CPace is salted. You should favor modified B-SPEKE or BS-SPEKE over AuCPace and (strong) AuCPace because the B-SPEKEs are simpler. AuCPace has a proof but does extra work because it's double salted. The B-SPEKEs are "easy" to prove since it's Noise-KN (which is secure) and the attacker doesn't know the generator (which means they can't do anything). The hard part is stating that in a proof when you don't know how proofs "work".

NameAugmentedSaltedKey ExchangeOPRFSecurity Proof
CPaceNoYesStandard DHN/AYes
modified B-SPEKEYesYesNoise-KNNoNo
(strong) AuCPaceYesTwiceOtherYesYes

While I knew that SRP6a can only use multiplicative groups and other PAKEs can use both multiplicative groups and elliptic curves. Thus those should use elliptic curves because they are better and faster. It just never occurred to me that only defining them with elliptic curves and not giving the option for multiplicative groups might be a barrier of entry. Thus people going with SRP6a. So here's simplified multiplicative groups descriptions for CPace and Modified B-SPEKE:

CPace (simplified version of this)

my Salt = random()

Swap salts

sqrt Generator = H(password, sort(my Salt, others Salt))
g = sqrt Generator ^ 2 (mod P)
my Private Key = random()
my Public Key = g ^ my Private Key (mod P)

Swap public keys

X = others Public Key ^ my Private Key (mod P)
key = H(X)
Note H() is just a fast cryptographic hash or KDF including the one for the password. You do not need to do key stretching on the password because there is nothing being stored and the exchange is cryptographically secure.

Modified B-SPEKE (simplified version of this)

Server has: g, salt, settings, and V = g ^ identity Private Key (mod P)
Client is sent: salt, settings

sqrt Generator || identity Private Key = password Kdf(password, salt, settings)
g = sqrt Generator ^ 2 (mod P)

my Private Key = random()
my Public Key = g ^ my Private Key (mod P)

Swap public keys

X = others Public Key ^ my Private Key (mod P)

Client: Y = others Public Key ^ identity Private Key (mod P)
Server: Y = V ^ my Private Key (mod P)
Both: key = H(X, Y)
Note to make this into BS-SPEKE instead of sending the salt you do an OPRF like:
r = random Range(1, (P-3)/2)
p = H(password) ^ 2 (mod P)
R = p ^ r (mod P)

Send R to server

R' = R ^ H(salt) (mod P)

Send R' to client

1/r = r ^ ((P-5)/2) (mod (P-1)/2)
Blind Salt = R' ^ (1/r) (mod P)
sqrt Generator || identity Private Key = password Kdf(password, Blind Salt, settings)