基于双重分组和密钥计数的并行认证模式

摘要

由于CBC－MAC模式不可并行处理，提出了一种基于双重分组的并行认证模式(PKCB)。PKCB模式同并行认证模式PMAC相比，安全性和速率都有显著提高，PKCB认证模式与CTR（计数器）加密模式结合可构成分组密码算法的一种全工作模式。在此基础上提出了一种基于密钥计数的并行认证模式（KCTR－MAC）。KCTR－MAC模式安全性比PMAC模式高得多，而速率未降低，KCTR－MAC认证模式和CTR加密模式结合也可构成分组密码算法的一种全工作模式（2CTR），2CTR模式的综合性能不亚于标准模式CCM（CTR with CBC－MAC），是一种安全快速的实用模式。

正文

《1 引言》

1 引言

对称密钥算法分为序列密码算法和分组密码算法。分组密码算法的主要优势是可并行处理。由于分组密码算法本身只定义了将一个分组明文加密成密文的变换, 而实际应用中要加密和认证的数据长度远远大于一个分组, 这就需要为分组密码算法选择工作模式, 避免采用固定格式带来的安全隐患^[1]。笔者主要讨论认证模式。

在128 MB内存环境下, AES (Rijndael) 算法^[2] 的速率约为50~70 Mb/s;而MD5算法^[3] 的速率将近120 Mb/s, SHA1^[4], SHA256^[5] 的速率可达80 Mb/s。也就是说, 由AES构成的CBC-MAC算法^[6] 速率低于常用散列函数。CBC-MAC有很多变体, 实质上只是增加了一些进程, 例如XCBC-MAC^[7]和RMAC^[8], 其综合性能和CBC-MAC差不多。

R. Housley等提出的CCM (CTR with CBC-MAC) 模式^[9] 是分组密码算法的一个标准工作模式。CCM分别采用CTR和CBC-MAC作为加密和认证模式;IEEE802.15.3 (WPAN) 已经采用CCM模式, IPSec考虑采用CTR模式, HP支持CBC-MAC模式^[1]。

CTR (计数器) 模式^[10] 是个性能很好的模式。CCM模式的主要缺点是采用CBC-MAC模式作为认证模式, 不可并行处理, 这使得CTR模式的速率优势化为乌有。笔者主要从这方面进行改进。

现有的并行认证模式主要是P. Rogaway提出的PMAC (并行MAC) 模式^[11]。

《2 CCM模式简介》

2 CCM模式简介

CTR模式包含CTR模式和CBC-MAC模式。

《2.1CCM的加密模式——CTR (计数器) 模式》

2.1CCM的加密模式——CTR (计数器) 模式

定义C = E_K (P) 表示用密钥K把明文P加密成密文C, P = D_K (C) 表示用密钥K把密文C解密成明文P;假设单个分组长度为T位, 明文分组为P₁, …, P_n;密文分组为C₁, …, C_n;最后一组明文长度为τ位, 信息认证码 (MAC) 长度为m位。

CTR模式是由Diffie和Hellman于1979年提出的, 加州大学的P. Rogaway等强烈推荐此模式为标准^[12], 现已发展成标准加密模式之一^[1], 其算法过程为^[1,10,12]:

$\begin{array}{l} f o r i = 1 t o n d o {Ι V_{i} = Ι V + i ； \\ S_{i} = E_{Κ} (Ι V_{i}) ；} (可预处理) \end{array}$ $\begin{array}{l} f o r i = 1 t o n d o {Ι V_{i} = Ι V + i ； \\ S_{i} = E_{Κ} (Ι V_{i}) ；} (可预处理) \end{array}$

(初始向量IV一般为计数器, 或为不重复的伪随机数, IV_i可扩展至所需长度)

for i =1 to n-1 do C_i = P_i⊕S_i ;

C_n = P_n⊕MSB_τ (S_n) ; (加密)

for i =1 to n-1 do P_i = C_i⊕S_i ;

P_n = C_n⊕MSB_τ (S_n) ; (解密)

