Independent Submission X. Zhang
Request for Comments: 6479 T. Tsou
Category: Informational Futurewei Technologies
ISSN: 2070-1721 January 2012
Independent Submission X. Zhang
Request for Comments: 6479 T. Tsou
Category: Informational Futurewei Technologies
ISSN: 2070-1721 January 2012
IPsec Anti-Replay Algorithm without Bit Shifting
无移位的IPsec反重放算法
Abstract
摘要
This document presents an alternate method to do the anti-replay checks and updates for IP Authentication Header (AH) and Encapsulating Security Protocol (ESP). The method defined in this document obviates the need for bit shifting and it reduces the number of times an anti-replay window is adjusted.
本文档提供了一种替代方法，用于对IP身份验证标头（AH）和封装安全协议（ESP）进行反重放检查和更新。本文档中定义的方法消除了位移位的需要，并减少了调整防重放窗口的次数。
Status of This Memo
关于下段备忘
This document is not an Internet Standards Track specification; it is published for informational purposes.
本文件不是互联网标准跟踪规范；它是为了提供信息而发布的。
This is a contribution to the RFC Series, independently of any other RFC stream. The RFC Editor has chosen to publish this document at its discretion and makes no statement about its value for implementation or deployment. Documents approved for publication by the RFC Editor are not a candidate for any level of Internet Standard; see Section 2 of RFC 5741.
这是对RFC系列的贡献，独立于任何其他RFC流。RFC编辑器已选择自行发布此文档，并且未声明其对实现或部署的价值。RFC编辑批准发布的文件不适用于任何级别的互联网标准；见RFC 5741第2节。
Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at http://www.rfc-editor.org/info/rfc6479.
有关本文件当前状态、任何勘误表以及如何提供反馈的信息，请访问http://www.rfc-editor.org/info/rfc6479.
Copyright Notice
版权公告
Copyright (c) 2012 IETF Trust and the persons identified as the document authors. All rights reserved.
版权所有（c）2012 IETF信托基金和确定为文件作者的人员。版权所有。
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (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.
本文件受BCP 78和IETF信托有关IETF文件的法律规定的约束(http://trustee.ietf.org/license-info)自本文件出版之日起生效。请仔细阅读这些文件，因为它们描述了您对本文件的权利和限制。
Table of Contents
目录
1. Introduction ....................................................2
2. Description of New Anti-Replay Algorithm ........................3
3. Example of New Anti-Replay Algorithm ............................5
4. Security Considerations .........................................9
5. Normative References ............................................9
6. Acknowledgements ................................................9
1. Introduction ....................................................2
2. Description of New Anti-Replay Algorithm ........................3
3. Example of New Anti-Replay Algorithm ............................5
4. Security Considerations .........................................9
5. Normative References ............................................9
6. Acknowledgements ................................................9
"IP Authentication Header" [RFC4302] and "IP Encapsulating Security Payload (ESP)" [RFC4303] define an anti-replay service that employs a sliding window mechanism. The mechanism, when enabled by a receiver, uses an anti-replay window of size W. This window limits 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 the replay packet can be detected and rejected. If the packet is received, the receiver gets the sequence number S in the packet. If S is inside window (S<=WT and S>=WB), then the receiver checks the corresponding bit (location is S-WB) in the window to see if this S has already been seen. If S<WB, the packet is dropped. If S>WT and is validated, the window is advanced by (S-WT) bits. The new window becomes [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. The typical implementation (for example, the integrity algorithm [RFC4302]) is done by shifting (S-WT) bits. In normal cases, the packets arrive in order, which results in continuous updates and bit-shifting operations.
“IP身份验证头”[RFC4302]和“IP封装安全有效负载（ESP）”[RFC4303]定义了采用滑动窗口机制的防重播服务。当接收器启用该机制时，使用大小为W的反重播窗口。该窗口限制了数据包相对于迄今为止已通过身份验证的序列号最高的数据包的无序程度。窗口可以用范围[WB，WT]表示，其中WB=WT-W+1。整个反重放窗口可以看作是一串位。每个比特的值指示是否已接收并验证了具有该序列号的分组，以便可以检测并拒绝重播分组。如果接收到数据包，则接收器获得数据包中的序列号S。如果S在窗口内（S<=WT和S>=WB），则接收器检查窗口中的相应位（位置为S-WB），以查看是否已看到该S。如果S<WB，则丢弃数据包。如果S>WT且已验证，则窗口将前进（S-WT）位。新窗口变为[WB+S-WT，S]。此新窗口中的新位被设置为指示未接收到具有这些序列号的数据包。典型的实现（例如，完整性算法[RFC4302]）是通过移位（S-WT）位来完成的。在正常情况下，数据包按顺序到达，这会导致连续更新和位移位操作。
[RFC4302] and [RFC4303] define minimum window sizes of 32 and 64. But no requirement is established for minimum or recommended window sizes beyond 64 packets. The window size needs to be based on reasonable expectations for packet re-ordering. For a high-end, multi-core network processor with multiple crypto cores, a window size bigger than 64 or 128 is needed due to the varied IPsec processing latency caused by different cores. In such a case, the window sliding is tremendously costly even with hardware acceleration to do the bit shifting. This document describes an alternate method to avoid bit shifting. It only discusses the anti-replay processing at the receiving side. The processing is always safe and has no interoperability effects. Even with a window size bigger than the usual 32- or 64-bit window, no interoperability issues are caused.
[RFC4302]和[RFC4303]定义了32和64的最小窗口大小。但是，对于超过64个数据包的最小或推荐窗口大小没有任何要求。窗口大小需要基于对数据包重新排序的合理预期。对于具有多个加密内核的高端多核网络处理器，由于不同内核导致不同的IPsec处理延迟，因此需要大于64或128的窗口大小。在这种情况下，即使使用硬件加速来进行位移动，窗口滑动的成本也非常高。本文档描述了避免位移位的替代方法。它只讨论接收端的反重放处理。处理始终是安全的，并且没有互操作性影响。即使窗口大小大于通常的32位或64位窗口，也不会导致互操作性问题。
Any node employing practices that potentially cause reordering beyond the usual 32- or 64-bit window may lead to interoperability or performance problems, however. For instance, if either the sending node or routers along the path cause significant re-ordering, this can lead to inability of the receiving IPsec endpoint to process the packets, as many current implementations do not support the extensions defined in this memo. Similarly, such reordering can cause significant problems for transport and upper-layer protocols, and is generally best avoided.
然而，任何采用可能导致超出常规32位或64位窗口的重新排序的做法的节点都可能导致互操作性或性能问题。例如，如果发送节点或路径上的路由器导致严重的重新排序，这可能导致接收IPsec端点无法处理数据包，因为许多当前实现不支持此备忘录中定义的扩展。类似地，这种重新排序可能会对传输和上层协议造成重大问题，通常最好避免。
Here we present an easy way to update the window index only, while also reducing the number window updates. 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 a power of two (2). Each block contains N bits, where N is also a power of two (2). It can be a byte (8 bit) or word (32 bit), or multiple words. The supported sliding window size is (M-1)*N. However, it covers up M blocks (four blocks as shown in Figure 1). All these M blocks are circulated and become a ring of blocks, each with N bits. In this way, the supported sliding window (M-1 blocks) is always a subset window of the actual window when the window slides.
在这里，我们提供了一种只更新窗口索引的简单方法，同时还减少了窗口更新的次数。基本思想如下图所示。假设我们配置窗口大小W，它由M-1个块组成，其中M是二（2）的幂。每个块包含N位，其中N也是2的幂。它可以是一个字节（8位）或字（32位），也可以是多个字。支撑的滑动窗口尺寸为（M-1）*N。但是，它覆盖了M个块（四个块，如图1所示）。所有这些M块都循环并成为一个块环，每个块都有N位。这样，当窗口滑动时，受支持的滑动窗口（M-1块）始终是实际窗口的子集窗口。
Initially, the actual window is defined by a low- and high-end index [WB, WT], as illustrated in Figure 1.
最初，实际窗口由低端和高端索引[WB，WT]定义，如图1所示。
+--------+--------+--------+--------+
|xxxxxxcc|cccccccc|cccccccc|ccccc100|
+--------+--------+--------+--------+
^ ^
| |
WB WT
+--------+--------+--------+--------+
|xxxxxxcc|cccccccc|cccccccc|ccccc100|
+--------+--------+--------+--------+
^ ^
| |
WB WT
Figure 1: The sliding window [WB, WT] in which WT is the last validated sequence number, and the supported window size W is WT-WB+1. (x=don't care bit, c=check bit)
图1：滑动窗口[WB，WT]，其中WT是最后验证的序列号，支持的窗口大小W是WT-WB+1。（x=不关心位，c=检查位）
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 and WB (WB is automatically changed as the window size is fixed). So, S becomes the largest sequence number of the received packets. Figure 2 shows the case that the packet with sequence number S=WT+1 is received.
如果我们收到序列号大于WT的数据包，我们滑动窗口。但我们仅通过将差值（S-WT）添加到WT和WB（当窗口大小固定时，WB会自动更改）来更改窗口索引。因此，S成为所接收分组的最大序列号。图2显示了接收序列号为S=WT+1的数据包的情况。
+--------+--------+--------+--------+
|xxxxxxcc|cccccccc|cccccccc|ccccc110|
+--------+--------+--------+--------+
^ ^
| |
WB WT
+--------+--------+--------+--------+
|xxxxxxcc|cccccccc|cccccccc|ccccc110|
+--------+--------+--------+--------+
^ ^
| |
WB WT
Figure 2: The sliding window [WB, WT] after S=WT+1
Figure 2: The sliding window [WB, WT] after S=WT+1
If S is in a 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 one block. Figure 3 shows that the sequence number already passed the block boundary. Immediately after the update, all the check bits should be 0 in the block where WT resides.
如果S与WT位于不同的块中，我们必须将块中的所有位值初始化为0，而不进行位移位。如果S通过几个块，我们必须初始化几个块，而不是只初始化一个块。图3显示序列号已通过块边界。更新之后，WT所在块中的所有检查位应立即为0。
+--------+--------+--------+--------+
|ccc10000|xxxxcccc|cccccccc|cccccccc|
+--------+--------+--------+--------+
^ ^
| |
WT WB
+--------+--------+--------+--------+
|ccc10000|xxxxcccc|cccccccc|cccccccc|
+--------+--------+--------+--------+
^ ^
| |
WT WB
Figure 3: The sliding window [WB, WT] after S passes the boundary
图3:S通过边界后的滑动窗口[WB，WT]
After the 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. In this way, the bit shifting is deemed unnecessary.
更新后，新窗口仍覆盖已配置的窗口。这意味着配置的子窗口也会滑动，符合滑动窗口协议。实际效果有点像移动块。这样，位移位被认为是不必要的。
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. Instead, it only depends on the sequence number of the received packet. 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).
使用序列号检查窗口也更容易、更快，因为序列号检查不依赖于最低索引WB。相反，它只取决于所接收数据包的序列号。如果我们收到序列号S，则位位置是序列号的最低几位，这仅取决于块大小（N）。块索引是位置位之前的几个位，位置位仅取决于窗口大小（M）。
We do not specify how many redundancy bits are needed, except that it should be a power of two (2) for computation efficiency. If the microprocessor is 32 bits, 32 might be a better choice while 64 might be better for 64-bit microprocessor. For a microprocessor with cache support, one cache line is also a good choice. It also depends on the size of the sliding window. If we have N redundancy bits (for example, 32 bits in the above description), we only need 1/N times update of blocks, comparing to the bit-shifting algorithm in [RFC4302].
我们没有指定需要多少冗余位，只是为了提高计算效率，它应该是两（2）的幂。如果微处理器为32位，则32位可能是更好的选择，而64位可能更适合64位微处理器。对于支持缓存的微处理器，一条缓存线也是一个不错的选择。它还取决于滑动窗口的大小。如果我们有N个冗余位（例如，上述描述中的32位），与[RFC4302]中的位移位算法相比，我们只需要1/N倍的块更新。
The cost of this method is extra byte(s) being used as a redundant window. 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 where index WB resides, i.e., the supported window size could be (M-1)*N, plus the unused bits in the last block.
此方法的成本是将额外字节用作冗余窗口。如果窗口足够大，成本将是最低的。实际上，额外的冗余位并没有完全浪费掉。我们可以重用索引WB所在的块中未使用的位，即支持的窗口大小可以是（M-1）*N，加上最后一个块中未使用的位。
Here is the example code to implement the algorithm of anti-replay checks and updates, which is described in the previous sections.
下面是实现反重播检查和更新算法的示例代码，在前面的部分中进行了描述。
<CODE BEGINS>
<代码开始>
/**
* Copyright (c) 2012 IETF Trust and the persons identified as
* authors of the code. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, is permitted pursuant to, and subject to the license
* terms contained in, the Simplified BSD License set forth in Section
* 4.c of the IETF Trust's Legal Provisions Relating to IETF Documents
* (http://trustee.ietf.org/license-info).
*
*/
/**
* Copyright (c) 2012 IETF Trust and the persons identified as
* authors of the code. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, is permitted pursuant to, and subject to the license
* terms contained in, the Simplified BSD License set forth in Section
* 4.c of the IETF Trust's Legal Provisions Relating to IETF Documents
* (http://trustee.ietf.org/license-info).
*
*/
/**
* In this algorithm, the hidden window size must be a power of two,
* for example, 1024 bits. The redundant bits must also be a power of
* two, for example 32 bits. Thus, the supported anti-replay window
* size is the hidden window size minus the redundant bits. It is 992
* in this example. The size of the integer depends on microprocessor
* architecture. In this example, we assume that the software runs on
* a 32-bit microprocessor. So the size of the integer is 32. In order
* to convert the bitmap into an array of integers, the total number of
* integers is the hidden window size divided by the size of the
* integer.
*
/**
* In this algorithm, the hidden window size must be a power of two,
* for example, 1024 bits. The redundant bits must also be a power of
* two, for example 32 bits. Thus, the supported anti-replay window
* size is the hidden window size minus the redundant bits. It is 992
* in this example. The size of the integer depends on microprocessor
* architecture. In this example, we assume that the software runs on
* a 32-bit microprocessor. So the size of the integer is 32. In order
* to convert the bitmap into an array of integers, the total number of
* integers is the hidden window size divided by the size of the
* integer.
*
* struct ipsec_sa contains the window and window related parameters, * such as the window size and the last acknowledged sequence number. * * all the value of macro can be changed, but must follow the rule * defined in the algorithm. */
* struct ipsec_sa包含窗口和与窗口相关的参数*，例如窗口大小和最后确认的序列号。**宏的所有值都可以更改，但必须遵循算法中定义的规则**/
#define SIZE_OF_INTEGER 32 /** 32-bit microprocessor */
#define BITMAP_LEN (1024/ SIZE_OF_INTEGER)
/** in terms of the 32-bit integer */
#define BITMAP_INDEX_MASK (IPSEC_BITMAP_LEN-1)
#define REDUNDANT_BIT_SHIFTS 5
#define REDUNDANT_BITS (1<<REDUNDANT_BIT_SHIFTS)
#define BITMAP_LOC_MASK (IPSEC_REDUNDANT_BITS-1)
#define SIZE_OF_INTEGER 32 /** 32-bit microprocessor */
#define BITMAP_LEN (1024/ SIZE_OF_INTEGER)
/** in terms of the 32-bit integer */
#define BITMAP_INDEX_MASK (IPSEC_BITMAP_LEN-1)
#define REDUNDANT_BIT_SHIFTS 5
#define REDUNDANT_BITS (1<<REDUNDANT_BIT_SHIFTS)
#define BITMAP_LOC_MASK (IPSEC_REDUNDANT_BITS-1)
int
ipsec_check_replay_window (struct ipsec_sa *ipsa,
uint32_t sequence_number)
{
int bit_location;
int index;
int
ipsec_check_replay_window (struct ipsec_sa *ipsa,
uint32_t sequence_number)
{
int bit_location;
int index;
/**
* replay shut off
*/
if (ipsa->replaywin_size == 0) {
return 1;
}
/**
* replay shut off
*/
if (ipsa->replaywin_size == 0) {
return 1;
}
/**
* first == 0 or wrapped
*/
if (sequence_number == 0) {
return 0;
}
/**
* 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 */
}
/**
* first check if the sequence number is in the range
*/
if (sequence_number>ipsa->replaywin_lastseq) {
return 1; /** larger is always good */
}
/**
* The packet is too old and out of the window
*/
if ((sequence_number + ipsa->replaywin_size) <
ipsa->replaywin_lastseq) {
return 0;
}
/**
* The packet is too old and out of the window
*/
if ((sequence_number + ipsa->replaywin_size) <
ipsa->replaywin_lastseq) {
return 0;
}
/**
* The sequence is inside the sliding window
* now check the bit in the bitmap
* bit location only depends on the sequence number
*/
bit_location = sequence_number&BITMAP_LOC_MASK;
index = (sequence_number>>REDUNDANT_BIT_SHIFTS)&BITMAP_INDEX_MASK;
/**
* The sequence is inside the sliding window
* now check the bit in the bitmap
* bit location only depends on the sequence number
*/
bit_location = sequence_number&BITMAP_LOC_MASK;
index = (sequence_number>>REDUNDANT_BIT_SHIFTS)&BITMAP_INDEX_MASK;
/*
* this packet has already been received
*/
if (ipsa->replaywin_bitmap[index]&(1<<bit_location)) {
return 0;
}
/*
* this packet has already been received
*/
if (ipsa->replaywin_bitmap[index]&(1<<bit_location)) {
return 0;
}
return 1;
}
return 1;
}
int
ipsec_update_replay_window (struct ipsec_sa *ipsa,
uint32_t sequence_number)
{
int bit_location;
int index, index_cur, id;
int diff;
int
ipsec_update_replay_window (struct ipsec_sa *ipsa,
uint32_t sequence_number)
{
int bit_location;
int index, index_cur, id;
int diff;
if (ipsa->replaywin_size == 0) { /** replay shut off */
return 1;
}
if (ipsa->replaywin_size == 0) { /** replay shut off */
return 1;
}
if (sequence_number == 0) {
return 0; /** first == 0 or wrapped */
}
if (sequence_number == 0) {
return 0; /** first == 0 or wrapped */
}
/**
* the packet is too old, no need to update
*/
if ((ipsa->replaywin_size + sequence_number) <
ipsa->replaywin_lastseq) {
return 0;
}
/**
* the packet is too old, no need to update
*/
if ((ipsa->replaywin_size + sequence_number) <
ipsa->replaywin_lastseq) {
return 0;
}
/**
* now update the bit
*/
index = (sequence_number>>REDUNDANT_BIT_SHIFTS);
/**
* 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) { /* something unusual in this case */
diff = BITMAP_LEN;
}
/**
* 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) { /* something unusual in this case */
diff = BITMAP_LEN;
}
for (id = 0; id < diff; ++id) {
ipsa->replaywin_bitmap[(id+index_cur+1)&BITMAP_INDEX_MASK]
= 0;
}
for (id = 0; id < diff; ++id) {
ipsa->replaywin_bitmap[(id+index_cur+1)&BITMAP_INDEX_MASK]
= 0;
}
ipsa->replaywin_lastseq = sequence_number;
}
ipsa->replaywin_lastseq = sequence_number;
}
index &= BITMAP_INDEX_MASK;
bit_location = sequence_number&BITMAP_LOC_MASK;
index &= BITMAP_INDEX_MASK;
bit_location = sequence_number&BITMAP_LOC_MASK;
/* this packet has already been received */
if (ipsa->replaywin_bitmap[index]&(1<<bit_location)) {
return 0;
}
/* this packet has already been received */
if (ipsa->replaywin_bitmap[index]&(1<<bit_location)) {
return 0;
}
ipsa->replaywin_bitmap[index] |= (1<<bit_location);
ipsa->replaywin_bitmap[index] |= (1<<bit_location);
return 1;
}
return 1;
}
<CODE ENDS>
<代码结束>
This document does not change [RFC4302] or [RFC4303]. It provides an alternate method for anti-replay.
本文件未更改[RFC4302]或[RFC4303]。它为反重播提供了另一种方法。
The idea in this document came from the software design on one high-performance multi-core network processor. The new network processor core integrates a dozen of crypto core in a distributed way, which makes hardware anti-replay service impossible.
本文档中的想法来自于一个高性能多核网络处理器上的软件设计。新的网络处理器内核以分布式方式集成了十几个加密内核，这使得硬件防重放服务变得不可能。
[RFC4302] Kent, S., "IP Authentication Header", RFC 4302, December 2005.
[RFC4302]Kent，S.，“IP认证头”，RFC43022005年12月。
[RFC4303] Kent, S., "IP Encapsulating Security Payload (ESP)", RFC 4303, December 2005.
[RFC4303]Kent，S.，“IP封装安全有效载荷（ESP）”，RFC 4303，2005年12月。
Authors' Addresses
作者地址
Xiangyang Zhang Futurewei Technologies 2330 Central Expressway Santa Clara, California 95051 USA
美国加利福尼亚州圣克拉拉市中心高速公路2330号向阳张未来威科技有限公司95051
Phone: +1-408-330-4545
EMail: xiangyang.zhang@huawei.com
Phone: +1-408-330-4545
EMail: xiangyang.zhang@huawei.com
Tina Tsou (Ting Zou) Futurewei Technologies 2330 Central Expressway Santa Clara, California 95051 USA
Tina Tsou（邹婷）Futurewei Technologies 2330美国加利福尼亚州圣克拉拉中央高速公路95051
Phone: +1-408-859-4996
EMail: tena@huawei.com
Phone: +1-408-859-4996
EMail: tena@huawei.com