Kerberos Working Group                                        K. Raeburn
Updates: Kerberos-revisions                                          MIT
Document: draft-raeburn-krb-rijndael-krb-00.txt        November 17, 2000 draft-raeburn-krb-rijndael-krb-01.txt             July 2, 2001

              Rijndael, Twofish, Serpent, and Serpent Twofish Cryptosystems
                             for Kerberos 5

Status of this Memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026 [RFC2026]. Internet-Drafts
   are working documents of the Internet Engineering Task Force (IETF),
   its areas, and its working groups. Note that other groups may also
   distribute working documents as Internet-Drafts. Internet-Drafts are
   draft documents valid for a maximum of six months and may be updated,
   replaced, or obsoleted by other documents at any time. It is
   inappropriate to use Internet-Drafts as reference material or to cite
   them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

1. Abstract

   The AES competition in the US [AES] has prompted the submission and
   analysis of a number of new ciphers intended to be significantly
   stronger and faster than the old DES algorithm.  This document
   describes the addition of some of these algorithms to the Kerberos
   cryptosystem suite. suite [Kerb].

   Comments should be sent to the author, or to the IETF Kerberos
   working group (ietf-krb-wg@anl.gov).

2. Conventions Used in this Document

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC 2119.

3. New Encryption and Checksum Types

   This document defines encryption key and checksum types for Kerberos
   5 to be used with the Rijndael (chosen by NIST as the AES cipher),
   Twofish and Serpent encryption algorithms.  The other AES finalists
   appear more problematic from an intellectual property perspective
   (involving licenses or patents), and so are not being addressed by
   the author.

   Each of these algorithms, as required by the AES specifications,
   supports 128-bit block encryption.  Longer encryption, and key sizes of 128, 192, or 256
   bits.  Other block sizes and key sizes are also supported by some of
   these algorithms, but will are not be used in
   Kerberos.

   Each considered here.

   Using the "simplified profile" of these algorithms permits 128-, 192- and 256-bit keys.  Their
   use in Kerberos will permit all section 6 of these key sizes.

   The Twofish specification also describes [Kerb], we can define
   a means for handling other
   key sizes in between.  Keys of these other sizes are effectively
   converted into 192- or 256-bit keys.  In order to avoid having
   multiple representations group of a single key causing potential confusion, encryption and to simplify the key derivation specification, Twofish keys in
   Kerberos will always be 128, 192, or 256 bits long. checksum schemes.  The EncryptedData objects basic encryption
   algorithms listed above are generated as described used in [Kerb] for
   des3-cbc-hmac-sha1, using one CBC mode, with a zero initial
   vector.  The associated checksum function is the function from
   [SHA256] with an output size of twice the key size (SHA256, SHA384,
   or SHA512).

   We use the above encryption algorithms in CBC mode, and a checksum hash
   algorithm of HMAC-SHA256. SHA256, SHA384, or SHA512 [SHA256], with the hash size
   twice the size of the encryption key, in the "simplified profile" of
   section 6 of [Kerb].  (As of the time of this writing, NIST is
   reviewing several new proposed modes of operation, some of which may
   permit encryption and integrity protection simultaneously.  Once this
   process is done, we may wish to consider using one of these modes to
   define a new profile.)  Unless otherwise specified, a zero initial
   vector must be used for CBC mode.

   (Q: Will NIST's new modes

4. Key Generation From Pass Phrases

   For each of operation include anything we might
   prefer over CBC-encrypt plus checksum?  Should we go ahead with this
   anyways?)

   These these new cryptosystems will encryption/checksum profiles, we define a
   process for generating a key from a pass phrase and salt string, both
   assumed to be supplied in UTF-8 representation.

   We use the PBKDF2 function from PKCS #5 v2.0 ([RFC2898]), with
   parameters indicated below, to generate an intermediate key, which is
   passed into the key derivation as described in
   [Kerb], algorithm with derived keys having the same length constant string
   "kerberos" as the original
   keys. in [Kerb].  The new keys will be the byte sequences generated from resulting key is the user's long-term
   key
   derivation algorithm; no adjustments (such as creating parity bits for triple-DES) are needed.  Thus use with the number of bits required as
   output are encryption algorithm in question:

     tkey = PBKDF2 (passphrase, salt, 2, keylength)
     key = DK(tkey, "kerberos")

   (As defined, PBKDF2 actually generates a random byte string, and the same as
   PKCS #5 spec assumes that the key size.

   (Open question: Should we drop key derivation?  The author space is
   somewhat but not overwhelmingly or, he likes to think, blindly in
   favor of keeping it.  Should we revive dense.  For the argument the author
   completely missed when pedantic,
   we get a "random byte string" from PBKDF2, and pass it came up through the
   random-to-key function in regard the profile -- which we define as a simple
   copy operation -- to triple-DES?  Perhaps
   not.) get a "key".)

   The confounder pseudorandom function used by PBKDF2 will be an HMAC of the
   passphrase and salt, as described in Appendix B.1 to PKCS#5, but
   using the hash function chosen for the encryption algorithm instead
   of SHA-1.  For example, all of the 192-bit-key profiles will use an
   HMAC based on SHA384.

   Note that since the hash function's output block size is larger than
   the key sizes, only one block, prepended block needs to be generated through the data.  The input data
   PBKDF2 algorithm, and only two iterations are specified.  Thus, using
   the notation from PKCS#5, the intermediate key is given by:

     U_1 = PRF(P, S || INT(0))
     U_2 = PRF(P, U_1)
     tmp = U_1 \xor U_2
     tkey = tmp<0..keylength-1>

   Sample test vectors are given in the appendix.

