srp-spec.nroff 17.1 KB
Newer Older
Niels Möller's avatar
Niels Möller committed
1
.\" -*- mode: nroff; fill-column: 68 -*-
Niels Möller's avatar
Niels Möller committed
2 3 4 5 6 7
.pl 10.0i
.po 0
.ll 7.2i
.lt 7.2i
.nr LL 7.2i
.nr LT 7.2i
Niels Möller's avatar
Niels Möller committed
8
.ds LF Niels Möller
Niels Möller's avatar
Niels Möller committed
9
.ds RF FORMFEED[Page %]
Niels Möller's avatar
Niels Möller committed
10
.ds CF
Niels Möller's avatar
Niels Möller committed
11
.ds LH INTERNET-DRAFT
12
.ds RH 27 March 2001
Niels Möller's avatar
Niels Möller committed
13 14 15 16
.ds CH SRP key exchange with Secure Shell.
.hy 0
.ad l
.in 0
Niels Möller's avatar
Niels Möller committed
17
INTERNET-DRAFT                                              Niels Möller
18 19
draft-nisse-secsh-srp-01.txt                               27 March 2001
Expires in September 2001
Niels Möller's avatar
Niels Möller committed
20

Niels Möller's avatar
Niels Möller committed
21 22

.ce
Niels Möller's avatar
Niels Möller committed
23
Using the SRP protocol as a key exchange method in Secure Shell
Niels Möller's avatar
Niels Möller committed
24 25 26 27 28 29

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

Niels Möller's avatar
Niels Möller committed
30 31
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.
Niels Möller's avatar
Niels Möller committed
32

Niels Möller's avatar
Niels Möller committed
33
Internet-Drafts are working documents of the Internet Engineering
Niels Möller's avatar
Niels Möller committed
34 35 36
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as
Internet-Drafts.
Niels Möller's avatar
Niels Möller committed
37

Niels Möller's avatar
Niels Möller committed
38 39 40
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
Niels Möller's avatar
Niels Möller committed
41 42 43 44 45 46 47 48 49 50 51
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

52
Copyright (C) The Internet Society (2001). See the Full Copyright
Niels Möller's avatar
Niels Möller committed
53 54 55 56 57 58 59 60
Notice below for details.

.ti 0
Abstract

This memo describes an experimental method for authentication and
keyexchange in the Secure Shell protocol.

Niels Möller's avatar
Niels Möller committed
61 62
The main virtue of the SRP protocol [SRP] is that it provides
authentication based on a small secret (typically a password). It is
Niels Möller's avatar
Niels Möller committed
63 64 65
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
66 67 68
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.
Niels Möller's avatar
Niels Möller committed
69 70 71 72

.ti 0
Conventions and notations

Niels Möller's avatar
Niels Möller committed
73 74
Some of the conventions used in this document are taken from
[SSH-TRANS], others are from [SRP].
Niels Möller's avatar
Niels Möller committed
75

Niels Möller's avatar
Niels Möller committed
76
C is the client, S is the server; q is a large safe prime, g is a
Niels Möller's avatar
Niels Möller committed
77 78 79 80
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).
Niels Möller's avatar
Niels Möller committed
81 82 83 84 85 86

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.

Niels Möller's avatar
Niels Möller committed
87 88
The | symbol indicates ssh-style string concatenation: For any
strings A and B, A | B is the encoding of
Niels Möller's avatar
Niels Möller committed
89 90 91 92

  string A
  string B

Niels Möller's avatar
Niels Möller committed
93 94 95 96 97 98 99 100 101 102 103 104 105 106
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.
Niels Möller's avatar
Niels Möller committed
107

Niels Möller's avatar
Niels Möller committed
108 109
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
Niels Möller's avatar
Niels Möller committed
110 111 112 113 114
containing triples <n, s, v>, indexed by n.

.ti 0
Protocol description

Niels Möller's avatar
Niels Möller committed
115 116
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.
Niels Möller's avatar
Niels Möller committed
117 118

2. S uses n to find v and s in its database. S generates a random
Niels Möller's avatar
Niels Möller committed
119
   number b, (lg(q) < b < q-1) and computes f = v + g^b mod q. S
Niels Möller's avatar
Niels Möller committed
120 121
   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
Niels Möller's avatar
Niels Möller committed
122
   computes K = (e * v^u)^b mod q. S sends s and f to C.
Niels Möller's avatar
Niels Möller committed
123

Niels Möller's avatar
Niels Möller committed
124 125 126
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.
Niels Möller's avatar
Niels Möller committed
127

Niels Möller's avatar
Niels Möller committed
128 129
Each party must check that e and f are in the range [1, q-1]. If
not, the key exchange fails.
Niels Möller's avatar
Niels Möller committed
130

Niels Möller's avatar
Niels Möller committed
131 132 133 134
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.
Niels Möller's avatar
Niels Möller committed
135

Niels Möller's avatar
Niels Möller committed
136 137
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
Niels Möller's avatar
Niels Möller committed
138
authenticating the server, the user must prove knowledge of the key
Niels Möller's avatar
Niels Möller committed
139 140 141 142 143 144 145 146 147 148 149 150
*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.
Niels Möller's avatar
Niels Möller committed
151

Niels Möller's avatar
Niels Möller committed
152 153 154
.ti 0
Protocol messages

Niels Möller's avatar
Niels Möller committed
155 156 157
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.
Niels Möller's avatar
Niels Möller committed
158 159 160

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
Niels Möller's avatar
Niels Möller committed
161 162
"diffie-hellman-group1-sha1" in [SSH-TRANS]. Its hexadecimal value
is
Niels Möller's avatar
Niels Möller committed
163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179

  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.

