消息认证与杂凑函数
　　本章首先介绍认证和认证系统的基本概念，认证码的基本理论[Meyer?等 1982]；然后介绍认证算法的基本组成部分——杂凑（Hash）函数；最后介绍几种实用的杂凑算法，如MD系列杂凑算法、SHA系列杂凑算法和中国商密标准SM3杂凑算法。
认证函数
　　本节讨论可以用来产生认证符的函数类型，这些函数可以分为以下三类。
* 消息加密：它采用整个消息的密文作为认证符。
* 消息认证码（MAC）：它是消息和密钥的公开函数，它产生定长的值，以该值作为认证符。
* 杂凑函数：它将任意长的消息映射为定长的杂凑值，以该杂凑值作为认证符。
5.1.1  消息加密
　　消息加密本身就提供了一种认证手段。信息加密能确保所接收消息的真实性吗？很多人相信，若消息收方对密文解密后能够得到符合语义的消息，他就认为密文是采用双方共享的密钥加密后得到的，据此可以判断消息发方是可信赖的人，且消息在传输过程中没有被篡改。事实上，由密文正确解密而得出发方可信及消息可信的结论是错误的。下面通过给出的几个反例就可以证实这一点。对称密码和公钥密码两种体制对消息加密的分析是不相同的。
1. 反例1——单钥加密
　　考虑一个使用单钥加密的简单例子，如图5-1（a）所示。发方A用A和B共享的密钥K对发送到收方B的消息M加密。理论上讲，若没有其他方知道该密钥，那么单钥加密可提供保密性，因为任何其他方均不能恢复出消息明文。一般来讲，若没有攻击者存在，B可确信该消息是由A产生的。
　　其实，单钥密码既可提供认证又可提供保密的结论是不正确的。考虑在B方发生的事件，给定解密函数D和密钥K，收方可接收任何输入X，并产生输出。若X是用相应的加密函数对合法消息M加密生成的密文，则Y就是明文消息M；否则Y可能是无意义的位串。因此在B端需要有某种方法能确定Y是合法的明文以及消息确实来自A，即需要对A进行身份认证。
　　第3章介绍了分组密码的8种工作模式，其中，ECB和CTR两种工作模式属于确定性的加密模式，即对同一明文进行两次加密，所得密文均相同。若攻击者窃取了上次通信的

图5-1  消息加密的基本用途
密文，隔一段时间后再重新发送旧的密文，收方B仍然可以解出上次通信的明文，而此时该密文是由攻击者发送的。因此，单钥加密不能提供对A的身份认证。
　　从认证的角度来看，上述推理存在这样一个问题。如果消息M可以是任意的位模式，那么收方无法确定接收到的消息是否为合法明文对应的密文，无论?M?的值是什么，都会作为真实的明文被接收。
　　一般来讲，要求合法明文只是所有可能位模式的一个小子集。这样，由任何伪造的密文都不太可能得出合法的明文。例如，假定种位模式中只有一种是合法明文的位模式，那么随机选择一个位模式作为密文，它产生合法明文消息的概率只有。
　　许多应用和加密方法都满足上述条件。例如，假定利用具有一次移位的Caesar密码传递英文消息，A发送下述合法的消息：
nbsftfbupbutboeepftfbupbutboemjuumfmbnctfbujwz
　　B解密并产生下述明文：
mareseatoatsanddoeseatoatsandlittlelambseativy
　　通过简单的频率分析可以发现，这个消息具有普通英语的特点。若攻击者产生下述随机的字符序列：
zuvrsoevgqxlzwigamdvnmhpmccxiuureosfbcebtqxsxq
则它被解密为
ytuqrndufpwkyvhfzlcumlgolbbwhttqdnreabdaspwrwp
这个序列不具有普通英语的特点。
　　对接收到的密文解密，再对所得明文的合法性进行判别，这不是一件容易的事。例如，若明文是二进制文件或数字化的X射线，那么很难确定解密后的消息是真实的明文。因此攻击者可以发布任何消息并伪称是发自合法用户的消息，从而造成某种程度的欺骗。
　　解决这个问题的方法之一：要求明文具有某种易于识别的结构，并且不通过加密函数是不能重复这种结构的。例如，可以考虑在加密前对每个消息附加一个错误检测码，也称为帧校验序列（FCS）或校验和，如图5-2（a）所示。A准备发送明文消息M，那么A将M作为函数F的输入，产生FCS，将FCS附加在M后并对M和FCS一起加密。在接收端，B解密其收到的信息，并将其看作消息和附加的FCS，B用相同的函数F重新计算FCS。若计算得到的FCS和接收到的FCS相等，则B认为消息是真实的。任何随机的位串不可能产生M和FCS之间的上述联系。