5. Kerberos Algorithm Profile Parameters

   This is padded with zero to fifteen trailing zero-valued octets to make it a multiple summary of the block size.

   Since parameters to be used with the Kerberos simplified
   algorithm profile described in section 6.4.2 of [Kerb]:

   +--------------------------------------------------------------------+
   |       protocol always passes around the key type and
   length as part of the EncryptionKey data, we can take advantage format              simple byte string of
   this when defining checksum types, such that a checksum algorithm can
   accept any       |
   |                                        128, 192 or 256 bits        |
   |                                                                    |
   |    string-to-key function              PBKDF2+DK (see previous     |
   |                                        section)                    |
   |                                                                    |
   |       key-generation seed              key size                    |
   |       length of key,                                                       |
   |                                                                    |
   |    random-to-key function              identity                    |
   |                                                                    |
   |             hash function              SHA-256, -384 or -512       |
   |                                        with output size twice      |
   |                                        the key size                |
   |                                                                    |
   |                block size              128 bits                    |
   |                                                                    |
   |      encryption and                    Rijndael, Serpent or        |
   |      decryption functions              Twofish, in CBC mode        |
   |                                        with zero ivec              |
   +--------------------------------------------------------------------+

   Expanding on the case set of key derivation, use sizes and the set of encryption
   functions, this gives us nine profiles for encryption and checksum
   algorithm specified by the key pairs.

6. Assigned Numbers (Cliff? IANA?)

   The following encryption type when deriving a new
   key.  Thus we define only one new value for the sumtype field, for an
   HMAC using the SHA-256 algorithm.

   assigned numbers (Cliff?): are assigned:

   +--------------------------------------------------------------------+
   |                         encryption types                           |
   +--------------------------------------------------------------------+
   |         type name                  etype value          key sizes size   |
   +--------------------------------------------------------------------+
   |   rijndael-hmac-sha256-kd   rijndael128-hmac-sha256              TBD                128      |
   |   rijndael192-hmac-sha384              TBD                192      |
   |   rijndael256-hmac-sha512              TBD            128, 192,                256      |
   |   twofish-hmac-sha256-kd   serpent128-hmac-sha256               TBD                128      |
   |   serpent192-hmac-sha384               TBD                192      |
   |   serpent256-hmac-sha512               TBD            128, 192,                256      |
   |   serpent-hmac-sha256-kd   twofish128-hmac-sha256               TBD                128      |
   |   twofish192-hmac-sha384               TBD                192      |
   |   twofish256-hmac-sha512               TBD            128, 192,                256      |
   +--------------------------------------------------------------------+

   The alias "aes-hmac-sha256-kd" may be used for whichever of the above
   types uses the algorithm chosen as the AES, if any.  Currently,
   Rijndael has been chosen, and the final AES will probably be Rijndael

   Where implementations accept type names in its current human-readable form, but the AES FIPS is not completed.  We recommend
   not using this alias until the final AES FIPS is published.  (Q: Or,
   is it definite that there will
   alternative names "aes128-hmac-sha256", "aes192-hmac-sha384" and
   "aes256-hmac-sha512" are recommended to be no changes?) permitted as aliases for
   the Rijndael key types.

   The following checksum type numbers are assigned:

   +--------------------------------------------------------------------+
   |                          checksum types                            |
   +--------------------------------------------------------------------+
   |         type name                  sumtype value          checksum          length   |
   +--------------------------------------------------------------------+
   |   hmac-sha256-kd   hmac-sha256-rijndael128               TBD                256     |
   |   hmac-sha384-rijndael192               TBD                384     |
   |   hmac-sha512-rijndael256               TBD                512     |
   |   hmac-sha256-serpent128                TBD                256     |
   |   hmac-sha384-serpent192                TBD                384     |
   |   hmac-sha512-serpent256                TBD                512     |
   |   hmac-sha256-twofish128                TBD                256     |
   |   hmac-sha384-twofish192                TBD                384     |
   |   hmac-sha512-twofish256                TBD                512     |
   +--------------------------------------------------------------------+

   (Q: Better to just define hmac-sha256, and say that it uses key
   derivation when the specified key type demands it?)

   The

   These checksum type hmac-sha256-kd types will be used with the corresponding encryption
   types defined above.

   (Similarly, the hmac-sha1-des3 and hmac-sha1-des3-kd checksum types
   in [Kerb] could be extended to be generic hmac-sha1 and hmac-sha1-kd
   checksums, making use of as much key data as is supplied,  Aliases "hmac-sha256-aes128" and the
   specified encryption algorithm.  Since this document isn't making use
   of SHA-1, such changes are outside its scope.)

