Network Working Group J. Etienne Internet-Draft Free world Expires: October 30, 2001 May 2001 Anti Replay Authentication draft-etienne-anti-replay-auth-00.txt Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other 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. This Internet-Draft will expire on October 30, 2001. Copyright Notice Copyright (C) The Internet Society (2001). All Rights Reserved. Abstract The anti-replay authentication is a new method which intends to solve the weaknesses we exposed. It offers a safer MAC function, an authentication of the IP header, a strict anti-replay across reset, and automatic re-keying. In this section, we describe the elements of the authentication field, the MAC calculation and the anti-replay mechanism. Etienne Expires October 30, 2001 [Page 1] Internet-Draft Anti Replay Authentication May 2001 Table of Contents 1. misc . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Authentication field . . . . . . . . . . . . . . . . . . . . 4 3. MAC calculation . . . . . . . . . . . . . . . . . . . . . . 5 4. Anti-replay with shared key . . . . . . . . . . . . . . . . 6 5. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 7 5.1 Initialisation . . . . . . . . . . . . . . . . . . . . . . . 7 5.2 Sending packets . . . . . . . . . . . . . . . . . . . . . . 7 5.3 Receiving packets . . . . . . . . . . . . . . . . . . . . . 7 5.4 Which packet is newer ? . . . . . . . . . . . . . . . . . . 7 5.5 Generation . . . . . . . . . . . . . . . . . . . . . . . . . 8 6. Hierarchical Sequence Numbers . . . . . . . . . . . . . . . 9 6.1 non-volatile memory . . . . . . . . . . . . . . . . . . . . 9 6.1.1 I/O Frequency . . . . . . . . . . . . . . . . . . . . . . . 9 6.1.2 Space requirement . . . . . . . . . . . . . . . . . . . . . 9 7. Automatic re-keying . . . . . . . . . . . . . . . . . . . . 10 7.1 Derivation . . . . . . . . . . . . . . . . . . . . . . . . . 10 7.2 Synchronisation . . . . . . . . . . . . . . . . . . . . . . 10 7.3 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . 11 7.4 Vulnerability . . . . . . . . . . . . . . . . . . . . . . . 11 8. Root Key Management . . . . . . . . . . . . . . . . . . . . 12 9. Future work . . . . . . . . . . . . . . . . . . . . . . . . 13 References . . . . . . . . . . . . . . . . . . . . . . . . . 14 Author's Address . . . . . . . . . . . . . . . . . . . . . . 14 Full Copyright Statement . . . . . . . . . . . . . . . . . . 15 Etienne Expires October 30, 2001 [Page 2] Internet-Draft Anti Replay Authentication May 2001 1. misc o generalize the concept of the authentication replay as much as possible o publish 2 or 3 separate memos about the application on OSPF/RIP/VRPP Etienne Expires October 30, 2001 [Page 3] Internet-Draft Anti Replay Authentication May 2001 2. Authentication field The OSPF packet header\cite[sec A.3.1]{rfc2328} includes an authentication field freely usable for any authentication method. We redefine it and append the MAC at the end of the packet. Our method keeps the core structure of the Cryptographic Authentication to make it easily pluggable in an existing OSPF implementation. The authentication field is 64 bit long and it is divided as follow: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Rsvd|KId| DCt | Generation Counter | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | Packet Counter | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ o The \emph{Reserved} and \emph{Rsv} fields are reserved for future extensions. They must be set to 0 on transmission, and are ignored on reception. o The \emph{root key identifier (KId)} has a role similar to the Key Id of the cryptographic authentication. It provides smooth root key transition and allows up to 4 distinct root keys at the same time. o The Derivation (DCt), Generation and Packet Counter are used by the anti-replay to accept or reject a packet. Etienne Expires October 30, 2001 [Page 4] Internet-Draft Anti Replay Authentication May 2001 3. MAC calculation The MAC is calculated over the whole IP packet: IP Header and OSPF packet. The IP Header is included to prevent an attacker from modifying it. Its processing is the same as in IPSec/AH\cite[sec 3.3.3]{rfc2402}. The implementation may be simplified because, in our environment, the IP header has no options. The OSPF packet processing is the same as in the cryptographic authentication\cite[sec D.4.3]{rfc2328}. Our method authenticates the packets with HMAC \cite{rfc2104} used with popular hash functions such as MD5\cite{rfc1321} or SHA1\cite{fips180-1}. HMAC has no significant impact on the performance and, according to the current public cryptanalytic knowledge, it is more secure than the secret suffix method. The HMAC function is : MAC = H( K1, H(K2, message) ) H() is the hash function. K1 and K2 are trivially derived from a secret key. Etienne Expires October 30, 2001 [Page 5] Internet-Draft Anti Replay Authentication May 2001 4. Anti-replay with shared key Authenticating packets with a MAC based on a shared secret key is common because it doesn't require one to dynamically negotiate a session key. A keying protocol\cite{rfc2409}\cite{rfc2522} may be unsuitable for several reasons: no implementation available, uses too many resources (e.g. CPU or memory) or an unsupported requirements(e.g. multicast). We present an anti-replay mechanism which can be applied in those cases. It includes a re-keying mechanism with 2 kinds of keys: the \emph{root keys} configured by the administrator and the \emph{derived keys} derived from the former. Further, to provide an anti-replay across reset with the low storage overhead, we introduce a concept of \emph{hierarchical sequence numbers}. The anti-replay is based on 3 fields: 1. The \emph{Packet Counter} is the number of packets sent by a given source during the current generation. When it rolls over, a new generation is started. 2. The \emph{Generation Counter} is the number of generation started during the current derived key. When it rolls over, a new key is derived. 3. The \emph{Derivation Counter} counts the key derivations. The first is distinct for each neighbor and is volatile, i.e. can be 'forgotten' when the source disappears. The last two are the non- volatile part. They are stored on a permanent memory at each modification and are synchronised among the neighbors. Etienne Expires October 30, 2001 [Page 6] Internet-Draft Anti Replay Authentication May 2001 5. Overview The anti-replay authentication is plugged in the interface data structure\cite[sec 9]{rfc2328}. It contains one or more root key context which, itself, include a root key ID and one or more anti- replay context. Each one is composed of a derived key, a Derivation Counter, a Generation Counter, a Sent Packet Counter and one Received Packet Counter per neighbor. In order to smooth the transition of Derivation or Generation Counter, an implementation should keep several anti-replay context in RAM. This data structure is used during 3 phases: 5.1 Initialisation When a router initializes the interface data structure, it read the corresponding Derivation Counter and Generation Counter from the non- volatile memory, increments the Generation Counter by one and zero the Sent Packet Counter. When a neighbor data structure is initialised, the Received Packet Counter is zeroed. 5.2 Sending packets Before sending a packet, the Sent Packet Counter is incremented by one. If it rolls over, the Generation Counter is incremented by one and stored. If the Generation counter rolls over, the Derivation Counter is incremented by one, a new key is derived and both are stored. The MAC is computed with the current derived key and cover the whole IP packet (section \ref{mac-coverage}). 5.3 Receiving packets The anti-replay is processed on packets received with a valid MAC. The packet is accepted only if it is newer (see section \ref{pkt- newer}). The Received Packet Counter is updated. If the Generation Counter or Derivation Counter of the received packet are different than the local ones, they are updated and stored. 5.4 Which packet is newer ? Our anti-replay accepts a packet only if it is newer than the last accepted one. It is determined using the following rules in order: 1. If 1 \le (unsigned)(DCt_{rcv} - DCt_{acc}) \le 6 (see section \ref{dct_space}), the received packet is newer. 2. If the received Generation Counter is greater than the last accepted one, the received packet is newer. Etienne Expires October 30, 2001 [Page 7] Internet-Draft Anti Replay Authentication May 2001 3. If the received Packet Counter is greater than the last accepted one from the same source, the received packet is newer. 4. The received packet isn't newer. 5.5 Generation In our environment, a generation is a set of neighbors (i.e. routers currently connected together to the same link). OSPF already keeps track of the current set to advertise it in the HELLO packets\cite[sec 7.1]{rfc2328}. To maintain the Generation Counter requires a small modification in the neighbors state machine \cite[sec 10.3]{rfc2328}: When a neighbor enters the DOWN state\cite[sec 10.1]{rfc2328} coming from another state, the Generation Counter is incremented by 1. In clear, when a neighbor leave the set, a new generation starts and the old packets can't be replayed because their Generation Counter is obsolete. Further, the Generation Counter is synchronised among the neighbors. When an accepted packet has a Generation Counter higher than the local value, the router set the local value to the received one. Etienne Expires October 30, 2001 [Page 8] Internet-Draft Anti Replay Authentication May 2001 6. Hierarchical Sequence Numbers To provide an anti-replay protection across reboot with a shared secret key, we must store a state in a non-volatile memory. To perform a write for each received packet would be expensive. We introduce \textit{hierarchical sequence numbers} in which the sequence number is split into a most significant non-volatile part, \emph{Generation Counter}, and a least significant volatile one, \emph{Packet Counter}. The most significant part is modified much less often and is the only one to be stored, so the number of writes is significantly smaller than the number of packets. 6.1 non-volatile memory The non-volatile memory requirement is a fundamental difference between our anti-replay and the usual ones. We studied its impacts and present its I/O frequency and its space requirement. 6.1.1 I/O Frequency The amount of I/O may be important when it consumes a non-negligible time(e.g. flash memory or hard disk) or when the number of writes is limited (e.g. flash memory). It may be neglected in case of battery-backed memory. In our case, four events can cause a write operation: (i) A generation starts. (ii) $2^{24}$ packets have been sent within a single generation. (iii) $2^{24}$ generations have been started. (iv) A new root key is configured. Each generation causes at least one write due to (i). The number of writes due to (ii) depends on the network usage\footnote{In the worst case, with a link of 1Gb/sec fully used by OSPF smallest packets (empty LSU of 44bytes), a write will occur every $5.5$ sec. We think that a router with such network capabilities can afford this.} , but to send more than 16 million OSPF packets within a single generation will likely be a very rare event. The I/O load due to (iii) and (iv) is considered negligible. We believe that most generations will cause only one write and the impact on the performance won't be noticeable. 6.1.2 Space requirement For each configured root key, the minimal stored parameters are : a root key identifier (2 bit), a key(128 bit for MD5, the default hash function), the total derivation counter i.e. $n$ used during derivation (128 bit), a Derivation Counter (3 bit), and a Generation Counter (24 bit). The total is 285 bit (less than 36 bytes). Etienne Expires October 30, 2001 [Page 9] Internet-Draft Anti Replay Authentication May 2001 7. Automatic re-keying Because of the anti-replay, the sequence number can't simply roll over. The communication would stop until a administrator manually configures a new key. To avoid this disruption, an automatic re- keying is provided. It is mostly used to increase the sequence number space without including it in the packet, not to provide forward secrecy\cite[sec 1.6.1]{rfc2408}. It uses the Derivation Counter, a 3 bit field which references the current derived key and can roll over. Despite the wrap around, it isn't possible to replay a packet. An older packet may have proper counter values, but the Derivation Counter would reference an obsolete derived key and the MAC verification would reject the packet. This section presents how the key is derived, and how the derivation counters are synchronized and compared. 7.1 Derivation A new key is the output of the MAC function applied to the old key. $K_0 = rootkey$. $K_{n+1} = HMAC( K_n, n )$\footnote{WORK:this formula must be reviewed by a cryptographer} $n$ is a counter as large as the HMAC output and $K_n$ the $n^{th}$ derived key. We chose HMAC because it is already required to sign the packets. 7.2 Synchronisation Because of the Derivation Counter wrap around, a sender Derivation Counter value may be equal to a receiver's one but reference a different key. To avoid this desynchronisation, when a router receives a Derivation Counter higher than its own (see section \ref{pkt-newer}), it updates it. Nevertheless, if the router is disconnected when others re-key many times, the router may be desynchronised and the fix requires an human intervention. This requires to be disconnected during $6*2^{24}$ generations\footnote{ If a new generation starts each second, a router has to stay disconnected 1165days to become desynchronised.}, so we believe these will be rare events. During normal operations, OSPF routers periodically (Default: 10sec) send HELLO packets\cite[sec 7.1]{rfc2328} to all the others. So any router will be able to synchronize with others in at most 10sec, assuming no packet loss. This convergence speed is applicable to the Generation Counter synchronisation too. Etienne Expires October 30, 2001 [Page 10] Internet-Draft Anti Replay Authentication May 2001 7.3 Comparison The Derivation Counter uses a circular space so one must be compared relative to another: The received derivation counter minus the last accepted one. $distance = (DCt_{rcv} - DCt_{acc})$. The distance is a 3 bit value which can be interpreted as unsigned or signed. To favour the synchronisation in case of long disconnection, the space has a 'newer' part bigger than in the 'older' one. If $1 \le (unsigned)distance \le 6$, the received DCt is newer. If $-1 \le (signed)distance < 0$, it is older, thus there is smooth transition between all the online routers. 7.4 Vulnerability An anti-replay service is safe if a given set (derived key, Generation Counter and Packet Counter) can be accepted only once. This is guaranteed by our scheme as long as the derived keys do not collide i.e. a derived key is never equal to an older one. If the key is derived using a perfect hash function with a 128 bit of output and the key has been derived $2^{64}$ times, the probability of a collision is $0.5$. MD5 and SHA1 are believed to have this property. We believe it isn't a practical threat because the probability is small and the re-keying is infrequent\footnote{An attacker who want a 50\% chance of collision must wait $2^{64+24}$ generations. He will wait for 100years if $9*10^{16}$ generations occur per second.}. Etienne Expires October 30, 2001 [Page 11] Internet-Draft Anti Replay Authentication May 2001 8. Root Key Management We provide a means of root key management which is used for initial configuration or if a key has been compromised. It includes a smooth key transition similar to the cryptographic authentication one. Each root key has additional parameters specifying the MAC: o The MAC algorithm (HMAC) o The Hash function (MD5 or SHA1) o The size of the output (128 bit for MD5, 180 bit for SHA1) The default value is HMAC-MD5-128. Every implementation must support it and should support HMAC-SHA1-180. Etienne Expires October 30, 2001 [Page 12] Internet-Draft Anti Replay Authentication May 2001 9. Future work WORK: this function is weird in a RFC It may be interesting to add encryption to our method. The OSPF payload (after the OSPF packet header) can be encrypted easily if we add a padding length field in the authentication field and append the initial value to the packet. To encrypt the first part of an OSPF packet header may be harder. Additionally, under some circumstances, packets can be disordered on the network and the anti-replay service may reject packets causing needless retransmissions. An anti-replay window like the AH\cite[sec 3.4.3]{rfc2402} one would reduce this problem. Etienne Expires October 30, 2001 [Page 13] Internet-Draft Anti Replay Authentication May 2001 References Author's Address Jerome Etienne Free world EMail: jetienne@arobas.net URI: http://w3.arobas.net/~jetienne Etienne Expires October 30, 2001 [Page 14] Internet-Draft Anti Replay Authentication May 2001 Full Copyright Statement Copyright (C) The Internet Society (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. Acknowledgement Funding for the RFC Editor function is currently provided by the Internet Society. Etienne Expires October 30, 2001 [Page 15]