Skip to content

算法Algorithm

认证记录的滑动重放窗

Authenticated anti-replay window · Sliding replay bitmap

在合法认证之后用最高序号和位图原子提交接收状态,允许有限乱序而拒绝重复,并说明伪造大序号、回滚和并发边界。

形式陈述 ​

AEAD完整性排除新鲜伪造,却不排除旧合法记录重送。本页对一个已固定的密钥、会话及方向维护状态 (h,b):h 是最高已接受序号,b 为 W bit位图;第 j 位为1表示序号 h−j 已接受。初态 h=−1,b=0,序号取非负整数且不允许回绕。

候选序号 s 的资格检查为:若 s>h,它尚未见过;若 0≤h−s<W 且位 h−s 为0,它在窗内且尚未见过;其余拒绝。资格通过不等于接受。还须以固定会话和方向验证完整AEAD元组;认证失败不得改变窗口。

认证成功后原子提交。若 s>h,令 d=s−h,当 d≥W 时先清空位图,否则左移d位并保留低W位,再置最低位为1、令 h=s。若 s≤h,只置位 h−s。并发实现必须在提交时重新检查资格,或把认证结果与窗口检查提交放入正确同步协议,防止两个线程同时交付同一序号。

直觉

位图记录最近一段“哪些位置来过”,而不是只存一个最大值。这样先收到2,再收到1时,仍能认出1是正常乱序,而不是一概丢弃所有小于2的记录。

窗口不保证补齐丢包,也不等待无限久的老包。向前推进后超出左边界的合法记录会被丢弃,这是有限状态预算换来的明确可用性限制。

例子与边界

取 W=4,右边最低位代表h。处理经过合法认证的序列 0,2,1,2,5,0,4:

到达s 结果 h 位图
0 接受 0 0001
2 接受 2 0101
1 接受 2 0111
2 重复拒绝 2 0111
5 接受 5 1001
0 窗外拒绝 5 1001
4 接受 5 1011

例如接受5时左移3位,旧h=2对应现在距离3,所以只留下高位1,再设置代表5的低位。最终窗口覆盖2至5,序号3仍可接受一次。

攻击者接着发送伪造的序号99。它可以通过廉价资格预检,但AEAD认证失败,状态仍是 (5,1011)。若预检时就推进到99,攻击者无需知道密钥便能把全部合法小序号挤出窗,造成拒绝服务。预检的作用是节省明显旧包的认证成本,不是授权更新状态。

认证后才提交位图
推论与应用

归纳不变量是:窗口覆盖范围内每个置1位恰对应已经提交的序号;每次交付只为资格通过且认证成功的序号发生。若h不回退,过去接受的号要么仍有置1位、要么已落到窗外,所以都不能再次交付。

跨重启继续使用同一会话密钥时,接收状态也要受恢复保护。若在交付前持久化窗口,崩溃可能导致某条已登记但尚未交付的记录被丢弃;若先交付再保存,崩溃可能造成再次交付。此处只承诺重复记录拒绝,不承诺业务恰好执行一次;业务状态与结果记录的原子提交需由更上层协议处理。回滚接收快照会重新接受旧合法元组,而这仍不是AEAD新鲜伪造。

窗口存储W位及一个序号。若机器字宽w且W可变,位图整体移位和掩码需 O(⌈W/w⌉) 字操作,单个位测试可用索引实现常数次字操作;认证还需按消息长度计AEAD成本。只有W固定且装入少量机器字时,才能把整个窗口步骤视为常数成本。

本窗口适合显式序号的有限乱序模型。TLS1.3的普通记录使用有序传输上的隐式序号,不直接采用本页窗口;ESP规范给出了独立的反重放窗口实例和扩展序号处理。

参考资料
  • Stephen Kent,RFC 4303,§3.4.3:序号初检与认证后的窗口更新;附录A:扩展序号窗口,本页不实现其回绕推断
  • RFC 5116,§1.2:重放保护不由AEAD接口本身提供
关系图谱6 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系

被这些条目使用