4. Key Generation From Pass Phrases

   As the des3-cbc-hmac-sha1-kd encryption type is specified in [Kerb],
   the recommended algorithm for generating a key from a pass phrase
   (primarily for users' long-term keys, as is assumed in the
   descriptive text here, but also occasionally for other purposes)
   involves n-folding the pass phrase to produce an intermediate
   encryption key, which is fed into the key derivation algorithm with a
   well-known constant to produce the final key of the user.  While the
   n-fold function does cause the bits of the input string to contribute
   equally to the output ([n-fold]), there so forth are cases in which it does a
   poor job of entropy preservation, and indeed entropy preservation was
   never described as a property of the algorithm in the original paper.

   Thus
   suggested for these algorithms we use the new NIST hash function SHA-256
   in generating the intermediate key.  The catenation of salt and UTF-8
   pass phrase is passed to the SHA-256 function.  The two halves of the
   hash function output are XORed together to get a 128-bit intermediate
   key.  This key is passed into the key derivation algorithm checksum types associated with the
   constant string "kerberos" as in [Kerb].  The resulting 128-bit key
   is the user's long-term key.

   Since in general memorable pass phrases will give nowhere near one
   block's worth of entropy, the author sees no need to make this
   algorithm capable of generating longer keys at this time.

   Sample test vectors are given in the appendix.

   (Q: Any weak keys?)

5. Rijndael keys.

7. Recommendations

   Rijndael, as the proposed AES cipher, is strongly RECOMMENDED. RECOMMENDED, with
   all three lengths.

   Twofish and Serpent, described in the AES report as weaker that
   Rijndael in terms of performance or implementability in certain
   environments but stronger in terms of anticipated resistance to
   certain types of possible attacks, are OPTIONAL.

6. Implementation notes

   Preauthentication algorithms involving smart cards or other hardware
   may provide additional unpredictability that may be used to generate
   longer keys, or simply be factored into a stronger new 128-bit key.
   Such schemes are outside the scope of this document, but implementors
   should recognize that using longer keys with these algorithms for
   AS_REP messages and preauth data may be plausible.

7.

8. Security Considerations

   These new algorithms have not been around long enough to receive the
   decades of intense analysis that DES has received.  It is possible
   that some weakness exists that has not been found by the
   cryptosystems' authors or other cryptographers analyzing these
   algorithms before and during the AES competition.  The AES report
   does indicate that arguments were put forth relating to this in favor
   of deploying multiple algorithms in case one is found to be
   significantly weaker than previously believed.

   The 256-bit SHA algorithm is a work in progress by the US National
   Institute of Standards and Technology.  To the best of the author's
   knowledge, the review process has not been completed.  The use of
   this algorithm in this document is with the assumption that the
   standardization process will go smoothly.

   The author is not a cryptographer.

8.

9. Acknowledgements

   Thanks to John Brezak for feedback on earlier versions of this
   document.

