密码编码学原理之密码学数据完整性-526互联

当数据从发送方传递到接收方手中的时候，接收方无法保证数据的质量，由于信道安全性的原因，消息可能缺失、可能被篡改、可能被附加了一些有害的数据。为了能够验证数据的有效性，需要使用消息认证算法校验消息的完整性。另外接收方通常也需要确认消息是正确的发送方发送的，这需要数字签名的算法来保证。

哈希函数的特性

消息认证和数字签名的算法基础就是密码学哈希函数，哈希函数使用变长的数据 $M$ 生成一个定长的哈希值 $h=H(M)$ 。哈希函数 $H$ 的特点是输入数据的长度是任意的，但是输出数据的长度是固定的。对于任意输入消息，计算哈希值 $h=H(M)$ 比较容易，而通过 $h$ 得到 $M$ 是不可行的。对于任意输入数据 $M \ne M’$ ，有 $H(M) \ne H(M’)$ 。如果 $M \ne M’$ ，且 $H(M)=H(M’)$ ，通过 $M$ 计算 $M’$ 是不可行的。消息 $M$ 的任意一位或几位改变， $H(M)$ 会发生很大的变化，并且变化值是随机的。

常见的哈希函数包括MD5、SHA-1、SHA-256、SHA-384、SHA-512等，其中SHA-256、SHA-384以及SHA-512等被统称为SHA-2，此外还有最新的SHA-3。MD5和SHA-1已经被攻破，而SHA-2目前还没有明显的弱点，所以新的系统都应该使用SHA-2作为哈希函数。SHA-2的具体算法请参考《FIPS 180-3》以及《RFC 6234》。

哈希函数的应用

哈希函数最常见的应用就是消息认证，发送方通过哈希函数计算一个消息摘要，然后将消息摘要和消息一同发送给接收方，接收方收到消息后，计算消息摘要然后与收到的摘要对比确认消息是否被改动过。

哈希函数另一个常见的应用是数字签名，发送方通过哈希值计算消息摘要，然后通过私钥加密数据摘要，将加密后的数据摘要和数据一起发送给接收方。接收方收到数据后，通过发送方的公钥解密数据摘要，然后通过与计算的数据摘要做对比以确认数据的完整性。因为接收方使用了发送方的公钥解密数据摘要，所以可以确定该数据确实是发送方发送的。

哈希函数另外的一个应用是单向口令。数据库或者操作系统保存用户口令的哈希值，用户登录后系统计算哈希值与保存的值比较以确定口令的正确性。如果口令文件不慎丢失也无所谓，因为不能通过口令文件还原出真实的口令。此外哈希函数还可以作为病毒和入侵检测使用。

消息认证

在通信过程中我们经常会遇到一种类型的攻击模式，攻击者扮演中间人的角色截获消息，然后给通信双方发送伪造的消息，或者是篡改消息，包括篡改消息内容、消息的序列或者消息的时间性质。消息认证就是为了防止这类攻击而发明的技术，接收方通过消息认证来确认消息的完整性和有效性。

消息认证提供两方面的含义，一方面是消息认证函数，另一方面是认证加密。消息认证函数生成关于消息的认证码，它保证了消息的完整性和有效性。认证加密保证消息以及消息认证码的保密性，使攻击者不能够生成虚假的消息认证码取代真实的消息认证码。

认证函数

我们首先讨论一下消息认证函数。最简单的消息认证函数是哈希函数，发送方通过哈希函数为消息计算一个摘要，然后将消息和摘要一同发送给接收端，接收端收到消息后计算摘要并与收到的摘要对比，以确定消息是否被篡改，过程如图所示：

使用哈希函数作为消息认证函数

使用哈希函数作为消息认证函数很容易被伪造，当攻击者篡改消息后很容易生成对应的认证码，这样接收方是无法分辨消息和认证码的真伪的。消息认证码(MAC)就可以有效的规避这个问题，消息认证码使用消息和共享密钥生成认证码：

$MAC = C(K, M)$

消息认证的过程与使用哈希函数作为消息认证码是类似的，过程如下图所示：

使用MAC作为消息认证函数

哈希函数作为消息认证函数之所以不安全是因为它没有引入共享密钥，MAC作为消息认证函数之所以安全是因为它引进了共享密钥。将密钥引入哈希函数用以生成认证码后，算法就变成了基于哈希函数的MAC：HMAC。HMAC使用共享密钥 $K$ 和消息 $M$ 生成认证码，它可以表示为如下的公式：

$HMAC(K, M) = H[f(IV, (K^+ \oplus opad))‖H[f(IV, (K^+ \oplus ipad))‖M]]$

这里 $IV$ 是哈希函数的初始向量， $K^+$ 是根据消息分组长度在左侧填充0后的密钥， $f$ 是哈希压缩函数， $H$ 是哈希函数(MD5, SHA-1, SHA-512等)， $ipad$ 和 $opad$ 都是与分组长度有关的固定值。关于 $HMAC$ 的详细算法请参考《RFC 2104》。

除了哈希函数可作为生成MAC的算法外，分组加密算法也可以作为生成消息认证码的算法，基于分组加密的MAC就是CMAC。AES、TDEA等算法都适用于CMAC，只是不同算法处理的分组长度不同，AES是128位，TDEA是64位。处理的过程是将消息分组与上一轮密文分组进行异或，之后使用共享密钥加密，得到的最后的密文的前 $s$ 位作为消息认证码，可以用如下方式表示：

