Secure Remote Password protocol

From HandWiki
Short description: Augmented password-authenticated key exchange protocol

The Secure Remote Password protocol (SRP) is an augmented password-authenticated key exchange (PAKE) protocol, specifically designed to work around existing patents.[1]

Like all PAKE protocols, an eavesdropper or man in the middle cannot obtain enough information to be able to brute-force guess a password or apply a dictionary attack without further interactions with the parties for each guess. Furthermore, being an augmented PAKE protocol, the server does not store password-equivalent data.[2] This means that an attacker who steals the server data cannot masquerade as the client unless they first perform a brute force search for the password.

In layman's terms, during SRP (or any other PAKE protocol) authentication, one party (the "client" or "user") demonstrates to another party (the "server") that they know the password, without sending the password itself nor any other information from which the password can be derived. The password never leaves the client and is unknown to the server.

Furthermore, the server also needs to know about the password (but not the password itself) in order to instigate the secure connection. This means that the server also authenticates itself to the client which prevents phishing without reliance on the user parsing complex URLs.

The only mathematically proven security property of SRP is that it is equivalent to Diffie-Hellman against a passive attacker.[3] Newer PAKEs such as AuCPace[4] and OPAQUE offer stronger guarantees.[5]

Overview

The SRP protocol has a number of desirable properties: it allows a user to authenticate themselves to a server, it is resistant to dictionary attacks mounted by an eavesdropper, and it does not require a trusted third party. It effectively conveys a zero-knowledge password proof from the user to the server. In revision 6 of the protocol only one password can be guessed per connection attempt. One of the interesting properties of the protocol is that even if one or two of the cryptographic primitives it uses are attacked, it is still secure. The SRP protocol has been revised several times, and is currently at revision 6a.

The SRP protocol creates a large private key shared between the two parties in a manner similar to Diffie–Hellman key exchange based on the client side having the user password and the server side having a cryptographic verifier derived from the password. The shared public key is derived from two random numbers, one generated by the client, and the other generated by the server, which are unique to the login attempt. In cases where encrypted communications as well as authentication are required, the SRP protocol is more secure than the alternative SSH protocol and faster than using Diffie–Hellman key exchange with signed messages. It is also independent of third parties, unlike Kerberos.

The SRP protocol, version 3 is described in RFC 2945. SRP version 6a is also used for strong password authentication in SSL/TLS[6] (in TLS-SRP) and other standards such as EAP[7] and SAML, and is part of IEEE 1363.2 and ISO/IEC 11770-4.

Protocol

The following notation is used in this description of the protocol, version 6:

  • q and N = 2q + 1 are chosen such that both are prime (which makes q a Sophie Germain prime and N a safe prime). N must be large enough so that computing discrete logarithms modulo N is infeasible.
  • All arithmetic is performed in the ring of integers modulo N, [math]\displaystyle{ \scriptstyle \mathbb{Z}_N }[/math]. This means that below gx should be read as gxmod N
  • g is a generator of the multiplicative group [math]\displaystyle{ \scriptstyle \mathbb{Z} N^* }[/math].
  • H() is a hash function; e.g., SHA-256.
  • k is a parameter derived by both sides; in SRP-6, k = 3, while in SRP-6a it is derived from N and g : k = H(N, g). It is used to prevent a 2-for-1 guess when an active attacker impersonates the server.[8][9]
  • s is a salt.
  • I is an identifying username.
  • p is the user's password.
  • v is the host's password verifier, v = gx where at a minimum x = H(s, p). As x is only computed on the client it is free to choose a stronger algorithm. An implementation could choose to use x = H(s | I | p) without affecting any steps required of the host. The standard RFC2945 defines x = H(s | H ( I | ":" | p) ). Use of I within x avoids a malicious server from being able to learn if two users share the same password.
  • A and B are random one time ephemeral keys of the user and host respectively.
  • | (pipe) denotes concatenation.

All other variables are defined in terms of these.

First, to establish a password p with server Steve, client Carol picks a random salt s, and computes x = H(s, p), v = gx. Steve stores v and s, indexed by I, as Carol's password verifier and salt. Carol must not share x with anybody, and must safely erase it at this step, because it is equivalent to the plaintext password p. This step is completed before the system is used as part of the user registration with Steve. Note that the salt s is shared and exchanged to negotiate a session key later so the value could be chosen by either side but is done by Carol so that she can register I, s and v in a single registration request. The transmission and authentication of the registration request is not covered in SRP.

