一种32比特分组长度的轻量级密码算法.doc

BeeCipher: 一种32比特分组长度的轻量级密码算法 基金项目：国家自然科学基金（61402280)，上海电机学院计算机应用技术学科建设（13XKJ01，A1-1201-14-005)，大学生科创项目. 第一作者简介：罗宜元（1986.9-），男，讲师，博士，主要研究方向为密码学，E-mail: .罗宜元 林智伟 陈炜家 徐禄丰(上海电机学院,电子信息学院 上海 200240)摘 要:本文设计了一个32比特分组长度，64比特密钥长度的分组密码BeeCipher。该算法基于IDEA和Lai-Massey结构，对IDEA算法的32比特版本的轮函数进行了改进，添加了正交置换，使得其具有可证明安全性，并且修改了密钥调度过程，从而使得目前已有对IDEA算法的攻击都对BeeCipher无效。BeeCipher的软件实现也非常简单，其速度要比目前已有的大多数32比特分组长度算法要快很多，硬件实现也很简单，这使得BeeCipher成为32比特分组长度轻量级分组密码中有力的候选算法。关键词:计算机安全; 密码学；分组密码； 轻量级中图分类号:TP309.7 文献标志码： ABeeCipher: A 32-bit Block Length Lightweight Block CipherLuo Yi-yuan and Lin Zhi-wei and Chen Wei-jia and Xu Lu-feng(School of Electronics and Information, Shanghai Dian Ji University, Shanghai 200240, China)Abstract: In this paper we propose a 32 bit block length, 64 bit key length block cipher BeeCipher. The structure of BeeCipher is based on the structure of IDEA and Lai-Massey. We revise the round function of IDEA-32 version and add an orthomorphism to the round function, which can achieve provable security. The key schedule is also updated such that all known attacks on IDEA cannot be applied to BeeCipher. The software implementation of BeeCipher is simple and is faster than most of other 32 bit block ciphers. The hardware implementation of BeeCipher is also simple and fast due to its simple byte operations. BeeCipher can be a candidate for 32 bit block ciphers for lightweight applications. Key Words:Cryptography；Computer Security; Cryptology; Block Cipher；Lightweight1.引言随着信息技术的发展，信息安全性的问题却愈来愈显得突出，保证信息安全的一个重要技术就是密码学。密码学在信息安全技术中扮演着基础的角色，是攻击者最难攻破的模块。而分组密码又是密码学中最常用的算法，是信息安全中的主力，通常称为信息安全中的驿马。目前学术界对分组密码的设计和研究已经相当成熟，每年都有很多新的加密算法推出。由于物联网等相关技术的进步，人们发现传统的加密算法已经在资源受限的环境中无法得到的广泛应用，因此，对资源消耗较少、实现效率较高的轻量级密码算法的设计已经成了学术界关注的热点。对于轻量级密码算法的设计，目前常用的算法的长度都是64比特长度的，例如PRESENT, LED, PRINTCipher,Twine, LBlock等3,6,8,10,12,14。在某些特殊应用下，用户可能会需要32比特分组长度的分组密码，例如如下场景：（1） 一个网站系统的数据库用户ID在数据表中是以32比特整型数字来表示，网站系统希望在用户访问的URL中标明这些ID，但同时又不让其他的用户知道用户ID的数量，一个很简单的方法就是使用一个32比特分组长度的加密算法对这些ID进行加密，将加密后的URL发给用户，使得用户无法查看ID的数量。同时当用户使用相应的URL访问时网站，系统就会进行相应的解密，并调出相应的用户ID。（2） 有些场景中需要将一组按序排列的32比特整数加密成另外一组无序排列的32比特的整数，同时需要一定的安全性。 对于64比特的密钥长度，穷举攻击需要264次加密过程，对于非政府或军事组织来说还是很难破译的。例如，为了攻击64比特的RC5算法， 花了4年10个月的时间，使用了7万台计算机才能恢复其密钥。所以，目前的64比特密钥的算法对于抵抗个人和小型组织的攻击还是能够提供一定的安全性。目前已有的轻量级算法主要采用Feistel 结构及其扩展和SPN结构（代换置换网络）, 如PRESENT采用代换置换网络结构，LBlock主要采用的是Feistel扩展结构等。除了Feistel结构和SPN结构外，还有一类比较成熟的分组密码设计结构Lai-Massey结构13, 以IDEA,FOX算法为代表7,9。其中IDEA是一个饱经考验的密码，在经过20多年的密码分析过程中，最好的结果是最近提出的Biclique攻击方法，该方法将攻击复杂度降低到穷举攻击复杂度的1/4，而且对于Biclique攻击，AES算法也不能幸免2。所以，IDEA算法还是一个很安全的算法。IDEA算法是一个比较特殊的算法，其安全性建立在三个不相合的代数群运算上。其主要运算是对16比特的数据块进行异或，模216加法，模216+1 乘法运算，由于这三个运算彼此在不同的代数群上，结合律，分配律均不使用，从而使得IDEA算法的混淆速度非常快，在经过4.5轮迭代后IDEA算法就能抵抗差分分析攻击。但IDEA算法的缺陷是其密钥调度过于简化，仅仅是简单的线性移位，目前所有对IDEA的攻击都是利用其密钥调度的缺陷。原始的IDEA算法的上层结构并不具有理论意义上的伪随机性，所以Vaudenay 对IDEA算法的结构进行了微小的改动，添加了一个正交置换，从而使其具有理论意义上的伪随机性，并且将此结构称为Lai-Massey结构13，该结构被证明是经过3轮后具有伪随机性，4轮后具有强伪随机性的。所以综合考虑，我们基于IDEA和Lai-Massey结构设计了一个32比特分组长度，64比特密钥长度的分组密码 BeeCipher。该算法对并非仅仅是IDEA算法的32比特版本，而是对其轮函数进行了修改，添加了正交置换，并且修改了密钥调度过程，从而使得目前已有对IDEA算法的攻击都对BeeCipher 攻击无效。BeeCipher的软件实现也是非常简单的，其速度要比目前已有的大多数32比特分组长度算法要快很多。目前其他已有的32比特分组长度的算法有密码学家Greg Rose基于Skipjack设计的Skip32算法11，以色列Canniere等人设计的KATAN算法5和最近美国国家安全局设计的SIMON和SPECK算法等1。下表描述了这些算法的特征。算法分组长度(bit)密钥长度(bit)结构设计者Skip323280Feistel扩展结构澳大利亚Greg Rose11KATAN3280移位寄存器结构以色列Canniere等5KTANTAN3280移位寄存器结构以色列Canniere等5SIMON3264Feistel 结构美国国家安全局(NSA)1SPECK3264Feistel 结构扩展美国国家安全局(NSA)1BeeCipher3264Lai-Massey本文表1：32比特分组长度密码算法本文的第2部分将会对BeeCipher进行具体的描述，第3部分讨论BeeCipher的安全性，第4部分讨论其实现效率以及与其他的算法比较，第5部分给出了全文的结论。2. BeeCipher算法的具体描述BeeCipher是一个32比特分组长度，64比特密钥长度的加密算法，其包括8轮轮函数和一个输出变换。其基于IDEA算法，采用Lai-Massey结构，但是轮函数和密钥调度过程都与IDEA算法有一定的不同。图1给出了BeeCipher的加密过程。 图1：BeeCipher 加密过程。其中Xi为明文字节，即8比特，Kir为密钥字节，Yi为密文字节。为比特异或运算为字节加法运算，即模28下加法运算为模28+1下的乘法运算，其中0被28替换。Figure 1：The encryption of BeeCipher. Xi are plaintext bytes，Kir are key bytes，Yi are ciphertext bytes。 is the bit exclusive or operation is the modular addition operation under 28 is the multiply operation with modular 28+1, and 0 is replaced by 28。2.1.BeeCipher加密过程在图1中，有三种如下运算：1. 字节上的比特异或运算，以符号表示；2. 字节加法运算，即模28下加法运算，以符号表示。3. 模28+1下的乘法运算，其中0被28替换，以符号表示，例如02=28*2 mod 257= 255。加密过程中32比特明文分为4个字节X1, X2 ,X3 ,X4, 对于r 0，则第r+1轮的子密钥由第r轮子密钥作如下变换生成：1 令第r+1轮子密钥中K1r+1=K1r (K2rPrimesi mod 54)，其中Primes是小于整数256的54个素数集合, mod 为求余运算，即Primes54=2，3，5，7，., 251,刚开始时i=0,后面每运行一次乘法操作后将i递增，即i=i+1;2 对r+1轮子密钥（K1r+1 , . ,K8r+1）循环左移一个字节。3 重复步骤1-2直到8次，然后再将r+1轮子密钥循环左移13比特。4 这样一直到生成了68个子密钥为止。3. BeeCipher算法的设计原则与安全性分析2.1.Lai-Massey结构与IDEA结构BeeCipher算法是基于Lai-Massey结构设计的，Lai-Massey结构与IDEA的结构是不同的，下图给出了Lai-Massey结构与IDEA结构的对比。图2. Lai-Massey结构（左）与IDEA上层结构（右）对比图。Figure 2. Lai-Massey scheme（left）and IDEA high-level（right）.从图2中可以看出，Lai-Massey结构中每轮对左边的值增加了一个正交置换，而IDEA的上层结构只是将左边数据块的右半部分与右边数据块的左边部分进行对称交换。对于Lai-Massey结构，Vaudenay等人已经证明下面的定理：定理2.1: 在轮函数F为独立随机函数时，3轮Lai-Massey结构构成一个伪随机置换，4轮Lai-Massey结构构成一个强伪随机置换。对于如图2所示的IDEA上层结构，无论迭代多少轮都无法达到伪随机型，因为可以采用下面的攻击方法：攻击2.2： 对于一轮IDEA上层结构，若输入为(L0,R0)=( L10 L20, R10R20), 输出为(L1,R1)=( L11 L21, R11R21), 若F的输出为（f1 f2），则有： L11 L21 R11 R21 = L10f1L20f2 R10f1R20f2 = L10L20R10R20所以，可以看出无论经过多少轮迭代后，攻击者都可以使用上面的攻击方法将其与一个伪随机置换区分开来。值得注意的是，这里的攻击并不表示IDEA算法不能达到伪随机性的，因为IDEA算法使用了不相容群上的运算，具有很强的混淆性。这里的攻击表示若IDEA算法轮函数输入与密钥的运算都在一个群上进行，例如将IDEA轮函数中最上面的明文与密钥的运算改为异或运算，则IDEA算法将无法达到伪随机性。BeeCipher对IDEA算法做出了相应的修改，在IDEA算法的基础上增加了正交置换，在理论上可以证明BeeCipher的结构具有强伪随机性，并且其同时具有IDEA算法不同群上运算的强混淆性，所以BeeCipher的安全性要强于32比特版本的IDEA算法。2.2.对BeeCipher的弱密钥分析。目前对IDEA的所有攻击都利用到了IDEA密钥调度过于简单的弱点，在BeeCipher的密钥调度中，我们使用了类似于非线性移位寄存器的方法，每一个新生成的字节密钥都是之前的密钥经过不同群上的模乘和异或运算得出。由于在28+1上的模乘与GF（28）上的异或运算不兼容，使得二者混合起来具有很高的非线性，所以BeeCipher不存在类似于IDEA的弱密钥。2.3.对BeeCipher的差分分析与线性分析。由于BeeCipher是IDEA的32比特版本的改进版，在文献7中，Lai使用了马尔科夫链理论证明了8比特和16比特版本的IDEA算法在经过了4轮后就能抵抗差分分析，并猜想32比特与64比特也是如此，就目前已有对IDEA的攻击结果来看，IDEA对差分分析抵抗能力的确很好。对于线性分析，由于BeeCipher采用了群上的不兼容运算，其非线性度非常高，在文献7中，Lai证实了MA结构，也就是图1中轮函数中最中间的结构是具有完美混淆性的，所以BeeCipher对线性分析具有很强的抵抗能力。2.4.对BeeCipher的Biclique 攻击Biclique攻击是目前最成功的攻击，不仅成功应用在IDEA上，也成功应用在AES上，Biclique攻击之所以成功主要利用了IDEA算法和AES算法的密钥调度的混淆速度都不是很快，而BeeCipher的密钥调度混淆速度却相当快，使得Biclique攻击无法奏效。所以，综上分析，我们认为BeeCipher是比32比特的IDEA算法更安全的，而且其能够达到最优安全性，即对BeeCipher的最好攻击就是穷举攻击。64比特的安全性能够满足对手是非政府组织和非军事组织，安全性需求不是太高，但又具有一定安全性的应用场景中，特别的，其可以应用在超市，购物商场上。4. BeeCipher算法的实现效率在这一部分里我们讨论BeeCipher的实现和运行速度，由于BeeCipher所以的运算都字节运算，所以其无论是软件实现，还是硬件实现，都是很简单的。我们在这里给出了其实现效率并将其与其他的算法进行对比。为了实现算法公平对比，我们在同一个运算平台实现了一下算法，所使用的平台是HP个人PC，CPU为Intel i5-5200U 2.20GHz, 下表给出了运行加密算法100万次所耗时间对比：算法加密百万次耗时 (ms)KATANTA32309，865KATAN3216，239AES1287，160Skip32998BeeCipher281SPECK32162SIMON32150表2：不同算法运行百万次耗时对比Table 2：Time comparison of different algorithms 从表2可以看出，BeeCipher的软件实现速度是Skip32算法的3倍还多，而KATAN32与KATANTA32主要是为了硬件平台实现的算法，所以其软件实现速度很慢。同时，BeeCipher一次的运行速度是AES128一次运行速度的25倍多一点。 BeeCipher的速度比美国国家安全局设计的SPECK32和SIMON32要慢40%左右，但SIMON32和SPECK32算法的安全性正在受到大量的攻击，且大多数人们对NSA的信任不够。同时，由于所有运算都是字节运算，BeeCipher的硬件实现也是很方便。所以，我们认为BeeCipher在32比特长度分组密码中是很有竞争力的候选算法。4. 结论本文主要设计了一个32比特分组长度，64比特密钥长度的分组密码算法BeeCipher， 并且对BeeCipher的安全性做出了分析。BeeCipher是对32比特IDEA算法版本的改进，在轮函数中增加了正交置换，从而使得结构具有可证明安全性，同时采用了IDEA算法中良好的乘法加法混淆模块，增加了算法混淆性，并且修改了密钥生成算法，避免了线性密钥调度过程，从而使得最新的Biclique攻击对BeeCipher不成立。 在软件实现上，BeeCipher算法比其他大多数32比特分组算法要快很多，只比美国国家安全局最新设计的SIMON和SPECK慢40%左右。在硬件实现上，BeeCipher也非常容易。考虑到美国国家安全局设计的算法目前还未被验证具有良好的安全性，所以我们认为BeeCipher 是一个有力32比特分组长度的候选分组密码算法参考文献1 Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., and Wingers, L. The SIMON and SPECK families of lightweight block ciphers. EB/OL Cryptology ePrint Archive, Report 2013/404 (2013), /2013/404.2 Bogdanov, A., Khovratovich, D., and Rechberger, C. Biclique Cryptanalysis of the Full AES. C In ASIACRYPT 2011. LNCS 7073, Springer-Verlag , 2011, pp. 344371. 3 Bogdanov, A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M.J.B., Seurin, Y., and Vikkelsoe, C.: PRESENT: An ultra-lightweight block cipher. C In CHES 2007. LNCS 4727, Springer-Verlag, 2007, pp. 450466. 4 Daemen, J., and Rijmen, V. The Design of Rijndael: AES-The Advanced Encryption Standard. M Springer-Verlag, 2002.5 De Canniere, C., Dunkelman, Orr., and Knezevic, M. KATAN and KTANTAN A Family of Small and Efficient Hardware-Oriented Block Ciphers. C In CHES 2009. LNCS 5747, Springer-Verlag, 2009, pp. 272-288.6 Guo, J., Peyrin, T., Poschmann and Robshaw. M. The LED Block Cipher. C In CHES 2011. LNCS 6971, Springer-Verlag, 2011, pp. 326-341.7 Junod, P., and Vaudenay, S. FOX: a new family of block ciphers. C/In SAC 2004, LNCS 3357, Springer-Verlag, 2004, pp. 114129. 8 Knudsen, L.R., Leander, G., Poschmann, A., Robshaw, M.J.B.: PRINTcipher: A Block Cipher for IC-Printing. C In CHES 201