Network Working Group Xiangyang Zhang Internet-Draft Tina Tsou Intended status: Informational Futurewei Technologies, Inc Expires: November 10, 2011 May 10, 2011 IPsec anti-replay algorithm without bit-shifting draft-zhang-ipsecme-anti-replay-00 Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. 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. Distribution of this memo is unlimited. This Internet-Draft will expire on November 10, 2011. Copyright Notice Copyright (c) 2011 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents Zhang-Tsou Expires November 10, 2011 [Page 1] Internet-Draft IPsec anti-replay 1.0 May 2011 (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the BSD License. Abstract This document presents a new method to do anti-replay check and update, which becomes one alternative to the anti-replay algorithm in RFC 4302 and RFC4303. The new method will deem the bit-shifting unnecessary. It will reduce the number of times to slide the window. In addition, it makes bit-check and bit-update easier as it does not depend on the low index of the sliding window. It is especially beneficial when the window size is much bigger than 64 bits, for example, 1024 bits. IPsec employs one anti-replay sliding window protocol to secure against an adversary that can insert the messages inside the network tunnel. This method still inherits the sliding window protocol, but use one or more redundant bytes to ease the update of sliding window. The bit-shifting is deemed unnecessary with updating the high and low index of the window, which is especially efficient in case of the big window size. Thus the method reduces the number of times to update the window. In addition, the bit location is fixed for one sequence number, thus makes the bit check easier and faster. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Description of new anti-replay algorithm . . . . . . . . . . . 3 3. Example of new anti-replay algorithm . . . . . . . . . . . . . 6 4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 9 5. Security considerations . . . . . . . . . . . . . . . . . . . 9 6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 9 Zhang-Tsou Expires November 10, 2011 [Page 2] Internet-Draft IPsec anti-replay 1.0 May 2011 1. Introduction IPsec standard defines the anti-replay sliding window protocol, where the receiver must maintain an anti-replay window of size W. This window will limit how far out of order a packet can be, relative to the packet with the highest sequence number that has been authenticated so far. The window can be represented by a range [WB, WT], where WB=WT-W+1. The whole anti-replay window can be thought of as a string of bits. The value of each bit indicates whether or not a packet with that sequence number has been received and authenticated, so that replay packet can be detected and rejected. If the packet is received, the receiver will get the sequence number S in the packet. If S is inside window (S<=WT and S>=WB), then check the corresponding bit (location is S-WB) in the window to see if this S has already been seen. If SWT and is validated, the window is advanced by (S-WT) bits. The new window will become [WB+S-WT, S]. The new bits in this new window are set to indicate that no packets with those sequence numbers have been received yet. The typical implementation (for example, RFC-2401 algorithm) is done by shifting (S-WT) bits. In normal cases, the packets arrive in order, which results in constant update and bit shifting operation. The minimum window size can be 32 or 64. But no requirement is established for minimum or recommended window sizes beyond 64-packet. The actual window size is required to be based on reasonable expectations for packet re-ordering. For high-end multi-core network processor with multiple crypto cores, the window size should be much bigger than 64bits or 128bits. In this case, the window sliding is tremendous costly even with hardware acceleration to do the bit shifting. Here we recommend one method to make the bit-shifting unnecessary. 2 Description of new anti-replay algorithm Here we present an easy way to only update the window index and also reduce the times of updating the window. The basic idea is illustrated in the following figures. Suppose that we configure the window size W, which consists of M-1 blocks, where M is power of two (2). Each block contains N bits, where N is also power of two (2). It can be a byte (8 Zhang-Tsou Expires November 10, 2011 [Page 3] Internet-Draft IPsec anti-replay 1.0 May 2011 bit) or word (32bit), or multiple words. We hide one block from the window. So the supported window size is (M-1)*N. All these M blocks are circulated and become a ring of blocks, each with N bits. In this way, the configured window (M-1 blocks) is always a subset window of the whole window when the supported window slides. Initially the supported window is defined by low and high end index [WB, WT], which is inside the whole window as illustrated in Figure 1. +--------+--------+--------+--------+ |xxxxxccc|cccccccc|cccccccc|ccccc100| +--------+--------+--------+--------+ ^ ^ | | WB WT Figure 1: the sliding window [WB, WT], in which WT is last sequence number and window size W is WT-WB+1. (x=don?t care bit, c=check bit) If we receive a packet with the sequence number (S) greater than WT, we slide the window. But we only change the window index by adding the difference (S-WT) to both WT (WB is automatically changed as window size is fixed). So S becomes the largest sequence number of the received packet. Figure 2 shows the case that the packet with sequence number S=WT+1 is received. +--------+--------+--------+--------+ |xxxxxxcc|cccccccc|cccccccc|ccccc110| +--------+--------+--------+--------+ ^ ^ | | WB WT Figure 2: the sliding window [WB, WT] after S=WT+1 If S is in the different block from where WT is, we have to initialize all bit values in the blocks to 0 without bit shifting. If S passes several blocks, we have to initialize several blocks instead of only Zhang-Tsou Expires November 10, 2011 [Page 4] Internet-Draft IPsec anti-replay 1.0 May 2011 one block. Figure 3 shows that the sequence number already pass the block boundary. +--------+--------+--------+--------+ |ccc10000|xxxxcccc|cccccccc|cccccccc| +--------+--------+--------+--------+ ^ ^ | | WT WB Figure 3: the sliding window [WB, WT] after S pass the boundary After update, the new window still covers the configured window. This means the configured sub-window also slides, conforming to the sliding window protocol. The actual effect is somewhat like shifting the block. It is also easier and much faster to check the window with the sequence number because the sequence number check does not depend on the lowest index WB. If we receive a sequence number S, the bit location is the lowest several bits of the sequence number, which only depends on the block size (N). The block index is several bits before the location bits, which only depends on the window size (M). We do not specify how many redundancy bits needed except that it should be power of two (2) for fast computation. If microprocessor is 32bit, 32bit might be a better choice while 64bits might be better for 64bit microprocessor. For microprocessor with cache support, one cache line is also a good choice. It also depends on how big the sliding window size is. If we have N redundancy bits (for example, 32 bit in the above description), we only need 1/N times update of blocks, comparing to the bit-shifting algorithm in RFC 4302. The cost of this method is extra byte or bytes used as redundant bits. The cost will be minimal if the window size is big enough. Actually the extra redundant bits are not completely wasted. We could reuse the unused bits in the block with least significant index, i.e. the supported window size could be (M-1)*N, plus the unused bits in the last block. Zhang-Tsou Expires November 10, 2011 [Page 5] Internet-Draft IPsec anti-replay 1.0 May 2011 3 Example of new anti-replay algorithm Here is one example code to do the anti-replay check and update with this algorithm. /** * In this example, the hidden window size is 1024. * In addition, there are 32 redundant bits * Thus, the supported anti-replay window size is 992. */ #define BITMAP_LEN 32 /** in terms of 32 bit integer */ #define BITMAP_INDEX_MASK (IPSEC_BITMAP_LEN-1) #define REDUNDANT_BIT_SHIFTS 5 #define REDUNDANT_BITS (1<replaywin_size == 0) { return 1; } /** * first == 0 or wrapped */ if (sequence_number == 0) { return 0; } /** * first check if the sequence number is in the range */ if (sequence_number>ipsa->replaywin_lastseq) { return 1; /** larger is always good */ } Zhang-Tsou Expires November 10, 2011 [Page 6] Internet-Draft IPsec anti-replay 1.0 May 2011 /** * The packet is too old and out of the window */ if (ipsa->replaywin_size < (ipsa->replaywin_lastseq-sequence_number)) { return 0; } /** * The sequence is inside the sliding window * now check the bit */ bit_location = sequence_number&BITMAP_LOC_MASK; index = (sequence_number>>REDUNDANT_BIT_SHIFTS)&BITMAP_INDEX_MASK; /* * this packet already seen */ if (ipsa->replaywin_bitmap[index]&(1<replaywin_size == 0) { /** replay shut off */ return 1; } if (sequence_number == 0) { return 0; /** first == 0 or wrapped */ } Zhang-Tsou Expires November 10, 2011 [Page 7] Internet-Draft IPsec anti-replay 1.0 May 2011 /** * too old */ if (ipsa->replaywin_size < (ipsa->replaywin_lastseq-sequence_number)) { return 0; } /** * now update the bit */ index = (sequence_number>>REDUNDANT_BIT_SHIFTS); /** * first check if the sequence number is in the range */ if (sequence_number>ipsa->replaywin_lastseq) { index_cur = ipsa->replaywin_lastseq>>REDUNDANT_BIT_SHIFTS; diff = index - index_cur; if (diff > BITMAP_LEN) { diff = BITMAP_LEN; } for (id = 0; id < diff; ++id) { ipsa->replaywin_bitmap[(id+index_cur+1)&BITMAP_INDEX_MASK] = 0; } ipsa->replaywin_lastseq = sequence_number; } index &= BITMAP_INDEX_MASK; bit_location = sequence_number&BITMAP_LOC_MASK; if (ipsa->replaywin_bitmap[index]&(1<replaywin_bitmap[index] &= (1<