Subject: SRP in OpenSSH draft protocol spec

From: Tom Holroyd <[email-masked]>
Date: Mon, 2 Apr 2001 13:21:52 +0900 (JST)

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: [email-masked]

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

   EMail: [email-masked]

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

---

From: RJ Atkinson <[email-masked]>
Date: Mon, 02 Apr 2001 15:21:42 -0400

>zero-knowledge exchange which provides strong authentication of both

        Does anyone know of any patents pending or patents
granted that cover SRP ?  My possibly incorrect understanding
is that SRP is patented or patent-pending.

Ran
[email-masked]

---

From: Tom Wu <[email-masked]>
Date: Mon, 02 Apr 2001 13:03:51 -0700

> is that SRP is patented or patent-pending.

RFC2945-style SRP authentication, which is what OpenSSH is using, is
royalty-free for commercial and non-commercial use worldwide.  See

  http://www.ietf.org/ietf/IPR/WU-SRP

for more information.

> [email-masked]

Tom
-- 
Tom Wu
Principal Software Engineer
Arcot Systems
(408) 969-6124

---

From: [email-masked] (Niels M�ller)
Date: 02 Apr 2001 22:32:49 +0200

> is that SRP is patented or patent-pending.

It's patented by Stanford, and the basic variant (that described in
the SRP rfc) is licensed freely. See http://www.ietf.org/ietf/IPR/WU-SRP:

: Received December 22, 2000
: From: Thomas Wu <[email-masked]>
: 
: The SRP Authentication and Key Exchange System, as specified in
: RFC 2945, is available royalty-free worldwide for commercial and
: non-commercial use.
: 
: Extended variants of SRP, such as those based on SRP-Z, may require
: a license, which Stanford will grant on a non-exclusive basis, under
: reasonable and non-discriminatory terms.
: 
: For questions about SRP, please contact me or visit
: http://otl.stanford.edu/
: 
: Tom Wu
: [email-masked]

I've discussed this some more with Tom Wu. I'm not sure it would be
appropriate to quote it all here, but the main point seem to be that
SRP is patented, but licensed freely. Thus, the SRP case is not much
different from CAST-128 and CAST-256, patented by Entrust, or for that
matter DES, which I believe was patented (by IBM?) and then freely
licensed after it became a US government standard.

Tom Wu wrote:

"Stanford's primary intention is to keep the strong password field
 open, by making a well-tested, well-standardized method available for
 free. It simply wouldn't make sense for us to change our minds about
 licensing, because it would undermine a great deal of work, time, and
 effort that we've already put in; that's why it won't happen."

I'm by no means a patent expert, but I feel that SRP is free enough
for use in free software, and that ought to be free enough for
anybody.

It would be good if someone more official at stanford could back up
Tom's statement, though.

/Niels

---

From: RJ Atkinson <[email-masked]>
Date: Mon, 02 Apr 2001 17:11:10 -0400

>  http://www.ietf.org/ietf/IPR/WU-SRP

        IMHO, it would be more clear, hence more helpful,
if there were a published RFC along the lines of the content
at the URL above.  Several such examples exist in the current
RFC archives.  In particular, it would be good if the patent
holder of record formally granted a royalty-free licence 
in such an RFC.  Tom's email is absolutely helpful, but is 
not likely to be sufficient for any commercial firm's patent
counsel.

        Note that I'm speaking as an individual IETF person,
not for my employer.

Thanks,

Ran
[email-masked]

---

From: Tom Wu <[email-masked]>
Date: Mon, 02 Apr 2001 15:42:54 -0700

> licensed after it became a US government standard.

Or, for that matter, PSS, DSA, SHA-1, etc.  The more I investigated
this, the more I found it to be the norm rather than the exception.

> It would be good if someone more official at stanford could back up