图5-2  内部和外部错误控制
　　注意，FCS和加密函数执行的顺序很重要。Diffie等[Diffie?等 1979]将如图5-2（a）所示的这种序列称为内部错误控制，以与外部错误控制（见图5-2（b））对应。对于内部错误控制，由于攻击者很难产生密文，使得解密后其错误控制位是正确的，因此内部错误控制可以提供认证；如果FCS是外部码，那么攻击者可以构造具有正确错误控制码的消息，虽然攻击者不知道解密后的明文是什么，但他可以造成混淆并破坏通信。
　　错误控制码仅是具有上述结构的一个例子。事实上，在待发送的消息中加入任何类型的结构信息都会增强认证能力。分层协议通信体系可以提供这种结构，例如，可以考虑使用TCP/IP传输的消息结构，图5-3给出的TCP段的格式说明了TCP报头的结构。假定每

图5-3　TCP段
对主机共享一个密钥，并且无论是何种应用，每对主机间都使用相同的密钥进行信息交换，那么可以对除IP报头外的所有数据报加密，如图5-4所示，如果攻击者用一条消息替代加密后的TCP段，那么解密后得出的明文将不等于原IP报头。在这种方法中，头不仅包含校验和，还含有其他一些有用的信息，如序列号。因为对于给定连接，连续的TCP段是按顺序编号的，所以加密使攻击者不能删除任何段或改变段的顺序。
2. 公钥加密
　　使用公钥加密（见图5-1（b））可提供保密性，但不能提供认证。发方A使用收方B的公钥对M加密，由于只有B拥有相应的私钥，所以只有B能对消息解密。但是任何攻击者可以假冒A用B的公钥对消息加密，所以这种方法不能保证消息发方A的身份真实性。

图5-4　不同加密策略的实现
　　若要提供认证，则A用其私钥对消息签名，而B用A的公钥对接收的签名进行验证（见图?5-1（c））。因为只有A拥有，能产生用可验证的签名，所以该消息一定来自A。同样，明文也必须有某种内部结构以使收方能区分真实的明文和随机的位串。
　　假定明文具有这种结构，那么图?5-1（c）的方法既可提供认证，又可提供数字签名功能。由于只有A拥有，所以只有A能够产生密文，甚至收方B也不能产生密文，因此若B接收到密文消息，则B可以确认该消息来自A。事实上，A通过用其私钥对消息加密实现对该消息“签名”。
　　注意，这种方法不能提供保密性，因为任何拥有A的公钥的人都可将密文解密。
　　如果既要提供保密性又要提供认证，那么A可先用其私钥对M加密，这就是数字签名；然后A用B的公钥对上述结果加密，这可保证保密性（图5-1（d））。但这种方法也有缺点，即一次通信中要执行4次复杂的公钥算法。
　　表5-1归纳总结了各种消息加密方法在提供保密性和认证方面的特点。
表5-1  各种消息加密方法在提供保密性和认证方面的特点

格    式
特    点
对称加密

提供保密性：只有A和B共享K
提供认证：只能发自A；传输中未被改变；需要某种数据组织形式或冗余
不能提供数字签名：收方可以伪造消息；发方可以否认消息
公钥（非对称）加密

提供保密性：只有B拥有用于解密的密钥
不能提供认证：任何一方都可用对消息加密并假称是A
公钥加密：认证和签名

提供认证和签名：只有A拥有用于加密的密钥；传输中未被改变；需要某种数据组织形式或冗余；任何一方可用验证签名
公钥加密：保密性、认证和签名

