SRP (Secure Remote Passwords) weakness
Bodo Moeller
(Secure Remote Passwords) that I found recently while looking at
protocols for password-based authenticated key exchange. (I have
reported this, and appropriate fixes have now been implemented -- see
version 2.1.1 of the SRP distribution at http://srp.stanford.edu/ .)
First, a brief description of what "password-based authenticated key
exchange" is all about.
"Key exchange" means something like Diffie-Hellman, i.e. two parties
(typically a client and a server) perform some cryptographic magic to
arrive at a common secret bitstring. We want this key exchange to be
"authenticated" so that the infamous Man In The Middle cannot sneak
in. But for authentication, we do not want to rely on pre-arranged
public keys or on certificates -- instead, we want this to be
"password-based" so that a user can use appropriate client software to
authenticate to a server, reyling just on a password.
A naive approach would be to start with standard Diffie-Hellman and
authenticate afterwards, employing the password in the authentication
step (e.g. send a hash of the common secret bitstring concatenated
with the password). This is not good enough, however, because it
allows for "offline attacks": An attacker that interacts with the
client or server just a single time can use the transcript from this
one protocol run to perform a brute-force search for the password,
without performing further interaction with one of the legitimate
parties. Instead, we want to limit attackers to "online attacks"
where verifying each single password guess requires a new protocol
run. Then, if the password space is within the range of brute-force
searches, the key exchange can still be reasonably secure if the
number of protocol runs that an attacker can perform with one of the
legitimite parties is limited.
The original idea for how to do this was Bellovin and Merrit's
"Encrypted Key Exchange" (EKE). Here the approach is that the
password is used as a symmetric key for encrypting the public values
that would be sent in clear during a "normal" key exchange such as
Diffie-Hellman. An attacker who participates in a protocol run with a
legitimate party should not be able to derive useful information from
the protocol transcript unless it has employed the correct password
when creating its encrypted key exchange messages; additional password
guesses made after the fact don't help. (This is just a brief sketch
of EKE -- it takes some care to actually get the protocol right.)
SRP (see, e.g., RFC 2945) is a specific protocol for password-based
authenticated key exchange, designed to achieve various nice
properties. The protocol uses parameters 'N' (a so-called safe prime,
i.e. a prime such that (N-1)/2 is prime as well) and 'g' (a primitive
element modulo N, i.e. a generator of the group of integers modulo N).
A protocol run proceeds as follows (this is copied from the RFC):
Client Host
-------- ------
U = <username> -->
<-- s = <salt from passwd file>
Upon identifying himself to the host, the client will receive the
salt stored on the host under his username.
a = random()
A = g^a % N -->
v = <stored password verifier>
b = random()
<-- B = (v + g^b) % N
p = <raw password>
x = SHA(s | SHA(U | ":" | p))
S = (B - g^x) ^ (a + u * x) % N S = (A * v^u) ^ b % N
K = SHA_Interleave(S) K = SHA_Interleave(S)
The "password verifier" v is defined as g^x % N. SHA_Interleave(),
as the name suggests, is a specific hashing construction based on SHA
(in all cases, "SHA" means SHA-1).
If all goes well so far in the protocol, the client and the server
(= host) will have computed the same value K, which can later be used
as a key for symmetric cryptography. But first, the client sends an
"evidence message" to the server so that the server can verify that it
is indeed interoperating with the legitimate client -- otherwise,
using 'K' as a key for symmetric cryptography might provide an active
attacker with the information needed for an offline attack. The
evidence message is a hash of various values:
M = H(H(N) XOR H(g) | H(U) | s | A | B | K)
-->
A crucial question to ask is: From where does the client obtain the
prime N and the generator g? The SRP specification provides some
recommended parameters for use. But while it is not shown in the
above protocol flow overview, SRP lets the server send the parameters
N and g to the client. The client can verify them, possibly reject to
interoperate in the protocol if it does not like them, or use them in
the SRP protocol flow.
One way to verify SRP parameters is simply to accept only those that
appear in the specification (as recommended parameters). Another way
is to perform certain checks on them, and this is what the SRP
distribution tried to do up to version 2.1.0: Parameters are deemed
acceptable if
- N is at least around 512 bits long and
- N is prime and
- (N-1)/2 is prime and
- g is a primitve element modulo N.
[Actually there was a bug somewhere in the SRP distribution affecting
the latter test, but this is not what this article is about.]
These conditions are requirements for parameters that are useful for
SRP. However, they are not sufficient to make the protocol secure!
Not all safe primes are created equal -- a malicious server might
compel the client into performing the SRP protocol where N is a
"trapdoor prime", a prime that has been specifically chosen to make
the computation of discrete logarithms feasible (see Daniel M. Gordon,
"Designing and Detecting Trapdoors for Discrete Log Cryptosystems",
CRYPTO '92, Springer-Verlag LNCS 740). The protocol will start as
usual when an unsuspecting client connects to this server:
Client Malicious Server
-------- ------------------
U = <username> -->
<-- s = <salt>
The malicious server can easily obtain the salt value s by connecting
to the legitimate server, claiming to be user U.
a = random()
A = g^a % N -->
In the normal protocol, the server now would have to employ the
password verifier v. The malicious server does not know v (otherwise
it could go straight ahead and perform an offline attack). So it just
makes up a random B for the protocol message that the legitimate
server would have to compute from v and a random value b:
<-- B = random() % N
p = <raw password>
x = SHA(s | SHA(U | ":" | p))
S = (B - g^x) ^ (a + u * x) % N
K = SHA_Interleave(S)
M = H(H(N) XOR H(g) | H(U) | s | A | B | K)
-->
Having chosen N to be a trapdoor prime, the malicious server can
compute the exponent 'a' from the transmitted value 'A'. Once it
knows 'a', it can try any conceivable password and see if the
client evidence message 'M' matches the guess -- i.e., it can
launch an offline attack, defeating the intention behind the SRP
protocol.
This weakness would be far from trivial to exploit, but it is a flaw.
A few days ago I noticed that the description of a related problem
appears in Daniel Bleichenbacher, "Breaking a Cryptographic Protocol
with Pseudoprimes", PKCS 2005, Springer-Verlag LNCS 3386:
Bleichenbacher has observed that the SRP implementation in
GNU Crypto 1.1.0 validates parameter 'N' using an inappropriate
primality test (Rabin-Miller using fixed bases where it should use
random bases instead). In that case, the attacker does not have to
create a trapdoor prime N; instead, the paper shows how a cleverly
constructed pseudoprime (a composite number that passes the GNU Crypto
primality test) allows performing a similar attack.
The recommendation of that paper is to fix the primality test.
However, this of course does not avoid the attack based on trapdoor
primes. The proper fix is to allow just a certain fixed
(standardized) set of parameters.
I can't see why we would we even want to let server choose the
parameters for SRP. For many cryptographic protocols, such as
standard Diffie-Hellman, there may be potential reasons to be
suspicious about fixed parameters; letting paranoids create their own
parameters is reasonable and might make the protocol stronger.
But in protocols such as SRP, this does not make that much sense:
An adversary is not limited to the specific carefully chosen
parameters that the server would *want* to use. Instead, when the
client starts the protocol and is exposed to an active attack, it's
the adversary that gets to choose the parameters; and this can only
make the protocol weaker. (We might assume that the server and client
can store some individually agreed-upon parameters in advance for use
in the protocol, but in that case we are in a scenario where we
wouldn't really require a password-based authenticated key exchange.)
It makes much more sense to allow only standardized parameters in
the first place, which would also avoid some protocol overhead because
there is no need to transmit the literal parameters.
Some means for parameter *negotiation* might be reasonable: If we have
a set of standardized parameters with primes 'N' of different
bitlength, then client and server implementations may have certain
minimum desired bitlengths deemed necessary for security. (These
might increase over the years. For example, the current SRP minimum
of 512 appears too low already.) The client could inform the server
about what values 'N' it supports, and the server could then choose
one of these. But the approach where the server simply sends its
preferred parameters to the client does not offer useful negotiation,
the client has no way to enforce its minimum other than by rejecting
to continue the SRP protocol.
References:
The SRP distribution, including the specifiation documents, is
available at http://srp.stanford.edu/download.html .
The specification for SRP for TLS authentication now warns about
this problem (draft-ietf-tls-srp-09.txt).
Bodo Moeller
with Pseudoprimes", PKC 2005, Springer-Verlag LNCS 3386:
Bodo Moeller
Bodo Moeller
> S = (B - g^x) ^ (a + u * x) % N S = (A * v^u) ^ b % N
... where 'u' is a 32-bit portion of SHA(B). Sorry for the omission.
Thomas Wu
>
> I can't see why we would we even want to let server choose the
> parameters for SRP. For many cryptographic protocols, such as
This is because the user's password verification data is dependent
on the parameters. To perform an SRP authentication for user Alice,
we must use the exact same N and g values that were used when Alice
set her password originally.
Tom
--
Tom Wu
http://www-cs-students.stanford.edu/~tjw/
Bodo Moeller
> bmoe...@acm.org (Bodo Moeller) writes:
>> I can't see why we would we even want to let server choose the
>> parameters for SRP. [...]
> This is because the user's password verification data is dependent
> on the parameters. To perform an SRP authentication for user Alice,
> we must use the exact same N and g values that were used when Alice
> set her password originally.
Certainly. The question is, what is the advantage in allowing Alice
(or the system administrator) to specify a group when she sets her
password? The non-standard group that Alice would prefer to use might
be "better" than a fixed standardized group -- but the adversary, when
sitting in for the server, can send Alice the parameters for any
well-formed group: Instead of letting Alice use her preferred group,
the adversary can make her compute in the standardized group anyway,
or in a group that is even worse. Thus, just allowing standardized
groups for the protocol looks better to me.