3.1　散列函数

散列函数是现代密码学的重要组成部分，不仅用于认证，还与口令安全存储、恶意代码检测、正版软件检测、数字签名相关。因此，本节首先介绍散列函数。

3.1.1　散列函数的要求

散列函数（Hash function），也称为“哈希函数”或“杂凑函数”，在应用于长度任意的数据块时将产生固定长度的输出。散列函数可以表示为：

h=H(M)

其中，H代表散列函数，M代表任意长度的数据（可以是文件、通信消息或其他数据块），h为散列函数的结果，称为“散列值”或“散列码”。当M为通信消息时，通常将h称为“报文摘要（message digest）”或“消息摘要”。对于特定的一种散列函数，散列值的长度是固定的。对M的任意修改都将使M的散列值出现变化，通过检查散列值即可判定M的完整性。因此散列值可以作为文件、消息或其他数据块的具有标识性的“指纹”（通常称为“数字指纹”）。

采用散列函数来保证文件（或消息）的完整性，首先需要通过散列函数获得文件（或消息）的散列值，并将该值妥善保存。在需要对文件（或消息）进行检查的时候，重新计算文件（或消息）的散列值，如果发现计算得到的散列值与保存的结果不同，则可以推断文件（或消息）被修改过。

安全领域使用的散列函数通常需要满足一些特性[1]，如表3-1所示。

具有单向性的散列函数可以应用于用户口令（或密码）存储。在信息系统中如果口令以明文形式存储，则存在很大的安全风险。一旦攻击者进入系统，或者系统由恶意的管理员管理，用户口令很容易泄露。而采用散列值来存储口令，散列函数的单向性可以确保即使散列值被攻击者获取，攻击者也无法简单地通过散列值推断出用户口令。同时，这种方法也不会影响对用户进行身份认证，用户在登录时输入的口令通过散列函数计算，如果所得的散列值与系统存储的相应账号的散列值相同，则允许用户进入系统。

抗弱碰撞性对于保证消息的完整性非常重要。举例来看，用户发送消息M，为了确保消息的完整性，将消息M的散列值的加密结果一同发送。在此过程中，之所以对散列值进行加密，是因为散列函数是公开的，如果不加密，攻击者可能修改消息M并同时产生修改后消息的散列值，接收方将难以察觉异常。如果散列函数不满足抗弱碰撞性，则攻击者可以找到一个不同于M的消息M＇，M＇的散列值与M的散列值相同，攻击者如果用消息M＇替换M，消息的接收方将无法发现消息已经遭到了篡改。

一个函数如果是抗强碰撞的，那么也同样是抗弱碰撞的，但反之则不一定成立。一个函数可以是抗强碰撞的，但不一定是抗原像攻击的，反之亦然。一个函数可以是抗弱碰撞的，但不一定是抗原像攻击的，反之亦然。

如果一个散列函数满足安全性需求（1）至（5），则称该函数为弱散列函数，如果还满足第（6）条需求，则该散列函数为强散列函数。第（6）条需求可以防止像生日攻击[2]这种类型的复杂攻击，生日攻击把n比特的散列函数的强度从2n降低到2n/2。一个40比特长的散列码是很不安全的，因为仅仅用220（大约一百万）次随机Hash就可至少以1/2的概率找到一个碰撞。为了抵抗生日攻击，建议散列码的长度至少应为128比特，此时生日攻击需要约264次Hash计算。通常将安全的Hash标准的散列码长度选为≥160比特。

各种数据完整性应用中的散列函数安全性需求如表3-2所示。

除了前面提到的口令安全存储，散列函数还可用于多种安全场景。在恶意代码检测中，常常利用散列函数计算已知恶意代码（源代码或可执行代码）的散列值，并保存在恶意代码特征库中。当需要检测截获的一段代码是否是恶意代码时，首先计算这段代码的散列值，并将其与特征库的散列值进行比较，如果有相等的，则可快速判断出该代码是一个已知的恶意代码。如果不是进行散列值比较，而是进行整段代码比较，则面对海量恶意代码时，效率非常低下。

同样的道理，散列函数亦可用于原版软件检测。当用户下载一个软件后，需要知道这个软件是被修改过的（很多攻击者经常将正版软件重打包，将恶意代码插入其中），还是没改过的原版软件，此时他只需计算该软件的散列值，并将其与软件厂商公布的原版软件的散列值进行比较。如果相同，则可放心使用；否则，该软件被修改过，需要进一步检测。

散列函数在数字签名和消息认证中的应用将在本章的后续章节讨论。MD、SHA是目前比较流行的散列函数，下面对它们进行简要介绍。

