4.认证单向散列函数单向散列函数的性质一些术语单向散列函数的实际应用检测软件是否被篡改基于口令的加密消息认证码数字签名伪随机数生成器一次性口令常见的散列函数MD4、MD5SHA-1、SHA-256、SHA-384、SHA-512RIPEMD-160SHA-3Keccak海绵结构吸收阶段 挤出阶段双工结构Keccak的内部结构函数 Keccak-f[b]步骤θ步骤ρ步骤π对Keccak的攻击对缩水版Keccak的攻击竞赛应该采用哪种单向散列函数对单向散列函数的攻击暴力破解生日攻击单向散列函数无法解决的问题消息认证码消息认证码的使用步骤消息认证码的应用实例SWIFTIPsecSSL/TLS消息认证码的实现方法认证加密HMAC详细介绍对消息认证码的攻击重放攻击密钥推测攻击消息认证码无法解决的问题对第三方证明防止否认
one-way hash function
有一个输入和一个输出，其中输入称为消息（message），输出称为散列值（hash value）。
单向散列函数可以根据消息的内容计算出散列值，而散列值可以被用来检查消息的完整性（integrity），或称一致性。
消息可以是文字，也可以是图像文件或声音文件。单向散列函数会将消息当作单纯的比特序列处理，计算出散列值。
散列值的长度和消息的长度无关。单向散列函数计算出的散列值是固定的。SHA-256单向散列函数计算出的散列值的长度一定是256比特（32字节）。
根据任意长度的消息计算出固定长度的散列值，长度最好是短且固定的。
能够快速计算出散列值
消息不同则散列值也不同
两个不同的消息产生同一个散列值的情况称为碰撞（collision）。如果要将单向散列函数用于完整性的检查，则需要确保在事实上不可能被人为地发生碰撞。
难以发现碰撞的性质称为 抗碰撞性 （collision resistance）。密码技术中所使用的单向散列函数，都需要具备抗碰撞性。
弱抗碰撞性：要找到和该条消息具有相同散列值的另一条消息是非常困难的；
强抗碰撞性：要找到散列值相同的两条不同的消息是非常困难的。
密码技术中所使用的单向散列函数，不仅需要具备弱抗碰撞性，还必须具备强抗碰撞性。
具备单向性
无法通过散列值反算出消息。
单向散列函数并不是一种加密，因此无法通过解密将散列值还原为原来的消息。
单向散列函数 ，也称为消息摘要函数（message digest function）、哈希函数或者杂凑函数。
输入单向散列函数的消息也称为原像（pre-image）。
单向散列函数输出的散列值也称为消息摘要（message digest）或者指纹（fingerprint）。
完整性也称为一致性。
hash一词源于古法语中的“斧子”，后来被引申为“剁碎的肉末”。单向散列函数的作用，实际上就是将很长的消息剁碎，然后再混合成固定长度的散列值。
许多软件在发布时会将其散列值一起公布，以便用户验证下载到的软件是否一致。对于多镜像站点发布的软件尤其重要。
Password Based Encryption——PBE
PBE的原理是将口令和盐（salt，通过伪随机数生成器产生的随机值）混合后计算其散列值，然后将这个散列值用作加密的密钥。
此方法能够防御针对口令的字典攻击。
使用单向散列函数可以构造消息认证码。
消息认证码是将【发送者和接收者之间的共享密钥】和【消息】进行混合后计算出的散列值。
使用消息认证码可以检测并防止通信过程中的错误、篡改以及伪装。
消息认证码在SSL/TLS中也得到运用。
数字签名是现实社会中的签名和盖章这样的行为在数字世界中的实现。
数字签名的处理过程非常耗时，因此一般不会对整个消息内容直接施加数字签名，而是先通过单向散列函数计算出消息的散列值，然后再对这个散列值施加数字签名。
用于构造伪随机数生成器。
利用单向散列函数的单向性，可以保证随机数列的不可预测性。
构造一次性口令，用于服务器对客户端的合法性认证。通过使用单向散列函数可以保证口令只在通信链路上传送一次，因此即使窃听者窃取了口令，也无法使用。
Message Digest——消息摘要
MD4和MD5已经被攻破，不再安全。
SHA——Secure Hash Algorithm——安全哈希算法
SHA-1已经被列入“可谨慎运用的密码清单”，即除了用于保持兼容性的目的以外，不推荐再用。其强抗碰撞性已于2005年被攻破。
SHA-256、SHA-384、SHA-512都是NIST设计的单向散列函数，它们的散列值长度分别为256比特、384比特、512比特。这些统称为SHA-2，消息长度存在上限（SHA-256的上限接近于264 比特，SHA-384和SHA-512的上限接近于2128 比特）。
SHA-2尚未被攻破。
6种版本的SHA-2（均衍生自SHA-256和SHA-512）：
| 名称 | 输出长度 | 内部状态长度 | 备注 |
|---|---|---|---|
| SHA-224 | 224 | 32X8=256 | 将SHA-256的结果截掉32比特，更适合32位系统 |
| SHA-256 | 256 | 32x8=256 | 更适合32位系统 |
| SHA-512/224 | 224 | 64x8=512 | 将SHA-512的结果截掉288比特 |
| SHA-512/256 | 256 | 64x8=512 | 将SHA-512的结果截掉256比特 |
| SHA-384 | 384 | 64x8=512 | 将SHA-512的结果截掉128比特 |
| SHA-512 | 512 | 64x8=512 |
来自欧盟RIPE项目，此系列还包括RIPEMD-128、RIPEMD-256、RIPEMD-320等版本。
RIPEMD的强抗碰撞性已经于2004年被攻破，但RIPEMD-160尚未被攻破，被列入“可谨慎运用的密码清单”。
比特币使用的就是RIPEMD-160。
2012年Keccak算法胜出竞争，称为SHA-3。
Keccak胜选的理由如下：
Keccak可以生成任意长度的散列值，但为了配合SHA-2的散列值长度，SHA-3标准中共规定了SHA3-224、SHA3-256、SHA3-384、SHA3-512四种版本。
对于输入数据的长度上限，SHA-3没有长度限制。
此外，FIPS 202中还规定了两个可输入任意长度散列值的函数（extendable-output function，XOF），分别位SHAKE128和SHAKE256.
sponge construction
输入数据在进行填充之后，要经过 吸收阶段 （absorbing phase）和 挤出阶段 （squeezing phase），最终生成输出的散列值。
流程如下：
函数 f 的作用是将输入的数据进行复杂的搅拌操作并输出结果（输入和输出的长度均为 b = r + c 个比特），其操作对象长度为 b = r + c 个比特的内部状态，内部状态的初始值为0。
r 被称为 比特率（bit rate）。
c 被称为 容量 （capacity）。
流程如下：
无论是吸收阶段还是挤出阶段，函数 f 的逻辑本身是完全相同的，每执行一次函数 f ，海绵结构的内部状态都会被搅拌一次。
挤出阶段中实际上执行的是【对内部状态进行搅拌并产生输出分组（ r 个比特）】的操作，也就是以比特率（ r 个比特）为单位，将海绵结构的内部状态中的数据一点一点地”挤“出来，就像从海绵里面把水分挤出来一样。
在挤出阶段中，内部状态 r + c 个比特中的容量（ c 个比特）部分是不会直接进入输出分组的，这部分数据只会通过函数 f 间接影响输出的内容。因此，容量 c 的意义在于防止将输入消息中的一些特征泄漏出去。
双工结构是海绵结构的变形。
输入和输出是以相同的速率进行的。
通过采用双工结构，Keccak不仅可以用于计算散列值，还可以作为伪随机数生成器，也可以用于流密码、认证加密、消息认证码等。
b = r + c
Keccak的内部状态是一个三维的比特数组。
具备 x、y、z 三个维度的内部状态整体称为 state ，state共有 b 个比特。
若只关注内部状态中的两个维度，可以将 xz 平面称为 plane ，将 xy 平面称为 slice ，将 yz 平面称为 sheet 。
x 轴称为 row ， y 轴称为 column ， z 轴称为 lane 。
可以将state看成是由5x5=25条 lane构成的，也可以看成是由与lane的长度相同数量的slice堆叠而成的。
Keccak的本质就是实现一个能够将上述结构的state进行有效搅拌的函数 f ，这与分组密码设计中的搅拌过程非常相似。
内部状态可以代表整个处理过程中的全部中间状态，因此有利于节约内存。
Keccak可有效抵御针对字节单位的攻击。
Keecak的函数 f 实际上应该叫做 Keccak-f[b]，这里的参数 b 称为 宽度 （width）。
根据设计规格，宽度 b 可以取 25、50（25的2倍）、100（25的4倍）、200（25的8倍）、400（25的16倍）、800（25的32倍）、1600（25的64倍） 共7种值（都是25的整数倍），SHA-3采用的最大宽度，即 b=1600。
一片slice的大小为5x5=25个比特，因此，b/25就相当于slice的片数（即lane的长度）。SHA-3的内部状态大小为 b=5x5x64=1600 比特。
通过改变宽度 b 就可以改变内部状态的比特长度。但 slice 的大小始终是5x5，改变的只是lane的长度，因此，Keccak宽度的变化并不会影响其基本结构。这种结构称为 套娃结构 。
Keccak-f[b] 中的每一轮包含5个步骤：θ、ρ、π、χ（凯）、ι（伊欧塔），总共循环12+2l轮。具体到SHA-3中所使用的Keccak-f[1600]函数，其循环轮数为24轮。
2l = b/25 = 1600/25=6 l=6 12+2l=24
将位置不同的两个column中各自5个比特通过XOR运算加起来，然后再与置换目标比特求XOR并覆盖掉目标比特。
沿 z 轴（lane方向）进行比特平移。
【从此以后就看不懂了】
MD结构（Merkle-Damgard construction）通过循环执行压缩函数的方式来生成散列值。
MD4、MD5、RIPEMD、RIPEMD-160、SHA-1、SHA-2等几乎所有的传统单向散列函数算法都是基于MD结构的。
Keccak采用了与MD结构完全不同的海绵结构，因此针对SHA-1的攻击方法对Keccak是无效的。
至今尚无对Keccak算法形成威胁的攻击方法。
尝试攻击一个比实际作为SHA-3标准运用的Keccak强度低一些的版本，据此评估实际运用的标准版Keccak的强度。
竞赛中使用的缩水版Keccak比标准版减少了迭代轮数，参赛者可以通过改变宽度 b 等各种方法来进行攻击。
任何文件中都或多或少地具有一定的 冗余性 （在不改变文档意思的前提下，能够对文件的内容进行修改的程度）。利用文件的冗余性生成具有相同散列值的另一个文件，就是一种针对单向散列函数的攻击。
暴力破解即：试图破解单向散列函数的【弱抗碰撞性】的攻击。
以SHA3-512为例，由于其散列值的长度为512比特，因此最多只要尝试 2512 次就能够找到目标消息了。如此多的尝试次数在现实中是不可能完成的。
单向散列函数的散列值长度越长，其抵御暴力破解的能力也就越强。
找出具有指定散列值的消息的攻击分为两种：【原像攻击】和【第二原像攻击】。
生日攻击（birthday attack）也称为冲突攻击（collision attack），是一种试图破解单向散列函数的【强抗碰撞性】的攻击。
生日问题：在 N 个人中，如果要保证至少有两个人生日一样的概率大于50%，那么 N 至少是多少？
N=23，即，只要有23人，就有超过50%的概率出现至少两个人生日一样的情况。有过N=100，这个概率就已经非常接近1了。
任意生日相同的概率比想象的要大，这个现象称为 生日悖论 （birthday paradox）。
将生日问题一般化：假设一年的天数为 Y ，那么 N 人的集合中至少有两个人生日一样的概率大于二分之一时，N 至少是多少？
当 Y 非常大时，近似的结果为 Y 的平方根。
生日攻击的原理来自生日悖论，即【任意散列值一致的概率比想象中要高】。
N 的大小是和散列值的长度相关的。
以512比特的散列值为例，对单向散列函数进行暴力破解所需的尝试次数为2512次，而对同一单向散列函数进行生日攻击所需的尝试次数为2256次，因此和暴力破解相比，生日攻击所需的尝试次数要少得多。
2005年王小云团队提出得碰撞攻击方法中，对于SHA-1所需要得尝试次数为269次，已经大大少于生日攻击所需的280次。同年，王小云团队又改进了该方法，使得尝试次数减少到263次。
使用单向散列函数可以实现完整性的检查，但有些情况下即使能够检查完整性也是没有意义的。
单向散列函数能够辨别出【篡改】，但无法辨别出【伪装】。
需要使用 认证 来确认文件的完整性和真实性。
认证的技术包括 消息验证码 和 数字签名 。
消息认证码能够向通信对象保证消息没有被篡改；数字签名不仅能保证消息没有被篡改，还能向所有第三方做出这样的保证。
认证需要使用密钥。
Message Authentication Code——消息认证码，是一种确认完整性并进行认证的技术，简称MAC。
消息认证码的输入包括任意长度的 消息 和一个发送者与接收者之间 共享的密钥 ，它可以输出固定长度的数据，这个数据称为 MAC值 。
这个过程比【单向散列函数】多了发送者和接收者之间的 共享密钥 。
没有共享密钥的人无法计算出MAC值。
可以将消息认证码理解为一种与密钥相关联的单向散列函数。
消息验证码不能被主动攻击者获取，否则攻击者可任意篡改和伪装攻击。消息认证码将失去作用。
密钥配送问题 在消息认证码中同样会发生。可使用公钥密码、DH密钥交换、密钥分配中心等方式解决此问题。
SWIFT——Society for Worldwide Interbank Financial Telecommunication（环球银行金融电信协会），成立于1973年，其目的是为国际银行间的交易保驾护航。
银行和银行之间是通过SWIFT传递交易消息。为了确认消息的完整性以及对消息进行验证，SWIFT中使用了消息认证码。
IPsec是对IP协议增加安全性的一种方式。
在IPsec中，对通信内容的认证和完整性校验都是采用消息认证码来完成的。
SSL/TLS对通信内容的认证和完整性校验也使用了消息认证码。
使用单向散列函数实现
SHA-2之类的单向散列函数可以实现，其中一种称为HMAC。
使用分组密码实现
使用AES可以实现。
其他方法
流密码和公钥密码等
AE——Authenticated Encryption
AEAD——Authenticated Encryption with Associated Data
一种将对称密码与消息认证码相结合，同时满足机密性、完整性和认证三大功能的机制。
Encrypt-then-MAC
先用对称密码将明文加密，然后计算密文的MAC值。
消息认证码的输入消息是密文，通过MAC值就可以防止【选择密文攻击】（攻击者通过发送任意伪造的密文，让服务器解密，以套取信息的攻击）
Encrypt-and-MAC
将明文用对称密码加密，并对明文计算MAC值
MAC-then-Encrypt
先计算明文的MAC值，然后将明文和MAC值同时用对称密码加密
GCM（Galois/Counter Mode）使用AES等128比特分组密码的CTR模式，并使用一个反复进行加法和乘法运算的散列函数来计算MAC值。
专门用于消息认证码的GCM称为GMAC。
GCM和CCM（CBC Counter Mode）都被列为推荐使用的认证加密方式。
HMAC是一种使用单向散列函数来构造消息认证码的方法（RFC2104），其中H是Hash的意思。
任何高强度的单向散列函数都可以被用于HMAC。
使用SHA-1、SHA-224、SHA-256、SHA-384、SHA-512所构造的HMAC分别称为HMAC-SHA-1、HMAC-SHA-224、HMAC-SHA-256、HMAC-SHA-384、HMAC-SHA-512。
HMAC步骤如下：
密钥填充
如果密钥比单向散列函数的分组长度短，就需要在末尾填充0，直到其长度达到单向散列函数的分组长度为止。
如果密钥比分组长度要长，则要用单向散列函数求出密钥的散列值，然后将这个散列值用作MAC的密钥。
填充后的密钥与ipad的XOR
将填充后的密钥与被称为ipad的比特序列进行XOR运算。 ipad 是将 00110110 这一比特序列（即16进制的36）不断循环反复直到达到分组长度所形成的比特序列，其中ipad的 i 是inner（内部）的意思。
XOR运算所得到的值，就是一个和单向散列函数的分组长度相同，且 和密钥相关的比特序列 。此比特序列称为 ipadkey。
与消息结合
随后，将ipadkey与消息进行组合，也就是将和密钥相关的比特序列附加到消息开头。
计算散列值
将上述结果输入单向散列函数，并计算出散列值。
填充后的密钥与opad的XOR
将填充后的密钥与被称为opad的比特序列进行XOR运算。 opad 是将 01011100 这一比特序列（即16进制的5C）不断循环反复直到达到分组长度所形成的比特序列，其中opad的 o 是outer（外部）的意思。
XOR运算所得到的结果也是一个和单向散列函数的分组长度相同，其和密钥相关的比特序列。这里我们将这个比特序列称为opadkey。
与散列值组合
将第四步的散列值拼在opadkey后面。
计算散列值
将第六步的结果输入单向散列函数，并计算出散列值。这个散列值就是最终的MAC值。
通过上述流程可以看出，最后得到的MAC值，一定是一个和输入的消息以及密钥都相关的长度固定的比特序列。
主动攻击者通过将事先保存的正确MAC值不断重放来发动攻击。
如下方法可防御重放攻击：
序号
约定每次都对发送的消息赋予一个递增的编号（序号），并且在计算MAC值时将序号也包含在消息中。
此方法虽然有效，但对于每个通信对象都需要记录最后一个消息的序号。
时间戳
约定在发送消息时包含当前的时间，如果收到以前的消息，即便MAC值正确也将其当作错误的消息来处理。
此方法要求发送者和接收者的时钟必须一致，而且考虑到通信的延迟，必须在时间的判断上留下缓冲，因此多多少少还是会存在可以进行重放攻击的空间。
nonce
在通信之前，接收者先向发送者发送一个一次性的随机数，这个随机数一般称为 nonce 。发送者在消息中包含这个nonce并计算MAC值。
这种方法虽然有效，但通信的数据量会有所增加。
对消息认证码也可以进行暴力破解以及生日攻击 。
对于消息认证码来说，应保证 不能根据MAC值推测出通信双方所使用的密钥 。
在生成消息认证码所使用的密钥时，必须使用密码学安全的、高强度的伪随机数生成器。
如果密钥时人为选定的，则会增加密钥被推测的风险。
第三方要校验MAC值，就需要收发双方之间共享的密钥。能够计算出正确MAC值的人只有发送者和接收者。
消息认证码无法防止否认（nonrepudiation）。