doc/draft-newman-sasl-passdss-xx.txt

   1
   2
   3
   4
   5
   6
   7 Network Working Group                                          C. Newman
   8 Internet Draft: PASSDSS-3DES-1 SASL Mechanism                   Innosoft
   9 Document: draft-newman-sasl-passdss-01.txt                    March 1998
  10                                                    Expires in six months
  11
  12
  13              DSS Secured Password Authentication Mechanism
  14
  15
  16 Status of this memo
  17
  18      This document is an Internet-Draft.  Internet-Drafts are working
  19      documents of the Internet Engineering Task Force (IETF), its areas,
  20      and its working groups.  Note that other groups may also distribute
  21      working documents as Internet-Drafts.
  22
  23      Internet-Drafts are draft documents valid for a maximum of six
  24      months and may be updated, replaced, or obsoleted by other
  25      documents at any time.  It is inappropriate to use Internet-Drafts
  26      as reference material or to cite them other than as "work in
  27      progress."
  28
  29      To view the entire list of current Internet-Drafts, please check
  30      the "1id-abstracts.txt" listing contained in the Internet-Drafts
  31      Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net
  32      (Europe), munnari.oz.au (Pacific Rim), ds.internic.net (US East
  33      Coast), or ftp.isi.edu (US West Coast).
  34
  35
  36 Abstract
  37
  38      Some system administrators are faced with a choice between
  39      deploying a new authentication infrastructure or sending
  40      unencrypted passwords in the clear over the Internet.  Deploying a
  41      new authentication infrastructure often involves modifying
  42      operating system services or keeping parallel authentication
  43      databases up to date and is thus unacceptable to many
  44      administrators.
  45
  46      Solutions which encrypt the entire session are often crippled with
  47      weak keys (due to government restrictions) which are unsuitable for
  48      passwords.  In addition, such solutions often reduce performance of
  49      the entire session to an unacceptable level.  This specification
  50      defines a SASL [SASL] mechanism which is compatible with existing
  51      password-based authentication databases and does not require a
  52      security layer for the remainder of the session.
  53
  54      [NOTE: Public discussion of this mechanism may take place on the
  55
  56
  57
  58 Newman                                                          [Page 1]
  59 \f
  60 Internet Draft       PASSDSS-3DES-1 SASL Mechanism            March 1998
  61
  62
  63      ietf-sasl@imc.org mailing list with a subscription address of
  64      ietf-sasl-request@imc.org.  Private comments may be sent to the
  65      author].
  66
  67 1. How to Read This Document
  68
  69      This document is intended primarily for a programmer.  If
  70      successful, it should be possible for a competent programmer to
  71      write a client implementation using this specification, the SASL
  72      [SASL] specification, an understanding of how to generate random
  73      numbers [RANDOM], a description or implementation of the DES and
  74      SHA1 [SHA1] algorithms and a multi-precision integer math library.
  75      A cryptographic library or a copy of "Applied Cryptography"
  76      [SCHNEIER] or similar reference is helpful for any implementation
  77      and necessary for server DSS key generation.
  78
  79      The key words "MUST", "MUST NOT", "SHOULD", "SHOULD NOT", and "MAY"
  80      in this document are to be interpreted as defined in "Key words for
  81      use in RFCs to Indicate Requirement Levels" [KEYWORDS].
  82
  83 1.1. Data Types Used in this Document
  84
  85      A list of data types used in this document follows.  Note that the
  86      majority of this section is copied from the secure shell
  87      specification [SSH-ARCH].
  88
  89      octet   A basic 8-bit unit of data.
  90
  91      uint32  A 32-bit unsigned integer.  Stored as four octets in
  92              network byte order (also known as big endian or most
  93              significant byte [MSB] first).  For example, the decimal
  94              value 699921578 (hexadecimal 29b7f4aa) is represented with
  95              the hexadecimal octet sequence 29 b7 f4 aa.
  96
  97      string  A string is a length-prefixed octet string.  The length is
  98              represented as a uint32 with the data immediately
  99              following.  A length of 0 indicates an empty string.  The
 100              string MAY contain NUL or 8-bit octets.  When used to
 101              represent textual strings, the characters are interpreted
 102              in UTF-8 [UTF-8].  Other character encoding schemes MUST
 103              NOT be used.
 104
 105      mpint   Represents multiple precision integers in two's complement
 106              format, stored as a string, most significant octet first.
 107              Negative numbers have one in the most significant bit of
 108              the first octet of the string data. If the most significant
 109              bit would be set for a positive number, the number MUST be
 110              preceded by a zero byte.  Unnecessary leading zero or 255
 111
 112
 113
 114 Newman                                                          [Page 2]
 115 \f
 116 Internet Draft       PASSDSS-3DES-1 SASL Mechanism            March 1998
 117
 118
 119              bytes MUST NOT be included.  The value zero MUST be stored
 120              as a string with zero bytes of data.
 121
 122              By convention, a number that is used in modular
 123              computations in the field of integers mod n SHOULD be
 124              represented in the range 0 <= x < n.
 125
 126              Examples:
 127
 128               value (hex)        representation (hex)
 129               -----------------------------------------------------------
 130               0                  00 00 00 00
 131               9a378f9b2e332a7    00 00 00 08 09 a3 78 f9 b2 e3 32 a7
 132               80                 00 00 00 02 00 80
 133               -1234              00 00 00 02 ed cc
 134               -deadbeef          00 00 00 05 ff 21 52 41 11
 135
 136 1.2. Glossary
 137
 138      This section includes some acronyms used in this document.
 139
 140      DES  The U.S. Government Data Encryption Standard is a symmetric
 141           encryption algorithm introduced in 1975 which uses a 56 bit
 142           key.  The algorithm is documented in [SCHNEIER].
 143
 144      DSA  The U.S. Government Digital Signature Algorithm standard.  A
 145           public key signature algorithm available for unrestricted use
 146           without a license.
 147
 148      DSS  The U.S. Government Digital Signature Standard [DSS] which
 149           employs the DSA algorithm.
 150
 151      HMAC A hash-based message authentication code [HMAC] summarized in
 152           Appendix A.4.  Test cases are available in [HMAC-TEST].
 153
 154      SHA  The Secure Hash Algorithm (version 1) which is part of the DSS
 155           standard.
 156
 157      triple-DES
 158           Use of the DES algorithm three times in an encrypt-decrypt-
 159           encrypt mode with three independent keys as described in
 160           appendix A.3.
 161
 162 2. Overview
 163
 164      This section includes a brief discussion of design goals, intended
 165      use and an overview for this SASL mechanism.  An overview of some
 166      of the algorithms used is in Appendix A.
 167
 168
 169
 170 Newman                                                          [Page 3]
 171 \f
 172 Internet Draft       PASSDSS-3DES-1 SASL Mechanism            March 1998
 173
 174
 175 2.1. Design Goals
 176
 177      The ideal authentication mechanism would be simple, fast, fully
 178      secure, freely distributable without restrictions and backwards
 179      compatible with deployed back-end authentication databases.
 180      Unfortunately, it is not possible to achieve all these goals so
 181      priorities and tradeoffs are necessary.  This mechanism has
 182      compatibility with deployed back-end authentication databases and
 183      protection from passive and active attacks on the underlying
 184      connection as primary design goals.  Simplicity and unrestricted
 185      binary distribution are secondary design goals.
 186
 187      Backwards compatibility is achieved by using plain-text
 188      passphrases.  Protection from passive and active attacks is
 189      achieved by using public and symmetric key technology to encrypt
 190      the passphrase and optionally protect the remainder of the session.
 191      Some simplicity is achieved by avoiding complicated public key
 192      certification issues and formats as well as making the SASL session
 193      security layer and certification by the client optional.
 194      Unrestricted binary distribution is hopefully achieved by using
 195      unencumbered algorithms and making the SASL privacy layer optional.
 196
 197 2.2. Intended Use
 198
 199      This is intended as a plug-and-play mechanism for services layered
 200      on top of deployed passphrase-based back-end authentication
 201      databases.  When no security layer is implemented it can be added
 202      to a SASL-based protocol without modifying or substituting network
 203      read and write APIs.  When the optional session privacy protection
 204      is omitted, the author speculates that it may be possible to make a
 205      binary implementation which would be exportable from the United
 206      States.
 207
 208      For cases where simplicity, speed or unrestricted source code
 209      distribution is more desirable than backwards compatibility or
 210      security, a mechanism such as CRAM-MD5 [CRAM-MD5] or SCRAM [SCRAM]
 211      is preferred.
 212
 213      The optional SASL integrity and privacy protection is provided as a
 214      simple alternative to full service security layers such as TLS
 215      [TLS] or Secure Shell [SSH-ARCH].  However, there are many
 216      advantages to full service security layers such as compression,
 217      faster symmetric cipher options, and the ability to leverage other
 218      public key infrastructures.  An implementation which supports TLS
 219      may have no incentive to support SASL security layers at all.  The
 220      complexity verses functionality tradeoff is significant enough that
 221      these mechanisms do not compete.
 222
 223
 224
 225
 226 Newman                                                          [Page 4]
 227 \f
 228 Internet Draft       PASSDSS-3DES-1 SASL Mechanism            March 1998
 229
 230
 231 2.3. Mechanism Overview
 232
 233      The PASSDSS-3DES-1 mechanism uses three components to perform a
 234      secure authentication against a legacy passphrase database.
 235
 236      In order to protect against active attacks, a DSS public key in a
 237      format compatible with Secure Shell [SSH-TRANS] is used to
 238      authenticate the server to the client.  The client is presumed to
 239      have the server's public key or a SHA-1 hash thereof stored locally
 240      in a secure database.  If the client is willing to risk exposure to
 241      active attacks, it may skip the public key certification step
 242      altogether or do a one-time initialization of its local database,
 243      perhaps with user interaction.
 244
 245      In addition to the DSS public key, a Diffie-Hellman key exchange is
 246      used to generate a key for encrypting the passphrase.  The
 247      "PASSDSS-3DES-1" variant of this mechanism uses the same fixed
 248      Diffie-Hellman group used by Secure Shell's diffie-hellman-group1-
 249      sha1 key exchange [SSH-TRANS].  If more groups are necessary, they
 250      will be assigned to mechanism variants "PASSDSS-3DES-2" and so
 251      forth.
 252
 253      Finally, the triple-DES algorithm is used to encrypt the client's
 254      passphrase and send it to the server.
 255
 256 2.4. Message Format Overview
 257
 258      This section provides a quick overview of the format of the
 259      messages.  The formal definition of the syntax for these messages
 260      is in section 6.  A detailed discussion of their implementation on
 261      clients and servers is in sections 3 and 4 respectively.
 262
 263      First message from client to server:
 264        string azname       ; the user name to login as, may be empty if
 265                              same as authentication name
 266        string authname     ; the authentication name
 267        mpint  X            ; Diffie-Hellman parameter X
 268
 269      The challenge from server to client is as follows:
 270        uint32   pklength   ; length of SSH-style DSA server public key
 271          string "ssh-dss"  ; constant string "ssh-dss" (lower case)
 272          mpint  p          ; DSA public key parameters
 273          mpint  q
 274          mpint  g
 275          mpint  y
 276        mpint    Y          ; Diffie-Hellman parameter Y
 277        OCTET    ssecmask   ; SASL security layers offered
 278        3 OCTET  sbuflen    ; maximum server security layer block size
 279
 280
 281
 282 Newman                                                          [Page 5]
 283 \f
 284 Internet Draft       PASSDSS-3DES-1 SASL Mechanism            March 1998
 285
 286
 287        uint32   siglength  ; length of SSH-style dss signature
 288          string "ssh-dss"  ; constant string "ssh-dss" (lower case)
 289          mpint  r          ; DSA signature parameters
 290          mpint  s
 291
 292      The client then sends the following message encrypted with
 293      triple-DES:
 294        OCTET    csecmask   ; SASL security layer selection
 295        3 OCTET  cbuflen    ; maximum client block size
 296        string   passphrase ; the user's passphrase
 297        20 OCTET cli-hmac   ; a client HMAC-SHA-1 signature
 298
 299 3. Client Implementation of PASSDSS-3DES-1
 300
 301      This section includes a step-by-step guide for client implementors.
 302      Although section 6 contains the formal definition of the syntax and
 303      is the authoritative reference in case of errors here, this section
 304      should be sufficient to build a correct implementation.
 305
 306      The SASL mechanism name is "PASSDSS-3DES-1".
 307
 308      The value of n used for the Diffie-Hellman exchange is as follows
 309      (represented as an unsigned hexadecimal integer):
 310
 311            FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
 312            29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
 313            EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
 314            E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
 315            EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE65381
 316            FFFFFFFF FFFFFFFF.
 317
 318      When represented as an "mpint", this would have a prefix of
 319      "0000008100."  The value of g is 2.  This group was taken from the
 320      ISAKMP/Oakley specification, and was originally generated by
 321      Richard Schroeppel at the University of Arizona.  Properties of
 322      this prime are described in [Orm96].
 323
 324      The client begins by doing the following:
 325
 326      (A) Generate the Diffie-Hellman private value "x".  This should be
 327      less than (n - 1)/2.  The number of bits of entropy to use in "x"
 328      is an important decision, as shorter lengths will be less secure
 329      and longer lengths will noticeably reduce performance.  At the time
 330      this was written, 192 bits of entropy [RANDOM] is probably
 331      sufficient.  For more information on this topic, see [SHORT-EXP].
 332
 333
 334
 335
 336
 337
 338 Newman                                                          [Page 6]
 339 \f
 340 Internet Draft       PASSDSS-3DES-1 SASL Mechanism            March 1998
 341
 342
 343      (B) Compute the Diffie-Hellman public value "X" as follows.  If X
 344      has a value of 0, repeat step (A).
 345                 x
 346            X = 2  mod n
 347
 348      The client then sends the following three pieces of information to
 349      the server:
 350
 351      (1) An authorization identity represented as a string.  When the
 352      empty string is used, this defaults to the authentication identity.
 353      This is used by system administrators or proxy servers to login
 354      with a different user identity.
 355
 356      (2) An authentication identity represented as a string.  This is
 357      the identity whose passphrase will be used.
 358
 359      (3) The "X" result from step (B) represented as an mpint.
 360
 361      The server responds by sending a message containing the following
 362      information:
 363
 364      (4) An "ssh-dss" public key compatible with Secure Shell, including
 365      the 32-bit length prefix in network byte order, the Secure Shell
 366      string "ssh-dss" and mpints for "p", "q", "g" and "y" (see Appendix
 367      A.1).
 368
 369      (5) The mpint "Y" as defined for the Diffie-Hellman key exchange
 370      (see Appendix A.2).
 371
 372      (6) A single octet bit mask representing the security layers
 373      available in the same format used by the KERBEROS_V4 mechanism
 374      [SASL].  Bit 0 (value 1) indicates it is permissible to have no
 375      security layer.  Bit 1 (value 2) indicates integrity protection is
 376      permissible.  Bit 2 (value 4) indicates privacy protection for the
 377      rest of the session is available.  The remaining bits are reserved
 378      for future use.
 379
 380      (7) A three octet unsigned integer in network byte order
 381      representing the maximum cipher-text buffer size the server is able
 382      to receive.  If this is less than 32, it indicates that a SASL
 383      security layer is not supported.
 384
 385      (8) A DSA signature, including a 32-bit length, the Secure Shell
 386      string "ssh-dss" and mpints for "r" and "s".
 387
 388      The client then does the following:
 389
 390      (C) Verify that "Y" is between 1 and n - 1 inclusive.  If "Y" is
 391
 392
 393
 394 Newman                                                          [Page 7]
 395 \f
 396 Internet Draft       PASSDSS-3DES-1 SASL Mechanism            March 1998
 397
 398
 399      outside this range, the client MUST cancel the authentication.
 400
 401      (D) Verify that the public key from step (4) belongs to the server.
 402      This can be done either with a database of SSH public keys or with
 403      a database of SHA1 hashes of such public keys.  If the client does
 404      not have a matching entry for the server or does not have a public
 405      key database, it MAY skip this step although it SHOULD alert the
 406      user that the connection is susceptible to active attacks if it
 407      does so.  It MAY also record the public key (or SHA1 hash thereof)
 408      in its database with permission from the user.
 409
 410      (E) Compute the Diffie-Hellman key K as follows.  It may be
 411      necessary to mask timing attacks [TIMING].
 412                 x
 413            K = Y  mod n
 414
 415      (F) Create a buffer containing data from steps (1) through (7) in
 416      order immediately followed by K represented as an mpint.
 417
 418      (G) Compute the SHA1 hash of the buffer from (F).  This produces a
 419      20 octet result.
 420
 421      (H) If the public key from step (4) was not certified, this step
 422      MAY be skipped.  Otherwise, verify that the DSS signature is a
 423      signature of (G).  This computation is done as defined in appendix
 424      A.1 where the output of step (G) represents the message "m" (note
 425      that this results in SHA1 being applied twice).
 426
 427      (I) Compute the following 20-octet values.  K represents the output
 428      of step (E) in mpint format.  H represents the output of step (G).
 429      The || symbol represents string concatenation.  "A" represents a
 430      single octet containing the US-ASCII value of capital letter A.
 431          cs-encryption-iv    = SHA1( K || "A" || H )
 432          sc-encryption-iv    = SHA1( K || "B" || H )
 433          cs-encryption-key-1 = SHA1( K || "C" || H )
 434          cs-encryption-key-2 = SHA1( K || cs-encryption-key-1 )
 435          cs-encryption-key   = cs-encryption-key-1 || cs-encryption-key-2
 436          sc-encryption-key-1 = SHA1( K || "D" || H )
 437          sc-encryption-key-2 = SHA1( K || sc-encryption-key-1 )
 438          sc-encryption-key   = sc-encryption-key-1 || sc-encryption-key-2
 439          cs-integrity-key    = SHA1( K || "E" || H )
 440          sc-integrity-key    = SHA1( K || "F" || H )
 441
 442      (J) Create a buffer beginning with a bit mask for the selected
 443      security layer (it MUST be one offered in 6) followed by three
 444      octets representing the maximum cipher-text buffer size (at least
 445      32) the client can accept in network byte order.  This is followed
 446      by a string containing the passphrase.  Note that integrity
 447
 448
 449
 450 Newman                                                          [Page 8]
 451 \f
 452 Internet Draft       PASSDSS-3DES-1 SASL Mechanism            March 1998
 453
 454
 455      protection is pointless unless the public key was certified in
 456      step (D) and the signature was verified in step (H).
 457
 458      (K) Create a buffer containing items (1) through (7) immediately
 459      followed by the first four octets of (J).
 460
 461      (L) Compute HMAC-SHA-1 with (K) as the data and the cs-integrity-
 462      key from step (I) as the key.  This produces a 20 octet result.  A
 463      summary of the HMAC-SHA-1 algorithm [HMAC] is in appendix A.4.
 464
 465      (M) Create a buffer containing (J) followed by (L) followed by an
 466      arbitrary number of zero octets as necessary to reach the block
 467      size of DES and conceal the passphrase length from an eavesdropper.
 468
 469      (N) Apply the triple-DES algorithm to (M) with the first 8 octets
 470      of cs-encryption-iv from step (I) as the initialization vector and
 471      the first 24 octets of cs-encryption-key as the key.  If optional
 472      privacy protection is negotiated on, the triple-DES state is not
 473      reset.
 474
 475      The client then sends a message to the server containing the
 476      following:
 477
 478      (9) The output of step (N).
 479
 480      If a SASL security layer is negotiated on, the following steps are
 481      used when sending a message:
 482
 483      (O) Create a buffer containing a uint32 client packet number
 484      (starting from 0) immediately followed by the cs-integrity-key from
 485      step (I).
 486
 487      (P) Compute HMAC-SHA-1 with (O) as the key and the data to transmit
 488      as the data.
 489
 490      (Q) Create a buffer containing the data to transmit followed by the
 491      20-octet output of (P).  If privacy was negotiated on, this is
 492      followed by zero to seven padding octets followed by one more octet
 493      indicating the number of padding octets.  The total size MUST be a
 494      multiple of the DES block size.
 495
 496      (R) The result of step (Q) is encrypted with triple-DES if privacy
 497      was negotiated and is sent prefixed by a uint32 length, as required
 498      by SASL.
 499
 500      If a SASL security layer was negotiated on, the following steps are
 501      taken when receiving a message:
 502
 503
 504
 505
 506 Newman                                                          [Page 9]
 507 \f
 508 Internet Draft       PASSDSS-3DES-1 SASL Mechanism            March 1998
 509
 510
 511      (S) If privacy was negotiated on, the message is decrypted using
 512      triple-DES with the first 24 octets of sc-encryption-key as the
 513      key.  The value of the last octet plus one indicates the number of
 514      octets to ignore at the end of the output.  The sc-encryption-iv is
 515      used to initialize triple-DES state the first time this is done.
 516
 517      (T) Create a buffer containing a uint32 server packet number
 518      (starting from 0) immediately followed by the sc-integrity-key.
 519
 520      (U) Compute HMAC-SHA-1 with (T) as the key over the portion of the
 521      data excluding the 20 octet signature and any encryption padding.
 522      If this is the same as the 20 octet signature, then the data is not
 523      corrupted.
 524
 525 4. Server Implementation of PASSDSS-3DES-1
 526
 527      The section includes a step-by-step guide for server implementors.
 528      It is intended to be read in conjunction with section 3.
 529
 530      The server MUST have a persistent DSS-SSH public key.  Mechanisms
 531      for generating such keys are described in [SCHNEIER] and [DSS].
 532
 533      IMPORTANT NOTE: The server MUST be able to process any message from
 534      the client, including messages of any size, messages with invalid
 535      content and messages with NULs in the middle of strings.  When
 536      input is illegal, the server MUST gracefully reject authentication
 537      or in extreme cases gracefully terminate the connection.
 538      Particular care to avoid buffer overruns is important if the user
 539      name or passphrase strings are copied.
 540
 541      The server performs the following computations prior to or during
 542      the connection by the client:
 543
 544      (a) Select a random number k less than (p - 1)/2.  It is important
 545      to generate a good random number [RANDOM].
 546
 547      (b) Compute signature component "r" as follows:
 548                  k
 549            r = (g  mod p) mod q
 550
 551      (c) Optionally pre-compute the group inverse of k, mod q and the
 552      value xr.
 553
 554      (d) Select a random Diffie-Hellman private key y less than (n -
 555      1)/2.  Follow the same guidance as in (A) above.
 556
 557
 558
 559
 560
 561
 562 Newman                                                         [Page 10]
 563 \f
 564 Internet Draft       PASSDSS-3DES-1 SASL Mechanism            March 1998
 565
 566
 567      (e) Compute the Diffie-Hellman public value Y as follows.  If Y has
 568      a value of 0, repeat step (d) above.
 569                 y
 570            Y = 2  mod n
 571
 572      (f) Verify that the value X from the client is between 1 and (n -
 573      1).  If it isn't, fail the authentication.
 574
 575      (g) Compute the Diffie-Hellman shared key K as follows.  It may be
 576      necessary to mask timing attacks [TIMING].
 577                 y
 578            K = X  mod n
 579
 580      (h) Create a buffer containing items (1) through (7) above followed
 581      by K represented as an mpint.
 582
 583      (i) Compute the SHA-1 hash of the buffer from (h).  This produces a
 584      20 octet result.
 585
 586      (j) Generate a DSS signature of (i).  The signature is made up of
 587      "r" from step (b) and the result following computation (partially
 588      completed in step c):
 589                  -1
 590            s = (k  (SHA1(h) + xr)) mod q
 591
 592      (k) Create a buffer containing items (4) through (8) and send it to
 593      the client.
 594
 595      (l) Perform the computations as described in step (I) where K is
 596      the result of step (g) in mpint format and H is the result of step
 597      (i).
 598
 599      (m) Decrypt message (9) from the client using triple-DES with cs-
 600      encryption-iv as the initialization vector and the first 24 octets
 601      of cs-encryption-key as the key.
 602
 603      (n) Verify the passphrase from the output of step (m) against the
 604      authentication database.  Fail the authentication if verification
 605      fails.
 606
 607      (o) Verify that the selected security layer is permitted and the
 608      cipher text buffer size is at least 32.  If not, fail the
 609      authentication.
 610
 611      (p) Create a buffer containing steps (1) through (7) followed by
 612      the first four octets of the result from (m).
 613
 614      (q) Compute the HMAC-SHA-1 of (p) with cs-integrity-key as the key.
 615
 616
 617
 618 Newman                                                         [Page 11]
 619 \f
 620 Internet Draft       PASSDSS-3DES-1 SASL Mechanism            March 1998
 621
 622
 623      This produces a 20-octet result.
 624
 625      (r) Compare the output of (q) with the 20 octet signature after the
 626      passphrase in the output of (m).  If they don't match, fail the
 627      authentication.
 628
 629      If a SASL security layer is negotiated on, sending and receiving
 630      procedures are similar to steps (O)-(U), with client and server
 631      roles exchanged (and thus sc-* values and cs-* value exchanged).
 632      Note that triple-DES state from step (m) is not reset.
 633
 634 5. Example
 635
 636      The following is an example of the PASSDSS-3DES-1 mechanism using
 637      the IMAP [IMAP4] profile of SASL.  Note that base64 encoding and
 638      the lack of an initial client response with the first command are
 639      characteristics of the IMAP profile of SASL and not characteristics
 640      of SASL or this mechanism.
 641
 642      In this example, "C:" represents lines sent from the client to the
 643      server and "S:" represents lines sent from the server to the
 644      client.  The wrapped lines are for editorial clarity -- there are
 645      no actual newlines in the middle of the messages.
 646
 647        C: a001 AUTHENTICATE PASSDSS-3DES-1
 648        S: +
 649        C: AAAAAAAAAAVjaHJpcwAAAIEAhuVbMxdLxrAQVyUWbAp+X09h6QmZ2Jebz
 650           H7YhtcbQyLbB9AGi1eIdojZYtAuVeE+PYkKUANLHI9XzWSFliIGMeUvBc
 651           bflHr+s9tZ5/5YZh9blb33km3tUYVKyB5XP530bDn+lY1lAv6tXHKZPrx
 652           b0zPhc+JGgpWGlmT5k9vx2Wk=
 653        S: + AAAA8gAAAAdzc2gtZHNzAAAAQQDPVlO6nFefrq6fA/dQKIoNj75Jjpp
 654           kVv3DkyILABCox2dMql0bnO48rHFuo167y6oukT/ocKupIw6bgKmdofgd
 655           AAAAFQDRpB6FrxemUGRuLjY/oiH/Qef14QAAAEEAkVr9rOlB58k5XoqmP
 656           NYTrVGZKWbCPcYtaL92ANxgWyjyRo49+m0+fHPNhNibQoLddEZF8lHPKW
 657           gb7z7qz0QMdgAAAEARcIEiMz5jTZo8COf2njL3BTWRND5NGAgZY7s1YOm
 658           2BfjVyf1/MkOiQMiXeonrsfMc0sWQGgpRYRtJWpe56cc2AAAAgQDoV5Uk
 659           bcy3Gjf16MZwPLlJlvmjpSNv2dSSApoddd4+BgZr01zyt7hzb0yRruaN5
 660           fG43DbJLkk7mtL1Hw8aYXBMQQzrPpHtx+anpCDoN2jlersCGFY2cnjxTf
 661           HqY139ohA8vVXYpapeXxKXR4//Ib/ApTGmwlOeIikKDrBmEGX/JgEAAAA
 662           AAAA8AAAAB3NzaC1kc3MAAAAVAI7j3HG8HyjCOxaGFOUTwZqe0xSHAAAA
 663           FHSqU41vPHTCRTqmxNFwXqazPlJH
 664        C: Obp6vQ83q1O/OnQDifZB1rWOci9LaSck8VxNB4UAFhRI56BAs4XPLqOWI
 665           CoB3LYZ
 666        S: a001 OK Authentication Completed
 667
 668      The following private values were used in this example.  These
 669      values are all represented as an mpint in hexadecimal (msb first).
 670
 671
 672
 673
 674 Newman                                                         [Page 12]
 675 \f
 676 Internet Draft       PASSDSS-3DES-1 SASL Mechanism            March 1998
 677
 678
 679      The client private Diffie-Hellman "x" value:
 680
 681        00000018 666E35B4 3BF4BF2B 40E31359 7A5D3AD0 61FD4F6F 736A6114
 682
 683      The server private Diffie-Hellman "y" value:
 684
 685        00000018 587BDFD6 800D101C 8E82E233 3B5A07AA DB87B8F1 68DC194D
 686
 687      The Diffie-Hellman shared secret:
 688
 689        00000080 3B46D3A8 D2163930 1C33D9FE EAFA528D F4B881CF DF906A03
 690        33249A88 42547FF6 49FDC149 1A5084B1 B425A105 CE571283 AC61D896
 691        AF8F7AF7 F95643F3 00A91E57 BCB8CFD7 77A25CBD 35F59A9E 59E98BEA
 692        EA866339 7F0F9AA0 2F0F335C 8C6AAFF7 76BDB668 DF4D51AF 5B4FB807
 693        81A70901 F478FB86 BF42055C BAF46094 EC72E98A
 694
 695      The DSA private key value (the public key is in the exchange):
 696
 697        00000014 252BCBFA 5634D706 6ED43128 972E181E 66BF9C30
 698
 699      The SHA-1 hash value used to compute the keys:
 700
 701        26 75 97 06 EB FE E3 69 C9 03 7D 49 64 19 D5 D2 97 66 E8 CE
 702
 703 6. Formal Syntax of PASSDSS-3DES-1 Messages
 704
 705      This is the formal syntactic definition of the client and server
 706      messages.  This uses ABNF [ABNF] notation including the core rules.
 707      The first three rules define the formal exchange.  The later rules
 708      define the elements of the exchange.
 709
 710      client-msg-1     = [azname] authname diffie-hellman-X
 711
 712      server-msg-1     = dss-public-key diffie-hellman-Y
 713                         ssecmask sbuflen dss-signature
 714
 715      client-msg-2     = client-blob
 716
 717
 718      authname         = string
 719                         ;; interpreted as UTF-8 [UTF-8]
 720
 721      azname           = string
 722                         ;; interpreted as UTF-8 [UTF-8]
 723
 724      cbuflen          = 3OCTET
 725                         ;; Big endian binary unsigned integer
 726                         ;; max length of client read buffer
 727
 728
 729
 730 Newman                                                         [Page 13]
 731 \f
 732 Internet Draft       PASSDSS-3DES-1 SASL Mechanism            March 1998
 733
 734
 735      cli-hmac         = 20OCTET
 736
 737      client-blob      = 8*OCTET
 738                         ;; encrypted version of client-encrypted
 739
 740      client-encrypted = csecmask cbuflen passphrase cli-hmac *NUL
 741                         ;; MUST be multiple of DES block size
 742
 743      csecmask         = OCTET
 744                         ;; client selected protection layer
 745
 746      diffie-hellman-X = mpint
 747
 748      diffie-hellman-Y = mpint
 749
 750      dss-g            = mpint
 751
 752      dss-p            = mpint
 753
 754      dss-public-key   = length NUL NUL NUL %x07 "ssh-dss"
 755                         dss-p dss-q dss-g dss-y
 756                         ;; length is total length of remainder
 757                         ;; as defined in [SSH-TRANS]
 758
 759      dss-q            = mpint
 760
 761      dss-r            = mpint
 762
 763      dss-signature    = length NUL NUL NUL %x07 "ssh-dss"
 764                         dss-r dss-s
 765                         ;; length is total length of remainder
 766
 767      dss-s            = mpint
 768
 769      dss-y            = mpint
 770
 771      length           = 4OCTET
 772                         ;; binary number, big endian format (MSB first)
 773
 774      mpint            = length *OCTET
 775                         ;; length specifies number of octets
 776                         ;; see section 1 for detailed mpint definition
 777
 778      passphrase       = string
 779                         ;; At least 64 octets MUST be supported
 780
 781
 782
 783
 784
 785
 786 Newman                                                         [Page 14]
 787 \f
 788 Internet Draft       PASSDSS-3DES-1 SASL Mechanism            March 1998
 789
 790
 791      sbuflen          = 3OCTET
 792                         ;; Big endian binary unsigned integer
 793                         ;; max length of server read buffer
 794
 795      ssecmask         = OCTET
 796                         ;; server protection layer mask
 797
 798      string           = length *OCTET
 799                         ;; the length determines the number of octets
 800                         ;; OCTETs are interpreted as UTF-8
 801
 802      NUL              = %x00  ;; US-ASCII NUL character
 803
 804 7. Security Considerations
 805
 806      Security considerations are discussed throughout this memo.
 807
 808      This mechanism supplies the server with the plain-text passphrase,
 809      so the server gains the ability to masquerade as the user to any
 810      other services which share the same passphrase.
 811
 812      If the public key certification step is skipped, then an active
 813      attacker can gain the client's passphrase and thus the ability to
 814      masquerade as the user to any other services which share the same
 815      passphrase.  Negotiating a security layer will fail to provide
 816      protection from an active attacker in this case.
 817
 818      If no security layer is negotiated, the rest of the protocol
 819      session is subject to active and passive attacks.
 820
 821      If an integrity-only layer is negotiated, the rest of the protocol
 822      is subject to passive eavesdropping.
 823
 824      The quality of this mechanism depends on the quality of the random
 825      number generator used.  See [RANDOM] for more information.
 826
 827 8. Multinational Considerations
 828
 829      As remote access is a crucial service, users are encouraged to
 830      restrict user names and passphrases to the US-ASCII character set.
 831      However, if characters outside the US-ASCII character set are used
 832      in user names and passphrases, then they are interpreted according
 833      to UTF-8 [UTF-8] and it is a protocol error to include any octet
 834      sequences not legal for UTF-8.  Servers are encouraged to enforce
 835      this restriction to discourage clients from using non-interoperable
 836      local character sets in this context.
 837
 838
 839
 840
 841
 842 Newman                                                         [Page 15]
 843 \f
 844 Internet Draft       PASSDSS-3DES-1 SASL Mechanism            March 1998
 845
 846
 847 9. Intellectual Property Issues and Acknowledgments
 848
 849      David Kravitz holds U.S. Patent #5,231,668 on the DSA algorithm.
 850      NIST has made this patent available world-wide on a royalty-free
 851      basis.
 852
 853      Diffie-Hellman was first published in 1976 [DIFFIE-HELLMAN].  U.S.
 854      Patent #4,200,770 granted April 1980 has expired.  Canada Patent
 855      #1,121,480 was granted April 6, 1982 and may still apply at this
 856      time.
 857
 858      DES is covered under U.S. Patent #3,962,539 granted June 1978,
 859      which has expired.
 860
 861      The majority of the constructions in this specification were copied
 862      from the Secure Shell specifications [SSH-ARCH, SSH-TRANS].
 863      Additional information is paraphrased from "Applied Cryptography"
 864      [SCHNEIER].
 865
 866 10. References
 867
 868      [ABNF] Crocker, Overell, "Augmented BNF for Syntax Specifications:
 869      ABNF", RFC 2234, Internet Mail Consortium, Demon Internet Ltd,
 870      November 1997.
 871
 872      [CRAM-MD5] Klensin, Catoe, Krumviede, "IMAP/POP AUTHorize Extension
 873      for Simple Challenge/Response", RFC 2195, MCI, September 1997.
 874
 875      [DIFFIE-HELLMAN] Diffie, W., Hellman, M.E., "Privacy and
 876      Authentication: An introduction to Cryptography," Proceedings of
 877      the IEEE, v. 67, n. 3, March 1979, pp. 397-427.
 878
 879      [DSS] National Institute of Standards and Technology, "Digital
 880      Signature Standard," NIST FIPS PUB 186, U.S. Department of
 881      Commerce, May 1994.
 882
 883      [HMAC] Krawczyk, Bellare, Canetti, "HMAC: Keyed-Hashing for Message
 884      Authentication", RFC 2104, IBM, UCSD, February 1997.
 885
 886      [HMAC-TEST] Cheng, Glenn, "Test Cases for HMAC-MD5 and HMAC-SHA-1",
 887      RFC 2202, IBM, NIST, September 1997.
 888
 889      [IMAP4] Crispin, M., "Internet Message Access Protocol - Version
 890      4rev1", RFC 2060, University of Washington, December 1996.
 891
 892      [KEYWORDS] Bradner, "Key words for use in RFCs to Indicate
 893      Requirement Levels", RFC 2119, Harvard University, March 1997.
 894
 895
 896
 897
 898 Newman                                                         [Page 16]
 899 \f
 900 Internet Draft       PASSDSS-3DES-1 SASL Mechanism            March 1998
 901
 902
 903      [Orm96] Orman, H., "The Oakley Key Determination Protocol", version
 904      1, TR97-92, Department of Computer Science Technical Report,
 905      University of Arizona.
 906
 907      [RANDOM] Eastlake, Crocker, Schiller, "Randomness Recommendations
 908      for Security", RFC 1750, DEC, Cybercash, MIT, December 1994.
 909
 910      [SASL] Myers, "Simple Authentication and Security Layer (SASL)",
 911      RFC 2222, Netscape Communications, October 1997.
 912
 913      [SCHNEIER] Schneier, B., "Applied Cryptography: Protocols,
 914      Algorithms and Source Code in C," John Wiley and Sons, Inc., 1996.
 915
 916      [SCRAM] Newman, "Salted Challenge Response Authentication Mechanism
 917      (SCRAM)", work in progress, January 1998.
 918
 919      [SHA1] NIST FIPS PUB 180-1, "Secure Hash Standard," National
 920      Institute of Standards and Technology, U.S. Department of Commerce,
 921      April 1995.
 922
 923      [SHORT-EXP] van Oorschot, P., Wiener, M., "On Diffie-Hellman Key
 924      Agreement with Short Exponents", Advances in Cryptography --
 925      EUROCRYPT Springer-Verlag, ISBN 3-540-61186-X, pp. 332-343.
 926
 927      [SSH-ARCH] Ylonen, Kivinen, Saarinen, "SSH Protocol Architecture",
 928      Work in progress, SSH, October 1997.
 929
 930      [SSH-TRANS] Ylonen, Kivinen, Saarinen, "SSH Transport Layer
 931      Protocol", Work in progress, SSH, October 1997.
 932
 933      [TIMING] Kocher, P., "Timing Attacks on Implementations of Diffie-
 934      Hellman, RSA, DSS and Other Systems", Advances in Cryptography --
 935      CRYPTO '96 Proceedings, Lecture Notes in Computer Science, Vol
 936      1109, Springer-Verlag, ISBN 3-540-61512-1, pp. 104-113.
 937
 938      [TLS] Dierks, Allen, "The TLS Protocol Version 1.0", Work in
 939      progress.
 940
 941      [UTF8] Yergeau, "UTF-8, a transformation format of ISO 10646",
 942      RFC 2279, Alis Technologies, January 1998.
 943
 944
 945
 946
 947
 948
 949
 950
 951
 952
 953
 954 Newman                                                         [Page 17]
 955 \f
 956 Internet Draft       PASSDSS-3DES-1 SASL Mechanism            March 1998
 957
 958
 959 11. Author's Address
 960
 961      Chris Newman
 962      Innosoft International, Inc.
 963      1050 Lakes Drive
 964      West Covina, CA 91790 USA
 965
 966      Email: chris.newman@innosoft.com
 967
 968 Appendix A. Algorithm Overview
 969
 970      This section provides a quick overview of the algorithms used.  For
 971      a full understanding, the reader is encouraged to read "Applied
 972      Cryptography" [SCHNEIER].  The follow descriptions are paraphrased
 973      from that source.
 974
 975      Note that an overview of the DES algorithm is not included as
 976      publicly available implementations and descriptions are very
 977      common.
 978
 979 Appendix A.1. DSA Algorithm
 980
 981      The DSA algorithm is a public key algorithm which can be used to
 982      sign messages such that the source can be verified using a public
 983      key.  The algorithm has the following parameters:
 984
 985      p is a prime number L bits long.  Implementations MUST support L
 986      between 512 and 1024 bits.
 987
 988      q is a 160-bit prime factor of (p - 1).
 989
 990           (p - 1)/q
 991      g = h          mod p  where h is any number less than p - 1 such
 992
 993               (p - 1)/q
 994         that h           is greater than 1.
 995
 996      x is a number less than q and represents the private key.
 997
 998           x
 999      y = g  mod p  and represents the public key.