Then to perform a proof of password at a later date the following exchange protocol occurs:

  1. Carol → Steve: generate random value a; send I and A = ga
  2. Steve → Carol: generate random value b; send s and B = kv + gb
  3. Both: u = H(A, B)
  4. Carol: SCarol = (Bkgx)(a + ux) = (kv + gbkgx)(a + ux) = (kgxkgx + gb)(a + ux) = (gb)(a + ux)
  5. Carol: KCarol = H(SCarol)
  6. Steve: SSteve = (Avu)b = (gavu)b = [ga(gx)u]b = (ga + ux)b = (gb)(a + ux)
  7. Steve: KSteve = H(SSteve) = KCarol

Now the two parties have a shared, strong session key K. To complete authentication, they need to prove to each other that their keys match. One possible way is as follows:

  1. Carol → Steve: M1 = H[H(N) XOR H(g) | H(I) | s | A | B | KCarol]. Steve verifies M1.
  2. Steve → Carol: M2 = H(A | M1 | KSteve). Carol verifies M2.

This method requires guessing more of the shared state to be successful in impersonation than just the key. While most of the additional state is public, private information could safely be added to the inputs to the hash function, like the server private key.[clarification needed]

Alternatively, in a password-only proof the calculation of K can be skipped and the shared S proven with:

  1. Carol → Steve: M1 = H(A | B | SCarol). Steve verifies M1.
  2. Steve → Carol: M2 = H(A | M1 | SSteve). Carol verifies M2.

When using SRP to negotiate a shared key K which will be immediately used after the negotiation, it is tempting to skip the verification steps of M1 and M2. The server will reject the very first request from the client which it cannot decrypt. This can however be dangerous as demonstrated in the Implementation Pitfalls section below.

The two parties also employ the following safeguards:

  1. Carol will abort if she receives B = 0 (mod N) or u = 0.
  2. Steve will abort if he receives A (mod N) = 0.
  3. Carol must show her proof of K (or S) first. If Steve detects that Carol's proof is incorrect, he must abort without showing his own proof of K (or S)

Example code in Python

"""
An example SRP authentication

WARNING: Do not use for real cryptographic purposes beyond testing.
WARNING: This below code misses important safeguards. It does not check A, B, and U are not zero.

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

# Note: str converts as is, str([1,2,3,4]) will convert to "[1,2,3,4]"
def H(*args) -> int:
    """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: int = 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)

F = '#0x' # Format specifier

print("#. H, N, g, and k are known beforehand to both client and server:")
print(f'{H = }\n{N = :{F}}\n{g = :{F}}\n{k = :{F}}')