If you ask the Stanford OTL, they will of course confirm the IETF
licensing statement.  It may take you a few weeks (they're busy folks),
and you'll have to wade through some legalese, but you'll get it.  In
the meantime, you have a clear statement from the inventor of the
royalty-free license.

-- 
Tom Wu
Principal Software Engineer
Arcot Systems
(408) 969-6124
"The Borg?  Sounds Swedish..."

---

From: Tom Wu <[email-masked]>
Date: Mon, 02 Apr 2001 15:49:12 -0700

> RFC archives.  In particular, it would be good if the patent

Can you point to any specific examples that you feel are representative
of what you are looking for?  Do you feel that the current IPR mechanism
does not address your concerns adequately?

> not likely to be sufficient for any commercial firm's patent

There is a link to the Stanford OTL, where any firm's lawyers can
contact Stanford's lawyers to get the appropriate legal assurances. 
IANAL, I deal with the technical/cryptographic aspects of SRP and leave
the legal issues to them.  It's free, that's the important part as far
as I'm concerned.

Tom

---

From: RJ Atkinson <[email-masked]>
Date: Mon, 02 Apr 2001 19:02:49 -0400

>this, the more I found it to be the norm rather than the exception.

        I believe DSA and SHA-1 were placed in the public domain.

>the meantime, you have a clear statement from the inventor of the

        Unfortunately, clear statement of the patent holder 
is what matters in court, not clear statement of the inventor.

        Any chance you could work a suitable text through the
Stanford OTL and get it published as an RFC (as others have
done in the past) ?

Thanks,

Ran

---

From: RJ Atkinson <[email-masked]>
Date: Mon, 02 Apr 2001 19:12:01 -0400

At 18:49 02/04/01, Tom Wu wrote:
>Can you point to any specific examples that you feel are representative of what you are looking for?  

Examples:
        RFC-1822
        RFC-1988
        (Other examples might exist; these just appeared
quickly when I searched rfc-index.txt)

        Obviously the language in the RFC should be wordsmith'd
by the patent holder's counsel to reflect which rights 
(and limitations, if any) the patent holder is willing
to grant.  In the IETF context, there ought not be a 
requirement for folks to individually and separately contact 
the patent holder to obtain a licence -- instead some form 
of general licence should be granted, IMHO.

        RFC-1790 & RFC-2339 might also be of interest,
though their scope is broader and a bit different than
the previous examples.

>Do you feel that the current IPR mechanism

        Yes.  There is no formal statement from the
holder of the patent(s) [pending ?] about the licence
terms, so my concerns are quite substantially not yet 
addressed.

>IANAL, I deal with the technical/cryptographic aspects of SRP and leave the legal issues to them.  It's free, that's the important 
>part as far as I'm concerned.

        The rest of us don't have a statement formally from
the patent holder indicating that SRP is free.  That is
a substantial legal problem lots of places.  While I believe
you, what matters is whether a court would take such on 
trust (and a court would not).

Thanks,

Ran
[email-masked]

---

From: Tom Wu <[email-masked]>
Date: Mon, 02 Apr 2001 16:33:39 -0700

> trust (and a court would not).

Do you have the same concerns with CAST:

http://www.ietf.org/ietf/IPR/CAST-128-entrust
http://www.ietf.org/rfc/rfc2144.txt

If so, your contention should be with RFC2026.  We should take the rest
of this discussion offline until a resolution is reached.

Tom

---

From: RJ Atkinson <[email-masked]>
Date: Mon, 02 Apr 2001 19:51:07 -0400

At 19:33 02/04/01, Tom Wu wrote:
>If so, your contention should be with RFC2026. 

        Not at all.  RFC-2026 describes the outer limits
that process rules permit, not IETF day to day practices.

        In particular, you have noted that Stanford holds 
the patent on SRP, so you aren't the patent holder yourself.
Entrust is in fact the patent holder for CAST.

        For the record, I object to the IETF SSH WG including
any technology in its specifications that is patented and 
for which a royalty-free, hassle-free, authorised licence 
statement from the patent holder has not been published 
in an RFC or is available from the IETF Secretariat.  
If each user needs to negotiate with the patent holder, 
then it is not acceptable.

Yours,

Ran
[email-masked]

---

From: Tom Wu <[email-masked]>
Date: Mon, 02 Apr 2001 17:08:23 -0700

> Entrust is in fact the patent holder for CAST.

But the IPR statement is not from Entrust, it is from the inventor,
Carlisle Adams.

Tom

---

From: Tom Wu <[email-masked]>
Date: Mon, 02 Apr 2001 17:44:36 -0700

> of general licence should be granted, IMHO.

Just so that others reading this don't get the wrong impression, the
free license for SRP is granted to all, *without* requiring a written
agreement with Stanford.  While people are welcome to contact Stanford
OTL to have their questions answered, they do *not* need to negotiate
with them in order to use SRP on a royalty-free basis.

In the interest of saving time in the future, I will have Stanford OTL
send the IETF secretariat an additional statement to this effect.

Tom

---

From: RJ Atkinson <[email-masked]>
Date: Mon, 02 Apr 2001 20:59:07 -0400

>But the IPR statement is not from Entrust, it is from the inventor,

        Using an Entrust email address and having represented
himself as authorised to speak for Entrust officially at
an IETF meeting...so not the same.

Ran

---

From: RJ Atkinson <[email-masked]>
Date: Mon, 02 Apr 2001 21:00:59 -0400

At 20:44 02/04/01, Tom Wu wrote:
>In the interest of saving time in the future, I will have Stanford OTL send the IETF secretariat an additional statement to this effect.

        Thanks, that would help a lot.  In particular, having
Stanford give the IETF Secretariat a specific licence statement
with clear inclusions/limitations/exclusions would help a great deal.
Publishing an RFC would not be substantially more work and
would be even better, as existing practice shows. :-)

