.\" -*- mode: nroff; fill-column: 68 -*-
.pl 10.0i
.po 0
.ll 7.2i
.lt 7.2i
.nr LL 7.2i
.nr LT 7.2i
.ds LF Niels Mller
.ds RF FORMFEED[Page %]
.ds CF
.ds LH INTERNET-DRAFT
.ds RH 27 March 2001
.ds CH SRP key exchange with Secure Shell.
.hy 0
.ad l
.in 0
INTERNET-DRAFT                                              Niels Mller
draft-nisse-secsh-srp-01.txt                               27 March 2001
Expires in September 2001


.ce
Using the SRP protocol as a key exchange method in Secure Shell

.ti 0
Status of this Memo
.fi
.in 3

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.

.ti 0
Copyright Notice

Copyright (C) The Internet Society (2001). See the Full Copyright
Notice below for details.

.ti 0
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.

.ti 0
Conventions and notations

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 <n, s, v>, indexed by n.

.ti 0
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.

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.

.ti 0
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
  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 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.

.ti 0
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

.ti 0
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
  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.

.ti 0
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.

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.

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.

.ti 0
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.


.ti 0
Author's Address

.nf
Niels Mller
LSH author
Sltbaksvgen 48
120 51 rsta
Sweden

EMail: nisse@lysator.liu.se

.ti 0
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

[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


.ti 0
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."