标签与加密的任务不同
认证标签让接收者检查消息是否符合双方共享的秘密密钥,但它不一定隐藏消息。我们研究一个刻意简化的一次性实验,证明精确的替换成功概率,并看清假设的重要性。
定义 11.1.1
(一次性仿射标签方案)
令 为素数,以 表示消息、标签与密钥分量的集合。发送者和接收者共享均匀随机的秘密对 ,且它与固定消息 独立。发送者在这次使用中公开 及
接收者恰在 时接受声称的消息与标签 。所有运算都在 中进行。两个密钥分量都从整个域选取,包括零。
攻击模型让攻击者看到一个真实对 ,然后对不同消息进行一次验证尝试;同一密钥下没有更早的观察或验证反馈。
一次尝试的精确界
定理 11.1.2
(替换成不同消息)
观察 后,攻击者选择任意 及标签 ,其选择可依赖观察结果及与密钥独立的私人随机性。接收者接受 的概率恰为 。
证明
(以观察到的标签为条件)
固定观察到的 。对 的每个选择,恰有一个 产生该观察。由于原来 个密钥对均匀,剩下的 个密钥等可能。对固定的 ,
差 非零,因而可逆,所以 遍历整个域时,此表达式恰好取遍每个标签值一次。在观察结果条件下, 的正确标签均匀分布。因此任何提出的 成功概率都是 。上述论证适用于每个观察结果及由它选出的不同 ;再对攻击者的独立随机选择取平均即可。
证明有两个要素,使用结果之前值得把它们分开。
证明透视
观察后什么仍是随机的?
均匀且与 独立,这个假设只用了一次:它使符合观察的 个密钥等可能,而且只由 参数化。公开标签消去密钥的一个自由度,另一个自由度则完全不受影响。
关键一步是改写 ,把未知的目标标签写成唯一剩下的未知量的函数。假设 正是在这里与 为素数一起使用:域中非零元素可逆,所以 是 的双射,把均匀的 送到均匀的标签。若改在 中而 ,则 只取 与 两个值,各有概率 ,伪造成功概率便是 而非 。
论证逐点收尾:界对每个观察及由它选出的每个 都成立,所以只要攻击者的随机性与密钥独立,取平均后任何自适应或随机的 选择都受同一界限制。
例题 11.1.3
(小域与观察到的标签)
取 ,假设密钥为 、。对 ,真实标签为 。只看到 的观察者不能确定 :对每个 ,密钥 都符合观察。若替换消息为 ,其有效标签是 ;当 遍历整个域,它取遍七个值。猜一个标签的成功概率为 。此处列出密钥值仅为检查算术;真正的密钥是秘密。
例题 11.1.4
(照抄观察到的标签)
仍取 及观察 。伪造者可能提交新消息 并沿用旧标签 。若 ,消息 的正确标签是 ,而
因为 在模七下可逆。在七个等可能的相容密钥 中,只有 接受照抄的标签,所以成功概率为 ,与定理一致。边界情形 正是标签与消息无关的密钥;定义允许它,而这个策略押注的就是它。
定义允许 取零。排除零看似只是让每个标签都依赖消息的无害做法,但它会改变精确界。
例题 11.1.5
(禁止零密钥分量)
改设 在 上均匀, 在 上均匀且两者独立,共有 个密钥。观察到 后,每个 仍恰有一个相容的 ,所以 在 个非零值上均匀。对 ,目标标签 取遍除 以外的每个值,各有概率 。提交任何 的伪造者成功概率为 ,大于 ;当 时为 。照抄标签此时必定失败,但最佳攻击反而改进了。
重用破坏此实验
反例模式
两对数据透露密钥
假设同一密钥为不同消息 产生标签 ,而两对数据都被观察到。则
因为消息不同,分母可逆。对上述例子,第二对真实数据 给出模七下 、。观察者便可计算每个域消息的标签,例如消息 的标签是 。一次观察的定理不适用于这个两次观察实验。
常见错误
(把此界当作防重放或防重复猜测的保证)
定理只涉及对消息 的一次尝试。重放真实对 会以概率 被接受,所以此方案不保证新鲜性。多次验证尝试也在结论之外:每次被拒绝都告诉攻击者哪些密钥已被排除,需要另行分析。
消息是公开的,没有加密。真正系统需要安全密钥建立、防重放、适当密钥处理与经审查的认证方案;这个小例子并非实现建议。
习题
快速检查
(若 、、,求消息 和 的标签。)
计算 并模七约化。
解答 · 答案
,,所以模七下标签分别是 和 。
快速检查
(已观察一对 ,还有多少个可能密钥 ?对每个可能的 , 是什么?)
从 解出 。
解答 · 答案
有 个等可能密钥:对每个 ,观察迫使 。
快速检查
(为什么证明要求 ?)
看目标标签中乘以 的因子。
解答 · 答案
这时 非零且可逆,所以 变化时目标标签 均匀。若 ,目标标签就是攻击者已知的观察值 。
快速检查
(若同一密钥产生的两对不同消息与标签都公开,情况有何改变?)
把两条标签方程相减。
解答 · 答案
相减得 ;由于 可逆,这确定 ,再由任一对确定 ,攻击者便可计算每个消息的标签。
延伸阅读
MIT 通用哈希讲义 讨论两两独立的仿射映射。加州大学伯克利分校消息认证讲义 讨论更广泛的认证构造。