$C_1 = E(K, M_1)$

$C_i = E(K, [M_i \oplus C_{i-1}]),\ i = 2,...,n-1$

$C_n = E(K, [M_n \oplus C_{n-1} \oplus K_1])$

$T = MSB_s(C_n)$

当消息长度是加密分组的整数倍的时候使用上述公式，如果不是分组长度的整数倍需要在消息后面进行填充，然后将 $K_1$ 变成 $K_2$ 。CMAC的详细算法可以参考《RFC 4493》。

认证加密

接下来我们再讲一讲认证加密。认证加密是为了在保证数据完整性的基础上提供保密性，为了提供完整性和保密性，我们可以使用先哈希再加密(H->E)的方式，或者是先认证再加密(A->E)的方式，或者是先加密再认证(E->A)的方式，再或者是使用两个密钥独立进行认证和加密(A+E)的模式。这些模式的哈希或者认证和加密的算法都是单独设计的，而NIST提出了两种工作模式综合考虑的认证和加密，将两者结合在一起。

分组密码链接-消息认证码(CCM)工作模式是基于AES加密算法、CTR工作模式以及CMAC认证算法的一种工作模式。CCM包括两部分，第一部分是使用CMAC生成认证码，第二部分是使用CTR模式的AES对明文和认证码加密。可以将消息认证码表示为如下过程：

$T = CMAC(K, [N‖A‖P])$

其中 $T$ 是生成的消息认证码， $K$ 是密钥， $N$ 是时变值， $A$ 是关联数据， $P$ 是明文。第二部分对明文 $P$ 和消息认证码 $T$ 加密，可以表示为：

$C = CTR(K, P, Ctr_1)‖CTR(K, T, Ctr_0)$

其中 $CTR$ 函数表示使用AES算法的CTR模式进行分组加密， $K$ 是密钥， $P$ 是明文， $T$ 是消息认证码， $Ctr_0$ 和 $Ctr_1$ 表示起始的计数器值。CCM工作模式的详细算法请参考《RFC 3610》。

另一种认证加密的工作模式是Galois计数器工作模式(GCM)。GCM的消息认证码生成以及加密都不使用前面讨论过的算法，而是使用新设计的GHASH哈希函数以及GCTR加密算法。GHASH可以表示为：

$GHASH(H, X) = (X_1 \bullet H^m) \oplus (X_2 \bullet H^{m-1}) \oplus … \oplus (X_m \bullet H)$

其中明文 $X$ 可以表示为 $X_1‖X_2‖…‖X_m$ $m$ 个分组， $H$ 是哈希密钥， $H^m$ 是 $H$ 的 $m$ 次幂， $\bullet$ 表示 $GF(2^{128})$ 域上的乘法。GCTR按照如下过程表示：

$CB_1 = ICB$

$CB_i = inc_{32}(CB_{i-1}),\ i = 2,...,n$

$Y_i = X_i \oplus E(K, CB_i),\ i = 1,...,n$

$Y = Y_1‖Y_2‖…‖Y_n$

其中明文 $X$ 可以表示为 $X_1‖X_2‖…‖X_n$ $n$ 个分组， $ICB$ 是计数器的初始值， $inc_{32}(CB_{i-1})$ 表示将 $CB_{i-1}$ 的右32位增加 $1\ mod\ 2^{32}$ 。GCM是先加密后认证的模式，GCM的工作过程可以表示为，加密的过程如下：

$H = E(K, 0^{128})$

$C = GCTR(K, P, J_0)$

首先计算哈希密钥，通过加密128位0分组获得 $H$ ，然后初始化计数器 $J_0$ ，最后获得密文 $C$ 。消息认证码 $T$ 可以表示为：

$S = GHASH(H, [A‖0^v‖C‖0^u‖len(A)_{64}‖len(C)_{64}])$

$T = GCTR(K, S, J_0)$

最后将分组 $(C, T)$ 发送给接收端。关于GCM的详细算法请参考《NIST SP800-38D》。

数字签名

消息认证只能保护消息不被第三方攻击，但是不能保证来自收发双方的攻击。来自收发双方的攻击也包括多种形式，例如在进行转账的时候，接收方伪造了发送方的消息，增加了转账的金额，并且声称这是发送方发送的真实金额，因为双方共享密钥，接收方所以无法确认是否为有效的消息。再比如发送方发送了消息给接收方，该消息造成了一定的损失，但是发送方声称自己没有发送该消息，因为接收方可以伪造这个消息，这样也无法确定该消息到底是否为真实的消息。

数字签名可以防止这类攻击，数字签名一般是采用私钥加密认证码，然后将消息和加密后的认证码一起发送给接收方，接收方通过公钥解密认证码并比较，确定消息的完整性，因为消息可以使用发送方公钥解密，所以确认了该消息由发送方发送，一般的流程如下：

数字签名的流程

上图是数字签名的基本原理，真正的数字签名算法要复杂的多，NIST发布了数字签名算法(DSA)，后续又经过了改版，2013年更新为FIPS 186-4：数字签名标准(DSS)，其中包含DSA和基于椭圆曲线密码学版本的DSA算法(ECDSA)，这些算法比较复杂，有兴趣的读者可以参考《FIPS PUB 186-4: Digital Signature Standard (DSS)》。