其中, MSB_τ (S_n) 表示截取S_n的前τ位。由上述算法可知, CTR模式是通过将明 (密) 文同密码流相异或进行加 (解) 密的。因此, CTR模式没有完整性^[12], 只能作为加密模式, 不能同时作为认证模式。

《2.2CCM的认证模式——CBC-MAC模式》

2.2CCM的认证模式——CBC-MAC模式

CBC (密码分组链接) 模式算法为^[13,14,15]:

$f o r i = 1 t o n d o Y_{i} = E_{Κ} (Ρ_{i} \oplus Y_{i - 1}) ；$ $f o r i = 1 t o n d o Y_{i} = E_{Κ} (Ρ_{i} \oplus Y_{i - 1}) ；$

(Y₀一般为计数器, 或为不重复的伪随机数)

$Y_{n} = E_{Κ_{1}} (Y_{n}) ； (可选进程)$ $Y_{n} = E_{Κ_{1}} (Y_{n}) ； (可选进程)$

MAC = MSB_m (Y_n) ;

当最后一组明文长度τ小于分组长度T时, 可采用补位或密文挪用等措施。当m=T时, 一般要采用可选进程, 以减轻穷举攻击的威胁。CBC模式既可作为加密模式, 又可作为认证模式, 还可同时实现加密和认证。当CBC模式同时作为加密和认证模式时, 需要采用可选进程。CBC模式作为认证模式时称为CBC-MAC模式^[13,14,15]。

《3 基于双重分组的并行认证模式及其与PMAC模式的性能比较》

3 基于双重分组的并行认证模式及其与PMAC模式的性能比较

《3.1基于双重分组的并行认证模式 (PKCB) 》

3.1基于双重分组的并行认证模式 (PKCB)

双重分组思想最初是用来构造散列长度为分组长度2倍的单向散列函数, 然而这些方案已被证明是不安全的^[14,15]。不过, 双重分组思想用来构造快速认证模式还是可取的。

以AES为例。众所周知, FIPS 197^[16] 定义的AES算法的分组长度为16 B, 密钥长度可以是16 B, 24 B或32 B, 而密钥长度为32 B的算法速率只比密钥长度为16 B的略慢一些。当然, Rijndael算法^[17] 本身定义的分组长度也可以是16 B, 24 B或32 B^[1]。利用这一特点, 可以得到一个串行速率约为CBC-MAC的2~3倍的并行模式。首先把明文按48 B (40 B或32 B) 分成n组:M₁, …, M_n。如果最后一组明文长度小于48 B (40 B或32 B) , 可采用补位或密文挪用等措施。每组又分为2组:P_i1, P_i2。不妨令P_i1为16 B, P_i2为32 B (24 B或16 B) 。则并行算法为:

$f o r i = 1 t o n d o {Ι V_{i} = i ∥ Ι V ；$ $f o r i = 1 t o n d o {Ι V_{i} = i ∥ Ι V ；$

(初始向量IV一般为计数器, 或为不重复的伪随机数, ‖ 表示串联)

$Κ_{i} = Ρ_{i 2} \oplus Ι V_{i} ；$ $Κ_{i} = Ρ_{i 2} \oplus Ι V_{i} ；$

(明文当密钥, 不能作为加密模式, IV_i可扩展至所需长度)

$\begin{array}{l} Y_{i} = E_{Κ_{i}} (Ρ_{i 1}) ；} \\ Y_{n} = E_{Κ_{A}} (Y_{n}) ； (可选进程, Κ_{A} 可与 Κ 相同) \\ Σ = \oplus_{i = 1}^{n} Y_{i}; Μ A C = Μ S B_{m} [E_{Κ} (Σ)] ； \end{array}$ $\begin{array}{l} Y_{i} = E_{Κ_{i}} (Ρ_{i 1}) ；} \\ Y_{n} = E_{Κ_{A}} (Y_{n}) ； (可选进程, Κ_{A} 可与 Κ 相同) \\ Σ = \oplus_{i = 1}^{n} Y_{i}; Μ A C = Μ S B_{m} [E_{Κ} (Σ)] ； \end{array}$