1000
1001      To sign a message m, the client generates a random number k less
1002      than q and computes:
1003
1004               k
1005         r = (g  mod p) mod q
1006
1007
1008
1009
1010 Newman                                                         [Page 18]
1011 \f
1012 Internet Draft       PASSDSS-3DES-1 SASL Mechanism            March 1998
1013
1014
1015               -1
1016         s = (k  (SHA1(m) + xr)) mod q
1017
1018      The signature is represented as r and s, and is verified as
1019      follows:
1020
1021               -1
1022         w  = s   mod q
1023
1024         u1 = (SHA1(m) * w) mod q
1025
1026         u2 = (rw) mod q
1027
1028                 u1    u2
1029         v  = ((g   * y  ) mod p) mod q
1030
1031      If v = r then the signature is verified.
1032
1033 Appendix A.2. Diffie-Hellman Algorithm
1034
1035      The Diffie-Hellman algorithm is a key-exchange algorithm.  It
1036      allows two ends of a communications channel to establish a shared
1037      secret which a passive eavesdropper can not easily determine.  This
1038      key can then be used in a symmetric algorithm such as triple-DES.
1039      The two ends have a prior agreement on two numbers:
1040
1041      n a large prime number
1042
1043      g a primitive mod n.
1044
1045      The client chooses a random large integer x and computes:
1046
1047             x
1048        X = g  mod n
1049
1050      and sends X to the server.  The server chooses a random large
1051      integer y and computes:
1052
1053            y
1054       Y = g  mod n
1055
1056            y
1057       K = X  mod n
1058
1059      The server sends Y to the client.  The client computes:
1060
1061            x
1062       K = Y  mod n
1063
1064
1065
1066 Newman                                                         [Page 19]
1067 \f
1068 Internet Draft       PASSDSS-3DES-1 SASL Mechanism            March 1998
1069
1070
1071      At this point, the client and server share the same secret K.
1072
1073 Appendix A.3. Triple-DES Algorithm in EDE/outer-CBC Mode
1074
1075      The DES algorithm uses an 8 octet (64 bit) key of which 56 bits are
1076      significant.  The triple-DES EDE algorithm uses a 24 octet (192
1077      bit) key of which roughly 112 bits are significant see [SCHNEIER]
1078      for more details.  The "EDE" refers to encrypt-decrypt-encrypt, and
1079      the "CBC" refers to cipher-block-chaining where each cipher block
1080      affects future cipher blocks.  If E() is the DES encryption
1081      function, D() is the DES decryption function, C is a cipher text
1082      block and P is a plain-text block, then triple-DES EDE in CBC mode
1083      with outer chaining is:
1084
1085         C  = E  (D  (E  (P  XOR C   )))
1086          i    K3  K2  K1  i      i-1
1087
1088      NOTE: C  is the initialization vector
1089             0
1090
1091      and the decryption function is:
1092
1093         P  = C    XOR D  (E  (D  (C )))
1094          i    i-1      K3  K2  K1  i
1095
1096      K1 is the first 8 octets of the triple-DES key, K2 is the second 8
1097      octets and K3 is the final 8 octets.
1098
1099 Appendix A.4. HMAC-SHA-1 Keyed hash function
1100
1101      HMAC-SHA-1 uses the SHA-1 hash function to create a keyed hash
1102      function suitable for use as an integrity protection function.  A
1103      more complete description is in [HMAC].  A brief summary of the
1104      algorithm follows:
1105
1106      (A) If the key is longer than 64 octets, it is run through the
1107      SHA-1 function to produce a 20 octet key.
1108
1109      (B) The key is exclusive-ored with a 64 octet buffer filled with
1110      the octet value 0x36.
1111
1112      (C) SHA-1 is computed over (B) followed by the input text.
1113
1114      (D) The key is exclusive-ored with a 64 octet buffer filled with
1115      the octet value 0x5C.
1116
1117      (E) SHA-1 is computed over (D) followed by the output of (C).
1118
1119
1120
1121
1122 Newman                                                         [Page 20]