消息认证码MAC

消息认证

消息认证，即验证所收到的消息确实来自真正的发送方，而且消息未被篡改过

消息加密提供认证

对于对称加密，理论上其可同时提供消息认证与消息保密性

例如密钥K仅由A、B共享，若A使用密钥K加密消息M并发送给B，则B可以相信消息来自于A，因为只有A能产生出可用K解密的密文

但上述推理其实隐含了一个假设：接收方容易对解密出的明文的可读性进行自动判断

显然实际中这个假设并不容易满足，若消息M是任意二进制序列，比如二进制文件或数字化的X射线等，则很难确定解密后的消息是合法明文还是无意义的位串

这个问题可以使用附加错误检测码来解决，也称为帧校验序列（FCS），但此处不展开说明

对于公钥加密，假设合法明文有易于判断的结构，则也可以同时提供消息认证与消息保密性

若A要给B发送消息M，则A依次用自己的私钥和B的公钥对M加密，就分别提供了认证与保密，前者是因为只有A的公钥才能解密出合法明文，后者是因为除B外没有人能用B的私钥解密

消息认证码

消息认证码MAC又称密码校验和

MAC使用MAC函数产生，其输入是不定长消息和密钥，输出为固定长度的短数据块

例如A、B间共享密钥K，若A要向B发送消息M，则A计算 $M A C = C (K, M)$
A将消息M和MAC同时发送给B，B使用密钥K对接收到的消息使用相同方法计算MAC，并与接收到的MAC比较，若相等，则B可以相信消息来自A且未被修改

MAC函数与加密函数的一个重要区别是，MAC函数不要求可逆性
由于这个性质，MAC与加密相比更不容易被攻破

如果消息需要保密性，则可以先计算MAC，将MAC附加于消息后再应用加密算法

使用MAC的理由

使用MAC而不是加密提供认证有一个很简单的理由，即在不关心保密性时消除解密过程造成的处理器资源浪费

此外将认证和保密分离可是层次结构更加灵活，例如我们可能希望在应用层进行消息认证，而在如传输层这样的底层进行保密

MAC的安全性

MAC函数应具有如下性质