该并行模式的思路是部分明文当密钥, 可称为PKCB (并行密钥密码分组) 模式。在128 MB内存环境下, AES-PKCB算法的串行速率可达140~170 Mb/s, 比常用散列函数快。PKCB (并行双重分组) 模式在思想上与P. Rogaway提出的PMAC (并行MAC) 模式^[11] 有类似之处, 不过PKCB模式对明文进行双重分组, 计算量约为PMAC模式的1/2~1/3。

《3.2PMAC模式》

3.2PMAC模式

PMAC是P. Rogaway提出的并行认证模式^[11]。该模式用到了GF (2ⁿ) 域, 以n=128为例。不可约多项式为

$p_{128} (x) = x^{128} + x^{7} + x^{2} + x + 1$ $p_{128} (x) = x^{128} + x^{7} + x^{2} + x + 1$

定义a (x) +b (x) = a (x) ⊕b (x) ,

$a (x) b (x) = [a (x) ⊙ b (x)] m o d p_{128} (x) ‚$ $a (x) b (x) = [a (x) ⊙ b (x)] m o d p_{128} (x) ‚$

⊙表示模乘, ntz (i) 表示二进制数i从右边数连0的个数, f (L, i) 表示 $L ⊙ x^{i} ‚ | Ρ |$ $L ⊙ x^{i} ‚ | Ρ |$ 表示取输入信息P的位数, γ₀, …, γ_2ⁿ-1 是相邻码元相差1位的格雷编码, 且γ₀ = 0, 则γ_i⊙L = (γ_i-1⊙L) ⊕L[ntz (i) ]。PMAC模式的算法过程为^[11,12]:

$\begin{array}{l} L = E_{Κ} (0) ； \\ f o r i = 1 t o n - 1 d o {Ζ_{i} = γ_{i} ⊙ L ； \\ Y_{i} = E_{Κ} (Ρ_{i} \oplus Ζ_{i}) ；} \\ i f | Ρ_{n} | = Τ t h e n Y_{n} = Ρ_{n} \oplus L ⊙ x^{- 1} ； \\ e l s e Y_{n} = Ρ_{n} 10^{Τ - | Ρ_{n} | - 1} ； (0^{*} 表示用 0 补位) \\ Σ = \oplus_{i = 1}^{n} Y_{i} ； Μ A C = Μ S B_{m} [E_{Κ} (Σ)] 。 \end{array}$ $\begin{array}{l} L = E_{Κ} (0) ； \\ f o r i = 1 t o n - 1 d o {Ζ_{i} = γ_{i} ⊙ L ； \\ Y_{i} = E_{Κ} (Ρ_{i} \oplus Ζ_{i}) ；} \\ i f | Ρ_{n} | = Τ t h e n Y_{n} = Ρ_{n} \oplus L ⊙ x^{- 1} ； \\ e l s e Y_{n} = Ρ_{n} 10^{Τ - | Ρ_{n} | - 1} ； (0^{*} 表示用 0 补位) \\ Σ = \oplus_{i = 1}^{n} Y_{i} ； Μ A C = Μ S B_{m} [E_{Κ} (Σ)] 。 \end{array}$

《3.3PMAC模式的安全性》

3.3PMAC模式的安全性

PMAC模式是一种高效的并行认证模式, 安全性较高。

分析认证模式的安全性必须结合加密模式。假设分组密码算法分别采用CTR和PMAC作为加密和认证模式。

令δ_ij = Z_i⊕Z_j , Δ_ij = S_i⊕S_j⊕δ_ij ;

$\begin{array}{l} C_{i}^{*} = C_{j} \oplus Δ_{i j} ‚ \\ C_{j}^{*} = C_{i} \oplus Δ_{i j} (密文差分互换) 。 \end{array}$ $\begin{array}{l} C_{i}^{*} = C_{j} \oplus Δ_{i j} ‚ \\ C_{j}^{*} = C_{i} \oplus Δ_{i j} (密文差分互换) 。 \end{array}$

解密得P^*_i = C^*_i⊕S_i = P_j⊕δ_ij,