提供保密性（因为）
提供认证和签名（因为）5.1.2  消息认证码
　　消息认证码又称MAC，也是一种认证技术，它利用密钥生成一个固定长度的短数据块，并将该数据块附加在消息之后。在这种方法中，假定通信双方，如A和B，共享密钥K。若A向B发送消息，则A计算MAC，它是消息和密钥的函数，即，其中：
　　　　　　　　　　　　　　　　M=输入消息
　　　　　　　　　　　　　　　　C=MAC函数
　　　　　　　　　　　　　　　　K=共享密钥
MAC=消息认证码
　　消息和MAC被一起发送给收方。收方对接收到的消息用相同的密钥K进行相同计算，得出新的MAC，并将接收到的MAC与其计算出的MAC进行比较（见图5-5（a））。如果假定只有收发双方知道该密钥，且若接收到的MAC值与计算得出的MAC值相等，则有：
　　（1）收方可以相信消息未被修改。如果攻击者改变了消息，但他无法改变相应的     MAC，那么收方计算出的MAC将不等于接收到的MAC。因为已假定攻击者不知道密钥，所以他不知道应如何改变MAC才能使其与修改后的消息相一致。
　　（2）收方可以相信消息来自真正的发方。因为其他各方均不知道密钥，因此不能产生具有正确MAC的消息。
　　（3）如果消息中含有序列号（如HDLC、X.25和TCP中使用的序列号），那么收方可以相信消息顺序是正确的，因为攻击者无法成功地修改序列号。
　　MAC函数与加密类似。其区别之一是MAC算法不要求可逆性，而加密算法必须是可逆的。一般而言，MAC函数是多对一函数，其定义域由任意长的消息组成，而值域由所有可能的MAC和密钥组成。若使用n位长的MAC，则有2n个可能的MAC，而有N条可能的消息，其中，。若密钥长为k，则有2k种可能的密钥。
　　例如，假定使用100位的消息和10位的MAC，那么总共有种不同的消息，但仅有种不同的MAC。所以平均而言，同一MAC可以有条不同的消息产生。若使用的密钥长为5位，则从消息集合到MAC值的集合有种不同的映射。
　　可以证明，因认证函数的数学性质，与加密相比，认证函数更不易被攻破。
　　如图5-5（a）所示的过程可以提供认证但不能提供保密性，因为整个消息是以明文形式传送的。若在MAC算法之后（见图5-5（b））或之前（见图5-5（c））对消息加密，则可以获得保密性。这两种情形都需要两个独立的密钥，并且收发双方共享这两个密钥。在第1种情形中，先将消息作为输入，计算MAC，并将MAC附加在消息后，然后对整个消息数据块加密；在第?2?种情形中，先将消息加密，然后将此密文作为输入，计算?MAC，并将MAC附加在上述密文之后形成待发送的消息数据块。一般而言，将MAC直接附加于明文之后更优，所以通常使用图5-5（b）中的方法。

图5-5  消息认证码（MAC）的基本应用
　　对称加密可以提供认证，且它已广泛应用于现有产品中，那么为什么不直接使用这种方法而要使用分离的消息认证码呢？Davies等提出了三种使用消息认证码的情形。
　　（1）有许多应用是将同一消息广播给很多收方。例如，需要通知各用户网络暂时不可使用，或一个军事控制中心要发一条警报。在这种情况下，一种经济可靠的方法就是只要一个收方负责验证消息的真实性，所以消息必须以明文加上消息认证码的形式进行广播。上述负责验证的收方拥有密钥并执行认证过程，若MAC错误，则发警报通知其他收方。
　　（2）在信息交换中，可能有这样一种情况，即通信的某一方的处理负荷很大，没有时间解密所有接收到的消息，此时该收方应具备随机选择消息并对其进行认证的能力。
　　（3）对明文形式的计算机程序进行认证是一种很有意义的服务。运行一个计算机程序不必每次对其解密，因为每次对其解密会浪费处理器资源。若将消息认证码附于该程序之后，则可在需要保证程序完整性的时候才验证消息认证码。
　　除此以外，还有下述三种情形。
　　（1）一些应用并不关心消息的保密性，而关心消息认证。例如，简单网络管理协议版本3（SNMP??v3）就是这样的例子，它将提供保密性和提供认证分离开来。对这些应用，管理系统应对其接收到的SNMP消息进行认证，这一点非常重要，尤其是当消息中包含修改系统参数的命令时更是如此，但管理系统不必对SNMP传输的消息进行加密。
　　（2）将认证和保密性分离开来，可使层次结构更加灵活。例如，可能希望在应用层对消息进行认证，而在更低层上，如传输层，则可能希望提供保密性。
　　（3）仅在接收消息期间对消息实施保护是不够的，用户可能希望延长对消息的保护时间。就消息加密而言，消息被解密后就不再受任何保护，这样只是在传输中可以使消息不被修改，而不是在收方系统中保护消息不被修改。由于收发双方共享密钥，因此MAC不能提供数字签名。
　　表5-2归纳总结了图5-5中各种采用MAC的认证方法在提供保密性和认证方面的特点。
表5-2  各种采用MAC的认证方法在提供保密性和认证方面的特点

格   式
基 本 应 用
消息认证

提供认证：只有A和B共享K
消息认证和保密性：
与明文有关的认证

提供认证：只有A和B共享K1
提供保密性：只有A和B共享K2
消息认证和保密性：
与密文有关的认证