print("\n0. 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

print(f'{I = }\n{p = }\n{s = :{F}}\n{x = :{F}}\n{v = :{F}}')

# 0. server stores(I, s, v) in its password database
# I = 'person'
# p = 'password1234'
# s = 0x67bc8932cfd26a49
# x = 0x98a4bce8dde877762a90222f1a1161eba9248590a47eb83aa9e5bd7ecda5368d
# v = 0xa7e2038e675d577ac0f318999cab67bba7ec2daf45d2d09f7911b1b78d2fc7f963cd0ac8f17851e0516f059e453672c3b70fcecf5f6843180b271abdd01f552ccda7b24fe4719336409cbc1352f8517be651b8935cc0b74ff2819fa07a3f031537d4cfd9f8df7b788a5f2f88e1cd4106b35c38b3d7205a

# <demo> --- stop ---

print("\n1. client sends username I and public ephemeral value A to the server")
a = cryptrand()
A = pow(g, a, N)
print(f"{I = }\n{A = :{F}}")  # client->server (I, A)

# 1. client sends username I and public ephemeral value A to the server
# I = 'person'
# A = 0x678556a7e76581e051af656e8cee57ae46df43f1fce790f7750a3ec5308a85da4ec4051e5cb74d3e463685ee975a2747cf49035be67c931b56e793f23ea3524af8909dcfbc8675d872361025bf884778587ac49454a57c53a011ac2be2839bfb51bf7847a49a483aba870dc7a8b467a81cec91b8ae7813

# <demo> --- stop ---

print("\n2. server sends user's salt s and public ephemeral value B to client")
b = cryptrand()
B = (k * v + pow(g, b, N)) % N
print(f"{s = :{F}}\n{B = :{F}}")  # server->client (s, B)

# 2. server sends user's salt s and public ephemeral value B to client
# s = 0x67bc8932cfd26a49
# B = 0xb615a0a5ea6abf138077bbd869f6a8da37dfc0b7e06a9f5fac5c1e4109c6302cb3e94dcc2cc76da7b3d87d7e9b68a1db998ab239cfde609f3f7a1ece4a491ce3d9a665c20cf4e4f06730daaa8f52ed61e45bbb67cdc337bf648027ffa7f0f215d5ebe43f9f51832518f1142266aae0dfa960e0082b5154


# <demo> --- stop ---

print("\n3. client and server calculate the random scrambling parameter")
u = H(A, B)  # Random scrambling parameter
print(f"{u = :{F}}")

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

# <demo> --- stop ---

print("\n4. 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)
print(f"{S_c = :{F}}\n{K_c = :{F}}")

# 4. client computes session key
# S_c = 0x699170aff6e9f08ed09a1dff432bf0605b8bcba05aadcaeea665757d06dbda4348e211d16c10ef4678585bcb2809a83c62b6c19d97901274ddafd4075f90604c06baf036af587af8540342b47867eaa22b9ca5e35ac14c8e85a0c4e623bd855828dffd513cea4d829c407137a0dd81ab4cde8a904c45cc
# K_c = 0x43f8df6e1d2ba762948c8316db5bf03a7af49391742f5f51029630711c1671e

# <demo> --- stop ---

print("\n5. server computes session key")
S_s = pow(A * pow(v, u, N), b, N)
K_s = H(S_s)
print(f"{S_s = :{F}}\n{K_s = :{F}}")

# 5. server computes session key
# S_s = 0x699170aff6e9f08ed09a1dff432bf0605b8bcba05aadcaeea665757d06dbda4348e211d16c10ef4678585bcb2809a83c62b6c19d97901274ddafd4075f90604c06baf036af587af8540342b47867eaa22b9ca5e35ac14c8e85a0c4e623bd855828dffd513cea4d829c407137a0dd81ab4cde8a904c45cc
# K_s = 0x43f8df6e1d2ba762948c8316db5bf03a7af49391742f5f51029630711c1671e

# <demo> --- stop ---

print("\n6. client sends proof of session key to server")
M_c = H(H(N) ^ H(g), H(I), s, A, B, K_c)
print(f"{M_c = :{F}}")
# client->server (M_c) ; server verifies M_c

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

# <demo> --- stop ---

print("\n7. server sends proof of session key to client")
M_s = H(A, M_c, K_s)
print(f"{M_s = :{F}}")
# server->client (M_s) ;  client verifies M_s

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


Implementation pitfalls

Offline bruteforce attack with server-first messaging in the absence of key verification

If the server sends an encrypted message without waiting for verification from the client then an attacker is able to mount an offline bruteforce attack similar to hash cracking. This can happen if the server sends an encrypted message in the second packet alongside the salt and B or if key verification is skipped and the server (rather than the client) sends the first encrypted message. This is tempting as after the very first packet, the server has every information to compute the shared key K.

The attack goes as follow:

  1. Carol → Steve: generate random value a; send I and A = ga
  2. Steve: u = H(A, B); S=Avu; K=H(S)
  3. Steve: generate message m and encrypts it to produce c=ENC(K,m)
  4. Steve → Carol: generate random value b; send s, B = kv + gb and c

Carol doesn't know x or v. But given any password p she can compute:

  • xp = H(salt, p)
  • Sp = (B - kgxp)(a + uxp)
  • Kp = H(Sp)

Kp is the key that Steve would use if p was the expected password. All values required to compute Kp are either controlled by Carol or known from the first packet from Steve. Carol can now try to guess the password, generate the corresponding key, and attempt to decrypt Steve's encrypted message c to verify the key. As protocol messages tend to be structured, it is assumed that identifying that c was properly decrypted is easy. This allows offline recovery of the password.

This attack would not be possible had Steve waited for Carol to prove she was able to computer the correct key before sending an encrypted message. Proper implementations of SRP are not affected by this attack as the attacker would be unable to pass the key verification step.

Offline bruteforce based on timing attack

In 2021 Daniel De Almeida Braga, Pierre-Alain Fouque and Mohamed Sabt published PARASITE,[10] a paper in which they demonstrate practical exploitation of a timing attack over the network. This exploits non-constant implementations of modular exponentiation of big numbers and impacted OpenSSL in particular.

Implementations

History

The SRP project was started in 1997.[11] Two different approaches to fixing a security hole in SRP-1 resulted in SRP-2 and SRP-3.[12] SRP-3 was first published in 1998 in a conference.[13] RFC 2945, which describes SRP-3 with SHA1, was published in 2000.[14] SRP-6, which fixes "two-for-one" guessing and messaging ordering attacks, was published in 2002.[8] SRP-6a appeared in the official "libsrp" in version 2.1.0, dated 2005.[15] SRP-6a is found in standards as:

  • ISO/IEC 11770-4:2006 "Key Agreement Mechanism 2" (calls the method "SRP-6, but has the k calculation of 6a)
  • RFC 5054 TLS-SRP of 2007 (again referred to as "SRP-6", but corrected in erratum[16])
  • IEEE Std 1363.2-2008 "DLAPKAS-SRP6" (again referred to as "SRP-6")[17]

IEEE 1363.2 also includes a description of "SRP5", a variant replacing the discrete logarithm with an elliptic curve contributed by Yongge Wang in 2001.[18] It also describes SRP-3 as found in RFC 2945.

See also

References

  1. "What is SRP?". Stanford University. http://srp.stanford.edu/whatisit.html. 
  2. Sherman, Alan T.; Lanus, Erin; Liskov, Moses; Zieglar, Edward; Chang, Richard; Golaszewski, Enis; Wnuk-Fink, Ryan; Bonyadi, Cyrus J. et al. (2020), Nigam, Vivek; Ban Kirigin, Tajana; Talcott, Carolyn et al., eds., "Formal Methods Analysis of the Secure Remote Password Protocol" (in en), Logic, Language, and Security: Essays Dedicated to Andre Scedrov on the Occasion of His 65th Birthday, Lecture Notes in Computer Science (Cham: Springer International Publishing): pp. 103–126, doi:10.1007/978-3-030-62077-6_9, ISBN 978-3-030-62077-6 
  3. Green, Matthew (18 October 2018). "Should you use SRP?" (in en). https://blog.cryptographyengineering.com/should-you-use-srp/.  NB: source refers to SRP-6 as SRPv4 for reason unknown.
  4. Haase, Björn (22 January 2023). "(strong) AuCPace, an augmented PAKE [draft-haase-aucpace-07"]. Internet Engineering Task Force. https://datatracker.ietf.org/doc/html/draft-haase-aucpace-07. 
  5. Stanislaw Jarecki; Hugo Krawczyk; Jiayu Xu. "OPAQUE: An Asymmetric PAKE Protoco lSecure Against Pre-Computation Attacks". Eurocrypt 2018. https://eprint.iacr.org/2018/163.pdf. 
  6. Taylor, David; Tom Wu (November 2007). "Using the Secure Remote Password (SRP) Protocol for TLS Authentication". http://tools.ietf.org/html/rfc5054.  RFC 5054
  7. Carlson, James; Bernard Aboba (July 2001). "EAP SRP-SHA1 Authentication Protocol". IETF. http://tools.ietf.org/html/draft-ietf-pppext-eap-srp-03.  Draft.
  8. 8.0 8.1 Template:Cite tech report
  9. "SRP Protocol Design". http://srp.stanford.edu/design.html. 
  10. "PARASITE: PAssword Recovery Attack against Srp Implementations in ThE wild". https://dl.acm.org/doi/10.1145/3460120.3484563. 
  11. "SRP: About the Project". http://srp.stanford.edu/project.html. 
  12. "SRP-2: Design Specifications". http://srp.stanford.edu/design2.html. 
  13. Wu, T., "The Secure Remote Password Protocol", Proceedings of the 1998 Internet Society Network and Distributed System Security Symposium pp. 97-111, March 1998.
  14. "SRP: Design Specifications". http://srp.stanford.edu/design3.html. 
  15. CHANGES file in srp-2.1.2.tar.gz, available from http://srp.stanford.edu/download.html
  16. Wang, Mingye. "RFC Errata Report #7538". https://www.rfc-editor.org/errata/eid7538. 
  17. IEEE 1363.2-2008: IEEE Standard Specification for Password-Based Public-Key Cryptographic Techniques
  18. Wang, Y., "IEEE P1363.2 Submission / D2001-06-21," [P1363.2-ecsrp-06-21.doc] A contribution by Yongge Wang for P1363.2 giving an elliptic curve version of the SRP protocol, June 21, 2001.

External links

  • SRP License—BSD like open source.
  • US6539479 - SRP Patent (Expired on May 12, 2015 due to failure to pay maintenance fees (according to Google Patents). Originally set to expire in July 2018).

Manual pages

RFCs

  • RFC 2944 - Telnet Authentication: SRP
  • RFC 2945 - The SRP Authentication and Key Exchange System (version 3)
  • RFC 3720 - Internet Small Computer Systems Interface (iSCSI)
  • RFC 3723 - Securing Block Storage Protocols over IP
  • RFC 3669 - Guidelines for Working Groups on Intellectual Property Issues
  • RFC 5054 - Using the Secure Remote Password (SRP) Protocol for TLS Authentication

Other links