斯坦福大学密码学-信息完整性 05

ppt链接：

消息认证码(MAC)

目标：只提供完整性，不提供私密性。举例：硬盘上的公共信息，不在乎私密性，只在乎是否被病毒入侵，被篡改。广告商。

MAC包含两个算法：S 签名算法，V验证算法。

完整性检测需要一个密钥。CRC 循环冗余检测，是一个经典的校验和算法，为检测信息中随机发生的错误而设计的，而不是恶意的错误。

安全的MAC。存在性伪造。

攻击者不能做到以下两点。

安全的MAC的定义。

例题。

攻击者像挑战者请求 m_0 的标签，得到 (m_0,t) ,然后攻击者发送 (m_1,t) ,则有 1/2 的概率会成功。优势为 1/2。

标签太短了，优势为 1/2^5=1/32 ,不可忽略。标签的长度要足够长。

应用。

安装了windows系统，windows系统让用户指定一个密码，然后根据这个密码推出一个密钥k，然后对每一个写入硬盘里的文件进行标签计算，并将标签和文件放在一起。然后删除密钥k，在内存、硬盘等任何地方都找不到。

设想一下，系统被病毒感染了，病毒试图修改一些系统文件。问用户是否可以检测出哪些文件被修改了？

解决办法:用户从一个干净的操作系统重启机器，并提供其密码，干净的操作系统会计算每一个文件的MAC，注意，病毒并不可以创建一个新文件并计算其MAC，因为这里的MAC是安全的。所以用户可以检测出哪些文件进行了修改。

假如病毒可以交换 F_1 和 F_2 ，那么也会造成伤害。解决办法：将文件名放在文件内容中进行完整性检测。

注意：MAC可以抵御文件的篡改或者广义上的数据篡改。但是无法帮助抵御认证信息的交换。

基于PRFs 的MACs

安全的PRFs \Rightarrow 安全的 MACs

例题。

唯一的问题。PRFs 输出的长度太小。

安全性。|Y| 足够大。

证明。

用真随机函数替换掉PRF的话，函数在m点的函数值和 m_1......m_q 没有任何关系。攻击者只能猜，猜的概率为 1/|Y|。

已经得到了一个MAC，即AES。但是AES只能处理16字节的消息。如何将处理短信息的MAC转换成处理长信息的MAC？

基于PRFs的MAC截断后也是安全的。

CBC-MAC 和 HMAC

我们将AES当作底层PRF。

CBC-MAC(ECBC)

用PRP，X^{\leq L} 的意思是ECBC取最多长为L个分组的信息，L可以为百万或十亿的大小。它还可以是变化的输入信息的长度。

意义是 X^{\leq L}=\cup^L_{i=1} X^i 。

注意：一定要多做一次加密。这一步使用一个独立的密钥完成。

如果不定义的话，叫做原CBC函数，不是一个安全的MAC。

如果进行攻击的话，不知道密钥k。

选择消息攻击。

NMAC(嵌套MAC)

可以注意到 X的长度远远大于密钥k的长度。

如果没有最后一步，叫做级联函数。并不是安全的MAC。

原因：

扩展攻击，也是级联函数的唯一一种攻击。

ECBC和NMAC的安全性定理。

举例。3DES不再适用。

扩展性质。

根据生日驳论，在 2^{64} 个消息询问下，很容易找到 t_u=t_v 。所以ECBC和NMAC的上限是存在的。AES使用同一个密钥小于2^{48} ,3DES小于 2^{16}。

ECBC vs NMAC

MAC 填充。

之前都假设消息正好是分组的倍数，如果不是，需要填充。

在后面补充0，大错特错。会导致 pad(m)=pad(m||0)。

补齐函数必须是一一映射的。注意：当信息长度是分组长度的整数倍时，加一个假的分组。

是否有一种补齐方式，从不需要加假的分组？

确定的补齐函数，在所有的情况下我们都需要补齐。长度是分组倍数的信息长度比长度不是分组倍数的信息长度少的多。因此我们无法获得一个从大的所有信息的集合到小的分组倍数长的信息集合的意义映射。所以必须扩展，就对应于添加一个假的分组。

CMAC

解决了最后一步加密的过程和补齐时添加一个假的分组的问题。

并行的MAC

之前的ECBC和NMAC都是串行的。

PMAC 如果没有p函数的话，那么交换m[0]和m[1]的位置输出的t结果是一样的。p函数的作用是用来为每一组数据固定位置。

安全性分析。

例题。可以快速更换标签。

One Time Key

任何密钥只能用于一条信息的完整性。

举例。

比基于PRF的MAC要快。这是一次性MAC，但不是二次安全的。如果看到了两条消息的MAC，那么攻击者就可以伪造第3条消息，第4条消息。

将 m[1]......m[L] 看成从0到 2^{128}-1 的数据。

One time MAC \Rightarrow Many times MAC

随机数r每次计算新的标签时，都被重新选择。计算同一个信息的标签，因为r，会得到不同的标签。不属于PRF。

验证。

文献介绍