提供认证：使用K1
提供保密性：使用K2
5.1.3  杂凑函数
　　杂凑函数（Hash Function）是将任意长的数字串M映射成一个较短的定长输出数字串H的函数，以h表示，易于计算，称为M的杂凑值，也称杂凑码、杂凑结果等，或简称杂凑。这个H无疑打上了输入数字串的烙印，因此又称其为输入M的数字指纹（Digital Finger Print）。h是多对一映射，因此不能从H求出原来的M，但可以验证任一给定序列是否与M有相同的杂凑值。
　　单向杂凑函数还可按其是否有密钥控制划分为两大类。一类有密钥控制，以h(k,?M)表示，为密码杂凑函数；另一类无密钥控制，为一般杂凑函数。无密钥控制的单向杂凑函数，其杂凑值只是输入字串的函数，任何人都可以计算，因而不具有身份认证功能，只用于检测接收数据的完整性，如篡改检测码（Manipulation Detection Code，MDC），用于非密码计算机应用中。有密钥控制的单向杂凑函数，要满足各种安全性要求，其杂凑值不仅与输入有关，而且与密钥有关，只有持此密钥的人才能计算出相应的杂凑值，因而具有身份验证功能，如消息认证码（Message Authentication Code，MAC）[ANSI X 9.9 1986]。此时的杂凑值也称作认证符或认证码。密码杂凑函数在现代密码学中有重要作用。本节主要讨论密码杂凑函数。
　　杂凑函数在实践中有广泛的应用。在密码学和数据安全技术中，它是实现有效、安全可靠的数字签名和认证的重要工具，是安全认证协议中的重要模块。由于杂凑函数应用的多样性和其本身的特点而有很多不同的名字，其含义也有差别，如压缩函数、紧缩函数、数据认证码（Data Authentication Code）、消息摘要（Message Digest）、数字指纹、数据完整性校验（Data Integrity Check）、密码检验和（Cryptographic Check Sum）、消息认证码、篡改检测码等。
　　密码学中所用的杂凑函数必须满足安全性的要求，要能防伪造，抗击各种类型的攻击，如生日攻击、中途相遇攻击等。因此必须深入研究杂凑函数的性质，从中找出能满足密码学需要的杂凑函数。下面首先引入一些基本概念。
　　单向杂凑函数是消息认证码的一种变形。与消息认证码一样，杂凑函数的输入是大小可变的消息M，输出是定长的杂凑值。与MAC不同，杂凑值运算不使用密钥，它仅是输入消息的函数。杂凑值有时也称为消息摘要。杂凑值也是所有消息位的函数，它具有错误检测能力，即改变消息的任何一位或多位都会导致杂凑值的改变。
消息认证码
　　MAC也称为密码校验和，它由下述形式的函数C产生：

其中，M是一个变长消息，K是收发双方共享的密钥，是定长的认证符。在假定或已知消息正确时，将MAC附于发方的消息之后发送给收方；收方可通过计算MAC来认证该消息。
5.2.1  对MAC的要求
　　为了获得保密性，可用对称或非对称密码对整个消息加密，这种方法的安全性一般依赖于密钥的位长。除了算法中本身的某些弱点外，攻击者可以对所有可能的密钥进行穷举攻击。对于一个k位的密钥，穷举攻击一般需要步。对仅依赖于明文的攻击，若给定密文C，攻击者要对所有可能的计算，直到产生的某具有适当的明文结构为止。
　　而对MAC来讲情况则完全不一样。一般来讲，MAC函数是多对一函数。攻击者如何用穷举法找到密钥呢？如果没有提供保密性，那么攻击者可访问明文形式的消息及其MAC。假定，即假定密钥位数比MAC长，那么对满足的和，密码分析者要对所有可能的密钥值计算，那么至少有一个密钥会使得。注意，总共会产生个MAC，但只有个不同的MAC值，所以许多密钥都会产生正确的MAC，而攻击者却不知道哪个是正确的密钥。一般来说，有个密钥会产生正确的MAC，因此攻击者必须重复下述攻击。
　　（1）循环1。
　　给定M1，MAC1= CK(M1)。
　　对所有个密钥，判断。
　　匹配数≈2(k?n)。
　　（2）循环2。
　　给定M2，MAC2= CK(M2)。
　　对余下的2(k?n)个密钥判断MACi= (M2)。
　　匹配数≈2(k?2n)。
　　平均来说，若，则需次循环。例如，如果使用80位的密钥和长为32位的MAC，那么第1次循环会得到约248个可能的密钥，第2次循环会得到约个可能的密钥，第3次循环则得到唯一一个密钥，这个密钥就是发方所使用的密钥。
　　如果密钥的长度小于或等于MAC的长度，则很可能在第1次循环中就得到一个密钥，当然也可能得到多个密钥，这时攻击者还需对新的（消息，MAC）对执行上述测试。
　　由此可见，用穷举法确定认证密钥不是一件容易的事，而且确定认证密钥比确定同样长度的加密密钥更困难。不过可能存在不需要寻找密钥的其他攻击。
　　分析下面的MAC算法。令消息是由64位分组连接而成的。定义：

