Internet Engineering Task Force D.Au Internet Draft P.Balke Category: Informational H.Fruehauf Expires: February, 2003 C.Helbig,K.Helbig Zyfer September, 2002 Zyfer's StealthKey Management for frequent rekeying Status of this Memo This document is an Internet-Draft and is subject to all provisions of Section 10 of RFC 2026 except that the right to produce derivative works is not granted. This memo provides information for the internet community. This memo does not specify an Internet standard of any kind and does not represent a consensus by an IETF working group. 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 made obsolete 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. Copyright Notice Copyright (C) The Internet Society (2002). All Rights Reserved. Abstract This document describes a key management, designated as StealthKey Management. StealthKey Management establishes short-term keys which are derived from a common long-term key in two entities, referred to as sender and receiver, for symmetric encryption algorithms and cryptographic authentication protocols based on a common secret. Stealthkey Management covers two main parts: - Independent generation of the short-term keys by the sender and receiver from either the common long-term key and the time, or from the common long-term key and a sequence number. Helbig Informational [Page 1] Internet Draft StealthKey Management September 2002 - Synchronisation of the short-term keys between both entities. The important advantages of using StealthKey Management for message encryption and authentication are the ability to change the short- term keys frequently, without exchanges between sender and receiver and the independence of other applications for the key change process (in band). A commonly used term for key change is rekeying. The required long-term key can be established remotely through the use of known symmetric or asymmetric key protocols, or locally via manual setup. StealthKey Management improves the performance of any of today's key management protocols, by extending the protocol with the frequent changing of keys. Table of Contents 1. Introduction....................................................3 1.1 Key Management Basics.......................................3 2. Terminology.....................................................3 3. StealthKey Management Basics....................................4 4. Pseudo Random Bit Generator.....................................4 4.1 Linear Generator............................................5 4.1.1 Length................................................5 4.1.2 Seed..................................................5 4.1.3 Starting Time.........................................6 4.1.4 Increment.............................................6 4.1.5 States................................................6 4.1.6 Output................................................7 4.2 AES-256.....................................................7 4.2.1 Input and Output......................................7 4.3 Output of the PRBG..........................................7 4.4 Cryptoperiod of the Short-term Keys.........................7 5. Generation and Synchronization of Short-term Keys by H-realization...................................................8 5.1 Generation..................................................8 5.2 Synchronization.............................................9 6. Generation and Synchronization of Short-term Keys by T-realization..................................................10 6.1 Generation.................................................10 6.2 Synchronization............................................10 7. Generation and Synchronization of Short-term Keys by N-realization..................................................11 7.1 Generation.................................................11 7.2 Synchronization............................................12 8. Long-term Keys.................................................13 9. Security Considerations........................................13 Intellectual Property Statement...................................15 References........................................................15 Authors' Addresses................................................15 Full Copyright Statement..........................................16 Expiration........................................................17 Helbig Informational [Page 2] Internet Draft StealthKey Management September 2002 1. Introduction The first sections of this document provides a detailed description of StealthKey Management, while the final sections contain security considerations and references. 1.1 Key Management Basics All of the following key management definitions are given in the reference [MENZ]. "A key management is the set of techniques and procedures supporting the establishment and maintenance of keying relationships between authorized parties." "The cryptoperiod of a key is the time period over which it is valid for use by legitimate parties." Keys for encryption of data traffic may be classified on the basis of the cryptoperiod as long-term keys or short-term keys. For encryption of stored data this classification is not applicable. These keys must be available over the lifetime of the encrypted data. Again, in the reference [MENZ], the key establishment is subdivided generally into key transport and key agreement. "Key transport is a key establishment technique where one party creates or otherwise obtains a secret value, and securely transfers it to other parties. Key agreement is a key establishment technique in which a shared secret is derived by two (or more) parties as a function of information contributed by, or associated with, each of these, (ideally) such that no party can predetermine the result value." Additional variations of key establishment exist; e.g., key derivation, whereby a key is computed per session from a parameter provided in a single message by one party (e.g., timestamp) and a long-term key stored in all participating parties. 2. Terminology The following operators are used to describe algorithms: - "x^i" denotes "x to the i-th power" - "x_i" denotes "x sub i" - If the subscript (or the exponentiation) is an expression, we surround it in braces, as in "x_{i+1}". - "X||Y" denotes the result of the concatenation of the items X and Y in that order - "/" yields the quotient of integers, - "+" the addition of integers, - "-" the subtraction of integers - "*" indicates multiplication of integers. Helbig Informational [Page 3] Internet Draft StealthKey Management September 2002 3. StealthKey Management Basics The StealthKey Management does not transport encrypted short-term keys across the media, nor does it perform key agreement or key derivation functions like described in paragraph 1. Sender and receiver build short-term keys independently from each other. The synchronization is time based (H- and T-realization) or event based (N-realization). Synchronization means that for each ciphertext, the receiver determines from two, three or more short-term keys, which short-term key the sender used. The receiver may utilize various criteria for the process of determining the correct short-term key (what presupposes different protocol steps by the sender): - Criteria 1: 32 bit additional information in the plaintext (Synchronization Header, SynH) - Criteria 2: Timestamp (equal or less than 32 bits) relating to the ciphertext - Criteria 3: Sequence number of the ciphertxt (e.g., ESP sequence number [RFC 2406]) In addition to the above, other criteria are possible. This Internet draft describes the above three realizations of StealthKey Management, named as H(eader)-realization, T(ime)-realization and N(umber)-realization. In all three realizations, StealthKey Management generates short- term keys from a long-term key of 256 bits with help of a cryptographic pseudo random bit generator (PRBG). The cryptoperiod sets the PRBG clock for the generation of the short-term keys. The cryptoperiod is specified in whole seconds (H- and T-realization) or numbers of events (positive integers) by the N- realization. The time period over which the events happen is not relevant. Short-term keys are generated independently by sender and receiver. The sender uses only one short-term key at a time and the receiver uses two, three or more. For use in open networks we recommend three (two) short-term keys by the receiver in the case of H- and T-realization (N-realization), and the applications with three and two short-term keys will be the focus of this document. However, it is possible to use more than three short-term keys for H- and T-realization, if the sender and receiver generally have large time differences or large delays in the data run time in the network. 4. Pseudo Random Bit Generator The short-term keys are generated with the help of a cryptographic Helbig Informational [Page 4] Internet Draft StealthKey Management September 2002 pseudo random bit generator (PRBG), which consists of a linear congruential generator (LG) and the Advanced Encryption Standard AES-256 of block size 256 [FIPS 197]. The 256 bit key for the AES-256 is defined as the long-term key of StealthKey Management. 4.1 Linear Generator The LG is determined by fixed, open parameters for the use in open networks. In closed networks these parameters can be used as additional long-term keys. 4.1.1 Length Assume that a short-term key has m bits, where m is a positive integer. - H-realization: The length of the LG is the integer n, where n is the smallest multiple of 256 and n is greater or equal to m+32. - T- and N-realization: The length of the LG is the integer n, where n is the smallest multiple of 256 and n is greater or equal to m. 4.1.2 Seed For all realizations the seed of the LG is a randomly chosen, but fixed bit sequence s0_{n-1}...s0_1 s0_0 of the length n. Let S[0] be the positive integer what is represented by this bit sequence. For the use in open networks S[0] is the positive integer what is represented by the n/256 multiple concatenation of following hexadecimal value in big endian format: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0x7A | 0x1C | 0xAC | 0xA7 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0x71 | 0xC1 | 0xA1 | 0xCA | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0xCC | 0xC1 | 0xA1 | 0x1A | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0xAC | 0xCA | 0xC1 | 0xCA | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0xC7 | 0x77 | 0xA7 | 0xC1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0xC1 | 0xCC | 0xA1 | 0x7C | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0xA1 | 0x11 | 0x77 | 0x1A | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0x11 | 0x11 | 0xC7 | 0x1C | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Helbig Informational [Page 5] Internet Draft StealthKey Management September 2002 4.1.3 Starting Time By H- and T-realization the LG is defined with a starting time t_0. At the time t_0 the content of the LG is the seed (refer to paragraph 4.1.2). In open networks we recommend as t_0 the value (00:00:00), January 1, 1970, Universal Coordinated Time (UTC). By N-realization the LG is defined without time. 4.1.4 Increment For all realizations the increment X is a randomly chosen, but fixed positive integer that is represented by the bit sequence x_{n-1}...x_1 x_0 of the length n, where x_0 = 1. For the use in open networks X is represented by the n/256 multiple concatenation of following hexadecimal value in big endian format: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0xA7 | 0xAA | 0xCC | 0xAA | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0xCA | 0xCC | 0x1C | 0x11 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0x1A | 0xCA | 0x71 | 0x7A | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0xAA | 0x17 | 0xCC | 0xCC | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0xAA | 0xC1 | 0xAA | 0xA1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0xAC | 0x1A | 0xCC | 0x71 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0xA1 | 0x77 | 0xCC | 0xCA | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0xCC | 0xA1 | 0xAA | 0x11 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4.1.5 States The LG contains in the state 0, for all realizations, the seed s0_{n-1}...s0_1 s0_0 of the length n. Assume, that i is a positive integer. The LG contains in the state i, for all realizations, the bit sequence si_{n-1}...si_1 si_0 of the length n. Let S[i] denote the positive integer what is represented by this bit sequence in a big endian format. S[i] is to be generated from S[i-1]as follows: S[i] = (S[i-1]+X) mod 2^n Helbig Informational [Page 6] Internet Draft StealthKey Management September 2002 4.1.6 Output For all realizations the output of the LG in the state i is the bit sequence si_{n-1}...si_1 si_0 of the length n. Consider the output fragmented in d = n/256 non-overlapping bit subsequences each of length 256. Let S(i,j) be the symbol for the subsequence j of the bit sequence si_{n-1}...si_1 si_0, then: si_{n-1}...si_1 si_0 = S(i,d-1)||...||S(i,1)||S(i,0) 4.2 AES-256 The AES-256 is in the Electronic Codebook Mode (ECB). Let K be, for all realizations, a randomly chosen long-term key of the length 256 bits (big endian) for the AES-256. 4.2.1 Input and Output In the state i of the LG every subsequence S(i,j) is an input of the AES-256 encryption algorithm, along with the key K. Let the bit sequence O(i,j) of length 256 be the output of the AES-256 encryption algorithm with the key K, when S(i,j) is the input. 4.3 Output of the PRBG The output of the PRBG in the state i is, for all realizations, the bit sequence of the length n, which is the concatenation of following outputs of the AES-256 algorithm with the key K: O(i,d-1)||...||O(i,1)||O(i,0) Consider the output of the PRBG as sequence of bits: oi_{n-1}...oi_1 Oi_0 The subsequence oi_{m-1}...oi_1 oi_0 of the output of the PRBG is, for all realizations, the short-term key of the length m in the state i. Let O(i) denote the short-term key in a big endian format. For the H-realization the subsequence oi_{m+31}...oi_{m+1} oi_m of the output of the PRBG is the SynH of the length 32 in the state i. 4.4 Cryptoperiod of the Short-term Keys For the cryptoperiod r exist technical (refer paragraph 5.2 and 6.2) and cryptographic restrictions (refer paragraph 9). For H- and T- realization the following values are proposed in consideration of these restrictions and the different communication speeds: Helbig Informational [Page 7] Internet Draft StealthKey Management September 2002 - r = 200s (<=1Gbps) - r = 50s (<=5Gbps) - r = 25s (<=10Gbps) - r = 12s (<=20Gbps) For the N-realization r = 2^17 (nearly 10^5) is recommended for open networks regardless of the communication speed. 5. Generation and Synchronization of Short-term Keys by H-realization 5.1 Generation After loading the long-term key by means described in paragraph 8, short-term keys are generated independently by sender and receiver. The sender uses only one short-term key in at a time. This is the short-term key that the PRBG has generated in the state that corresponds to the actual time of the sender and the cryptoperiod. A more detailed description follows: The generation of short-term keys starts at the beginning of the encrypted connection. For the sender, the beginning of an encrypted connection is defined as the state in which the long-term key for the connection is established by the sender. The sender defines an initial time. This is the largest time value ts_0 in seconds, with A = (ts_0-t_0)/r an integer and ts_0 smaller or equal to the actual time of the sender at the beginning of the encrypted connection. The generation of the short-term keys takes place every time the actual time of the sender is equal to ts_0 increased by a multiple of cryptoperiod r. The sender has in place at the time between ts_0+i*r and ts_0+(i+1)*r the short-term key O(A+i), where i is an integer i >= 0. The receiver generates three short-term keys based on the common long-term key and the receiver time. These short-term keys are valid in the prior, present and next cryptoperiod around the receiver time. Again, for details: The generation of short-term keys starts at the beginning of the encrypted connection. For the receiver the beginning of an encrypted connection is defined as the state in which the long-term key for the connection is established by the receiver. The receiver defines an initial time. This is the largest time value tr_0 in seconds, with B = (tr_0-t_0)/r an positive integer and tr_0 smaller or equal to the actual time of the receiver at the beginning of the encrypted Helbig Informational [Page 8] Internet Draft StealthKey Management September 2002 connection. The generation of short-term keys takes place every time the actual time of the receiver is equal to tr_0 increased by a multiple of cryptoperiod r. The receiver has in place at the time between tr_0+i*r and tr_0+(i+1)*r the three short-term keys O(B+i-1), O(B+i), and O(B+i+1), where i is an integer i >= 0. In addition to every short-term key, both parties generate the SynH of 32 bits (refer to paragraph 4.3). One SynH is valid over a cryptoperiod and represents the cryptoperiod. The sender adds the current SynH to the top of each plaintext and encrypts this new plaintext with the current short-term key. 5.2 Synchronization Synchronization for the H-realization depends on time synchronization between sender and receiver. The internal clock of the sender and receiver must be periodically synchronized to Universal Coordinated Time (UTC), which can be obtained from a variety of timing sources (e.g., from NTP or other time sources, including free-running precision oscillators.) Because the sender and receiver clocks will not be perfectly synchronized and the run time of data can be different for different ciphertexts, the receiver uses the SynH, located in the plaintext, to determine the correct short-term key to be used. The receiver makes this choice for each ciphertext. The receiver decrypts at least the first 32 bits of the ciphertext with each of the actual three short-term keys and uses that key giving the right SynH as the properly valid key to decrypt the rest of the ciphertext. Let t_s be the internal time of the sender when it encrypts and sends an arbitrary plaintext. Let t_r be the internal time of the receiver when it receives and decrypts the related ciphertext. Assume t_s = UTC+d_s and d_s is the difference of the internal time to UTC. Assume t_r = UTC+d_r and d_r is the difference of the internal time to UTC. Let d_t be the absolute time necessary for the transmission of the ciphertext. A premise for decryption is that |t_r-t_s| = |d_r-d_s-d_t| < 2*r We recommend to choose an r what suffices the condition that each of the expected values for d_s, d_r and d_t is smaller than 2/3*r. Helbig Informational [Page 9] Internet Draft StealthKey Management September 2002 6. Generation and Synchronization of Short-term Keys by T-realization 6.1 Generation The generation of the short-term keys by sender and receiver happens in the same manner as by the H-realization, described in paragraph 5.1, except that SynH is generated by any of the parties. Instead, the sender adds a timestamp (time of encryption) to the top of each ciphertext. 6.2 Synchronization This synchronization, like the synchronization in 5.2, depends on time synchronization between sender and receiver. The internal clock of the sender and receiver must be periodically synchronized to Universal Coordinated Time (UTC). Because the sender and receiver clocks will not be perfectly synchronized and the run time of data can be different for different ciphertexts, the receiver uses the timestamp of the ciphertext to determine the correct short-term key to be used. The receiver makes this choice for each ciphertext. Before the decryption of the ciphertext with one of the three possible short-term keys, the receiver compares the timestamp of the ciphertext with its internal three time intervals corresponding with three cryptoperiods. The receiver determines which period the timestamp fits in and uses the related short-term key to decrypt the ciphertext. To detect ciphertext an adversary sent, the timestamp and the ciphertext must be secured with a cryptographic hash-function. The short-term key for the cryptographic hash- function is generated like the short-term key for the encryption and enlarges the length of the PRBG. A more detailed description follows: Assume that the time of the receiver is between tr_0+i*r and tr_0+(i+1)*r-1, which means that the receiver has generated and has in place three short-term keys O(B+i-1), O(B+i), and O(B+i+1), where i is an integer i>=0 (refer to paragraph 5.1). When a ciphertext with the timestamp T is received, the receiver decides which of the following relations is true and selects the corresponding short- term key: t_0+(B+i-1)*r <= T < t_0+(B+i)*r t_0+(B+i)*r <= T < t_0+(B+i+1)*r t_0+(B+i+1)*r <= T < t_0+(B+i+2)*r For r we recommend the same restrictions like in paragraph 5.2. Helbig Informational [Page 10] Internet Draft StealthKey Management September 2002 7. Generation and Synchronization of Short-term Keys by N-realization 7.1 Generation The generation of short-term keys by sender and receiver is different from H- and T- realizations. For the sender and receiver an internal sequence number C is defined to count the ciphertexts. The sender counts in C the ciphertexts he sends to the receiver and attaches the lower part of L bits (e.g. 32) of C as the external sequence number S to the ciphertexts. The counter starts with C=1. The receiver uses C to count the ciphertexts it receives from the sender. The counter has the expression C=C1*2^L+C2 and starts with C=C1=C2=0. When receiving a ciphertext with attached external sequence number S and the ciphertext is not discarded by any reason (e.g. an anti-replay detection), then the receiver adjusts its internal sequence number C using the following algorithm: C = C1*2^L+S if C2+W >= S > C2, C = (C1+1)*2^L+S if C2 > S and C2+W >= 2^L+S, C = C1*2^L+C2 else. The positive integer W is designated as acceptance window for the external sequence number of the incoming ciphertexts. When the receiver has implemented an anti replay check then W should be adapted to it, otherwise we recommend W=32. After loading the long-term key by the means described in paragraph 8, short-term keys are generated independently by sender and receiver. The sender has only one short-term key in use at a time. This is the short-term key generated by the PRBG in the state that corresponds to the actual internal sequence number of the sender and the cryptoperiod. A more detailed description follows: The sender generates the short-term key O(i*r+1) for encryption of the plaintext with the internal sequence number C=i*r+1, where i is an integer i >= 0 and r is the cryptoperiod. This short-term key is then used for all plaintexts with the internal sequence number from C=i*r+1 to C=i*r+r. The receiver generates the short-term keys based on the common long-term key and its internal sequence number. Different methods are possible how to generate and to store the short-term keys in time. One method is described here more in the detail. Helbig Informational [Page 11] Internet Draft StealthKey Management September 2002 The receiver always stores two short-term keys around the internal sequence number, valid in the prior and present or present and future cryptoperiod. After establishing the encrypted connection with the sender, the receiver immediately generates O(1) as the short-term key for its present cryptoperiod and sets symbolically any O(-r+1) as the short-term key for its prior cryptoperiod. The receiver uses following algorithm to erase and to generate short-term keys. Assume the receivers internal sequence number is C=i*r+q with i>=0 and r>=q>0. Depending on the value of q two cases exist: (a) q <= r/2 stored are O((i-1)*r+1) as the prior and O(i*r+1) as the present short-term key, (b) q > r/2 stored are O(i*r+1) as the present and O((i+1)*r+1) as the future short-term key. Assume the receiver gets a ciphertext with external sequence number and has after adjustment the new internal sequence number C=j*r+p, with j>=0 and r=>p>0 and p different from q and j different from i. Let the acceptance window W < r/2. Case (a): Only i=j is possible because W r/2 O((i-1)*r+1) will be erased, O(i*r+1) stays as the present and O((i+1)*r+1) will be generated as the future short-term key. Case (b): Two subcases exists: (b.1) j = i no change (b.2) j = i+1 the state of O(i*r+1) changes from present to prior and the state of O((i+1)*r+1) from future to present. 7.2 Synchronization Synchronization for the N-realization does not depend on time, but it depends on the external sequence number of each ciphertext, as described in paragraph 7.1. The receiver determines one short-term key for a ciphertext based on the external sequence number of the ciphertext and its internal sequence number. Helbig Informational [Page 12] Internet Draft StealthKey Management September 2002 Before the ciphertext can be decrypted with one of the two possible short-term keys, the receiver derivates its current internal sequence number from the external sequence number of the ciphertext, as described above. The receiver determines which of the cryptoperiods the external sequence number corresponds to and uses the related short-term key for decryption of the ciphertext. To detect an ciphertext an adversary has sent, the external sequence number and the ciphertext must be secured with a cryptographic hash-function like described in paragraph 6.2. A more detailed description follows: Assume that the ciphertext with the external sequence number S arrives and the corresponding internal sequence number is C, with C=C1*2^32+C2 and C=i*r+q, where C1, C2, i and q are integers with i>=0 and 0