Dan Boneh密码学笔记5

开始之前先补充一下第4篇笔记的总结。

5.Message integrity

信息完整性

1.Message Auth. Codes(MAC消息验证码)

2.MACs based on PRFs

3.CBC-MAC and NMAC

4.MAC padding

5.a parallel MAC

1.Message Auth. Codes(MAC消息验证码)

只考虑完整性，先不考虑私密性

常见错误，不用共享密钥就能提供完整性

如果只用CRC冗余校验码（CRC没有密钥），不安全

攻击者可以篡改信息后加上修改后的CRC

CRC是为检测随机错误而设计的，并非针对恶意错误的。

安全的MAC系统

⇒ attacker cannot produce a valid tag for a newmessage

⇒ given (m,t)attacker cannot even produce (m,t’) for t’ ≠ t

Q1

加密两条不同的消息，有一半的概率得到相同的密文结果，不安全。

攻击者可以以1/2的优势破解。

Q2，MAC算法只输出五位长度，不安全

攻击者不需要CPA，只要输出存在性伪造，选择一个随机标签t，输出他的存在性伪造（m0，t），

1/2^5概率，这个标签是m0的一个有效标签，攻击者优势为1/32，不可忽略

所以，标签不能太短

看一个例子，如何用MAC加密硬盘上的系统文件

MAC可以帮你抵御文件篡改，但是不能抵御认证信息的交换。

安装系统，设置密码，根据密码扩张出一个密钥K，计算每个文件的标签t，标签和文件存放在一块。删除密钥K。

病毒攻击，因为MAC是安全的（不可被存在性伪造），所以病毒不能创建新的文件f'和标签t’

因为MAC，可以检测出被篡改的文件

病毒可以交换两个文件，user运行F1时实际运行F2，也是危害，防止这样做的方法就是把文件名放在求MAC的区域里。把文件名和文件内容一起MAC。

2.MACs based on PRFs

现在我们知道了MAC是什么，继续构建第一类安全的MAC

一个设计的不好的例子

假设PRF只输出10位标签

如果用这个PRF得到的MAC，是不安全的。因为标签太短了。

攻击者有1/2^10的概率猜中MAC

如何把短的MAC转化为长的MAC

两种方法：

CBC-MAC 应用在银行业

HMAC应用在网络协议

这些基于PRF的MAC，它们的输出可以被截断。

对于AES，是一个输出128位的PRF，一个容易证明的引理，如果你有一个n位的PRF，如果截断它（只输出前k位），结果依然是安全的PRF。

如过一个MAC是基于PRF的，可以把它截断成w位，如果1/2^w是可以忽略的，得到的MAC就是安全的。W>64

3.CBC-MAC and NMAC

两个经典的MAC

一个PRF只能处理有限的信息，比如AES只能处理16字节（128b）的信息。

我们要构建一个PRF来处理长信息，比如几个G的信息。

第一个机制：加密的CBC-MAC。简称ECBC

我们把最大信息长度界定为L

取信息，分割成分组。每个分组和底层函数f的分组一样长。CBC运行，但不输出中间值。

这种情况下标签为N位长。截断标签。

最后一步加密是干什么的。

如果没有最后一步，叫做raw CBC 函数

原CBC并不安全。最后一步对于MAC的安全性很重要

第二个机制：NMAC

如果没有最后一步，叫做级联函数cascade，不安全

如果没有最后一步的加密，是不安全的

对于NMAC，级联函数，不安全的，给定一个信息的MAC，我可以产生另一个信息的MAC。在m后面加上w， 因为通过询问原m的标签，攻击者获得了这个更长的m的标签，就可以输出它作为伪造了。

实际上这些PRF都有如下扩展性质。

如果给我一个碰撞发生在信息x和y上，这也意味着有一个碰撞发生在x和y的扩展上。

4.MAC padding

当信息长度不是分组长度的整数倍，padding

全补0，不安全

支票后面加个0，不安全。

padding函数必须是不可逆的。无碰撞的。

ISO的标准，加10000…..倒着数数到1把1和后面的都删掉

整数倍时，末尾添加一组dummy假的分组。重要的安全措施。

CMAC，使用一个随机的补齐函数，不用加假分组。

用了三个密钥，也称三密钥机制。

如果是有补位，用k1异或，没有补位用k2异或

先用ISO的方法，补100….但是我们还要把最后一个分组和密钥k1xor

好处是没有最后的加密步骤，不用加假分组。

CMAC 和CBC-MAC有同样的安全性。

5.a parallel MAC

并行MAC

One time MAC

与一次性密码本类似，但是是关于完整性的。

一次性MAC转化成多次MAC

通用的MAC构建carter-wegman MAC

我们对信息m应用一次性MAC然后用PRF加密结果。

如何加密结果呢？我们选择一个随机数r，根据r计算一个一次性密码本。

通过r应用PRF，然后把结果与一次性MAC异或。

好处是，快速的一次性MAC被用到了很大的数据上。而费时的PRF只被用在新鲜值r上。r接着被用来加密MAC的最后结果。

这个carter-wegman MAC是个随机MAC的好例子。每次都换新鲜值。如果你试图两次计算同一信息的标签，你会选择不同的r，因此两次你会得到不同的标签。这个MAC不是基于PRF的，因为单个信息可以被映射到许多不同的标签。

这就是我们关于MAC的第一章内容。

补充内容

第一篇，三密钥机制，是CMAC的基础，给出了CBC-MAC的一个非常有效的机制。

第二篇，更技术点，如何证明CBC-MAC作为PRF的上界

第三篇，讨论了PMAC及其机制

第四篇，讨论了NMAC和HMAC的安全性

第五篇，我们总是假设AES是一个16字节信息的伪随机函数，然后构建一个PRF能计算长得多的信息的MAC，这篇文章说，如果AES不是为随机函数，但满足某些弱化的性质，叫做不可预测函数，我们该怎么办？如果AES仅为不可预测函数，不是伪随机函数的话，我们还能构建长信息的MAC了吗？他们成功给出了基于弱假设，即AES是不可预测函数而构建的机制。但是他们的机制远没有CBC-MAC 或NMAC或PMAC充分，