其中，是异或（XOR）运算，加密算法是电子密码本模式DES，那么密钥长为56位，MAC长为64位。若攻击者知道，则确定K的穷举攻击需执行至少次加密，但是攻击者可以用任何期望的至替代至，用替代来进行攻击，其中的计算如下。

　　攻击者可以将至与原来的MAC连接成一个新的消息，而收方却认为该消息是真实的。用这种方法，攻击者可以随意插入任意长为位的消息。
　　因此，评价MAC函数的安全性时，应该考虑对该函数的各种类型的攻击。下面介绍MAC函数应满足的要求。假定攻击者知道MAC函数C，但不知道K，那么MAC函数应具有下述性质。
　　（1）若攻击者已知M和CK(M)，想构造满足CK(M′)=CK(M)的消息，在计算上是不可行的。
　　（2）CK(M)应为均匀分布，即对任何随机选择的消息和，CK(M)=CK(M′)的概率是，其中，n是MAC的位数。
　　（3）设是M的某个已知的变换，即。例如，f可表示逆转M的一位或多位，那么Pr[CK(M)=CK(M′)]=2?n。
　　前面已介绍过，攻击者即使不知道密钥，也可以构造出与给定MAC匹配的新消息，第1个要求就是针对这种情况提出的。第2个要求是为了阻止基于选择明文的穷举攻击，也就是说，假定攻击者不知道K，但可能知道MAC函数，能对消息产生MAC，那么攻击者可对各种消息计算MAC，直至找到与给定MAC相同的消息为止。如果MAC函数具有均匀分布特征，那么穷举法平均需要步才能找到具有给定MAC的消息。
　　（4）认证算法对消息的某一部分或位的保护不应比其他部分或位更弱；否则，已知M和CK(M)的攻击者可以对M的已知“弱点”处进行修改，然后再计算MAC，这样有可能更早得出具有给定MAC的新消息。
5.2.2  基于杂凑函数的MAC
　　杂凑函数自然而然地成为数据完整性的一种密码原型。在共享密钥的情况下，杂凑函数将密钥作为它的一部分输入，另一部分输入为需要认证的消息。因此，为了认证消息M，发方计算

其中，k为收方和发方的共享密钥，“‖”表示比特串的连接。
　　根据杂凑函数的性质可以假设：为了用杂凑函数生成一个有效的关于密钥k和消息M的MAC，该主体必须拥有正确的密钥和正确的消息。与发方共享密钥k的收方应当由所接收的消息M重新计算出MAC，并检验同所接收的MAC是否一致。如果一致，就可以相信该消息来自所声称的发方。
　　因为这样的MAC是使用杂凑函数构造的，因此也称为HMAC（用杂凑函数构造的MAC）。为谨慎起见，HMAC通常按照下面的形式计算：

　　也就是说，密钥是要认证消息的前缀和后缀，这是为了阻止攻击者利用某些杂凑函数的“轮函数迭代”结构。如果不用密钥保护消息的两端，某些杂凑函数所具有的已知结构，可使攻击者不必知道密钥k就可以选择一些数据用作消息前缀或后缀来修改消息。
5.2.3  基于分组加密算法的MAC
　　构造密钥杂凑函数的标准方法是使用分组密码算法的CBC运行模式。这样构造的密钥杂凑函数通常称为CBC-MAC。
　　令表示输入消息为m，密钥为k的分组密码加密算法。为了认证消息M，发方首先对M进行分组：

其中，每个子消息组mi的长度都等于分组加密算法输入的长度。如果最后一个子消息组长度小于分组长度，就必须对其填充一些随机值。设为随机初始向量。现在，发方用CBC加密：
，
然后，数值对

作为MAC将附在M后送出。
　　很明显，在生成CBC-MAC的计算中包括不可求逆的数据压缩（本质上，CBC-MAC是整个消息的“短摘要”），因此CBC-MAC是一个单向变换，而且所用的分组密码加密算法的混合变换性质为这个单向变换增加了一个杂凑特点（也就是说，将MAC分布到MAC