aboutsummaryrefslogtreecommitdiff
path: root/doc/draft-ietf-secsh-dh-group-exchange-04.txt
blob: ee6b2fb8c62b4190b94bc1589963a8513ea1c1ad (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
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
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
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
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
Network Working Group                                      Markus Friedl
INTERNET-DRAFT                                              Niels Provos
Expires in six months                                 William A. Simpson
                                                               July 2003


   Diffie-Hellman Group Exchange for the SSH Transport Layer Protocol
               draft-ietf-secsh-dh-group-exchange-04.txt


1.  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 docu-
     ments 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.

2.  Copyright Notice

     Copyright (C) 2000-2003 by Markus Friedl, Niels Provos and William
     A. Simpson.

3.  Abstract

     This memo describes a new key exchange method for the SSH protocol.
     It allows the SSH server to propose to the client new groups on
     which to perform the Diffie-Hellman key exchange.  The proposed
     groups need not be fixed and can change with time.

4.  Overview and Rational

     SSH [4,5,6,7] is a a very common protocol for secure remote login
     on the Internet.  Currently, SSH performs the initial key exchange



Friedl/Provos/Simpson     expires in six months                 [Page 1]

INTERNET DRAFT                                                 July 2003


     using the "diffie-hellman-group1-sha1" method.  This method pre-
     scribes a fixed group on which all operations are performed.

     The Diffie-Hellman key exchange provides a shared secret that can
     not be determined by either party alone.  In SSH, the key exchange
     is signed with the host key to provide host authentication.

     The security of the Diffie-Hellman key exchange is based on the
     difficulty of solving the Discrete Logarithm Problem (DLP).  Since
     we expect that the SSH protocol will be in use for many years in
     the future, we fear that extensive precomputation and more effi-
     cient algorithms to compute the discrete logarithm over a fixed
     group might pose a security threat to the SSH protocol.

     The ability to propose new groups will reduce the incentive to use
     precomputation for more efficient calculation of the discrete loga-
     rithm.  The server can constantly compute new groups in the back-
     ground.

5.  Diffie-Hellman Group and Key Exchange

     The server keeps a list of safe primes and corresponding generators
     that it can select from.  A prime p is safe, if p = 2q + 1, and q
     is prime.  New primes can be generated in the background.

     The generator g should be chosen such that the order of the gener-
     ated subgroup does not factor into small primes, i.e., with p = 2q
     + 1, the order has to be either q or p - 1.  If the order is p - 1,
     then the exponents generate all possible public-values, evenly dis-
     tributed throughout the range of the modulus p, without cycling
     through a smaller subset. Such a generator is called a "primitive
     root" (which is trivial to find when p is "safe").

     Implementation Notes:

          One useful technique is to select the generator, and then
          limit the modulus selection sieve to primes with that genera-
          tor:

            2   when p (mod 24) = 11.
            5   when p (mod 10) = 3 or 7.

          It is recommended to use 2 as generator, because it improves
          efficiency in multiplication performance.  It is usable even
          when it is not a primitive root, as it still covers half of
          the space of possible residues.





Friedl/Provos/Simpson     expires in six months                 [Page 2]

INTERNET DRAFT                                                 July 2003


     The client requests a modulus from the server indicating the pre-
     ferred size.  In the following description (C is the client, S is
     the server; the modulus p is a large safe prime and g is a genera-
     tor for a subgroup of GF(p); min is the minimal size of p in bits
     that is acceptable to the client; n is the size of the modulus p in
     bits that the client would like to receive from the server; max is
     the maximal size of p in bits that the client can accept; V_S is
     S's version string; V_C is C's version string; K_S is S's public
     host key; I_C is C's KEXINIT message and I_S S's KEXINIT message
     which have been exchanged before this part begins):

     1.   C sends "min || n || max" to S, indicating the minimal accept-
          able group size, the preferred size of the group and the maxi-
          mal group size in bits the client will accept.

     2.   S finds a group that best matches the client's request, and
          sends "p || g" to C.

     3.   C generates a random number x (1 < x < (p-1)/2). It computes e
          = g^x mod p, and sends "e" to S.

     4.   S generates a random number y (0 < y < (p-1)/2) and computes f
          = g^y mod p. S receives "e".  It computes K = e^y mod p, H =
          hash(V_C || V_S || I_C || I_S || K_S || min || n || max || p
          || g || e || f || K) (these elements are encoded according to
          their types; see below), and signature s on H with its private
          host key.  S sends "K_S || f || s" to C.  The signing opera-
          tion may involve a second hashing operation.

          Implementation Notes:

               To increase the speed of the key exchange, both client
               and server may reduce the size of their private expo-
               nents. It should be at least twice as long as the key
               material that is generated from the shared secret.  For
               more details see the paper by van Oorschot and Wiener
               [1].

     5.   C verifies that K_S really is the host key for S (e.g. using
          certificates or a local database).  C is also allowed to
          accept the key without verification; however, doing so will
          render the protocol insecure against active attacks (but may
          be desirable for practical reasons in the short term in many
          environments).  C then computes K = f^x mod p, H = hash(V_C ||
          V_S || I_C || I_S || K_S || min || n || max || p || g || e ||
          f || K), and verifies the signature s on H.

          Servers and clients SHOULD support groups with a modulus



Friedl/Provos/Simpson     expires in six months                 [Page 3]

INTERNET DRAFT                                                 July 2003


          length of k bits, where 1024 <= k <= 8192.  The recommended
          values for min and max are 1024 and 8192 respectively.

          Either side MUST NOT send or accept e or f values that are not
          in the range [1, p-1]. If this condition is violated, the key
          exchange fails.  To prevent confinement attacks, they MUST
          accept the shared secret K only if 1 < K < p - 1.


     The server should return the smallest group it knows that is larger
     than the size the client requested.  If the server does not know a
     group that is larger than the client request, then it SHOULD return
     the largest group it knows.  In all cases, the size of the returned
     group SHOULD be at least 1024 bits.

     This is implemented with the following messages.  The hash algo-
     rithm for computing the exchange hash is defined by the method
     name, and is called HASH.  The public key algorithm for signing is
     negotiated with the KEXINIT messages.

     First, the client sends:
       byte      SSH_MSG_KEY_DH_GEX_REQUEST
       uint32    min, minimal size in bits of an acceptable group
       uint32    n, preferred size in bits of the group the server should send
       uint32    max, maximal size in bits of an acceptable group

     The server responds with
       byte      SSH_MSG_KEX_DH_GEX_GROUP
       mpint     p, safe prime
       mpint     g, generator for subgroup in GF(p)

     The client responds with:
       byte      SSH_MSG_KEX_DH_GEX_INIT
       mpint     e

     The server responds with:
       byte      SSH_MSG_KEX_DH_GEX_REPLY
       string    server public host key and certificates (K_S)
       mpint     f
       string    signature of H

     The hash H is computed as the HASH 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    K_S, the host key



Friedl/Provos/Simpson     expires in six months                 [Page 4]

INTERNET DRAFT                                                 July 2003


       uint32    min, minimal size in bits of an acceptable group
       uint32    n, preferred size in bits of the group the server should send
       uint32    max, maximal size in bits of an acceptable group
       mpint     p, safe prime
       mpint     g, generator for subgroup
       mpint     e, exchange value sent by the client
       mpint     f, exchange value sent by the server
       mpint     K, the shared secret

     This value is called the exchange hash, and it is used to authenti-
     cate the key exchange.


6.  diffie-hellman-group-exchange-sha1

     The "diffie-hellman-group-exchange-sha1" method specifies Diffie-
     Hellman Group and Key Exchange with SHA-1 as HASH.

7.  Summary of Message numbers

     The following message numbers have been defined in this document.

       #define SSH_MSG_KEX_DH_GEX_REQUEST_OLD  30
       #define SSH_MSG_KEX_DH_GEX_REQUEST      34
       #define SSH_MSG_KEX_DH_GEX_GROUP        31
       #define SSH_MSG_KEX_DH_GEX_INIT         32
       #define SSH_MSG_KEX_DH_GEX_REPLY        33

     SSH_MSG_KEX_DH_GEX_REQUEST_OLD is used for backwards compatibility.
     Instead of sending "min || n || max", the client only sends "n".
     Additionally, the hash is calculated using only "n" instead of "min
     || n || max".

     The numbers 30-49 are key exchange specific and may be redefined by
     other kex methods.

8.  Security Considerations

     This protocol aims to be simple and uses only well understood prim-
     itives.  This encourages acceptance by the community and allows for
     ease of implementation, which hopefully leads to a more secure sys-
     tem.

     The use of multiple moduli inhibits a determined attacker from pre-
     calculating moduli exchange values, and discourages dedication of
     resources for analysis of any particular modulus.

     It is important to employ only safe primes as moduli.  Van Oorshot



Friedl/Provos/Simpson     expires in six months                 [Page 5]

INTERNET DRAFT                                                 July 2003


     and Wiener note that using short private exponents with a random
     prime modulus p makes the computation of the discrete logarithm
     easy [1].  However, they also state that this problem does not
     apply to safe primes.

     The least significant bit of the private exponent can be recovered,
     when the modulus is a safe prime [2].  However, this is not a prob-
     lem, if the size of the private exponent is big enough.  Related to
     this, Waldvogel and Massey note: When private exponents are chosen
     independently and uniformly at random from {0,...,p-2}, the key
     entropy is less than 2 bits away from the maximum, lg(p-1) [3].

9.  Acknowledgments

     The document is derived in part from "SSH Transport Layer Protocol"
     by T. Ylonen, T. Kivinen, M. Saarinen, T. Rinne and S. Lehtinen.

     Markku-Juhani Saarinen pointed out that the least significant bit
     of the private exponent can be recovered efficiently when using
     safe primes and a subgroup with an order divisible by two.

     Bodo Moeller suggested that the server send only one group, reduc-
     ing the complexity of the implementation and the amount of data
     that needs to be exchanged between client and server.

10.  Bibliography


     10.1.  Informative References


     [1]  P. C. van Oorschot and M. J. Wiener, On Diffie-Hellman key
          agreement with short exponents, In Advances in Cryptology -
          EUROCRYPT'96, LNCS 1070, Springer-Verlag, 1996, pp.332-343.

     [2]  Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Van-
          stone.  Handbook of Applied Cryptography. CRC Press, 1996.

     [3]  C. P. Waldvogel and J. L. Massey, The probability distribution
          of the Diffie-Hellman key, in Proceedings of AUSCRYPT 92, LNCS
          718, Springer- Verlag, 1993, pp. 492-504.










Friedl/Provos/Simpson     expires in six months                 [Page 6]

INTERNET DRAFT                                                 July 2003


     10.2.  Normative References


     [4]  Ylonen, T., et al: "SSH Protocol Architecture", Internet-
          Draft, draft-secsh-architecture-07.txt

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

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

     [7]  Ylonen, T., et al: "SSH Connection Protocol", Internet-Draft,
          draft-ietf-secsh-connect-09.txt



11.  Appendix A:  Generation of safe primes

     The Handbook of Applied Cryptography [2] lists the following algo-
     rithm to generate a k-bit safe prime p.  It has been modified so
     that 2 is a generator for the multiplicative group mod p.

      1. Do the following:
        1.1 Select a random (k-1)-bit prime q, so that q mod 12 = 5.
        1.2 Compute p := 2q + 1, and test whether p is prime, (using, e.g.
            trial division and the Rabin-Miller test.)
        Repeat until p is prime.

   If an implementation uses the OpenSSL libraries, a group consisting
   of a 1024-bit safe prime and 2 as generator can be created as fol-
   lows:

      DH *d = NULL;
      d = DH_generate_parameters(1024, DH_GENERATOR_2, NULL, NULL);
      BN_print_fp(stdout, d->p);

      The order of the subgroup generated by 2 is q = p - 1.













Friedl/Provos/Simpson     expires in six months                 [Page 7]

INTERNET DRAFT                                                 July 2003


12.  Author's Address

     Markus Friedl
     Ganghoferstr. 7
     80339 Munich
     Germany

     Email: markus@openbsd.org

     Niels Provos
     Center for Information Technology Integration
     535 W. William Street
     Ann Arbor, MI, 48103

     Phone: (734) 764-5207
     Email: provos@citi.umich.edu

     William Allen Simpson
     DayDreamer
     Computer Systems Consulting Services
     1384 Fontaine
     Madion Heights, Michigan 48071

     Email: wsimpson@greendragon.com



























Friedl/Provos/Simpson     expires in six months                 [Page 8]