无线网络机制中分组密码标准安全性分析[权威资料]

无线网络机制中分组密码标准安全性分析 本文档格式为 WORD,感谢你的阅读。 摘要： 分组密码算法凭借其在各种软件和硬件平台上的高效率特点，广泛地应用在无线通信系统的安全认证及保密机制中。本文对几种著名分组密码标准（美国高级加密标准 AES 算法、韩国分组加密标准 SEED 算法、欧洲分组加密标准 Camellia 算法和中国商用密码标准 SMS4 算法）的安全性进行了分析，通过研究分组密码算法中的非线性结构 S 盒的密码学性质，对比分组密码算法抵抗插 入攻击、差分密码分析攻击和线性密码分析攻击的能力，揭示各种算法的安全性。 Abstract： With the characteristics of high efficiency in a variety of software and hardware platforms， block ciphers are widely used in wireless communication systems security authentication and privacy. A detailed analysis of the cryptographic properties of several well-known block ciphers， such as AES， SEED， Camellia and SMS4， is made in this paper. S-box， which brings nonlinearity to block cipher， is well investigated and the attack capability resisting to insertion attacks， differential cryptanalysis and linear cryptanalysis is also provided. The security of AES， SEED， Camellia and SMS4 is revealed as compared with each other. 关键词： 分组密码； S 盒；布尔函数；差分密码分析攻击；线性密码分析攻击 Key words： block cipher； S-boxes； boolean function； differential cryptanalysis attack； linear cryptanalysis attack TP393 A 1006-4311（ 2013） 09-0196-04 0 引言 由于无线网络能够使用户真正实现随时、随地、随意地接入网络，无线网络的使用群体在不断地扩大，用户对无线网络的要求也日益提高，例如，终端之间的安全认证、信息的安全传输等。无线网络虽然具有易于实施、组网灵活、快捷高效的特点，但其所采用的无线技术缺乏固定的物理保护，容 易遭受多种网络安全攻击，且难以检测。因此，无线网络迅速发展的同时，对网络的安全性也提出了更高的要求。分组密码算法以其在各种软件和硬件平台上的高效率这一显著特点成为无线网络安全认证及保密机制的主要产品。 随着美国数据加密标准 DES（ Data Encryption Standard）被攻破， 1997 年初，美国已经开始计划建立高级加密标准 AES（ Advanced Encryption Standard），并在世界范围内公开征集 AES 算法，经过历时三年的遴选和评估，比利时密码学家 Joan Daemen 和 Vincent Rijmen 提交的Rijndael 算法 1成为美国的高级加密标准。继 AES 之后，韩国信息安全协会于 1998 年确定了 128 比特分组加密算法 SEED算法 2，并服务于很多安全系统。 2000 年 1 月 1 日，欧洲启动了欧洲签名、完整性和加密新方案计划 NESSIE3，三年后确定了 Camellia 算法 4为其分组密码标准算法之一。 2006年 1 月 6 日，中国国家密码管理局发布第 7 号公告，将用于我国无线局域网产品的加密算法确定为 SMS4 算法 5，这是国内官方公布的第一个商用密码算法。随着各种分组加密算法 在实际生活中的不断应用 6-9，算法的安全性值得我们深入探讨与研究。 对于大多数分组密码算法而言，安全性取决于一个重要组成部分，即， S 盒。这个非线性结构任何不好的性质都会影响到整个密码算法的安全性。本文深入分析美国高级加密标准 AES 算法、韩国分组加密标准 SEED 算法、欧洲分组加密标准 Camellia 算法和中国商用密码新标准 SMS4 算法 S 盒的密码学性质，研究其平衡性、非线性、代数表达式、 Walsh 谱等性质，同时分析比较了各种加密标准在抵抗插入攻击、差分密码分析攻击和线性密码分析攻击的能力。通过比较 ，在理论上揭示了各种分组密码算法所具有的安全特性。 本文结构如下：第 1 节对各种分组密码算法进行了简单的介绍；第 2 节给出了各种分组密码算法 S 盒布尔函数密码学性质的比较；第 3 节分析对比了各种分组密码算法抵抗各种攻击的能力；最后第 4 节对全文进行总结。 1 分组密码算法简介 1.1 AES 算法 美国高级加密标准 AES 算法分组长度和密钥长度均可取 128 比特、 192 比特和 256 比特三种不同长度，加密算法与密钥扩展算法都采用非线性的迭代结构，不同的分组长度与密钥长度的迭代次数是不同的，如表 1 所示。每一轮的迭代结构包含四个基本操作：非线性的字节替换，行移位，列混合和轮密钥加。 1.2 SEED 算法 韩国分组加密标准 SEED 算法的分组明文长度为 128 比特，密钥长度为 128 比特，生成 128 比特密文。加密算法与密钥扩展算法都采用 16轮非线性迭代结构。解密过程与加密过程的结构相似，只是轮密钥的使用顺序相反。 1.3 Camellia 算法 欧洲分组加密标准 Camellia 算法的分组明文长度为 128 比特，密钥长度可取 128 比特、 192 比特和 256 比特三种不同长度，生成 128 比特密文。 加密算法与密钥扩展算法都采用 18轮（ 128 比特长度的密钥）或者 24轮（ 192 或 256 比特长度的密码）的 Feistel 结构。解密过程与加密过程的结构相似，只是轮密钥的使用顺序相反。 1.4 SMS4 算法 中国商用密码新标准 SMS4 算法的分组长度为128 比特，密钥长度为 128 比特，生成 128 比特密文。加密算法与密钥扩展算法都采用 32轮非线性迭代结构。解密过程与加密过程的结构相似，只是轮密钥的使用顺序相反。 2 分组密码算法安全性分析 S 盒是大多数分组密码算法中唯一的非线性结构，其密码 特性直接决定了密码算法的好坏。本节对美国高级加密标准 AES 算法、韩国分组加密标准 SEED 算法、欧洲分组加密标准 Camellia 算法和中国商用密码标准 SMS4 算法的 S 盒密码学性质进行了深入分析，研究其平衡性、非线性、代数表达式、 Walsh 谱等性质，通过比较，揭示各种分组密码算法的优缺点。 2.1 S 盒布尔函数表达式 S 盒的布尔函数表达式给出了 S 盒的输入比特与输出比特之间的代数逻辑关系，这种表达式的次数和所含项数表明了 S 盒的代数复杂度。通常， S 盒的设计准则 10要求布尔函数表达式的次数尽可能高，项数尽可能多。 以我国无线局域网产品 SMS4 算法为例，我们求得 SMS4算法 S 盒第一个布尔函数为f0=x2+x1x2+x1x3+x2x3x4x5x6x7x8 ，全部的非零下表值列于表 2 中，其它布尔函数可类似计算。 由表 2 可知 f0中的项数为 134，最高次数为最大可能值 7。其它输出比特的布尔函数 f1， ， f7的项数分别为130， 128， 123， 126， 124， 139， 124，代数次数均为 7。不难发现 SMS4 算法 S 盒每个布尔函数多项式表达式的次数均为最大可能值 7，项数均不少于 123 项，这在某种意义 上保证了SMS4 算法 S 盒的代数复杂度和安全强度。 通过计算，我们得到四种标准中的 8 个 S 盒（其中，AES 算法含有 1 个、 SEED 算法含有 2 个、 Camellia 算法含有4 个、 SMS4 算法含有 1 个）的布尔函数表达式的次数和项数，如表 3 所示。 通过比较，四种算法的 S 盒布尔函数表达式的次数都达到了最大上限 7。对于它们的 S 盒布尔函数表达式的最小项数而言， Camellia 算法的为 126， SMS4 算法的为 123，比SEED 算法的 111 和 AES 算法的 110 多，并且 SEED 算法的略大于 AES 算法的。从这个方面 而言， SEED 算法、 Camellia 算法和 SMS4 算法 S 盒布尔函数表达式复杂度略优于 AES 算法。 2.2 S 盒布尔函数代数性质 一个好的 S 盒应该具有好的代数性质，良好的性质能保证算法能够抵抗各种密码分析的攻击。对于大多数算法而言， S 盒是唯一的非线性结构，并在整个算法中多次使用，因此 S 盒任何不好的性质都将影响到整个算法的安全性。本节讨论 SMS4 算法 S 盒的平衡性和非线性度等性质。 定义 110 对 n 元布尔函数 f： GF（ 2） nGF （ 2），若其真值表中 “1” 的个数等于 “0” 的个数，即均为 2n-1，则称 f 满足平衡性。 定义 210 设 f（ x）是一个 n 元布尔函数，记 Lnx为所有 n 元线性函数（包括仿射函数）之集。 f（ x）的非线性度定义 f（ x）与所有线性函数之最短距离 N=d （ f，l）， 若 f（ x）的非线性度满足 N=2 -2 ，则称 f（ x）为 Bent 函数，也称完全非线性函数。 布尔函数 f（ x）的非线性度 Nf是用来衡量抵抗 “ 线性攻击 ” 能力的一个非线性准则， Nf 越大，则在某种意义上布尔函数 f（ x）抵抗 “ 线性攻击 ” 的能力越强；反之， Nf越小，则布尔函数 f（ x）抵抗 “ 线性攻击 ” 的能力越弱。 通过计算可知，四种标准中的 8 个 S 盒的所有布尔函数均是平衡函数，非线性度均为 112，与完全非线性函数有6.67%的距离。 2.3 S 盒布尔函数 Walsh 循环谱 Walsh 循环谱衡量的是布尔函数表达式与线性函数 w x 的相符合程度。布尔函数的 Walsh 循环谱的数值越大，说明布尔函数的 Walsh 循环谱与线性函数越接近，对应的 S 盒就越容易被攻击，算法性能就越坏。 以我国无线局域网产品 SMS4 算法为例，我们计算得到的 SMS4 算法 S 盒布尔函数 f0的 256 倍的 Walsh 循环谱如表 4所示，相应的谱图如图 1 所示。显然，其各点谱值的绝对值大多在 4 到 30的范围之内，最大不超过 32，处于较小的状态，再次说明其与线性函数相似程度之小。 通过计算可知，我们得到四种标准中的 8 个 S 盒的布尔函数 Walsh 循环谱的性质，如表 5 所示。 通过比较，四种标准中的 S 盒布尔函数 Walsh 循环谱绝对值的 256 倍最大值均为 32，说明其与线性函数相似程度之小。由于零谱值过大将导致非线性度的下降 11，反之非线性度上升，通过计算可知各种算法的零谱值个数均较小，仅为 17，再次说明其与线性函数 相似程度之小。 3 分组密码算法抵抗攻击能力的分析 研究 AES算法、 SEED 算法、 Camellia 算法和 SMS4 算法抵抗插入攻击、差分密码分析攻击和线性密码分析攻击的能力。 3.1 抵抗插入攻击 插入攻击 11， 12的攻击者利用密码的一些输入 /输出对来构造多项式，用于逼近密码算法的加解密过程，此攻击方法对变换代数次数和复杂度低的密码尤为奏效。因此，在密码设计中，为了防止插入攻击，通常要求变换的代数式具有足够高的次数和项数。 以我国无线局域网产品 SMS4 算法为例，当构 造的有限域为以不可约多项式 m（ x） =x8+x4+x3+x1+1 为生成多项式，以元素 =x+1 为生成元时（与 AES 的 S 盒保持一致），求得SMS4 算法 S 盒的代数表达式为 f（ x） =D6+53x+1Ex2+D9x253+02x254 ， 其中，各次项系数列于表 6。 因此，我们可以得到四种标准中 8 个 S 盒的代数表达式，如表 7 所示。 由表 7 可知，虽然 AES 算法、 SEED 算法、 Camellia 算法和 SMS4 算法 S 盒的代数表达式的次数均为 254，但 SMS4 算法、 SEED 算法和 Camellia 算法的项数多至 255，而 AES 算法的仅为 9。可见， SEED 算法、 Camellia 算法和 SMS4 算法 S 盒的代数表达式要比 AES 的更为复杂，在一定程度上更好地保证算法的安全性。 3.2 抵抗差分密码分析 差分密码分析 13是通过分析特定明文差对相应密文差的影响来获得可能性最大的密钥的一种攻击方式。它是目前对分组密码最为有效的攻击方法之一。具有较小的差分均匀度是 S 盒抗击差分攻击的必要条件。 通过计算 AES 算法、 SEED 算法、 Camellia 算法、 SMS4算法中 S 盒的 256256 的差分 矩阵，我们发现四种算法中的8 个 S 盒的差分均匀度均为 4，且最大值在每一行每一列（首行首列除外）中出现且仅出现一次。因此，我们认为 AES 算法、 SEED 算法、 Camellia 算法和 SMS4 算法抵抗差分密码分析的能力是相当的。 3.3 抵抗线性密码分析 线性密码分析 14是通过寻找并利用明文 P，密文 C 和密钥 K 的若干位之间的一个线性表达式（ P ）？茌（ C ） =（ K ）进行的一种攻击方式。该表达式成立的概率与二分之一的偏差大小是线性密码分析成功的一个重要的衡量指标。各个算法 S 盒的输入输出比特之间的关系 可以衡量算法抵抗线性密码分析的能力。 通过计算 AES 算法、 SEED 算法、 Camellia 算法、 SMS4算法中 S 盒的 256256 的线性分布矩阵，我们发现四种算法中的 8 个 S 盒中的矩阵元素最大绝对值都是 16，且最大值在每一行每一列（首行首列除外）中出现且仅出现五次，这意味着 S 盒的线性逼近概率较低（二百五十六分之十六），即线性性较弱，符合分组密码非线性性较强的要求。因此，我们认为 AES 算法、 SEED 算法、 Camellia 算法和 SMS4 算法抵抗线性密码分析的能力是相当的。 4 结束语 本文通过对无线网络中的几种主要分组密码标准 S 盒密码学性质的分析，以及对各种标准在抵抗插入攻击、差分密码分析攻击和线性密码分析攻击能力的对比，理论上揭示了 SEED 算法、 Camellia 算法和 SMS4 算法的密码学安全性在一定程度上优于 AES 算法，而 SEED 算法、 Camellia 算法和SMS4 算法密码学安全性是相当的。 参考文献： 1Daemen J and Rijmen V. AES proposal： Rijndael Version 2EB/OL http： / .east. kuleuven.ac.be / rijmen/rijndael.1999. 2Network Working Group. Request for Comments： 4009. RFC 4269. 2005. 3European IST.NESSIE Project EB/OL. https：/.cosic.esat.kuleuven.be/nessie/.1999. 4Aoki K， Ichikawa T， Kanda M， et al， . Camellia： A 128-bit block cipher suitable for multiple platformsEB/OL. http：/info.isl.ntt.co.jp/camellia. 2000. 5国家密码管理办公室 .无线局域网产品使用的 SMS4密码算法 EB/OL. http： /./Doc/6 /News_1106.htm. 2006. 6Li J， Gan L and Du F F. Research on encryption algorithm conforming to AES in WLAN C. Advanced Materials Research， 2012： 1517-1521. 7刘佳 . 基于密码学的无线局域网认证协议设计与实现 J. 价值工程， 2012， 31（ 277）： 223-228. 8Lu Y， ONeill M P and McCanny J V. Differential power analysis resistance of Camellia and countermeasure strategy on FPGAsC. International Conference on Field-Programmable Technology， 2009： 183-189. 9Kitsos P and Skodras A N. An FPGA implementation and performance evaluation of the seed block cipherC. 17th International Conference on Digital Signal Processing （ DSP）， 2011： 1-5. 10温巧燕，钮心忻，杨义先 .现代密码学中的布尔函数 M.北京：科学出版社， 2000. 11Jakobsen T and Kundsen L R. The Interpolation Attack on Block Ciphe