$Ρ_{j}^{*} = C_{j}^{*} \oplus S_{j} = Ρ_{i} \oplus δ_{i j} ‚$ $Ρ_{j}^{*} = C_{j}^{*} \oplus S_{j} = Ρ_{i} \oplus δ_{i j} ‚$

则Y^*_i = E_K (P^*_i⊕Z_i) = Y_j ,

$Y_{j}^{*} = E_{Κ} (Ρ_{j}^{*} \oplus Ζ_{j}) = Y_{i} 。$ $Y_{j}^{*} = E_{Κ} (Ρ_{j}^{*} \oplus Ζ_{j}) = Y_{i} 。$

即密文差分互换后MAC值不变。

虽然Δ_ij是个伪随机数, 但任意2组密文 (最后一组或最后2组除外) 满足线性差分互换关系, 是其不足之处。因此, PMAC模式的安全性明显低于CBC-MAC。假设PMAC模式中密文篡改成功的概率为P_PMAC。

《3.4PKCB认证模式的安全性》

3.4PKCB认证模式的安全性

假设分组密码算法分别采用CTR和PKCB作为加密和认证模式, 不管可选进程, 以AES-128为例, P_2i-1 = P_i1, P_2i = P_i2 。

令 Δ_{2i-1, 2j-1} = S_2i-1⊕S_2j-1,

$\begin{array}{l} Δ_{2 i, 2 j} = S_{2 i} \oplus S_{2 j} \oplus i \oplus j ‚ δ_{i j} = i \oplus j ‚ \\ C_{2 i - 1}^{*} = C_{2 j - 1} \oplus Δ_{2 i - 1, 2 j - 1} ‚ \\ C_{2 j - 1}^{*} = C_{2 i - 1} \oplus Δ_{2 i - 1, 2 j - 1} ‚ \\ C_{2 i}^{*} = C_{2 j} \oplus Δ_{2 i, 2 j} ‚ \\ C_{2 j}^{*} = C_{2 i} \oplus Δ_{2 i, 2 j} (密文差分互换) ‚ \end{array}$ $\begin{array}{l} Δ_{2 i, 2 j} = S_{2 i} \oplus S_{2 j} \oplus i \oplus j ‚ δ_{i j} = i \oplus j ‚ \\ C_{2 i - 1}^{*} = C_{2 j - 1} \oplus Δ_{2 i - 1, 2 j - 1} ‚ \\ C_{2 j - 1}^{*} = C_{2 i - 1} \oplus Δ_{2 i - 1, 2 j - 1} ‚ \\ C_{2 i}^{*} = C_{2 j} \oplus Δ_{2 i, 2 j} ‚ \\ C_{2 j}^{*} = C_{2 i} \oplus Δ_{2 i, 2 j} (密文差分互换) ‚ \end{array}$

解密得

$\begin{array}{l} Ρ_{2 i - 1}^{*} = C_{2 i - 1}^{*} \oplus S_{2 i - 1}^{*} = Ρ_{2 j - 1} ‚ \\ Ρ_{2 j - 1}^{*} = C_{2 j - 1}^{*} \oplus S_{2 j - 1}^{*} = Ρ_{2 i - 1} ‚ \\ Ρ_{2 i}^{*} = C_{2 i}^{*} \oplus S_{2 i}^{*} = Ρ_{2 j} \oplus δ_{i j} ‚ \\ Ρ_{2 j}^{*} = C_{2 j}^{*} \oplus S_{2 j}^{*} = Ρ_{2 i} \oplus δ_{i j} ‚ \\ 则 Κ_{i}^{*} = Ρ_{2 i}^{*} \oplus Ι V_{i} = Κ_{j} ‚ \\ Κ_{j}^{*} = Ρ_{2 j}^{*} \oplus Ι V_{j} = Κ_{i} ‚ \\ Y_{i}^{*} = E_{Κ_{i}^{*}} (Ρ_{2 i - 1}^{*}) = Y_{j}, \\ Y_{j}^{*} = E_{Κ_{j}^{*}} (Ρ_{2 j - 1}^{*}) = Y_{i} 。 \end{array}$ $\begin{array}{l} Ρ_{2 i - 1}^{*} = C_{2 i - 1}^{*} \oplus S_{2 i - 1}^{*} = Ρ_{2 j - 1} ‚ \\ Ρ_{2 j - 1}^{*} = C_{2 j - 1}^{*} \oplus S_{2 j - 1}^{*} = Ρ_{2 i - 1} ‚ \\ Ρ_{2 i}^{*} = C_{2 i}^{*} \oplus S_{2 i}^{*} = Ρ_{2 j} \oplus δ_{i j} ‚ \\ Ρ_{2 j}^{*} = C_{2 j}^{*} \oplus S_{2 j}^{*} = Ρ_{2 i} \oplus δ_{i j} ‚ \\ 则 Κ_{i}^{*} = Ρ_{2 i}^{*} \oplus Ι V_{i} = Κ_{j} ‚ \\ Κ_{j}^{*} = Ρ_{2 j}^{*} \oplus Ι V_{j} = Κ_{i} ‚ \\ Y_{i}^{*} = E_{Κ_{i}^{*}} (Ρ_{2 i - 1}^{*}) = Y_{j}, \\ Y_{j}^{*} = E_{Κ_{j}^{*}} (Ρ_{2 j - 1}^{*}) = Y_{i} 。 \end{array}$

