斯坦福大学密码学-抗碰撞 06

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_t\neq M'_r\ \ or\ \ PB\neq 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'_i\Rightarrow 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：

攻击者无法知道到底在比较什么字符串，所以无法进行攻击。

不要自己设计密码，不要自己实现密码！！！！！！