Skip to content

算法Algorithm

AEAD nonce的预留与重启

AEAD nonce lifecycle · Durable nonce reservation

用先持久化后使用的区间预留维持同密钥nonce唯一性,证明崩溃跳号安全,并界定回滚、克隆、并发写者与耗尽边界。

形式陈述 ​

AEAD的nonce-respecting游戏把“同一密钥下加密nonce不重复”交给调用方。本页证明的是这项状态不变量,不重证AEAD保密或完整性。固定一个方向密钥 K、一个独占分配器和不回滚的可靠稳定存储。分配器内的取号与区间切换必须串行执行或受锁等机制保护,使读取并递增next成为原子操作;只有实例唯一并不能保证多线程安全。nonce取 N=032‖u64(q),q 是序号;不同方向使用不同密钥。

稳定状态 D 是已预留序号的排他上界,易失状态为 next,end。固定块大小 B≥1,序号预算Q不超过 264。一次预留从旧 D=d<Q 开始,先原子持久化新上界 D′=min(d+B,Q),确认成功后,才在内存启用区间 [d,D′),置 next=d,end=D';若 d=Q 则拒绝并要求换钥,不做溢出回绕。每次调用返回next并递增;在 next=end 时必须重新预留。重启只读D,置 next=end=D,故以前预留但未使用的号全部跳过。

不变量为:每次实际加密使用的 q 属于某个已经持久化成功的区间,且同一分配器对每个区间中的数至多发放一次。稳定上界单调增加,所以各次预留区间互不相交。失败或结果未知的加密调用也应消耗其序号,不能因“可能没发出去”把nonce退回池中。

直觉

先发记录、再保存计数器,会留下断电窗口:记录已经被攻击者看到,计数却没有落盘,重启后又发同一号。预留把顺序倒过来,让系统宁可浪费未使用的号,也不重新使用已经可能出现过的号。

无崩溃且完整用完每块时,每B个号一次稳定写,每次取号只做常数个计数操作,稳定状态和内存状态都为常数空间。频繁崩溃可能每次只用一个号甚至一个也未用,实际稳定写摊销不能无条件仍算1/B。预留块越大,每条记录在顺利运行时分摊的稳定写越少,崩溃时可能跳过的号越多。这是写入成本与号码消耗的权衡,不改变安全不变量。

例子与边界

取 B=4,D=0。先持久化 D=4,才能使用0、1、2、3。发送0、1后崩溃,磁盘D仍为4,重启从4开始重新预留到8,因此实际发送序列是 0,1,4,5。2、3被永久丢弃没有关系,nonce唯一性不要求号码连续。

归纳证明按事件分类:发号仅使用内存区间中尚未用过的next;预留把新范围接在稳定上界之后;崩溃清除内存范围,恢复从已持久化上界之后开始。三种事件都不能产生过去已用过的号。若新上界写入未确认成功,不能启用新区间;若存储损坏无法判定最新值,应停止使用该密钥。

错误变体在使用0、1之后把D恢复到0。重新加密时再次使用 (K,N0)。检查器对真实AES-GCM加密两个等长正文 balance=100、balance=900,去掉末尾16字节标签后,密文主体异或等于明文异或。它展示了一个具体保密失败,而且执行已离开旧AEAD游戏允许的nonce-respecting范围;不是在合法游戏中破解了AEAD。

预留、发号与重启
推论与应用

普通原子写不阻止虚拟机快照回滚或磁盘克隆。若两份实例都恢复到同一D并继续使用同一K,仍会发出相同范围。必须由外部不回滚的代际、可靠独占或重新建立真正不同的密钥来解决;只在文件里同时保存一个可回滚epoch没有帮助。多个写者也要共享原子区间分配,或采用经证明不相交的nonce子域。

序号达到表示上限前必须换钥;更早还要遵守所用AEAD对记录数、总块数和失败验证次数的安全界。64位序号绝不意味着可安全发送 264 条AES-GCM记录。TLS1.3在新流量密钥下重置序号,有自己的有序连接与限额规则;本页的持久区间模型用于解释跨重启继续使用同一密钥时的额外责任。

参考资料
  • RFC 5116,§§3.1–3.2:nonce生成、检查点/非易失保存与多设备;§5.1.1:GCM重复nonce后果
  • RFC 8446,§§5.3、5.5:序号构造nonce与每密钥使用界
关系图谱6 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

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

被这些条目使用