INTERNET-DRAFT Niels M÷ller draft-nisse-secsh-srp-01.txt 27 March 2001 Expires in September 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 (2001). 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 either skip the secsh "ssh-userauth"-service [SSH-USERAUTH] when using SRP, or allow login with the "none" or "external-keyx" method. Conventions and notations Niels M÷ller [Page 1] INTERNET-DRAFT SRP key exchange with Secure Shell. 27 March 2001 Some of the conventions used in this document are taken from [SSH- 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 , 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. 27 March 2001 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. 27 March 2001 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. 27 March 2001 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 | H) 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 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. 27 March 2001 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 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. 27 March 2001 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. The SRP keyexchange was originally designed primarily a user authentication method, but it also provides a peculiar form of host authentication. If SRP succeeds, using a particular user name and password, the client can be confident that the remote server knows some verifier corresponding to that password. But if the same password is used with several servers, the client can't distinguish them from eachother, even if the actual verifiers are not shared between servers. 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. Consider 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. According to Tom Wu, the worst the attacker can do is getting information that enables him to verify guessed passwords. 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. Niels M÷ller [Page 7] INTERNET-DRAFT SRP key exchange with Secure Shell. 27 March 2001 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. Further questions This document should give a list of rings that can be used, which should include the rings used by libsrp (is there any specification, besides the source code, that lists these rings)? In general, to what extent should the protocol be compatible with libsrp? Rings can be transmitted either by sending modulo and generator explicitly, like above, or by identifyng rings with names or numbers. It may be a good idea to optionally include the server's host key in the SSH_MSG_KEXSRP_REPLY above, and in the exchange hash. It is not needed for the SRP exchange, but it is a convenient way to transmit an authentic host key, and it is useful for key re-exchanges later on. To strengthen host authentication, in the case that a user has the same password on several servers, it may be a good idea to include the hostname somewhere in the computation of x, either in the user name or in the salt. One can also consider adding the description of the group as another element in the computation of x, to add robustness in the "middle- man-sends-booby-trapped-group" scenario. More analysis is needed to say if adding the group description would really help, though. Author's Address Niels M÷ller LSH author Sl„tbaksv„gen 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-ietf-secsh-dh-group-exchange-00.txt Niels M÷ller [Page 8] INTERNET-DRAFT SRP key exchange with Secure Shell. 27 March 2001 [SRP] T. Wu, "The SRP Authentication and Key Exchange System", RFC 2945 [SSH-ARCH] Ylonen, T., et al, "SSH Protocol Architecture", Internet Draft, draft-ietf-secsh-architecture-07.txt [SSH-TRANS] Ylonen, T., et al, "SSH Transport Layer Protocol", Internet Draft, draft-ietf-secsh-transport-09.txt [SSH-USERAUTH] Ylonen, T., et al, "SSH Authentication Protocol", Internet Draft, draft-ietf-secsh-userauth-09.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 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]