Ran

---

From: Tom Wu <[email-masked]>
Date: Mon, 02 Apr 2001 18:32:02 -0700

> an IETF meeting...so not the same.

But it is precisely the same.  There's still no legally-binding document
to cite in court, which is presumably what you're objecting to, just a
clear statement from the inventor on behalf of the organization he did
the work for.
I suppose you didn't notice that the SRP IPR notice was received from
Stanford, either.  Why the double-standard?

Tom

---

From: RJ Atkinson <[email-masked]>
Date: Mon, 02 Apr 2001 21:56:45 -0400

>clear statement from the inventor on behalf of the organization he did

        ...which I noted earlier I was not comfortable with
most of the IPR statements online at IETF.

>Stanford, either.  Why the double-standard?

        No double standard.  I really want an RFC from
everyone, which folks who've been around for a while have
seen from me in other WGs in the past (e.g. in IPsec).

Ran

---

From: Tom Wu <[email-masked]>
Date: Mon, 02 Apr 2001 19:43:39 -0700

> seen from me in other WGs in the past (e.g. in IPsec).

Understood.  As I have indicated in a different posting, I am willing to
work with Stanford and the IETF to ensure that IPR concerns are dealt
with properly.  But I also want to understand the nature of those
concerns, in light of the fact that there seems to be considerable
disagreement as to what it means to be "free", and that indeed, many of
the things that are commonly thought to be free don't seem to be free
enough for some, especially in the crypto community.

In any case, this issue will go away with Stanford's statement to the
secretariat, and we can go back to the hard work of getting the strong
password authentication code tested and polished for general use.

Tom

---

From: Bill Sommerfeld <[email-masked]>
Date: Tue, 03 Apr 2001 14:31:45 -0400

Ok, I think this issue has been adequately covered here.  .

To summarize briefly:

The IETF process requires prompt public disclosure of any IPR issues
connected to a technology.  This appears to have happened.

The WG then gets to decide (by the usual rough consensus) whether the
IPR presents an obstacle to adoption of the technology as a standard.

So, in order to get adoption by the WG, the IPR owner needs to
convince the members of the WG that any IPR issues will not be an
obstacle to implementation/deployment/... otherwise, the path of least
resistance is to find another technology which is less encumbered or
unencumbered.

Note that there is at least one non-patented technology which is a
possible alternative to SRP; see draft-perlman-strong-cred-00.txt.
(affiliation disclaimer: Radia Perlman and I both work for Sun, though
we are in completely different divisions of the company).

Anyhow, it appears that the existing IPR statement from Tom Wu is not
sufficient for (at least) Ran, but one from the Stanford OTL might
be..  Let's wait and see what the revised IPR statement from Stanford
says.

					- Bill