Niels Möller's avatar
Niels Möller committed
180 181 182
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.
Niels Möller's avatar
Niels Möller committed
183 184 185 186 187 188 189 190 191 192 193 194 195 196

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
Niels Möller's avatar
Niels Möller committed
197 198
SSH_MSG_KEXSRP_INIT message.

Niels Möller's avatar
Niels Möller committed
199 200
At this point, both sides can compute the exchange hash H, as the
HASH of the concatenation of the following:
Niels Möller's avatar
Niels Möller committed
201 202 203 204 205 206 207 208 209 210 211

  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

Niels Möller's avatar
Niels Möller committed
212 213
The client computes m1 = HMAC(K, H), and sends it to the server, to
prove that it knows the shared key. It sends
Niels Möller's avatar
Niels Möller committed
214 215 216 217

  byte SSH_MSG_KEXSRP_PROOF
  string m1

Niels Möller's avatar
Niels Möller committed
218 219
[ Would it be possible to instead send the exchange hash in the
  clear, e.g. use m1 = H? ]
Niels Möller's avatar
Niels Möller committed
220

Niels Möller's avatar
Niels Möller committed
221 222 223
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.
Niels Möller's avatar
Niels Möller committed
224

225
Finally, the server computes m2 as the HMAC(K, e | m1 | H) and sends
Niels Möller's avatar
Niels Möller committed
226 227 228 229

  byte SSH_MSG_KEXSRP_PROOF
  string m2

Niels Möller's avatar
Niels Möller committed
230 231
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.
Niels Möller's avatar
Niels Möller committed
232 233 234 235 236 237 238 239 240 241 242 243 244

.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

Niels Möller's avatar
Niels Möller committed
245 246 247 248
.ti 0
Ring negotiation

This section sketches the changes needed in order to get away from
Niels Möller's avatar
Niels Möller committed
249 250 251 252 253
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".
Niels Möller's avatar
Niels Möller committed
254 255 256 257

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
Niels Möller's avatar
Niels Möller committed
258 259
first three elements are the name, salt and verifier as before, and
q and g determines the ring and the generator.
Niels Möller's avatar
Niels Möller committed
260

Niels Möller's avatar
Niels Möller committed
261
C initiates the protocol by sending its user name to the server:
Niels Möller's avatar
Niels Möller committed
262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286

  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.

Niels Möller's avatar
Niels Möller committed
287 288
Now the client kan compute K. Both sides compute the exchange hash
as the HASH of the concatenation of the following:
Niels Möller's avatar
Niels Möller committed
289 290 291 292 293 294 295 296 297 298 299 300 301

  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

Niels Möller's avatar
Niels Möller committed
302 303
The final exchange of SSH_MSG_KEXSRP_PROOF is unchanged. Note that
the ability use different rings costs one more roundtrip.
Niels Möller's avatar
Niels Möller committed
304

Niels Möller's avatar
Niels Möller committed
305 306 307
.ti 0
Security Considerations

Niels Möller's avatar
Niels Möller committed
308 309 310 311
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.
Niels Möller's avatar
Niels Möller committed
312

Niels Möller's avatar
Niels Möller committed
313 314 315
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
Niels Möller's avatar
Niels Möller committed
316 317 318 319 320
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's avatar
Niels Möller committed
321

Niels Möller's avatar
Niels Möller committed
322
SRP has been designed not only to counter the threat of casual
Niels Möller's avatar
Niels Möller committed
323 324 325 326 327
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
Niels Möller's avatar
Niels Möller committed
328 329
confidentiality.

330 331 332 333 334 335 336 337 338
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.

Niels Möller's avatar
Niels Möller committed
339 340 341 342
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
343 344 345 346 347
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.
Niels Möller's avatar
Niels Möller committed
348 349 350 351 352 353 354 355 356

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.

Niels Möller's avatar
Niels Möller committed
357 358 359 360
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
Niels Möller's avatar
Niels Möller committed
361 362 363 364 365 366 367 368 369 370 371 372 373 374 375
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.
Niels Möller's avatar
Niels Möller committed
376

377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406
.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.


Niels Möller's avatar
Niels Möller committed
407 408 409 410
.ti 0
Author's Address

.nf
Niels Möller's avatar
Niels Möller committed
411
Niels Möller
Niels Möller's avatar
Niels Möller committed
412
LSH author
Niels Möller's avatar
Niels Möller committed
413 414
Slätbaksvägen 48
120 51 Årsta
Niels Möller's avatar
Niels Möller committed
415 416 417 418 419 420 421
Sweden

EMail: nisse@lysator.liu.se

.ti 0
References

Niels Möller's avatar
Niels Möller committed
422
[PROVOS] Niels Provos, et al, "Diffie-Hellman Group Exchange for the
Niels Möller's avatar
Niels Möller committed
423
SSH Transport Layer Protocol", Internet Draft,
424
draft-ietf-secsh-dh-group-exchange-00.txt
Niels Möller's avatar
Niels Möller committed
425

426 427
[SRP] T. Wu, "The SRP Authentication and Key Exchange System",
RFC 2945
Niels Möller's avatar
Niels Möller committed
428 429

[SSH-ARCH] Ylonen, T., et al, "SSH Protocol Architecture", Internet
430
Draft, draft-ietf-secsh-architecture-07.txt
Niels Möller's avatar
Niels Möller committed
431 432

[SSH-TRANS] Ylonen, T., et al, "SSH Transport Layer Protocol", Internet
433
Draft, draft-ietf-secsh-transport-09.txt
Niels Möller's avatar
Niels Möller committed
434 435

[SSH-USERAUTH] Ylonen, T., et al, "SSH Authentication Protocol",
436
Internet Draft, draft-ietf-secsh-userauth-09.txt
Niels Möller's avatar
Niels Möller committed
437

Niels Möller's avatar
Niels Möller committed
438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465

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