3.1.2　MD算法

报文摘要（Message Digest,MD）算法是由Rivest从20世纪80年代末所开发的系列散列算法的总称，历称MD2、MD3、MD4和最新的MD5。

1991年Den Boer和Bosselaers发表文章指出MD4算法的第1步和第3步存在可被攻击的漏洞，将导致对不同的内容进行散列计算却可能得到相同的散列值。针对这一情况，Rivest于1991年对MD4进行了改进，推出新的版本MD5 (RFC 1321)。

与MD4相比，MD5进行了下列改进：

（1）加入了第4轮。

（2）每一步都有唯一的加法常数。

（3）第2轮中的G函数从((X∧Y)∨(X∧Z)∨(Y∧Z))变为((X∧Z)∨(Y∧～Z))，以减小其对称性。

（4）每一步都加入了前一步的结果，以加快“雪崩效应”。

（5）改变了第2轮和第3轮中访问输入子分组的顺序，减小了形式的相似程度。

（6）近似优化了每轮的循环左移位移量，以期加快“雪崩效应”，各轮循环左移都不同。

MD5的输入为512位分组，输出是4个32位字的级联（128位散列值）。具体过程如下：

消息首先被拆成若干个512位的分组，其中最后512位分组是“消息尾+填充字节(100…0)+64位消息长度”，以确保对于不同长度的消息，该分组不相同。而4个32位寄存器字初始化为A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210，它们将始终参与运算并形成最终的散列结果。

接着各个512位消息分组以16个32位字的形式进入算法的主循环，512位消息分组的个数决定了循环的次数。主循环有4轮，每轮分别用到的非线性函数如下：

F(X,Y,Z)=(X∧Y)∨(～X∧Z)

G(X,Y,Z)=(X∧Z)∨(Y∧～Z)

H(X,Y,Z)=X⊕Y⊕Z

I(X,Y,Z)=X⊕(Y∨～Z)

这4轮变换是对进入主循环的512位消息分组的16个32位字分别进行如下操作：将A、B、C、D的副本a、b、c、d中的3个经F、G、H、I运算后的结果与第4个相加，再加上32位字和一个32位字的加法常数，并将所得之值循环左移若干位，最后将所得结果加上a、b、c、d之一，并回送至A、B、C、D，由此完成一次循环。

所用的加法常数由表T来定义，T[i]是i的正弦绝对值之4 294 967 296次方的整数部分（其中i为1…64），这样做是为了通过正弦函数和幂函数来进一步消除变换中的线性特征。

当所有512位分组都运算完毕，ABCD的级联将被输出为MD5散列的结果。下面是一些MD5散列结果的例子：

MD5 ("")=d41d8cd98f00b204e9800998ecf8427e

MD5 ("a")=0cc175b9c0f1b6a831c399e269772661

MD5 ("abc")=900150983cd24fb0d6963f7d28e17f72

MD5 ("message digest")=f96b697d7cb7938d525a2f31aaf161d0

