INTERNET-DRAFT Niels M÷ller
draft-nisse-secsh-srp-00.txt 3 August 2000
Expires in March 2001
Using the SRP protocol as a key exchange method in Secure Shell
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that other
groups may also distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Copyright Notice
Copyright (C) The Internet Society (2000). See the Full Copyright
Notice below for details.
Abstract
This memo describes an experimental method for authentication and
keyexchange in the Secure Shell protocol.
The main virtue of the SRP protocol [SRP] is that it provides
authentication based on a small secret (typically a password). It is
useful in situations where no authentic host key is known. For Secure
Shell, it can be used as a bootstrapping procedure to get the host
key of a server in a safe way. SRP also provides authentication of
the user, which means that it might make sense to skip the secsh
"ssh-userauth"-service [SSH-USERAUTH] when using SRP.
Conventions and notations
Some of the conventions used in this document are taken from [SSH-
Niels M÷ller [Page 1]
INTERNET-DRAFT SRP key exchange with Secure Shell. 3 August 2000
TRANS], others are from [SRP].
C is the client, S is the server; q is a large safe prime, g is a
primitive root. V_S is S's version string; V_C is C's version string;
I_C is C's KEXINIT message and I_S S's KEXINIT message which have
been exchanged before this part begins. (See [SSH-TRANS] for more
information).
The ^ operator is the exponentiation operation, and the mod operator
is the integer remainder operation. Most implementations perform the
exponentiation and remainder in a single stage to avoid generating
unwieldy intermediate results.
The | symbol indicates ssh-style string concatenation: For any
strings A and B, A | B is the encoding of
string A
string B
Computation takes place in the ring Z/q. Actually, most of the action
takes place in its multiplicative group, which is generated by g. The
ring structure is not absolutely essential, what we really need is a
group G and and two mixing operations + and -, unrelated to the group
operation, each mapping G x G onto a set that is "almost" equal to G
(in the ring case, the image includes zero, which is outside the
multiplicative group. This is not really a problem). We must have a =
(a + b) - b, for all a, b in G such that also a + b is in G, and this
is why it is convenient to use the ring structure.
Furthermore, HASH is a hash function (currently SHA1), n is the
user's name (used for looking up salt and verifier in the server's
database), p is a password, and s is a random salt string.
x is constructed from the strings n, p and s as HASH(s | HASH(n |
p)), and the verifier is computed as g^x mod q. S keeps a database
containing triples <n, s, v>, indexed by n.
Protocol description
1. C renerates a random number a (lg(q) < a < q-1) and computes
e = g^a mod q. C sends e and n to S.
2. S uses n to find v and s in its database. S generates a random
number b, (lg(q) < b < q-1) and computes f = v + g^b mod q. S
selects u as the integer corresponding to the first 32 bits of
HASH(f). If f or u happens to be zero, S must try another b. S
computes K = (e * v^u)^b mod q. S sends s and f to C.
Niels M÷ller [Page 2]
INTERNET-DRAFT SRP key exchange with Secure Shell. 3 August 2000
3. C gets the password p and computes x = HASH(s | H(n | p)) and
v = g^x mod q. C also computes u in the same way as S. Finally, C
computes K = (f - v) ^ (a + u * x) mod q.
Each party must check that e and f are in the range [1, q-1]. If not,
the key exchange fails.
Note the addition in step 2, v + g^b mod q, and the corresponding
subtraction f - v in step 3, are the only operations that uses the
ring structure. C should also check that f - v is non-zero, i.e.
belongs to the multiplicative group generated by g.
At this point C and S have a shared secret K. They must now prove
that they know the same value. Even if we're primarily interested in
authenticating the server, the user must prove knowledge of the key
*first*. (Otherwise, the server leaks information about the
verifier).
To do this, the client sends m1 = HMAC(K, H) to the server, where H
is the "exchange hash" defined below. After verifying the MAC, the
server responds by sending m2 = HMAC(K, e | m1 | H) to the client.
Actually, the purpose of this final message exchange is twofold: (i)
to prove knowledge of the shared secret key K, completing the SRP
protocol, and (ii) to use the shared key K to authenticate the
exchange hash. The latter is needed in order to protect against
attacks on the algorithm negotiation that happens before the SRP
exchange, as well as version rollback attacks.
Protocol messages
The name of the method, when listed in the SSH_MSG_KEXINIT message,
is "srp-ring1-sha1". The SSH_MSG_KEXINIT negotiation determines which
hash function is used, as well as the values of q and g.
For the "srp-ring1-sha1", q is equal to 2^1024 - 2^960 - 1 + 2^64 *
floor( 2^894 Pi + 129093 ). This is the same prime used for "diffie-
hellman-group1-sha1" in [SSH-TRANS]. Its hexadecimal value is
FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE65381
FFFFFFFF FFFFFFFF.
In decimal, this value is
179769313486231590770839156793787453197860296048756011706444
Niels M÷ller [Page 3]
INTERNET-DRAFT SRP key exchange with Secure Shell. 3 August 2000
423684197180216158519368947833795864925541502180565485980503
646440548199239100050792877003355816639229553136239076508735
759914822574862575007425302077447712589550957937778424442426
617334727629299387668709205606050270810842907692932019128194
467627007.
The generator used for "srp-ring1-ring1" is g = 5. This is different
from the generator used in [SSH-TRANS], because we need to generate
the entire multiplicative group.
First, the client sends:
byte SSH_MSG_KEXSRP_INIT
string n
mpint e
The server responds with
byte SSH_MSG_KEXSRP_REPLY
string s
mpint f
The server MUST NOT send this message until it has received the
SSH_MSG_KEXSRP_INIT message.
At this point, both sides can compute the exchange hash H, as the
HASH of the concatenation of the following:
string V_C, the client's version string (CR and NL excluded)
string V_S, the server's version string (CR and NL excluded)
string I_C, the payload of the client's SSH_MSG_KEXINIT
string I_S, the payload of the server's SSH_MSG_KEXINIT
string n, the user name
string s, the salt
mpint e, exchange value sent by the client
mpint f, exchange value sent by the server
mpint K, the shared secret
The client computes m1 = HMAC(K, H), and sends it to the server, to
prove that it knows the shared key. It sends
byte SSH_MSG_KEXSRP_PROOF
string m1
[ Would it be possible to instead send the exchange hash in the
clear, e.g. use m1 = H? ]
The server verifies that m1 is correct using its own K. If they don't
Niels M÷ller [Page 4]
INTERNET-DRAFT SRP key exchange with Secure Shell. 3 August 2000
match, the keyexchange fails, and the server MUST NOT send any proof
back to the client.
Finally, the server computes m2 as the HMAC(K, e | m1 | K) and sends
byte SSH_MSG_KEXSRP_PROOF
string m2
to the client. The client verifies that m2 is correct, and if so, the
key exchange is successful and its output is H and K.
Message numbers
The following message numbers have been defined in this protocol
/* Numbers 30-49 used for kex packets.
Different kex methods may reuse message numbers in
this range. */
#define SSH_MSG_KEXSRP_INIT 30
#define SSH_MSG_KEXSRP_REPLY 31
#define SSH_MSG_KEXSRP_PROOF 32
Ring negotiation
This section sketches the changes needed in order to get away from
using a fixed ring. The client MUST not use a ring unless its quality
is checked in some way (see next section). I will assume that the
client either keeps a list of trusted rings, or makes extensive
quality checks at runtime. The name of this keyexchange method is
"srp-sha1".
Each verifier must be associated with a particular ring, which was
used when computing the verifier in the first place. Therefore, the
server's userdatabase will contain entries <n, s, v, q, g> where the
first three elements are the name, salt and verifier as before, and q
and g determines the ring and the generator.
C initiates the protocol by sending its user name to the server:
byte SSH_MSG_KEXSRP_INIT
string n, username
Note that e can not be computed yet, as the ring is not known. S
replies with
byte SSH_MSG_KEXSRP_REPLY
mpint q
mpint g
Niels M÷ller [Page 5]
INTERNET-DRAFT SRP key exchange with Secure Shell. 3 August 2000
string s, salt
C computes e, and sends it to S:
byte SSH_MSG_KEXSRP_VALUE
mpint e
S computes f and K, and responds with
byte SSH_MSG_KEXSRP_VALUE
mpint f
The server MUST NOT send this message until after it has received e
from the client.
Now the client kan compute K. Both sides compute the exchange hash as
the HASH of the concatenation of the following:
string V_C, the client's version string (CR and NL excluded)
string V_S, the server's version string (CR and NL excluded)
string I_C, the payload of the client's SSH_MSG_KEXINIT
string I_S, the payload of the server's SSH_MSG_KEXINIT
string n, the user name
string s, the salt
mpint q
mpint g
mpint e, exchange value sent by the client
mpint f, exchange value sent by the server
mpint K, the shared secret
The final exchange of SSH_MSG_KEXSRP_PROOF is unchanged. Note that
the ability use different rings costs one more roundtrip.
Security Considerations
This entire draft discusses an authentication and key-exchange system
that protects passwords and exchanges keys across an untrusted
network. Most of this section is taken from [SRP], which also
provides more details.
Knowledge of the verifier enables an attacker to mount an offline
search (also known as a "dictionary attack") on the user's password,
as well as to impersonate the server. So the verifier should be kept
secret. The <name, salt, verifier> entry can be created on the user's
machine and transferred to the server, just like a user's public key,
or it could be created on the server. The former approach has the
advantage that the cleartext password is not even temporarily known
by the server.
Niels M÷ller [Page 6]
INTERNET-DRAFT SRP key exchange with Secure Shell. 3 August 2000
SRP has been designed not only to counter the threat of casual
password-sniffing, but also to prevent a determined attacker equipped
with a dictionary of passwords from guessing at passwords using
captured network traffic. The SRP protocol itself also resists active
network attacks, and implementations can use the securely exchanged
keys to protect the session against hijacking and provide
confidentiality.
As some of the best know algorithms for computing discrete logarithms
use extensive precomputations, it is desirable not to depend on a
single fixed group like the multiplicative group used with "srp-
ring1-sha1". However, care must be taken whenever the a client starts
to use a new ring. An attacker that knows how to compute discrete
logarithms in the multiplicative group of a particular ring, and can
convince the client to use that group, can impersonate *any* server
that client connects to.
In "diffie-hellman-group-exchange-sha1" [PROVOS] the client knows the
server's hostkey a priori, and uses that to authenticate the groups
the server proposes.
With SRP, authenticating a proposed ring seems more difficult; if the
ring is weak, authenticating it using the negotiated session key
proves nothing.
SRP also has the added advantage of permitting the host to store
passwords in a form that is not directly useful to an attacker. Even
if the host's password database were publicly revealed, the attacker
would still need an expensive dictionary search to obtain any
passwords. The exponential computation required to validate a guess
in this case is much more time-consuming than the hash currently used
by most UNIX systems. Hosts are still advised, though, to try their
best to keep their password files secure.
At the time of this writing, SRP is still quite a new protocol, and
it is too early to say definitely that it is secure. It is therefore
recommended not to use SRP for general remote access that lets the
client to execute arbitrary programs on the server.
SRP can be used for read-only access to public files (such as the
server's host key, or a users known_hosts file). Used in this way,
SRP can be used to obtain an authentic public key for the server,
while a more conservative authentication mechanism is used for
further access.
Author's Address
Niels M÷ller
Niels M÷ller [Page 7]
INTERNET-DRAFT SRP key exchange with Secure Shell. 3 August 2000
LSH author
Sltbaksvgen 48
120 51 Êrsta
Sweden
EMail: nisse@lysator.liu.se
References
[PROVOS] Niels Provos, et al, "Diffie-Hellman Group Exchange for the
SSH Transport Layer Protocol", Internet Draft,
draft-provos-secsh-dh-group-exchange-00.txt
[SRP] T. Wu, "The SRP Authentication and Key Exchange System",
Internet Draft, draft-wu-srp-auth-03.txt
[SSH-ARCH] Ylonen, T., et al, "SSH Protocol Architecture", Internet
Draft, draft-ietf-secsh-architecture-05.txt
[SSH-TRANS] Ylonen, T., et al, "SSH Transport Layer Protocol", Internet
Draft, draft-ietf-secsh-transport-07.txt
[SSH-USERAUTH] Ylonen, T., et al, "SSH Authentication Protocol",
Internet Draft, draft-ietf-secsh-userauth-07.txt
Full Copyright Statement
Copyright (C) The Internet Society (1997). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implmentation may be prepared, copied, published and
distributed, in whole or in part, without restriction of any kind,
provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of developing
Internet standards in which case the procedures for copyrights defined
in the Internet Standards process must be followed, or as required to
translate it into languages other than English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
Niels M÷ller [Page 8]
INTERNET-DRAFT SRP key exchange with Secure Shell. 3 August 2000
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT
NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN
WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE."
Niels M÷ller [Page 9]