SRP in OpenSSH draft protocol spec

[Tom Holroyd <tomh%po.crl.go.jp@localhost>]

A beta-test version of the following protocol specification is currently
available (see http://members.tripod.com/professor_tom/archives/index.html).

SRP (Secure Remote Passwords, RFC2945) is a Diffie-Hellman style
zero-knowledge exchange which provides strong authentication of both
client and server.

This protocol differs from the (recently expired) draft describing the LSH
implementation in that SRP is used as an authentication mechanism within
SSH2, rather than as a key exchange.  The session id resulting from the
normal SSH2 key exchange is also incorporated into the exchange hashes,
providing protection against active host-spoofing attacks, even in the
case where the client does not know the server's host key.  Also, this
protocol provides better security than ordinary password authentication
because of the zero-knowledge properties of SRP.

It is hoped that the above-mentioned implementation will eventually be
incorporated into the official OpenSSH sources.

Comments are welcome.

(I've never written one of these before and I simply copied an existing
format -- I've left the Status and other boilerplate sections mostly blank
for now; I'm just documenting the implementation.  Please let me know
what's required here.)

INTERNET-DRAFT                                                T. Holroyd
draft-tomh-secsh-srp-00.txt                                        T. Wu
Expires in September 2001                                     N. Moeller
                                      20 March 2001

   Using the SRP protocol as an authorization 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.

Copyright Notice

   Copyright (C) The Internet Society (2000).

Abstract

   This memo describes an experimental method for authentication in the
   Secure Shell protocol, version 2 [SSH-ARCH].

   The main virtue of the use of the SRP protocol [SRP] as an
   authentication method in the "ssh-userauth"-service [SSH-USERAUTH] is
   its ability to provide strong authentication in both directions,
   without using any client state apart from the user-entered
   passphrase.  That is, SRP authenticates the server in addition to the
   user, and can also authenticate the server host key.  It is useful in
   situations where no authentic host key is known.

Conventions and notations

   Some of the conventions used in this document are taken from [SSH-
   USERAUTH], others are from [SRP].

   C is the client, S is the server; q is a large safe prime, g is a
   primitive root.

   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 string concatenation.

   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
   passphrase, and s is a random salt string 80 bits long.

   x is constructed from the strings n, p and s as HASH(s | HASH(n | ":"
   | p)), and the verifier v is computed as g^x mod q.  S keeps a
   database containing entries of the form <n, v, s, q, g>, indexed by
   n.

   Numerical ranges such as e in (1, q-1) are non-inclusive, i.e. 1 < e
   < q-1.

Protocol description

   1. C sends n to S.

   2. S uses n to find v, s, q, and g in its database.  S sends q, g,
      and s to C.

   3. C renerates a random number a with ALEN bits (lg(q) < a) and
      computes e = g^a mod q.  C sends e to S.

   4. S generates a random number b with ALEN bits (lg(q) < b) 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 happen
      to be zero, S must try another b.  S sends f to C, and then
      computes the shared secret K = (e * v^u)^b mod q.

   5. C gets the passphrase p from the user and computes
      x = HASH(s | HASH(n | ":" | p)) and v = g^x mod q.  C also
      computes u in the same way as S.  Finally, C computes the
      shared secret K = (f - v) ^ (a + u * x) mod q.

   C must check that q is a safe prime and that g is a primitive root,
   ideally by looking these values up in a well known table.

   The random exponents a and b have ALEN bits, or lg(q) bits if lg(q) <
   ALEN.  ALEN should be at least 256, but either side may use a longer
   value (at the expense of speed).

   Each party must check that e and f are in the range (1, q-1). If not,
   the key exchange fails.

   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.
   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 session id,
   which is part of the exchange hash and which is itself a hash of the
   server host key and other data.  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 SSH2_MSG_USERAUTH_REQUEST
   message, is "srp-gex-sha1".

   First, the client sends:

     byte      SSH2_MSG_USERAUTH_REQUEST
     string    user name (in ISO-10646 UTF-8 encoding [RFC-2279])
     string    service name (in US-ASCII)
     string    "srp-gex-sha1"

   The server responds with

     byte      SSH2_MSG_USERAUTH_SRP_REPLY
     mpint     q
     mpint     g
     string    s

   The client MUST verify that q is a safe prime (i.e., that q is prime,
   and that (q - 1) / 2 is also prime), and that g is a primitive root
   of the multiplicative group formed by q (i.e., that for all x in [1,
   q-1], there exists a y such that g^y mod q = x).  If q is not safe,
   or g is not primitive, the client MUST abort authentication.

   The client then sends

     byte      SSH2_MSG_USERAUTH_SRP_VALUE
     mpint     e

   The server MUST abort if e is not in the range (1, q-1).

   The server responds with

     byte      SSH2_MSG_USERAUTH_SRP_VALUE
     mpint     f

   The server MUST NOT send this message until after it has received and
   checked the the client's SSH2_MSG_USERAUTH_SRP_VALUE message.

   Both sides compute u as the first 32 bits of HASH(f).  The server
   MUST NOT send an f such that u == 0, and f MUST be in the range (1,
   q-1).  The client MUST abort if u is 0 or f is outside the range (1,
   q-1).

   At this point, both sides calculate K.  The client obtains a
   passphrase from the user, and calculates x, v, and K.  The server
   MUST abort if e * v^u == 1 or -1 (mod q).

   Both sides now compute the exchange hash H, as the HASH of the
   concatenation of the following data:

     string    session_id, calculated during the initial key exchange
                  (see [SSH-TRANS] for more information)
     byte      SSH2_MSG_USERAUTH_REQUEST
     string    user name (in ISO-10646 UTF-8 encoding [RFC-2279])
     string    service name (in US-ASCII)
     string    "srp-gex-sha1"
     string    s, the salt
     mpint     q, the prime sent by the server
     mpint     g, the primitive root sent by the server
     mpint     e, exchange value sent by the client
     mpint     f, exchange value sent by the server

   The client computes m1 = HMAC(K, H), and sends it to the server, to
   prove that it knows the shared key.  It sends

     byte      SSH2_MSG_USERAUTH_SRP_PROOF
     string    m1

   The server verifies that m1 is correct using its own K.  If they
   don't match, the server MUST NOT send any proof back to the client,
   but MAY continue without disconnecting in order to allow retries.

   Finally, the server computes m2 = HMAC(K, H2), where H2 is the HASH
   of:

     mpint     e
     string    m1
     string    H

   and sends to the client either:

     byte      SSH2_MSG_USERAUTH_SRP_PROOF
     boolean   0

   in the case that the client's proof was rejected, or:

     byte      SSH2_MSG_USERAUTH_SRP_PROOF
     boolean   1
     string    m2

   in the case that the client's proof was accepted.  If m2 was not
   sent, the client is not authenticated and MAY retry after receiving
   the SSH2_MSG_USERAUTH_FAILURE message that the server MUST send.  If
   m2 was sent, the client verifies that m2 is correct, and if so, the
   server is authenticated.

   Note that according to the SSH2 protocol [SSH-USERAUTH], it is the
   server that either rejects the authentication request by sending
   SSH2_MSG_USERAUTH_FAILURE, or accepts it by sending
   SSH2_MSG_USERAUTH_SUCCESS.  If the m2 value sent by the server does
   not match the value computed by the client, the client MUST abort if
   it receives a SSH2_MSG_USERAUTH_SUCCESS message, since the
   authenticity of the server is in doubt.

Message numbers

   The following message numbers have been defined in this protocol:

     /* 60-79 User authentication method specific (numbers can be
      *       reused for different authentication methods)
      */

     #define SSH2_MSG_USERAUTH_SRP_REPLY           60
     #define SSH2_MSG_USERAUTH_SRP_VALUE           61
     #define SSH2_MSG_USERAUTH_SRP_PROOF           62

Security Considerations

   This entire draft discusses an authentication and key exchange system
   that provides strong authentication, protects passphrases, 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
   passphrase, as well as to impersonate the server.  So the verifier
   should be kept secret.  The <name, salt, verifier, prime, gen> entry
   can be created on the user's machine and transferred to the server
   over a secure channel, or it could be created on the server.  The
   former approach has the advantage that the cleartext passphrase is
   not even temporarily known by the server.

   SRP has been designed not only to counter the threat of casual
   passphrase-sniffing, but also to prevent a determined attacker
   equipped with a dictionary of passphrases from guessing at
   passphrases 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.

   Although SRP may be used as an initial authentication and key-
   exchange method (e.g. instead of the diffie-hellman-group1-sha1
   method required by SSH-TRANS), using SRP as an authentication method
   in Secure Shell has the following advantages: 1) the username is not
   transmitted in the clear; 2) the server is authenticated to the
   client, preventing server spoofing; and 3) since the session id is
   incorporated into the exchange hashes, it (and implicitly the host
   key it was generated from) is authenticated along with the server.

   As some of the best known algorithms for computing discrete
   logarithms use extensive precomputations, it is desirable not to
   depend on a single fixed group.  However, care must be taken whenever
   a client starts to use a new group.  An attacker that knows how to
   compute discrete logarithms in the multiplicative group of a
   particular prime, and can convince the client to use that group (by
   spoofing the server, for example), can obtain the random value a from
   e, and mount a dictionary attack on m1.  While dictionary attacks may
   often be successful due to weak passphrases or simple passwords, this
   one depends on the ability to compute discrete logs in a safe-prime
   group, which is currently theoretically difficult, and requires
   expensive modular exponentiation and multiplication for each test
   passphrase.  In addition, this is not a passive attack, although most
   of the calculations can be carried out off-line.

   SRP authentication of the host key protects against a man-in-the-
   middle attack, where a client is tricked into connecting to a fake
   server, who would then capture the user's password, along with
   session data.

   SRP also has the added advantage of permitting the host to store
   passphrases in a form that is not directly useful to an attacker.
   Even if the host's passphrase verifier database were publicly
   revealed, the attacker would still need an expensive dictionary
   search to obtain any passphrases.  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 passphrase verifier
   files secure.

Author's Address

   Dr. Tom Holroyd
   Kansai Advanced Research Center
   588-2 Iwaoka, Iwaoka-cho, Nishi-ku
   Kobe-shi, Hyogo 651-2492 JAPAN

   EMail: tomh%po.crl.go.jp@localhost

   Thomas Wu
   Arcot Systems
   3200 Patrick Henry Blvd.
   Santa Clara, CA 95054

   EMail: tom%arcot.com@localhost

References

   [SRP]  T. Wu, "The SRP Authentication and Key Exchange System",
   Internet Draft, RFC 2945

   [SSH-ARCH] Ylonen, T., et al, "SSH Protocol Architecture", Internet
   Draft, draft-ietf-secsh-architecture-08.txt

   [SSH-TRANS] Ylonen, T., et al, "SSH Transport Layer Protocol", Internet
   Draft, draft-ietf-secsh-transport-10.txt

   [SSH-USERAUTH] Ylonen, T., et al, "SSH Authentication Protocol",
   Internet Draft, draft-ietf-secsh-userauth-10.txt