06

消息乱序处理

Skipped Keys · Cache

收到 M3 → M1 → M2 时, 用 chain_index + 跳过 MK 缓存正确解密 · 同链乱序 vs 跨棘轮乱序

🌪️ 场景: Alice 连发 M₁ M₂ M₃ (chain_index = 1, 2, 3) · 由于网络抖动, Bob 收到顺序为 M₃ → M₁ → M₂ 📡 网络层 — 发送 vs 到达 Alice 发送顺序: M₁ idx=1 M₂ idx=2 M₃ idx=3 Bob 接收顺序 (乱): M₃ idx=3 M₁ idx=1 M₂ idx=2 🛠️ Bob 端处理 — 三步走 Step ① 收到 M₃ (idx=3) 收到前状态: CK_recv = CK₀, idx=0 cache = {} 问题: msg.idx=3 但我在 idx=0 → 缺 idx=1,2 的 MK 动作 (前进 ChainKey 直到 idx=3): CK₀ → KDF → CK₁, MK₁ (缓存) CK₁ → KDF → CK₂, MK₂ (缓存) CK₂ → KDF → CK₃, MK₃ (使用 → 解 M₃) 收到后状态: CK_recv = CK₃, idx=3 cache = {1: MK₁, 2: MK₂} ✅ M₃ 解密成功 ⚠ MK₃ 立即清除 (用完即丢) Step ② 收到 M₁ (idx=1) 收到前状态: CK_recv = CK₃, idx=3 cache = {1: MK₁, 2: MK₂} 问题: msg.idx=1 在我已推过的范围内 (过去) 动作 (查 cache): cache.lookup(idx=1) → MK₁ decrypt(M₁, MK₁) → 明文 cache.evict(1) → 删除 MK₁ 收到后状态: CK_recv = CK₃, idx=3 cache = {2: MK₂} ✅ M₁ 解密成功 📌 ChainKey 没有倒退 Step ③ 收到 M₂ (idx=2) 收到前状态: CK_recv = CK₃, idx=3 cache = {2: MK₂} 问题: msg.idx=2 在我已推过的范围内 (过去) 动作 (查 cache): cache.lookup(idx=2) → MK₂ decrypt(M₂, MK₂) → 明文 cache.evict(2) → 删除 MK₂ 最终状态: CK_recv = CK₃, idx=3 cache = {} 全部消费 ✅ M₂ 解密成功 · 三条全部送达 🔀 进阶: 跨棘轮乱序 — 旧 RecvChain 的 skipped MK 也要保留 场景: Alice 发了 (M₁ M₂ M₃), 然后 Bob 回了一条 → Alice 的下一条 M₄ 用了新 ratchet_key (DH 翻转) 问题: Bob 先收到 M₄ (新链, ratchet_key 变化) → RecvChain reset → 旧的 M₁ M₂ M₃ 后到时, 当前 RecvChain 已经不对应了 解决: Reset RecvChain 时, 先把旧链上未消费的 MK 全部缓存到一个二级 cache (按 ratchet_key 分组) 缓存上限: libsignal: MAX_SKIPPED = 1000 Olm/vodozemac: ≈ 40~2000 超过上限的旧 MK 直接丢弃 (DoS 防护) ⚠ 副作用: 超过 MAX_SKIPPED 的 idx 跳跃将导致永久无法解密那些消息 (例如恶意客户端故意制造大跳跃) 💡 带走结论 同链乱序: chain_index 快进 + skipped MK 缓存 跨链乱序: reset RecvChain 前把旧链未消费 MK 转存二级缓存 · MAX_SKIPPED 限制内才能恢复
规则

chain_index — 乱序的"路标"

  • • 每条加密消息头部携带 chain_index (u32)
  • • 表示这条消息在当前 ChainKey 下是第几个
  • • 比当前 idx 大 → 快进 ChainKey 并缓存中间 MK
  • • 小于等于 → 查 cache; 找不到则解密失败
缓存

Skipped MK Store

  • • 一级缓存: 当前 RecvChain 内的未到达 MK
  • • 二级缓存: 旧 RecvChain (上一个 ratchet_key) 的剩余 MK
  • • 索引方式: (ratchet_key, chain_index) → MK
  • • 命中即用 + 立即从缓存清除
DoS

MAX_SKIPPED — 内存防护

  • • 防止恶意一方发送 idx=10⁹ 触发巨量计算
  • • libsignal: 1000; Olm/vodozemac: 默认 ~40, 可调
  • • 超限消息直接 reject (返回错误)
  • • 上限 + UI 重发机制 = 工程权衡
💡 一句话理解： Symmetric Ratchet 的 ChainKey "只能向前转，不能倒回"—— 但乱序消息不是真的"倒回"，而是"先把链快进到目标位置, 把跳过的 MK 暂存"。 DH 翻转后的旧链 MK 也要保留一段, 这就是为什么实现 Double Ratchet 比讲解它要复杂得多。

📚 基础知识速查 · Reference

不熟悉以下底层概念? 这里是 30 秒回顾。

算法AEAD MAC 校验

解密前必须先校验 MAC, 失败立即丢弃且不暴露错误细节 (防侧信道)。这是抗篡改的关键。

verify_mac() → if fail: discard

协议字段chain_index

u64 计数器, 标识消息在当前 ChainKey 序列中的位置, 从 0 开始递增。每次推进一格 ChainKey 时 +1。

pub chain_index: u64

工程MAX_SKIPPED 上限

防止恶意客户端发 idx=10⁹ 触发 OOM。libsignal 默认 1000, vodozemac/Olm 默认 ~40 (可调)。

const MAX_SKIPPED: u32 = 1000;

数据结构Skipped MK Cache

键 = (ratchet_key, chain_index), 值 = MessageKey。命中即用 + 立即清除。一般用 HashMap + 容量上限。

HashMap<(PubKey, u64), MessageKey>

Signal Double Ratchet · Diagram 06/11 · Out-of-Order Handling