10. References

   [AES] Nechvatal, J., Barker, E., Bassham, L., Burr, W., Dworkin, M.,
   Foti, J., Roback, E., "Report on the Development of the Advanced
   Encryption Standard (AES)", National Institute of Standards and
   Technology, October 2, 2000.

   [Kerb] Neuman, C., Kohl, J., Ts'o, T., Raeburn, K., Yu, T., "The
   Kerberos Network Authentication Service (V5)", draft-ietf-cat-kerberos-
   revisions-06.txt, July 14, 2000. draft-ietf-cat-
   kerberos-revisions-08.txt, March 2, 2001.  Work in progress.

   [RFC2026] Bradner, S., "The Internet Standards Process -- Revision
   3", RFC 2026, October, 1996.

   [RFC2898] Kaliski, B., "PKCS #5: Passowrd-Based Cryptography
   Specification Version 2.0", RFC 2898, September 2000.

   [Rijn] Daemen, J., Rijmen, V., "AES Proposal: Rijndael", September 3,
   1999. *

   [Serp] Anderson, R., Biham, E., Knudsen, L., "Serpent: A Proposal for
   the Advanced Encryption Standard", June 1998. *

   [SHA256] NIST doc ... *

   [Twof] Schneier, B., Kelsey, J., Whiting, D., Wagner, D., Hall, C.,
   Ferguson, N., "The Twofish Encrytion Algorithm: A 128-Bit Block
   Cipher", Wiley Computer Publishing, 1999.

   [Serp] Anderson, R., Biham, E., Knudsen, L., "Serpent: A Proposal for
   the Advanced Encryption Standard", June 1998. *

   [RFC2026] Bradner, S., "The Internet Standards Process -- Revision
   3", RFC 2026, October, 1996.

   [SHA256] NIST doc ... *

   [n-fold] Blumenthal & Bellovin ...

   * Need more substantial references (RFCs or published papers) if
   possible; web-accessible copy may not be a permanent reference.

9.

11. Author's Address

   Kenneth Raeburn
   Massachusetts Institute of Technology
   77 Massachusetts Avenue
   Cambridge, MA 02139

10.
   raeburn@mit.edu

12. Full Copyright Statement

   Copyright (C) The Internet Society (2000). (2001).  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 implementation 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."

A. Sample test vectors

   Some sample test vectors for the string-to-key algorithm:

   (values to be filled in later)

   Salt: none

   Pass phrase: "test"
   Salt: none
     74 65 73 74
   SHA-256 folded to intermediate
   PBKDF2 128-bit output (intermediate key):
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
   Rijndael 128-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
   Serpent 128-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
   Twofish 128-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
   PBKDF2 192-bit output (intermediate key):
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx
   Rijndael 192-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx
   Serpent 192-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx
   Twofish 192-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx
   PBKDF2 256-bit output (intermediate key):
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
   Rijndael 256-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
   Serpent 256-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx

   Salt: "ATHENA.MIT.EDUraeburn"
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
   Twofish 256-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx

   Pass phrase: "password"
     ...
   SHA-256 folded to intermediate
     70 61 73 73 77 6f 72 64
   Salt: "ATHENA.MIT.EDUraeburn"
     41 54 48 45 4e 41 2e 4d 49 54 2e 45 44 55 72 61
     65 62 75 72 6e
   PBKDF2 128-bit output (intermediate key):
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
   Rijndael 128-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
   Serpent 128-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
   Twofish 128-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
   PBKDF2 192-bit output (intermediate key):
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx
   Rijndael 192-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx
   Serpent 192-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx
   Twofish 192-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx
   PBKDF2 256-bit output (intermediate key):
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
   Rijndael 256-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
   Serpent 256-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx

   Salt: none
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
   Twofish 256-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx

   Pass phrase: something with a variety of non-ASCII characters
     ...
   SHA-256 folded to intermediate eszett
     c3 9f
   Salt: "ATHENA.MIT.EDUJuri" + s-caron + "i" + c-acute
     41 54 48 45 4e 41 2e 4d 49 54 2e 45 44 55 4a 75
     72 69 c5 a1 69 c4 87
   PBKDF2 128-bit output (intermediate key):
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
   Rijndael 128-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx

   Serpent 128-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
   Twofish 128-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
   PBKDF2 192-bit output (intermediate key):
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx
   Rijndael 192-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx
   Serpent 192-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx
   Twofish 192-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx
   PBKDF2 256-bit output (intermediate key):
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
   Rijndael 256-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
   Serpent 256-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
   Twofish 256-bit key:
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
     xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx

B. Change History

   Delete this section before RFC publication.

   Major changes from -00:

   Define different types based on key/hash sizes, with hash size always
   twice key size.  Use simplified profile of revised section 6 of
   RFC1510bis.  Drop "-kd" from the names.

   Use PKCS#5 instead of simple hash.  Changed string-to-key vector to
   use some "Appendix Z" cases also submitted for kerberos-revisions.