idnits 2.17.1 draft-zhang-ipsecme-anti-replay-07.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (October 31, 2011) is 4553 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'WB' is mentioned on line 176, but not defined == Missing Reference: 'WT' is mentioned on line 176, but not defined Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group Xiangyang Zhang 3 Internet-Draft Tina Tsou 4 Intended status: Informational Futurewei Technologies, Inc 5 Expires: April 30, 2012 October 31, 2011 7 IPsec anti-replay algorithm without bit-shifting 8 draft-zhang-ipsecme-anti-replay-07 10 Status of this Memo 12 This Internet-Draft is submitted to IETF in full conformance with 13 the provisions of BCP 78 and BCP 79. 15 Internet-Drafts are working documents of the Internet Engineering 16 Task Force (IETF), its areas, and its working groups. Note that 17 other groups may also distribute working documents as Internet- 18 Drafts. 20 Internet-Drafts are draft documents valid for a maximum of six 21 months and may be updated, replaced, or obsoleted by other documents 22 at any time. It is inappropriate to use Internet-Drafts as 23 reference material or to cite them other than as "work in progress." 25 The list of current Internet-Drafts can be accessed at 26 http://www.ietf.org/ietf/1id-abstracts.txt. 28 The list of Internet-Draft Shadow Directories can be accessed at 29 http://www.ietf.org/shadow.html. 31 Distribution of this memo is unlimited. 33 This Internet-Draft will expire on April 30, 2012. 35 Copyright Notice 37 Copyright (c) 2011 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (http://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with respect 45 to this document. Code Components extracted from this document must 46 include Simplified BSD License text as described in Section 4.e of 47 the Trust Legal Provisions and are provided without warranty as 48 described in the Simplified BSD License. 50 Abstract 52 This document presents an alternate method to do the anti-replay 53 checks and updates for IP Authentication Header (AH) and 54 Encapsulating Security Protocol (ESP). The method defined 55 in this document obviates the need for bit-shifting and it reduces 56 the number of times anti-replay window is adjusted. 58 Table of Contents 60 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 61 2. Description of new anti-replay algorithm . . . . . . . . . . . 4 62 3. Example of new anti-replay algorithm . . . . . . . . . . . . . 6 63 4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 10 64 5. Security considerations . . . . . . . . . . . . . . . . . . . 10 65 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 66 7. Normative References . . . . . . . . . . . . . . . . . . . . . 10 67 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 10 69 1. Introduction 71 IP Authentication Header (AH) [RFC4302] and IP Encapsulating Security 72 Payload (ESP) [RFC4303] define an anti-replay service that employs a 73 sliding window mechanism. The mechanism, when enabled by a 74 receiver, uses an anti-replay window of size W. This window limits 75 how far out of order a packet can be, relative to the packet 76 with the highest sequence number that has been authenticated so far. 77 The window can be represented by a range [WB, WT], where WB=WT-W+1. The 78 whole anti-replay window can be thought of as a string of bits. The 79 value of each bit indicates whether or not a packet with that sequence 80 number has been received and authenticated, so that replay packet can 81 be detected and rejected. If the packet is received, the receiver 82 gets the sequence number S in the packet. If S is inside window (S<=WT 83 and S>=WB), then checks the corresponding bit (location is S-WB) in the 84 window to see if this S has already been seen. If SWT and is validated, the window is advanced by (S-WT) 86 bits. The new window becomes [WB+S-WT, S]. The new bits in this 87 new window are set to indicate that no packets with those sequence 88 numbers have been received. The typical implementation (for 89 example, [RFC4302] algorithm) is done by shifting (S-WT) bits. 90 In normal cases, the packets arrive in order, which results in constant 91 update and bit shifting operation. 93 [RFC4302][RFC4303] defined minimum window sizes of 32 and 64. But no 94 requirement is established for minimum or recommended window sizes 95 beyond 64-packet. The window size needs to be based on reasonable 96 expectations for packet re-ordering. For a high-end multi-core network 97 processor with multiple crypto cores, a window size bigger than 64 or 98 128 is needed due to the varied IPsec processing latency caused by 99 different cores. In such a case, the window sliding is tremendous 100 costly even with hardware acceleration to do the bit shifting. 101 This draft describes an alternate method to avoid bit-shifting. 102 It only discusses the anti-replay processing at the receiving side. 103 The processing is always safe and has no interoperability effects. 104 Even with the window size beyond the usual 32 or 64 bit window, it 105 does not cause any interoperability issue. 107 Any node employing practices that potentially causes reordering 108 beyond the usual 32 or 64 bit window may lead to interoperability 109 or performance problems, however. For instance, if either the 110 sending node or routers on path cause significant re-ordering, 111 this can lead to inability of the receiving IPsec endpoint to 112 process the packets, as many current implementations do not support 113 the extensions defined in this memo. Similarly, such reordering 114 can cause significant problems for transport and upper layer 115 protocols, and is generally best avoided. 117 2 Description of new anti-replay algorithm 119 Here we present an easy way to only update the window index and also 120 reduce the times of updating the window. The basic idea is illustrated 121 in the following figures. Suppose that we configure the window size W, 122 which consists of M-1 blocks, where M is power of two (2). Each block 123 contains N bits, where N is also power of two (2). It can be a byte 124 (8 bit) or word (32bit), or multiple words. The supported sliding 125 window size is (M-1)*N. However, it covers up M blocks (four blocks 126 as shown in Figure 1). All these M blocks are circulated and become 127 a ring of blocks, each with N bits. In this way, the supported 128 sliding window (M-1 blocks) is always a subset window of the actual 129 window when window slides. 131 Initially the actual window is defined by low and high end index 132 [WB, WT], as illustrated in Figure 1. 134 +--------+--------+--------+--------+ 135 |xxxxxxcc|cccccccc|cccccccc|ccccc100| 136 +--------+--------+--------+--------+ 137 ^ ^ 138 | | 139 WB WT 141 Figure 1: the sliding window [WB, WT], 142 in which WT is last validated sequence number 143 and the supported window size W is WT-WB+1. 144 (x=don't care bit, c=check bit) 146 If we receive a packet with the sequence number (S) greater than WT, 147 we slide the window. But we only change the window index by adding 148 the difference (S-WT) to both WT (WB is automatically changed as 149 window size is fixed). So S becomes the largest sequence number of 150 the received packets. Figure 2 shows the case that the packet with 151 sequence number S=WT+1 is received. 153 +--------+--------+--------+--------+ 154 |xxxxxxcc|cccccccc|cccccccc|ccccc110| 155 +--------+--------+--------+--------+ 156 ^ ^ 157 | | 158 WB WT 160 Figure 2: the sliding window [WB, WT] after S=WT+1 162 If S is in the different block from where WT is, we have to initialize 163 all bit values in the blocks to 0 without bit shifting. If S passes 164 several blocks, we have to initialize several blocks instead of only 165 one block. Figure 3 shows that the sequence number already pass the 166 block boundary. Immediately after update, all the check bits should 167 be 0 in the block where WT resides. 169 +--------+--------+--------+--------+ 170 |ccc10000|xxxxcccc|cccccccc|cccccccc| 171 +--------+--------+--------+--------+ 172 ^ ^ 173 | | 174 WT WB 176 Figure 3: the sliding window [WB, WT] after S pass the boundary 178 After update, the new window still covers the configured window. This 179 means the configured sub-window also slides, conforming to the sliding 180 window protocol. The actual effect is somewhat like shifting the block. 181 In this way, the bit-shifting is deemed unnecessary. 183 It is also easier and much faster to check the window with the sequence 184 number because the sequence number check does not depend on the lowest 185 index WB. Instead, it only depends on the sequence number of the 186 received packet. If we receive a sequence number S, the bit location 187 is the lowest several bits of the sequence number, which only depends 188 on the block size (N). The block index is several bits before the 189 location bits, which only depends on the window size (M). 191 We do not specify how many redundancy bits needed except that it should 192 be power of two (2) for computation efficiency. If microprocessor is 193 32 bit, 32 might be a better choice while 64 might be better for 64 bit 194 microprocessor. For microprocessor with cache support, one cache line 195 is also a good choice. It also depends on how big the sliding window 196 size is. If we have N redundancy bits (for example, 32 bit in the above 197 description), we only need 1/N times update of blocks, comparing to the 198 bit-shifting algorithm in [RFC4302]. 200 The cost of this method is extra byte or bytes used as redundant window. 201 The cost will be minimal if the window size is big enough. Actually 202 the extra redundant bits are not completely wasted. We could reuse the 203 unused bits in the block where index WB resides, i.e. the supported 204 window size could be (M-1)*N, plus the unused bits in the last block. 206 3 Example of new anti-replay algorithm 208 Here is the example code to implement the algorithm of anti-replay 209 check and update, which is described in the previous sections. 211 213 /** 214 * Copyright (c) 2011 IETF Trust, Xiangyang Zhang and Tina Tsou. 215 * All rights reserved. 216 * 217 * Redistribution and use in source and binary forms, with or without 218 * modification, is permitted pursuant to, and subject to the license 219 * terms contained in, the Simplified BSD License set forth in Section 220 * 4.c of the IETF Trust's Legal Provisions Relating to IETF Documents 221 * (http://trustee.ietf.org/license-info). 222 * 223 */ 225 /** 226 * In this algorithm, the hidden window size must be a power of two, 227 * for example, 1024 bits. The redundant bits must also be a power of 228 * two, for example 32 bits. Thus, the supported anti-replay window 229 * size is the hidden window size minus the redundant bits. It is 992 230 * in this example. The size of integer depends on microprocessor 231 * architecture. In this example, we assume that the software runs on 232 * 32 bit microprocessor. So the size of integer is 32. In order to 233 * convert the bitmap into an array of integer, the total number of 234 * integers is the hidden window size divided by size of integer. 235 * 236 * struct ipsec_sa contains the window and window related parameters, 237 * such as the window size, the last acknowledged sequence number. 238 * 239 * all the value of macro can be changed, but must follow the rule 240 * defined in the algorithm. 241 */ 243 #define SIZE_OF_INTEGER 32 /** 32 bit microprocessor */ 244 #define BITMAP_LEN (1024/ SIZE_OF_INTEGER) 245 /** in terms of 32 bit integer */ 246 #define BITMAP_INDEX_MASK (IPSEC_BITMAP_LEN-1) 247 #define REDUNDANT_BIT_SHIFTS 5 248 #define REDUNDANT_BITS (1<replaywin_size == 0) { 262 return 1; 263 } 265 /** 266 * first == 0 or wrapped 267 */ 268 if (sequence_number == 0) { 269 return 0; 270 } 272 /** 273 * first check if the sequence number is in the range 274 */ 275 if (sequence_number>ipsa->replaywin_lastseq) { 276 return 1; /** larger is always good */ 277 } 279 /** 280 * The packet is too old and out of the window 281 */ 282 if ((sequence_number + ipsa->replaywin_size) < 283 ipsa->replaywin_lastseq) { 284 return 0; 285 } 286 /** 287 * The sequence is inside the sliding window 288 * now check the bit in the bitmap 289 * bit location only depends on sequence number 290 */ 291 bit_location = sequence_number&BITMAP_LOC_MASK; 292 index = (sequence_number>>REDUNDANT_BIT_SHIFTS)&BITMAP_INDEX_MASK; 294 /* 295 * this packet already seen 296 */ 297 if (ipsa->replaywin_bitmap[index]&(1<replaywin_size == 0) { /** replay shut off */ 313 return 1; 314 } 316 if (sequence_number == 0) { 317 return 0; /** first == 0 or wrapped */ 318 } 320 /** 321 * the packet is too old, no need to update 322 */ 323 if ((ipsa->replaywin_size + sequence_number) < 324 ipsa->replaywin_lastseq) { 325 return 0; 326 } 327 /** 328 * now update the bit 329 */ 330 index = (sequence_number>>REDUNDANT_BIT_SHIFTS); 332 /** 333 * first check if the sequence number is in the range 334 */ 335 if (sequence_number>ipsa->replaywin_lastseq) { 336 index_cur = ipsa->replaywin_lastseq>>REDUNDANT_BIT_SHIFTS; 337 diff = index - index_cur; 338 if (diff > BITMAP_LEN) { /* something unusual in this case */ 339 diff = BITMAP_LEN; 340 } 342 for (id = 0; id < diff; ++id) { 343 ipsa->replaywin_bitmap[(id+index_cur+1)&BITMAP_INDEX_MASK] 344 = 0; 345 } 347 ipsa->replaywin_lastseq = sequence_number; 348 } 350 index &= BITMAP_INDEX_MASK; 351 bit_location = sequence_number&BITMAP_LOC_MASK; 353 /* this packet already seen */ 354 if (ipsa->replaywin_bitmap[index]&(1<replaywin_bitmap[index] |= (1< 364 4. Acknowledgements 366 The idea in this document came from the software design on one 367 high-performance multi-core network processor. The new network 368 processor core integrates a dozen of crypto core in distributed way, 369 which makes hardware anti-replay service impossible. 371 5. Security considerations 373 This document does not change [RFC4302] or [RFC4303]. It provides 374 an alternate method for anti-replay. 376 6. IANA Considerations 378 None. 380 7. Normative References 382 [RFC4302] "IP Authentication Header", RFC 4302. 383 [RFC4303] "IP Encapsulating Security Payload (ESP)", RFC 4303. 385 Author's address 387 Xiangyang Zhang 388 Futurewei Technologies 389 2330 Central Expressway 390 Santa Clara, California 95051 391 USA 393 Phone: +1-408-330-4545 394 Email: xiangyang.zhang@huawei.com 396 Tina TSOU (Ting ZOU) 397 Futurewei Technologies 398 2330 Central Expressway 399 Santa Clara, California 95051 400 USA 402 Phone: +1-408-859-4996 403 Email: tena@huawei.com