也就是说, 要同时猜测2个伪随机数Δ_{2i, 2j}和Δ_{2i-1, 2j-1}, 才能确保密文篡改成功。因此, PKCB认证模式采用AES-128算法时密文篡改成功的概率约为P_PKCB = P $_{Ρ Μ A C}^{2}$ $_{Ρ Μ A C}^{2}$ 。类似地, 可求得采用AES-192算法时密文篡改成功的概率约为P_PKCB = P $_{Ρ Μ A C}^{2.5}$ $_{Ρ Μ A C}^{2.5}$ ;采用AES-256算法时密文篡改成功的概率约为P_PKCB = P $_{Ρ Μ A C}^{3}$ $_{Ρ Μ A C}^{3}$ 。由此可以说明, PKCB与PMAC算法相比, 安全性和速率都有显著提高。

《4 计数器认证模式及其与PMAC, PKCB模式的性能比较》

4 计数器认证模式及其与PMAC, PKCB模式的性能比较

《4.1计数器认证模式 (KCTR-MAC) 》

4.1计数器认证模式 (KCTR-MAC)

由于CTR模式是纯加密模式, 不能同时作为认证模式, 可将它改造成认证模式 (如果最后一组明文长度小于分组长度, 可采用补位或密文挪用等措施) :

$f o r i = 1 t o n d o {Ι V_{i} = i | | Ι V ；$ $f o r i = 1 t o n d o {Ι V_{i} = i | | Ι V ；$

(IV为计数器, 或为不重复的伪随机数)

$Κ_{i} = Κ \oplus Ι V_{i} ；$ $Κ_{i} = Κ \oplus Ι V_{i} ；$

(可预处理, IV_i可扩展至所需长度)

$\begin{array}{l} Y_{i} = E_{Κ_{i}} (Ρ_{i});} \\ Y_{n} = E_{Κ_{A}} (Y_{n}) ； (可选进程) \\ σ = \oplus_{i = 1}^{n} Y_{i} \end{array}$ $\begin{array}{l} Y_{i} = E_{Κ_{i}} (Ρ_{i});} \\ Y_{n} = E_{Κ_{A}} (Y_{n}) ； (可选进程) \\ σ = \oplus_{i = 1}^{n} Y_{i} \end{array}$

(密文可互换, 不能同时作为加密模式)

$\begin{array}{l} Σ = E_{Κ} (σ) ； \\ Μ A C = Μ S B_{m} (Σ) ； \end{array}$ $\begin{array}{l} Σ = E_{Κ} (σ) ； \\ Μ A C = Μ S B_{m} (Σ) ； \end{array}$

