Dan Boneh密码学笔记6

6.Collision Resistance

1.introduction

2.Generic birthday attack

3.The Merkle-Damgard Paradigm

4.Constructing Compression Functions

5.HMAC: a MAC from SHA-256

6.Timing attacks on MAC verification

1.introduction

条件1，有一个MAC可以加密短信息，比如AES

条件2，有一个哈希函数是抗碰撞的。

Ibig为长信息的MAC

这个原型可以处理短输入，扩展成一个长输入。

这个特性不光是MAC特有的，以后讨论数字签名也要这么做。

这个定理：如果底层MAC是安全的，且H是抗碰撞的，那么这个组合可以计算长信息的MAC，得到的MAC也是安全的。

举例，在只读的公共区域保存软件安装包的哈希值，攻击者无法篡改这个空间里的哈希值。

这种方式和MAC相比较，如果用MAC，我们需要一个密钥来验证单个文件的标签，但我们不需要一个只读的公共空间。

用抗碰撞的哈希函数，我们不需要一个密钥来验证，任何人都可以验证。

数字签名可以在完整性和资源（不需要只读公共空间）两方面都达到最优。

哈希和MAC都只能保证其一。

实际上Linux用只读公共空间看来发布软件包的哈希值。

2.Generic birthday attack

这种生日攻击可以在2的n/2次内找到可能的碰撞，低于2的64次是危险的。

所以我们一般不用128位输出的哈希。用256。

3.The Merkle-Damgard Paradigm

非常通用的机制， Merkle-Damgard 机制

目标是把大的M映射到小的标签T

碰撞的定义

我们的目标是构建抗碰撞的哈希函数

就算存在碰撞，也没有有效的算法找到碰撞

分两步构造，第一步，给定一个处理短信息的抗碰撞的哈希函数，可以扩展它来构建一个处理长信息的抗碰撞哈希函数。

假设h是处理短信息的抗碰撞哈希函数，有时也叫压缩函数

链接变量，h0是初始值，h4是最终输出

PB补齐分组，这个分组最重要的部分是我们对信息长度进行编码，在所有的SHA哈希函数中，最大信息长度为2的64次方减一。

不是整数倍，加一个假分组。

所有的标准哈希函数都遵循这个机制

这个机制之所以留行，因为下面这个定理

如果小的哈希是抗碰撞的，那么大的 Merkle-Damgard 哈希函数也是抗碰撞的。

证明逆否命题：如果你能找到这个大哈希函数的一个碰撞，那么我们就可以推出这个小压缩函数的一个碰撞。

4.Constructing Compression Functions

构建安全压缩函数，使得压缩函数是抗碰撞的。

从分组密码来构建压缩函数

通过生日攻击的方式可以在2的n/2次方时间里找到碰撞。

这个机制非常常见。SHA函数都使用了Davies-Mayer机制。

链接变量H

Q，假设我们不使用Davies-Mayer机制里面的异或H，求证这个压缩函数不是抗碰撞的。

Davies-Mayer机制不是唯一的。还有其他方法根据分组密码构建抗碰撞的压缩函数。

HW那个不是抗碰撞的。

这里不描述SHACAL-2分组加密算法

一类压缩函数由分组密码构建，还有一类有数论里面的困难问题构建。

选取一个大质数，约700个十进制数，2000位二进制数，选择两个随机数uv。其压缩率为2比1，取两个数，输出一个数。

计算双重指数

这是可证明的，以后讲

如果你可以找到这个压缩函数的一个碰撞，你就可以解一个标准的数论难题——离散对数问题。Discreet log problem

与分组密码相比，速度慢，所以不流行

5.HMAC: a MAC from SHA-256

一个标准方法，把一个抗碰撞的哈希函数转成一个MAC，HMAC

使用SHA-256来构建MAC

在密钥k后面联结一个叫做内部密码本ipad，使它成为MD机制的一个分组。对于SHA-256来说是512位的。放在M前面，然后求哈希。只做这些是不安全的。

所以，除此之外，HMAC还取这256位输出计算密钥k与外部密码本opad异或，把异或结果附在256位输出的前面，也是512位。

然后HMAC取这两个分组的哈希值，最终得到信息M的标签。

这些密码本ipad 和opad，是固定的常数。标准中给出了。512位常数，永不改变。

6.Timing attacks on MAC verification

攻击者提供信息始终是一样的查询多次。

第一次查询，提交一个m和随机tag，然后测量服务器反应时间

第二次查询，将尝试标签的第一字节的所有256种情况，剩下的tag都是随便取，不重要。但是对于第一个字节，攻击者会提交一个以字节0开头的标签，然后观察服务器是否比之前耗时长一点来验证标签。如果服务器耗时与第一步严格相同，攻击者再次尝试，这次以字节1开头，如果还是相同，以字节2开头…直到服务器耗时稍微长一点，就意味着当服务器比较正确的MAC和攻击者提交的MAC时，在这个字节上，两个MAC是一样的，而不一样的是第二个字节。现在攻击者直到标签的第一个字节是3了，现在他对第二个字节实施一模一样的攻击。

使用计时攻击，碰出正确的MAC。

如何防御？

第一种方法，重写库函数，实际上已经更新了。

计数器累加方法。不要直接中断。

哈哈哈哈，但是优化编译器看到这份代码会觉得你愚蠢，给你又自动改回来。

法二，不常用，把字符串的比较对攻击者隐藏起来，攻击者无法知道在比较第几个字节。

专家在实现密码库时也会犯错，千万别自己设计密码。