1CAT working group M. Swift 2Internet Draft J. Brezak 3Document: draft-brezak-win2k-krb-rc4-hmac-03.txt Microsoft 4Category: Informational June 2000 5 6 7 The Windows 2000 RC4-HMAC Kerberos encryption type 8 9 10Status of this Memo 11 12 This document is an Internet-Draft and is in full conformance with 13 all provisions of Section 10 of RFC2026 [1]. Internet-Drafts are 14 working documents of the Internet Engineering Task Force (IETF), its 15 areas, and its working groups. Note that other groups may also 16 distribute working documents as Internet-Drafts. Internet-Drafts are 17 draft documents valid for a maximum of six months and may be 18 updated, replaced, or obsoleted by other documents at any time. It 19 is inappropriate to use Internet- Drafts as reference material or to 20 cite them other than as "work in progress." 21 22 The list of current Internet-Drafts can be accessed at 23 http://www.ietf.org/ietf/1id-abstracts.txt 24 The list of Internet-Draft Shadow Directories can be accessed at 25 http://www.ietf.org/shadow.html. 26 271. Abstract 28 29 The Windows 2000 implementation of Kerberos introduces a new 30 encryption type based on the RC4 encryption algorithm and using an 31 MD5 HMAC for checksum. This is offered as an alternative to using 32 the existing DES based encryption types. 33 34 The RC4-HMAC encryption types are used to ease upgrade of existing 35 Windows NT environments, provide strong crypto (128-bit key 36 lengths), and provide exportable (meet United States government 37 export restriction requirements) encryption. 38 39 The Windows 2000 implementation of Kerberos contains new encryption 40 and checksum types for two reasons: for export reasons early in the 41 development process, 56 bit DES encryption could not be exported, 42 and because upon upgrade from Windows NT 4.0 to Windows 2000, 43 accounts will not have the appropriate DES keying material to do the 44 standard DES encryption. Furthermore, 3DES is not available for 45 export, and there was a desire to use a single flavor of encryption 46 in the product for both US and international products. 47 48 As a result, there are two new encryption types and one new checksum 49 type introduced in Windows 2000. 50 51 522. Conventions used in this document 53 54 55 56Swift Category - Informational 1 57 58 Windows 2000 RC4-HMAC Kerberos E-Type June 2000 59 60 61 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 62 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in 63 this document are to be interpreted as described in RFC-2119 [2]. 64 653. Key Generation 66 67 On upgrade from existing Windows NT domains, the user accounts would 68 not have a DES based key available to enable the use of DES base 69 encryption types specified in RFC 1510. The key used for RC4-HMAC is 70 the same as the existing Windows NT key (NT Password Hash) for 71 compatibility reasons. Once the account password is changed, the DES 72 based keys are created and maintained. Once the DES keys are 73 available DES based encryption types can be used with Kerberos. 74 75 The RC4-HMAC String to key function is defined as follow: 76 77 String2Key(password) 78 79 K = MD4(UNICODE(password)) 80 81 The RC4-HMAC keys are generated by using the Windows UNICODE version 82 of the password. Each Windows UNICODE character is encoded in 83 little-endian format of 2 octets each. Then performing an MD4 [6] 84 hash operation on just the UNICODE characters of the password (not 85 including the terminating zero octets). 86 87 For an account with a password of "foo", this String2Key("foo") will 88 return: 89 90 0xac, 0x8e, 0x65, 0x7f, 0x83, 0xdf, 0x82, 0xbe, 91 0xea, 0x5d, 0x43, 0xbd, 0xaf, 0x78, 0x00, 0xcc 92 934. Basic Operations 94 95 The MD5 HMAC function is defined in [3]. It is used in this 96 encryption type for checksum operations. Refer to [3] for details on 97 its operation. In this document this function is referred to as 98 HMAC(Key, Data) returning the checksum using the specified key on 99 the data. 100 101 The basic MD5 hash operation is used in this encryption type and 102 defined in [7]. In this document this function is referred to as 103 MD5(Data) returning the checksum of the data. 104 105 RC4 is a stream cipher licensed by RSA Data Security [RSADSI]. A 106 compatible cipher is described in [8]. In this document the function 107 is referred to as RC4(Key, Data) returning the encrypted data using 108 the specified key on the data. 109 110 These encryption types use key derivation as defined in [9] (RFC- 111 1510BIS) in Section titled "Key Derivation". With each message, the 112 message type (T) is used as a component of the keying material. This 113 summarizes the different key derivation values used in the various 114 115Swift Category - Informational 2 116 117 Windows 2000 RC4-HMAC Kerberos E-Type June 2000 118 119 120 operations. Note that these differ from the key derivations used in 121 other Kerberos encryption types. 122 123 T = 1 for TS-ENC-TS in the AS-Request 124 T = 8 for the AS-Reply 125 T = 7 for the Authenticator in the TGS-Request 126 T = 8 for the TGS-Reply 127 T = 2 for the Server Ticket in the AP-Request 128 T = 11 for the Authenticator in the AP-Request 129 T = 12 for the Server returned AP-Reply 130 T = 15 in the generation of checksum for the MIC token 131 T = 0 in the generation of sequence number for the MIC token 132 T = 13 in the generation of checksum for the WRAP token 133 T = 0 in the generation of sequence number for the WRAP token 134 T = 0 in the generation of encrypted data for the WRAPPED token 135 136 All strings in this document are ASCII unless otherwise specified. 137 The lengths of ASCII encoded character strings include the trailing 138 terminator character (0). 139 140 The concat(a,b,c,...) function will return the logical concatenation 141 (left to right) of the values of the arguments. 142 143 The nonce(n) function returns a pseudo-random number of "n" octets. 144 1455. Checksum Types 146 147 There is one checksum type used in this encryption type. The 148 Kerberos constant for this type is: 149 #define KERB_CHECKSUM_HMAC_MD5 (-138) 150 151 The function is defined as follows: 152 153 K - is the Key 154 T - the message type, encoded as a little-endian four byte integer 155 156 CHKSUM(K, T, data) 157 158 Ksign = HMAC(K, "signaturekey") //includes zero octet at end 159 tmp = MD5(concat(T, data)) 160 CHKSUM = HMAC(Ksign, tmp) 161 162 1636. Encryption Types 164 165 There are two encryption types used in these encryption types. The 166 Kerberos constants for these types are: 167 #define KERB_ETYPE_RC4_HMAC 23 168 #define KERB_ETYPE_RC4_HMAC_EXP 24 169 170 The basic encryption function is defined as follow: 171 172 T = the message type, encoded as a little-endian four byte integer. 173 174Swift Category - Informational 3 175 176 Windows 2000 RC4-HMAC Kerberos E-Type June 2000 177 178 179 180 BYTE L40[14] = "fortybits"; 181 BYTE SK = "signaturekey"; 182 183 ENCRYPT (K, fRC4_EXP, T, data, data_len, edata, edata_len) 184 { 185 if (fRC4_EXP){ 186 *((DWORD *)(L40+10)) = T; 187 HMAC (K, L40, 10 + 4, K1); 188 }else{ 189 HMAC (K, &T, 4, K1); 190 } 191 memcpy (K2, K1, 16); 192 if (fRC4_EXP) memset (K1+7, 0xAB, 9); 193 add_8_random_bytes(data, data_len, conf_plus_data); 194 HMAC (K2, conf_plus_data, 8 + data_len, checksum); 195 HMAC (K1, checksum, 16, K3); 196 RC4(K3, conf_plus_data, 8 + data_len, edata + 16); 197 memcpy (edata, checksum, 16); 198 edata_len = 16 + 8 + data_len; 199 } 200 201 DECRYPT (K, fRC4_EXP, T, edata, edata_len, data, data_len) 202 { 203 if (fRC4_EXP){ 204 *((DWORD *)(L40+10)) = T; 205 HMAC (K, L40, 14, K1); 206 }else{ 207 HMAC (K, &T, 4, K1); 208 } 209 memcpy (K2, K1, 16); 210 if (fRC4_EXP) memset (K1+7, 0xAB, 9); 211 HMAC (K1, edata, 16, K3); // checksum is at edata 212 RC4(K3, edata + 16, edata_len - 16, edata + 16); 213 data_len = edata_len - 16 - 8; 214 memcpy (data, edata + 16 + 8, data_len); 215 216 // verify generated and received checksums 217 HMAC (K2, edata + 16, edata_len - 16, checksum); 218 if (memcmp(edata, checksum, 16) != 0) 219 printf("CHECKSUM ERROR !!!!!!\n"); 220 } 221 222 The header field on the encrypted data in KDC messages is: 223 224 typedef struct _RC4_MDx_HEADER { 225 UCHAR Checksum[16]; 226 UCHAR Confounder[8]; 227 } RC4_MDx_HEADER, *PRC4_MDx_HEADER; 228 229 The KDC message is encrypted using the ENCRYPT function not 230 including the Checksum in the RC4_MDx_HEADER. 231 232 233Swift Category - Informational 4 234 235 Windows 2000 RC4-HMAC Kerberos E-Type June 2000 236 237 238 The character constant "fortybits" evolved from the time when a 40- 239 bit key length was all that was exportable from the United States. 240 It is now used to recognize that the key length is of "exportable" 241 length. In this description, the key size is actually 56-bits. 242 2437. Key Strength Negotiation 244 245 A Kerberos client and server can negotiate over key length if they 246 are using mutual authentication. If the client is unable to perform 247 full strength encryption, it may propose a key in the "subkey" field 248 of the authenticator, using a weaker encryption type. The server 249 must then either return the same key or suggest its own key in the 250 subkey field of the AP reply message. The key used to encrypt data 251 is derived from the key returned by the server. If the client is 252 able to perform strong encryption but the server is not, it may 253 propose a subkey in the AP reply without first being sent a subkey 254 in the authenticator. 255 2568. GSSAPI Kerberos V5 Mechanism Type 257 2588.1 Mechanism Specific Changes 259 260 The GSSAPI per-message tokens also require new checksum and 261 encryption types. The GSS-API per-message tokens must be changed to 262 support these new encryption types (See [5] Section 1.2.2). The 263 sealing algorithm identifier (SEAL_ALG) for an RC4 based encryption 264 is: 265 Byte 4..5 SEAL_ALG 0x10 0x00 - RC4 266 267 The signing algorithm identifier (SGN_ALG) for MD5 HMAC is: 268 Byte 2..3 SGN ALG 0x11 0x00 - HMAC 269 270 The only support quality of protection is: 271 #define GSS_KRB5_INTEG_C_QOP_DEFAULT 0x0 272 273 In addition, when using an RC4 based encryption type, the sequence 274 number is sent in big-endian rather than little-endian order. 275 276 The Windows 2000 implementation also defines new GSSAPI flags in the 277 initial token passed when initializing a security context. These 278 flags are passed in the checksum field of the authenticator (See [5] 279 Section 1.1.1). 280 281 GSS_C_DCE_STYLE - This flag was added for use with Microsoft�s 282 implementation of DCE RPC, which initially expected three legs of 283 authentication. Setting this flag causes an extra AP reply to be 284 sent from the client back to the server after receiving the server�s 285 AP reply. In addition, the context negotiation tokens do not have 286 GSSAPI framing - they are raw AP message and do not include object 287 identifiers. 288 #define GSS_C_DCE_STYLE 0x1000 289 290 291 292Swift Category - Informational 5 293 294 Windows 2000 RC4-HMAC Kerberos E-Type June 2000 295 296 297 GSS_C_IDENTIFY_FLAG - This flag allows the client to indicate to the 298 server that it should only allow the server application to identify 299 the client by name and ID, but not to impersonate the client. 300 #define GSS_C_IDENTIFY_FLAG 0x2000 301 302 GSS_C_EXTENDED_ERROR_FLAG - Setting this flag indicates that the 303 client wants to be informed of extended error information. In 304 particular, Windows 2000 status codes may be returned in the data 305 field of a Kerberos error message. This allows the client to 306 understand a server failure more precisely. In addition, the server 307 may return errors to the client that are normally handled at the 308 application layer in the server, in order to let the client try to 309 recover. After receiving an error message, the client may attempt to 310 resubmit an AP request. 311 #define GSS_C_EXTENDED_ERROR_FLAG 0x4000 312 313 These flags are only used if a client is aware of these conventions 314 when using the SSPI on the Windows platform, they are not generally 315 used by default. 316 317 When NetBIOS addresses are used in the GSSAPI, they are identified 318 by the GSS_C_AF_NETBIOS value. This value is defined as: 319 #define GSS_C_AF_NETBIOS 0x14 320 NetBios addresses are 16-octet addresses typically composed of 1 to 321 th 322 15 characters, trailing blank (ascii char 20) filled, with a 16 323 octet of 0x0. 324 3258.2 GSSAPI Checksum Type 326 327 The GSSAPI checksum type and algorithm is defined in Section 5. Only 328 the first 8 octets of the checksum are used. The resulting checksum 329 is stored in the SGN_CKSUM field (See [5] Section 1.2) for 330 GSS_GetMIC() and GSS_Wrap(conf_flag=FALSE). 331 332 MIC (K, fRC4_EXP, seq_num, MIC_hdr, msg, msg_len, 333 MIC_seq, MIC_checksum) 334 { 335 HMAC (K, SK, 13, K4); 336 T = 15; 337 memcpy (T_plus_hdr_plus_msg + 00, &T, 4); 338 memcpy (T_plus_hdr_plus_msg + 04, MIC_hdr, 8); 339 // 0101 1100 FFFFFFFF 340 memcpy (T_plus_hdr_plus_msg + 12, msg, msg_len); 341 MD5 (T_hdr_msg, 4 + 8 + msg_len, MD5_of_T_hdr_msg); 342 HMAC (K4, MD5_of_T_hdr_msg, CHKSUM); 343 memcpy (MIC_checksum, CHKSUM, 8); // use only first 8 bytes 344 345 T = 0; 346 if (fRC4_EXP){ 347 *((DWORD *)(L40+10)) = T; 348 HMAC (K, L40, 14, K5); 349 }else{ 350 HMAC (K, &T, 4, K5); 351 352Swift Category - Informational 6 353 354 Windows 2000 RC4-HMAC Kerberos E-Type June 2000 355 356 357 } 358 if (fRC4_EXP) memset(K5+7, 0xAB, 9); 359 HMAC(K5, MIT_checksum, 8, K6); 360 copy_seq_num_in_big_endian(seq_num, seq_plus_direction); 361 //0x12345678 362 copy_direction_flag (direction_flag, seq_plus_direction + 363 4); //0x12345678FFFFFFFF 364 RC4(K6, seq_plus_direction, 8, MIC_seq); 365 } 366 3678.3 GSSAPI Encryption Types 368 369 There are two encryption types for GSSAPI message tokens, one that 370 is 128 bits in strength, and one that is 56 bits in strength as 371 defined in Section 6. 372 373 All padding is rounded up to 1 byte. One byte is needed to say that 374 there is 1 byte of padding. The DES based mechanism type uses 8 byte 375 padding. See [5] Section 1.2.2.3. 376 377 The encryption mechanism used for GSS wrap based messages is as 378 follow: 379 380 381 WRAP (K, fRC4_EXP, seq_num, WRAP_hdr, msg, msg_len, 382 WRAP_seq, WRAP_checksum, edata, edata_len) 383 { 384 HMAC (K, SK, 13, K7); 385 T = 13; 386 PAD = 1; 387 memcpy (T_hdr_conf_msg_pad + 00, &T, 4); 388 memcpy (T_hdr_conf_msg_pad + 04, WRAP_hdr, 8); // 0101 1100 389 FFFFFFFF 390 memcpy (T_hdr_conf_msg_pad + 12, msg, msg_len); 391 memcpy (T_hdr_conf_msg_pad + 12 + msg_len, &PAD, 1); 392 MD5 (T_hdr_conf_msg_pad, 393 4 + 8 + 8 + msg_len + 1, 394 MD5_of_T_hdr_conf_msg_pad); 395 HMAC (K7, MD5_of_T_hdr_conf_msg_pad, CHKSUM); 396 memcpy (WRAP_checksum, CHKSUM, 8); // use only first 8 397 bytes 398 399 T = 0; 400 if (fRC4_EXP){ 401 *((DWORD *)(L40+10)) = T; 402 HMAC (K, L40, 14, K8); 403 }else{ 404 HMAC (K, &T, 4, K8); 405 } 406 if (fRC4_EXP) memset(K8+7, 0xAB, 9); 407 HMAC(K8, WRAP_checksum, 8, K9); 408 copy_seq_num_in_big_endian(seq_num, seq_plus_direction); 409 //0x12345678 410 411Swift Category - Informational 7 412 413 Windows 2000 RC4-HMAC Kerberos E-Type June 2000 414 415 416 copy_direction_flag (direction_flag, seq_plus_direction + 417 4); //0x12345678FFFFFFFF 418 RC4(K9, seq_plus_direction, 8, WRAP_seq); 419 420 for (i = 0; i < 16; i++) K10 [i] ^= 0xF0; // XOR each byte 421 of key with 0xF0 422 T = 0; 423 if (fRC4_EXP){ 424 *(DWORD *)(L40+10) = T; 425 HMAC(K10, L40, 14, K11); 426 memset(K11+7, 0xAB, 9); 427 }else{ 428 HMAC(K10, &T, 4, K11); 429 } 430 HMAC(K11, seq_num, 4, K12); 431 RC4(K12, T_hdr_conf_msg_pad + 4 + 8, 8 + msg_len + 1, 432 edata); /* skip T & hdr */ 433 edata_len = 8 + msg_len + 1; // conf + msg_len + pad 434 } 435 436 437 The character constant "fortybits" evolved from the time when a 40- 438 bit key length was all that was exportable from the United States. 439 It is now used to recognize that the key length is of "exportable" 440 length. In this description, the key size is actually 56-bits. 441 4429. Security Considerations 443 444 Care must be taken in implementing this encryption type because it 445 uses a stream cipher. If a different IV isn�t used in each direction 446 when using a session key, the encryption is weak. By using the 447 sequence number as an IV, this is avoided. 448 44910. Acknowledgements 450 451 We would like to thank Salil Dangi for the valuable input in 452 refining the descriptions of the functions and review input. 453 45411. References 455 456 1 Bradner, S., "The Internet Standards Process -- Revision 3", BCP 457 9, RFC 2026, October 1996. 458 459 2 Bradner, S., "Key words for use in RFCs to Indicate Requirement 460 Levels", BCP 14, RFC 2119, March 1997 461 462 3 Krawczyk, H., Bellare, M., Canetti, R.,"HMAC: Keyed-Hashing for 463 Message Authentication", RFC 2104, February 1997 464 465 4 Kohl, J., Neuman, C., "The Kerberos Network Authentication 466 Service (V5)", RFC 1510, September 1993 467 468 469 470Swift Category - Informational 8 471 472 Windows 2000 RC4-HMAC Kerberos E-Type June 2000 473 474 475 476 5 Linn, J., "The Kerberos Version 5 GSS-API Mechanism", RFC-1964, 477 June 1996 478 479 6 R. Rivest, "The MD4 Message-Digest Algorithm", RFC-1320, April 480 1992 481 482 7 R. Rivest, "The MD5 Message-Digest Algorithm", RFC-1321, April 483 1992 484 485 8 Thayer, R. and K. Kaukonen, "A Stream Cipher Encryption 486 Algorithm", Work in Progress. 487 488 9 RC4 is a proprietary encryption algorithm available under license 489 from RSA Data Security Inc. For licensing information, contact: 490 491 RSA Data Security, Inc. 492 100 Marine Parkway 493 Redwood City, CA 94065-1031 494 495 10 Neuman, C., Kohl, J., Ts'o, T., "The Kerberos Network 496 Authentication Service (V5)", draft-ietf-cat-kerberos-revisions- 497 04.txt, June 25, 1999 498 499 50012. Author's Addresses 501 502 Mike Swift 503 Dept. of Computer Science 504 Sieg Hall 505 University of Washington 506 Seattle, WA 98105 507 Email: mikesw@cs.washington.edu 508 509 John Brezak 510 Microsoft 511 One Microsoft Way 512 Redmond, Washington 513 Email: jbrezak@microsoft.com 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529Swift Category - Informational 9 530 531 Windows 2000 RC4-HMAC Kerberos E-Type October 1999 532 533 534 53513. Full Copyright Statement 536 537 "Copyright (C) The Internet Society (2000). All Rights Reserved. 538 539 This document and translations of it may be copied and 540 furnished to others, and derivative works that comment on or 541 otherwise explain it or assist in its implementation may be 542 prepared, copied, published and distributed, in whole or in 543 part, without restriction of any kind, provided that the above 544 copyright notice and this paragraph are included on all such 545 copies and derivative works. However, this document itself may 546 not be modified in any way, such as by removing the copyright 547 notice or references to the Internet Society or other Internet 548 organizations, except as needed for the purpose of developing 549 Internet standards in which case the procedures for copyrights 550 defined in the Internet Standards process must be followed, or 551 as required to translate it into languages other than English. 552 553 The limited permissions granted above are perpetual and will 554 not be revoked by the Internet Society or its successors or 555 assigns. 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588Swift Category - Informational 10 589 590