消息认证

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

消息加密提供认证

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

例如密钥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计算$MAC=C(K,M)$
A将消息M和MAC同时发送给B，B使用密钥K对接收到的消息使用相同方法计算MAC，并与接收到的MAC比较，若相等，则B可以相信消息来自A且未被修改

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

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

使用MAC的理由

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

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

MAC的安全性

MAC函数应具有如下性质

  • 若攻击者已知消息$M$和其认证码$MAC(K,M)$，则构造满足$MAC(K,M’)=MAC(K,M)$的$M’$在计算上不可行
  • $MAC(K,M)$应是均匀分布的，即对任何随机消息$M$和$M’$，$MAC(K,M’)=MAC(K,M)$的概率为$2^{-n}$，其中$n$为MAC的位数
  • 若$M’$是$M$的某个已知变换，即$M’=f(M)$，要求$MAC(K,M’)=MAC(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=MAC(K, M_2)$
第二轮，攻击者使用$(M_2,T_2)$验证，匹配数约为$2^{k-2n}$
依此类推，攻击者需要约$\frac{k}{n}$轮穷举，说明穷举法确定认证密钥比较困难

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

基于Hash的MAC

简单但不安全的构造

直接将消息附加在密钥之后计算Hash值的构造$T=MAC(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=MAC(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算法结构，其具体步骤如下

  1. 在密钥$K$左侧填充0得到b位的$K^+$，令$S_i=K^+\oplus ipad$，其中$ipad$为常数00110110（十六进制36）重复b/8次的结果
  2. 将消息M按b位分组并附加于$S_i$之后，计算Hash值$h=H(S_i|M)$
  3. 令$S_o=K^+\oplus opad$，其中$opad$为常数01011100（十六进制5C）重复b/8次的结果
  4. 将Hash值h附加于$S_i$之后，再次计算Hash值即可获得$MAC=H(S_o|h)$

该过程可表示为$HMAC(K,M)=H[(K^+\oplus opad)|H[(K^+\oplus ipad)|M]]$

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

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

hmac

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

我们可以预先计算$f(IV,K^+\oplus opad)$和$f(IV,K^+\oplus ipad)$，在消息较短时这种方式很有意义

hmac_new

基于分组密码的MAC

数据认证算法DAA

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

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

daa

基于密码的消息认证码CMAC

为了克服DAA的缺陷，CMAC使用三个密钥
即一个长度为k​的加密密钥K，两个长度为分组长度b的密钥$K_1、K_2$

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

密钥$K_1,K_2$按如下方式导出

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

CMAC