应用密码学入门

从哈希到加密，一网打尽。

1哈希
2MAC
3未完待续......

起步

MAC，即消息认证码（Message Authentication Code），用于检查某段消息的完整性，并作身份验证。它的目标不是加密某个消息，而是：

  • 确认消息是否被篡改。
  • 确认消息是否来自持有共享密钥的一方。

一个简单的想法是使用哈希来作为认证码。我们知道，哈希函数能生成消息 MM 的对应哈希摘要，但是问题在于我们无法通过这个摘要来标识消息发送者的身份。我们举一个例子，如果 Alice 想要将消息发送给 Bob，而中间人如果能够将消息 MM 篡改为 M′M'，那么中间人也自然有能力针对 M′M' 求出对应的哈希摘要，并将篡改过的消息和哈希摘要传递给 Bob，而消息的接受者 Bob 无法辨别这个消息到底是否被篡改过。

在大部分实现中，虽然的确会间接使用到哈希函数，不过这些实现会在哈希函数之外再引入一个只有通信双方知道的密钥 key（并且也并非简单地直接调用哈希函数），因此攻击者即便知道消息和哈希算法，也无法伪造出正确的认证码（因为不知道 key）。接收者能确认消息来自某个持有共享密钥的一方，并且没有被不知道密钥的人篡改。

如前所述，我们知道，一个 MAC 实现需要接收一个密钥 key 和消息内容，然后生成对应的消息认证码。当我们需要验证消息的时候，我们会重新计算，并比较自己计算的认证码和随消息附带的认证码是否一致。因为这里的 key 是仅通信双方知晓的，这样，一旦发现不一致，就应将消息视为未通过认证并拒绝处理。

基于哈希算法的 MAC 实现很常见。例如 HMAC 和 KMAC 都属于这类实现。需要注意，在一些情况中，我们不能直接把密钥和消息拼接后做普通哈希，例如 H(K∥M)H(K \mathbin{\|} M)，这类自制构造可能会受到长度扩展攻击。我们会在后文进一步讨论。不过除了基于哈希算法的 MAC 实现之外，我们还有基于其他 MAC 实现，比如 CMAC 就基于分组密码实现。

数字签名和 MAC 有相似的目标，不过，数字签名不要求双方共享一个密钥，它底层使用公钥密码学，所以验证完整性的一方只要信任签名者的公钥即可。MAC 和数字签名最重要的区别就是是否存在非对称性。同时，因为 MAC 使用共享密钥，所以它不能提供数字签名那种不可否认性：Alice 和 Bob 都知道同一个 key，那么 Bob 也可以生成合法的 MAC。

还有一些场景中，我们希望加密某个消息，同时我们也希望加上认证码来防止被篡改，那么我们一般会使用 AEAD 算法。

实现

HMAC

HMAC（Hash-based Message Authentication Code），即基于哈希的消息认证码。

HMAC 是一个主流的 MAC 实现，它一般使用 SHA-2 算法来计算认证码。对于 SHA-2 这类 Merkle-Damgard 结构的哈希函数，简单的前缀 MAC 构造可能受到长度扩展攻击；HMAC 则使用内外两层哈希和不同的填充值，将密钥和消息放在特定结构中。我们可以选择使用不同的 SHA-2 函数，例如 SHA-256 或者 SHA-512，此时我们一般称其为 HMAC-SHA256 或者 HMAC-SHA512。

给定哈希函数 HH、密钥 KK 和消息 MM，HMAC 可以写为：

HMAC(H,K,M)=H((K⊕opad)∥H((K⊕ipad)∥M))\mathrm{HMAC}(H, K, M) = H((K \oplus \mathrm{opad}) \mathbin{\|} H((K \oplus \mathrm{ipad}) \mathbin{\|} M))

其中 ipad 和 opad 是两个固定常量，分别用于内层和外层计算。这里的 KK 不是原始密钥直接参与异或，而是先按照哈希函数的 block size 做规范化：如果密钥太长，先对密钥做哈希；如果密钥太短，则补零到 block size。因为使用了内外两层哈希和不同的 pad，即使底层哈希算法会受到长度扩展攻击，HMAC 也不会退化为简单的前缀 MAC。

KMAC

KMAC 是 NIST SP 800-185 中基于 Keccak / cSHAKE 的一种 MAC 算法。因为它底层使用 Keccak 算法，不存在 SHA-2 那类 Merkle-Damgard 结构上的长度扩展问题。

例如 KMAC128 算法实现如下（这里的 128 的意思是安全等级，即表示目标安全强度是 128 bits）：

def kmac128(key: bytes, message: bytes, mac_len: int) -> bytes:
    message = bytepad(encode_string(key), 168) + message + right_encode(mac_len * 8)
    return cshake128(input_data=message, output_len=mac_len, function_name="KMAC")

值得注意的是，这个表示经过了一定程度的简化，不过大体上和真实世界中的 KMAC 逻辑是一致的。KMAC 的核心形式是先用规范化编码把 key、消息和输出长度组织起来，再调用带函数名定制的 cSHAKE。

链接和引用

  1. 深入浅出密码学. [美] David Wong 著, 韩露露等译, 人民邮电出版社.
  2. cryptologie.net / Posts / SHAKE and SP 800-185: https://www.cryptologie.net/posts/shake-and-sp-800-185/
  3. NIST / SP 800-185 / SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash, and ParallelHash: https://csrc.nist.gov/pubs/sp/800/185/final
上一篇哈希