MD5 ("12345678901234567890123456789012345678901234567890123456789012345678

901234567890")=57edf4a22be3c955ac49da2e2107b67a

尽管MD5比MD4要复杂，导致其计算速度较MD4要慢一些，但更安全，在抗分析和抗差分方面表现更好。有关MD5算法的详细描述可参见RFC 1321。

MD5在推出后很长一段时间内，人们认为它是安全的。但在2004年国际密码学会议(Crypto’2004)上，来自中国山东大学的王小云教授做了破译MD5、HAVAL-128、MD4和RIPEMD算法的报告，提出了密码哈希函数的碰撞攻击理论，即模差分比特分析法；2005年王小云教授等人又提出了SHA-1的破解方法。王教授的相关研究成果提高了破解包括MD5、SHA-1在内的5个国际通用的哈希函数算法的概率，给出了系列消息认证码MD5-MAC等的子密钥恢复攻击和HMAC-MD5的区分攻击方法。自此，这5个散列函数被认为不再安全。尽管如此，在一些安全性要求不是特别高的场合下，MD5仍然不失为一种可用的散列函数算法。

3.1.3　SHA算法

SHA（Secure Hash Algorithm）算法是使用最广泛的Hash函数，由美国国家标准与技术研究院（NIST）和美国国家安全局（NSA）设计，包括5个算法，分别是SHA-1、SHA-224、SHA-256、SHA-384和SHA-512，后四个算法有时并称为SHA-2。SHA-1在许多安全协议中被广为使用，如TLS、SSL、PGP、SSH、S/MIME和IPsec等。

SHA算法建立在MD4算法之上，其基本框架与MD4类似。SHA-1算法产生160 bit的散列值，因此它有5个参与运算的32位寄存器字，消息分组和填充方式与MD5相同，主循环也同样是4轮，但每轮进行20次操作，非线性运算、移位和加法运算也与MD5类似，但非线性函数、加法常数和循环左移操作的设计有一些区别。SHA-2与SHA-1类似，都使用了同样的迭代结构和同样的模算法运算与二元逻辑操作。

不同版本SHA算法参数如表3-3所示。

下面以SHA-512为例，简要介绍算法的操作过程。

算法的输入是最大长度小于2128位的消息，并被分成1 024位的分组为单位进行处理，输出是512位的消息摘要。算法的主要步骤如下：

（1）附加填充位。填充消息使其长度模1 024与896同余，即长度≡ 896 (mod 1024)。即使消息已经满足上述长度要求，仍然需要进行填充，因此填充位数在1~1 024之间，填充由一个1和后续的0组成。

（2）附加长度。在消息后附加一个128位的块，将其作为128位的无符号整数（最高有效字节在前），它包含填充前消息的长度。

前两步的结果是产生了一个长度为1 024整数倍的消息。经过扩展后的消息为一串长度为1 024位的消息分组M1,M2,…,MN，总长度为N× 1024位。

（3）初始化Hash缓冲区。Hash函数的中间结果和最终结果保存于512位的缓冲区中，缓冲区用8个64位的寄存器（a,b,c,d,e,f,g,h）表示，并将这些寄存器初始化为下列64位的整数（十六进制值）：

a=6A09E667F3BCC908　b=BB67AE8584CAA73B　c=3C6EF372FE94F82B

d=A54FF53A5F1D36F1　e=510E527FADE682D1　f=9B05688C2B3E6C1F

g=1F83D9ABFB41BD6B　h=5BE0CD19137E2179

这些值以高位在前格式存储，其获取方式如下：前8个素数取平方根，取小数部分的前64位。

（4）以1 024位的分组（128个字节）为单位处理消息。算法的核心是具有80轮运算的模块。每一轮都把512位缓冲区的值abcdefgh作为输入，并更新缓冲区的值。每一轮，如第j轮，使用一个64位的值Wj，该值由当前被处理的1 024位消息分组Mi导出，导出消息即是消息扩展算法。每一轮还将使用附加的常数Kj，其中0≤j≤79，用来使每轮的运算不同。Kj的获取方法如下：对前80个素数开平方根，取小数部分的前64位。这些常数提供了64位随机串集合，可以初步消除输入数据里的统计规律。第80轮的输出和第1轮的输入Hi-1相加产生Hi。缓冲区中的8个字和Hi-1中对应的字分别进行模264的加法运算。SHA-512轮函数比较复杂，读者可参考文献[16]的11.5.1节。

（5）输出。所有N个1 024位分组都处理完以后，从第N阶段输出的是512位的消息摘要。

SHA-512算法具有如下特性：散列码的每一位都是全部输入位的函数。基本函数F多次复杂重复运算使得结果充分混淆，从而使得随机选择两个消息，甚至这两个消息有相似特征，都不太可能产生相同的散列码。正常情况下，要找到两个具有相同摘要的消息的复杂度是2256次操作，而给定摘要寻找消息的复杂度是2512次操作。

SHA-1的安全性如今被密码学家严重质疑。2005年2月，王小云等人发表了对SHA-1的攻击，只需少于269的计算复杂度，就能找到一组碰撞，而此前的利用生日攻击法找到碰撞需要280的计算复杂度。此外，王小云还展示了对58次加密循环SHA-1的破密，在233个单位操作内就找到一组碰撞。2019年10月，密码学家盖坦·勒伦（Gaëtan Leurent）和托马·佩林（Thomas Peyrin）宣布已经对SHA-1成功计算出第一个选择前缀冲突，并选择安全电子邮件PGP/GnuPG的信任网络（参见第10章）来演示SHA-1的前缀冲突攻击。目前为止尚未出现对SHA-2有效的攻击，它的算法跟SHA-1基本上相似，因此人们开始发展其他替代的散列算法。NIST在2007年公开征集新一代NIST的Hash函数标准，称为SHA-3，并于2012年10月公布了设计算法的优胜者，未来将逐渐取代SHA-2。SHA-3的设计者使用一种称为海绵结构的迭代结构方案，详细情况读者可参考文献[16]的11.6节。

SM3是我国政府采用的一种密码散列函数标准，由国家密码管理局于2010年12月17日发布，相关标准为“GM/T 0004-2012 《SM3密码杂凑算法》”，其安全性及效率与SHA-256相当。