若攻击者已知消息 $M$ 和其认证码 $M A C (K, M)$ ，则构造满足 $M A C (K, M^{'}) = M A C (K, M)$ 的 $M^{'}$ 在计算上不可行
$M A C (K, M)$ 应是均匀分布的，即对任何随机消息 $M$ 和 $M^{'}$ ， $M A C (K, M^{'}) = M A C (K, M)$ 的概率为 $2^{- n}$ ，其中 $n$ 为MAC的位数
若 $M^{'}$ 是 $M$ 的某个已知变换，即 $M^{'} = f (M)$ ，要求 $M A C (K, M^{'}) = M A C (K, M)$ 的概率为 $2^{- n}$

其中最后一点要求MAC函数不应在消息的某个部分弱于其它部分，否则敌手获得M和MAC值后就有可能修改M中弱的部分，从而伪造出一个与原MAC相匹配的新消息

我们可以分析对具备上述条件的MAC的穷举攻击

设密钥长度为k，MAC长度为n，假设攻击者有若干对消息 $M_{i}$ 及其MAC $T_{i}$
第一轮，攻击者枚举 $2^{k}$ 个密钥，并找到约 $2^{k - n}$ 个密钥满足 $T_{1} = M A C (K, M_{2})$
第二轮，攻击者使用 $(M_{2}, T_{2})$ 验证，匹配数约为 $2^{k - 2 n}$
依此类推，攻击者需要约 $\frac{k}{n}$ 轮穷举，说明穷举法确定认证密钥比较困难

MAC的主要局限在与无法抵御重放攻击
例如客户A给银行发消息转账给B，银行验证其MAC并执行了操作，但攻击者截获了该消息及MAC，并对银行反复发送，将会使得银行误以为要多次转账

基于Hash的MAC

简单但不安全的构造

直接将消息附加在密钥之后计算Hash值的构造 $T = M A C (K, M) = H (K | M)$ 称为秘密前缀MAC

秘密前缀MAC易受扩展长度攻击

设 $M^{'}$ 为填充后的消息 $M$ ， $f$ 为安全Hash函数的压缩函数（可参考密码学Hash函数基础）
假设攻击者已知消息M和其MAC值 $T = H (K | M^{'})$ ，则攻击者可选择任意消息 $y$ 并计算出消息 $M^{'} | y$ 的MAC值 $T^{'} = H (K | M^{'} | y) = f (T, y)$

直接将密钥附加在消息之后计算Hash值的构造 $T = M A C (K, M) = H (M | K)$ 称为秘密后缀MAC

对于秘密后缀MAC，若攻击者可以找到两个不同消息 $M, M^{'}$ 使得 $H (M) = H (M^{'})$ ，则对任何密钥K都有 $H (M | K) = H (M^{'} | K)$
显然秘密后缀MAC的安全性取决于Hash函数的抗碰撞性

HMAC的设计目标

基于Hash函数的MAC称为HMAC，其思路是将密钥和消息一起作为哈希函数的输入求哈希值

HMAC的设计目标是将Hash函数视为“黑盒”，具体来说目标如下

可以使用任何现有的哈希函数而不需要对其进行修改
一旦有更快或者更安全的哈希函数，能够容易的对原来的嵌入Hash函数进行替代
能保持原有哈希函数的性能
对密钥的使用和管理要简单
若已知嵌入的哈希函数的强度，则可以知道认证机制抗密码分析的强度

HMAC算法

如图所示为HMAC算法结构，其具体步骤如下

在密钥 $K$ 左侧填充0得到b位的 $K^{+}$ ，令 $S_{i} = K^{+} \oplus i p a d$ ，其中 $i p a d$ 为常数00110110（十六进制36）重复b/8次的结果
将消息M按b位分组并附加于 $S_{i}$ 之后，计算Hash值 $h = H (S_{i} | M)$
令 $S_{o} = K^{+} \oplus o p a d$ ，其中 $o p a d$ 为常数01011100（十六进制5C）重复b/8次的结果
将Hash值h附加于 $S_{i}$ 之后，再次计算Hash值即可获得 $M A C = H (S_{o} | h)$

该过程可表示为 $H M A C (K, M) = H [(K^{+} \oplus o p a d) | H [(K^{+} \oplus i p a d) | M]]$

其中密钥K两次异或是为了伪随机地产生两个密钥

对于HMAC算法，可以证明成功攻击HMAC的概率等效于针对嵌入哈希函数的攻击

如图所示为HMAC更有效的实现方案，其中 $f$ 是安全Hash结构中的压缩函数

我们可以预先计算 $f (I V, K^{+} \oplus o p a d)$ 和 $f (I V, K^{+} \oplus i p a d)$ ，在消息较短时这种方式很有意义

基于分组密码的MAC

数据认证算法DAA

DAA采用CBC模式的DES，如图所示，其中 $D_{i}$ 为64位明文分组，其输出称为数据认证吗DAC

这个方法有一个明显的缺陷，若 $T = M A C (K, X)$ 是消息分组 $X$ 的认证码，则攻击者直接知道消息 $X | (X \oplus T)$ 的认证码，因为这还是 $T$

基于密码的消息认证码CMAC

为了克服DAA的缺陷，CMAC使用三个密钥
即一个长度为k的加密密钥K，两个长度为分组长度b的密钥 $K_{1} 、 K_{2}$

若最后一个分组长度为b，则该明文分组与密钥 $K_{1}$ 及上一个分组加密结果异或
若最后一个分组长度不足b，则先填充1个1和若干个0，再与密钥 $K_{2}$ 及上一个分组加密结果异或

密钥 $K_{1}, K_{2}$ 按如下方式导出

L = E (K, 0^{b}) K_{1} = L \times x K_{2} = L \times x^{2}

其中乘法在域 $G F (2^{b})$ 上进行， $x$ 和 $x^{2}$ 就是 $G F (2^{b})$ 的两个多项式