ppt链接 ：
简介
回顾。
回顾上一部分介绍的四种MAC：
MAC系统是安全的，即在选择消息攻击下，是不可被存在性伪造的。
任何一个安全的PRF都能给我们一个安全的MAC。
基于CBC的MAC：两种变形：ECBC，CMAC。常与AES一起使用，在802.11i标准里，CBC-MAC被用于信息完整性。
NMAC和CBC-MAC 都是串行的。PMAC是并行的。
Carter-Wegman MAC不是基于PRFs，它是一个随机MAC。所以单个信息可以有许多不同的标签。首先取大量的信息，用快速的一次性MAC计算哈希值，得到一个小标签，然后用PRF加密。
这一章要从抗碰撞的概念出发，构建MAC。
抗碰撞。
注意：|M|>>|T|，根据鸽巢定理，一定会有很多消息被映射到相同的输出。但是问题在于有没有一个能直接找出这些碰撞的有效算法。注意：仅仅说这种算法存在是远远不够的，要输出碰撞的算法。
从抗碰撞的哈希函数到MAC。
哈希函数必须是抗碰撞的，否则构成的MAC则是不安全的。
用哈希函数保护文件的完整性。
和MAC不同，MAC需要一个密钥k，而哈希则需要一个公共的空间。
生日攻击
攻击方法。
生日悖论。
注意：r_1,......,r_n 必须是独立的，相同分布的。当它们是均匀分布时，Pr是1/2。也就是均匀分布是最糟糕的情况。
以下证明假设r变量的分布为均匀分布。如果分布不是均匀分布，那么都会有一个更低的下界满足该性质。
在B的平方根之上，概率很快的接近于1。在B的平方根之下，概率很快的接近于0。
生日攻击一次成功的概率为1/2,所以需要迭代两次。证明了哈希函数通常不输出128位。攻击所需时间 2^{64} 。
注意：SHA-1 最好的攻击需要 2^{61} 。SHA-1 现在最好不要用。
Merkle-Damgard 机制
分两步构造，第一步，给定一个处理短信息的抗碰撞的哈希函数，可以扩展它来构建一个处理长信息的抗碰撞哈希函数。
所有标准的哈希函数都遵循这个机制，由一个压缩函数构成一个抗碰撞的哈希函数。
假设h是处理短信息的抗碰撞哈希函数，也叫压缩函数。
IV内嵌在代码和标准里，只是一个固定的ID，是函数的一部分。
在所有的SHA哈希函数中，最大的信息长度为2的64次方减1。如果消息正好是分组的整数倍，那么需要添加一个假分组。
定理：如果h是抗碰撞的哈希函数，那么H也是一个抗碰撞的哈希函数。
证明：
如果 H_t neq H'_r or M_tneq M'_r or PBneq PB' ,则证明 h 哈希出现了碰撞。
如果h哈希没有出现碰撞，意味着 H_t = H'_r and M_t= M'_r and PB= PB' 。
如果 PB=PB' ,因为填充的消息的长度，意味着 t=r 。
如果 H_t=H_r' ，则推出 h(H_{t-1},M_{t-1})=h(H'_{t-1},M'_{t-1}) 。到这里，如果h哈希没有出现碰撞，意味着 H_{t-1} = H'_{r-1} and M_t= M'_r and M_{t-1}= M'_{t-1} 。
.....一直推到最前面。两种情况：
1.找到h的碰撞。
2. forall i:M_i=M'_iRightarrow M=M' 与H发生碰撞题意不符。 得证。
构造安全的压缩函数
从分组密码构造压缩函数。
Davies-Mayer 机制。攻击的最佳方式是生日攻击，没有比生日攻击更好的。意味着它是抗碰撞的哈希函数。
SHA函数都用了Davies-Mayer 机制。
少了后面的异或是不安全的。E(m',H')=h(H',m')=h(H,m)=E(m,H) 。构造出碰撞。
其它构造方法。
注意 h(H,m)=E(m,H)oplus m 是不安全的。
SHA-256。
没有描述 SHACAL-2的详细内容。只给了一些参数。
基于数论的压缩函数构造。
离散对数。压缩比为2：1。速度太慢。
HMAC
直接用抗碰撞的H哈希函数构造MAC，不依靠PRF？
尝试1：
扩展攻击：
HMAC
ipad 和opad，是固定的常数。512位常数，永不改变。
和NMAC类似。
证明是下图NMAC，意味着说明压缩函数h是PRF，密钥是下面的函数输入。
ipad 和opad，是固定的常数。512位常数，永不改变。
HMAC和NMAC不同之处在于，HMAC的密钥是互相有关联的。只是同样的密钥k异或上不同的常量。所以k1和k2也是互相有关联的，它们是在同样的固定值IV上应用PRF计算得到的。为了证明k1和k2是伪随机的且相互独立的，我们必须证明压缩函数不仅当它上面的输入是密钥时，它是PRF，也要证明当它使用关联密钥时，它也是PRF。
HAMC的安全分析
TLS
HMAC 由SHA-1函数构建，并截断到96位。SHA-1输出160位，取高96位。
注意：HMAC不要求SHA-1是抗碰撞的，只要求SHA-1的压缩函数是PRF，就可以了。
MAC认证的计时攻击
当第一个字节不相等时，就返回错误。
根据提交后服务器给出结果的时间，一个字节一个字节的判断。
解决方案1：
但是一个优化的编译器可能会提前终止循环。
解决方案2：
攻击者无法知道到底在比较什么字符串，所以无法进行攻击。
不要自己设计密码，不要自己实现密码！！！！！！