该模式只能作为认证模式, 采用密钥计数思想, 可称为密钥计数认证 (KCTR-MAC) 模式。CBC-MAC算法采用相同密钥加密, 而KCTR-MAC算法采用变密钥加密, 因此, KCTR-MAC模式的安全性更高些。KCTR-MAC模式描述比PMAC模式简单, 但KCTR-MAC模式需进行多次密钥编排 (可预处理) , 计算量和PMAC模式差不多。

《4.2KCTR-MAC模式的安全性》

4.2KCTR-MAC模式的安全性

由于CTR加密模式是通过将明 (密) 文同密码流相异或进行加 (解) 密的, 而PMAC和PKCB认证模式又有一定的差分线性, 这样就可通过密文差分互换实现明文差分互换, 而MAC值不变。

假设分组密码算法分别采用CTR和KCTR-MAC作为加密和认证模式。KCTR-MAC模式对不同顺序的明文采用不同的密钥进行处理, 即采用密钥计数方式对数据进行定位, 可以抵抗密文的增删和互换攻击。虽然密钥的计数是线性的, 但经过加密算法的非线性处理, 数据的偏移不存在差分线性关系, 可以抵抗密文差分互换攻击。虽然PKCB认证模式也采用不同的密钥对不同顺序的明文进行处理, 但引入部分明文当密钥, 可通过修改数据控制密钥。因此, KCTR-MAC模式的安全性比PMAC和PKCB模式高。不过, KCTR-MAC模式不能与相同的加密模式共存 (PMAC模式也不能与相同的加密模式共存) 。

PMAC模式中的伪随机序列Z_i实质上是计数值的伪随机变换;PMAC模式实质上也是一种计数器模式。因此, KCTR-MAC模式是PMAC模式的改进模式。当然, 也可把PMAC模式中的伪随机序列Z_i引入到KCTR-MAC模式中, 以增强复杂度;这样需增加存储空间以便预处理。

KCTR-MAC算法是陷门单向函数, 不能作为无陷门单向散列函数, 可采用它来构造并行的无陷门单向散列函数。另外, KCTR-MAC模式可扩展为同时实现加密和认证的全工作模式。

《5 CCM并行模式》

5 CCM并行模式

CCM模式^{[18,19,20,21]} 把CTR和CBC-MAC有机结合, 前者用于加密, 而后者用于认证。该模式在不少地方已被标准化^[1]。CTR模式是个性能很好的模式, 但CBC-MAC模式不可并行处理, 这使得CTR模式的速率优势荡然无存。

《5.1CCM并行模式1 (CTR with PKCB-MAC) 》

5.1CCM并行模式1 (CTR with PKCB-MAC)

将PKCB认证模式与CTR加密模式结合构成分组密码算法的一种全工作模式, 称为CPK模式。CPK模式加解密和认证都可并行处理, 但安全性明显低于CCM模式。

《5.2CCM并行模式2 (2CTR) 》

5.2CCM并行模式2 (2CTR)

KCTR-MAC只能作为认证模式, 而CTR只能作为加密模式, 将KCTR-MAC与CTR结合构成分组密码算法的一种全工作模式, 称为2CTR (双计数器) 模式。2CTR (CTR with KCTR-MAC) 模式与CCM模式相比, 安全性未降低, 至少未明显降低, 而加解密和认证都可并行处理, 因此, 2CTR模式的综合性能不亚于标准模式CCM。

《6 结语》

6 结语

笔者给出了一种基于双重分组的并行认证模式 (PKCB) ;PKCB模式与PMAC模式相比, 安全性和速率都有显著提高;PKCB认证模式与CTR加密模式结合可构成分组密码算法的一种全工作模式 (CPK) ;CPM模式加解密和认证都可并行处理, 但安全性明显低于CCM模式。在此基础上给出了一种基于密钥计数的并行认证模式 (KCTR-MAC) ;KCTR-MAC模式安全性比PMAC模式高得多, 而速率未降低;KCTR-MAC认证模式和CTR加密模式结合也可构成分组密码算法的一种全工作模式 (2CTR) ;2CTR模式解决了CCM认证 (CBC-MAC) 不可并行处理的问题。2种新工作模式描述简单, 便于性能评估, 其中2CTR模式的综合性能不亚于标准模式CCM。

展示更多