LED轻量级分组密码设计的研究与改进探讨

中图分类TP309.7 文献标志A文章编2095-641X(2014)09-0015-05LED轻量级分组密码设计的研究与改进探讨郭淳1徐兴坤2（1.中图分类TP309.7 文献标志A文章编2095-641X(2014)09-0015-05LED轻量级分组密码设计的研究与改进探讨郭淳1徐兴坤2（1.中国科学院信息工程研究所，北京1000932.中国电力科学研究院，北京100192）摘未来电力系统的安全体系需要高效率分组密码的支持。为探讨现有分组密码在此领域应用的可能性文章选取分组密码LED作为研究对象讨论了其设计理念及改进的可能性。LED轻量级分组密码由JianGuo等发表于CHES201利用一系列优化措施LED在安全性与软件实现性能方面均突出硬件实现面积也十分紧凑不足之处在于硬件实现的延时对此可能的改进方法为重排其加密过程以便在不降低安全性的前提下减少总轮数。关键LE轻量级分组密分组密码设计与分析技术研究与应用对LED进行分析归纳如下。1整体结构设采用安全界限有理论保障的AES-like结构。2）各部件的设：①S：采用了Serpent型S；②最大距离可分（MaximalDistanceSeparableMDS矩采用了基于线性反馈移位寄存（LinearFeedbackShiftRegisterLFSR的MDS矩③密钥编直接运用主密钥因“几乎没密钥编排。3优安全性与软件实现性能均十分优异。4可能的改进方①利用后续发现的性能更好的S盒MDS矩阵等替换原设计中的部件以求得更优异的整体性②对其安全界限进行更精细的推算藉此对加密过程进行重排设法达到缩减轮数的目的以降低硬件实现的数据处理时延。0 引言轻量级分组密码的设计与分析兴起于2005年前后此后世界各地的研究组陆续设计了HIGHT[1]、DESL[2]PRESENT[3]等多个方案其中有些方案综合性能优异并得到广泛认可如PRESENT方案凭借良好的安全性与优异的硬件实现面积已被采纳为国际标准[4]。通常认为低计算能力应用场景要求方案的硬件实现面积不超过2000GE[5]而高级加密标准（AdvancedEncryptionStandardAES最紧凑的实现仍需2400GE[6]。为弥补这一缺失较早提出的方案十分注重硬件实现规模的控制相对忽视了软件实现致使软件实现性能不理想[7]。LED轻量级分组密码发表于CHES2011[8]是一个软件与硬件性能兼顾的尝试。综合地看LED在安全性与软件实现性能方面均突出硬件实现方面尽管数据处理时延较长但也十分紧凑。本文从设计理念优缺点及可能的改进等方面，1 LED的设计要点1.1设计理念LED的设计目标是在设法取得紧凑硬件实现的4年第12卷第9期CRT........................................CWERT同时实现以下3个设计目：1探讨........................................CWERT同时实现以下3个设计目：1探讨超轻量甚至于密钥编排过程的效；2考究对相关密钥攻击的抵抗；3兼顾软件实现的性能。LED的设计者特别强调了对相关密钥攻击的抵抗性并证明了安全界设计者将密钥编排过程设计“几乎没有的形式起到了减少密钥差分对各轮密钥的影响简化安全界限推导的作用。1.1.1 轮函数LED的轮函数采用AES-like结构这一设计思路有以下3点优：1在差分与线性攻击抵抗能力分析方面可以直接借用已有的成熟结；2可以从上述结论推导出相关密钥下的安全界；3AES-like结构是基于小数据块的结构软件实现性能优于基于bit的结构。AES-like结构由迭代的多轮组成每轮通常包括4个步骤分别是密钥异或代换行移位与列混淆。其中代换运算为非线性变换多由S盒组成每个S盒将更小的数据单位替换为特定的行移位与列混淆则均为线性变换分别促成状态矩阵内列间与行间数据的扩散。单纯的S盒与行移位列混淆等的密码学特性并不突出然而这样的运算迭代多轮即可实现香农提出的扩散与混淆的设计原则。1.1.2 LED各部件1S盒。LED直接沿用了PRESENT的S盒，该S盒为Serpent型S盒[9]最大差分概率与线性逼近偏差均为2–2不存在输入输出差分值权重均为1的差分对但存在很多输入输出掩码值权重均为1的线性逼近。但在AES-like结构中真正起作用的是最大差分/线性概率因此其没有显著的不良影响。2行移位。行移位都被设计“循环左移i个nibble的形式这是AES-like结构安全界限证明的要求可使得各列的4个nibble被行移位运算分散到4个不同列中。若不严格依照此规则设计则可能出现严重问题如KLEIN[10]。3列混淆矩阵。文献[11]利用了基于单个nibble级LFSR构造的MDS矩阵作为列混淆矩阵，其优势是硬件实现时只需实现一个nibble级LFSR，所需面积较小。同时由于这一过程可以用移位反馈的机制实现状态中若干nibble可以实现为更紧凑的单输入触发器进一步降低了硬件实现面积LED沿用了该矩阵。这种设计的缺点是线性变换所需的时钟周期数目较多LED的线性变换需40个周期而PRESEN-like结构的线性变换一般只需1个周期。1.2参数LED的分组长度为64bit密钥长度从64bit至128bit连续可调然而多数情况下讨论的是64bit、80bit与128bit密钥的变体LED-64LED-80与LED-128。1.3整体结构LED整体设计为广义Even-Mansour结构[12]，该结构中各随机置换用4轮轮函数实现伪随机置换代替设计者将这样的伪随机置换称为步函数。Even-Mansour结构示意如图1所示。技术研究与应用P为明文输入C为密文输出K-K为子密钥t为轮数F与F为随机置换。图1Even-Mansour结构示意Fig.1Even-Mansourstructure1.4加密过程对64bit数据分组交替地运用轮密钥加addRoundKey与步函数step其中轮密钥加addRoundKey通过异或的方式将轮密钥引入状态，而步函数完成主要的变经多轮运算之后得密文数据分组LED加密过程示意如图2所示LED加密过程的伪代码如：轮密钥加运算通过位异或运算将密钥引入状态LED加密过程中轮密钥加运算的伪代码如：对LED-64需经过8次步函数的运而对更4年第12卷第9期CRTfunctionaddRoundKey(STE,SKs)STE:=STESKsfori=0tos–1do{addRoundKey(STE,SKi)step(STE)}addRoundKey(STE,SKs),,,,,1 $1 $BὍU=1ௐᄉ&WFO–.BOTPVSፆౝ CὍU=2ௐᄉ&WFO–.BOTPVSፆౝ'''CWERT........................................对i=0,1,2,3将矩阵的第i行循环左移i个nibble的位置。4MixColumnsSerial。具体可视为矩阵A的连续4次运如上将中间状态看作4×4的4bCWERT........................................对i=0,1,2,3将矩阵的第i行循环左移i个nibble的位置。4MixColumnsSerial。具体可视为矩阵A的连续4次运如上将中间状态看作4×4的4bitnibble矩阵然后用矩阵A进行4次左乘矩阵A与最终的MDS矩阵W可写：P为明文输入C为密文输出SK-SK为子密钥。图2LED加密过程示意Fig.2LEDencryptionprocess40 401001010216E225AF200 86大密钥长度的变体则需经过12次步函数的运算。1.5步函数与轮函数如上所述LED的步函数由4轮轮函数迭代构成。轮函数运算则由AddConstants、SubCellsShiftRow与MixColumnsSerial4次操作组成。将中间状态M=m0||m1||…||m63看作16个4bitnibble即n0||n1||…||n15对0≤i≤15，ni=(mi×4,mi×4+1,mi×4+2,mi×4+3)则轮函数的4次操作可分别描述如下。1AddConstants。该步骤在中间状态的特定位置通过异或的方式引入常量常量的定义如每轮中将6bitLFSR(rc5,rc4,rc3,rc2,rc1,rc0)左移1位，W()4901 B422B其中各元均视为GF(24)中的元不可约多项式为X4+X+1。1.6取轮密钥的规则对LED-64反复运用64bit的主密钥。对更大密钥长度的变体将主密钥看作nibble的序列ik0,k1,…,kl并将第i个子密钥SK表示成nibble方阵的形：skiskiskiski0123技术研究与应用iiiisk4sk5sk6sk7更新值的计算式为*=⊕⊕1。LEFR初始iiii0 5 4s8sk9s10s11 ii化为全0的状态并在每轮中AddConstants运算进行前先完成1次更将密钥长度记作8bit值iis12s13s14s15i则取密钥的操作为skj=k(j+i16odl)。注意到对128bit主密钥操作时这样的方式相当于是交替地取128bit主密钥的前64bit与后64bit。(ks,ks,…,ks)其中ks为最低有效位所得的轮常7 607量矩阵如：0(s7||s6||5||4)(c5||c4||c3)000001(s7||s6||5||4)(c2||1||c0)2(s3||s2||1||0)(c5||c4||c3)002 LED主要优缺点2.1LED性能设计者成功达成了兼顾软硬件实现性能的目：LED软件实现速度很而在硬件实现方面尽管利用了较复杂的MDS矩阵但与以硬件性能著称的PRESENT相比其面积反而更低这是因为其存储中间状态的部分寄存器可以用更紧凑的单输入触发器实现且密钥寄存器也可用单输入触发器实现因此节约了大量硬件面积。但采用这样的MDS矩阵增大了线性变换的时钟周期消耗而LED的各变体所用轮数极最少的LED-64也有32这样总的数据处理时延很高。例如LED-80完成一个分组的加密需1872个时钟周期有着相同密钥长度的PRESEN-80则至多只需547个。综合地看与PRESEN-like结构相比LE与3(s3||s2||1||0)(c2||1||c0)02SubCells。该步骤将每个nibbleni的值用经由4×4bitS盒S:F4→F4运算后所得的值代替，2 2对每个0≤i≤15(mi×4,mi×4+1,mi×4+2,mi×4+3):=S(ni)=S(mi×4,mi×4+1,mi×4+2,mi×4+3)。S盒以16进制表示可表示如：3ShiftRow。该步骤中将中间状态n0||n1||…||n15看作4×4的4bitnibble矩：0159132610143M4871112154年第12卷第9期CRTxS[x]0123456789ABCDEFC56B90AD3EF847124,4,4,4,4,1 $1൥4ᣂ4ᣂ4ᣂ........................................CWERT了较多重视........................................CWERT了较多重视[14]并催生“低时延分组密码方案PRINCE[15]。减少时延的方法之一是合理缩减轮数，考虑到文献[8]中的安全界限是较为粗略的上界对其做更细致的讨论求得更紧凑的界限并依据其适当重排结构增加单步的轮数而缩减总步数使得整体轮数减少这是一个可能的改进方向。AES-like结有如下优：1有可在理论上证明的安全界；2软件实现有一定优；3在合理的实现策略下硬件面积也可有一定优势。缺点则是硬件实现的数据处理时延很高而若牺牲面积来弥补时延则面积又会很高。2.2LED安全性LED在安全性方面最突出的特色是拥有对相关密钥差分攻击的可证明安全性这是其简单密钥调度形式所造成的。以LED-64为例简述其证明原理如若密钥差分不为0则不可能有连续两步差分均为0因此每两步中必有一步计算过程中差分不为0因此对s步的路径至少有[s/2]·25个活跃S盒概率上界为2-[s/2]·50。4 结语本文从LED整体结构设计思路各部件的设计理念优缺点及可能的改进方向对LED进行了分析。由于采用AES-like结构LED对传统差分线性等攻击的抵抗能力得到了可证明的保障且软件实现性能优由于采用了简单易于分析的密钥编排方案LED对相关密钥攻击的抵抗能力也得到了可证明的安全界由于在实现时利用了基于LFSR的MDS矩阵的性质LED的硬件实现面积同样控制到了极低的水平。设计者赋予了LED极高的轮数这拖累了其硬件实现的加密时延。此外后续研究对S盒与MDS矩阵设计的改进也使得通过改用更优异的部件以取得更好的效果成为可能这些都是LED可能的改进方向。3 LED的改进讨论本节从各部件进一步优化及总体设计优化的可能性等方面讨论LED改进的可能性。3.1S盒的进一步优化LED采用的S盒最紧凑的实现亦无法低于20GE。后续的研究表明提供同样等级的安全性的S盒实现面积可以低达15GE其运用有助于进一步压缩硬件面积。3.2MDS矩阵的进一步优化文献[13]中讨论了更加紧凑的MDS矩阵的构造表明基于多个nibble级LFSR能取得显著的面积优势而安全性与早期方案所采用的相同，实现复杂度也并未增加是全方位的进步。其成果如运用于LEDSpongent等能显著缩减硬件实现面积。3.3密钥运用的瑕疵对LED-128而言第一次轮密钥加与最后一次轮密钥加运算所用的轮密钥相同且都为64bi；因此利用264的计算开销即“剥离这两步[12]，等在理论白白损失两步。尽管2步相对于LED-128合计12的总步数而言并不严重但如将步数改为奇数则可避免这一点而并不会造成额外开销。3.4轮数缩减的可能性极高的轮数保障了高度安全性但也拖累了LED硬件实现时延。近年来时延这一性能得到技术研究与应用参考文献：[1]HONGD,SUNGJ,HONGS,etal.HIGH:Anewblockciphersuitableforlow-resourcedevice[C]//CryptographicHardwareandEmbeddedSystems(CHES2006),2006:46–59.LEANDERG,AARC,POSCHMANNA,etal.NewlighweightDESvariants[C]//FastSoftwareEncryption2007(FSE2007),2007:196–210.BOGDANOVA,KNUDSENLR,LEANDERG,etal.[2][3]PRESEN:Anultra-lightweightblockcipher[C]//CryptographicHardwareandEmbeddedSystems(CHES2007),2007:450–466.[4]ISO/IEC29192-2:2012.Informationtechnology-securitytechniques-lightweightcryptography-Part2:Blockciphers[S].2012.JUELSA,WEISSA.Authenticatingpervasivedeviceswithhumanprotocols[C]//AdvancesinCryptology(CYPO2005),[5]2005:293–308.MORADIA,POSCHMANNA,LINGS,etal.Pushingthelimits:Averycompactandathresholdimplementationof[6]4年第12卷第9期CRTCWERT........................................AES[C]//AdvancesCWERT........................................AES[C]//AdvancesinCryptology(EUROCYPT201),201:69–88.applications[C]//AdvancesinCryptology(ASIACYPT2012),2012:208–225.[7]BENADJILAR,GUOJ,LOMNE,etal.Implementinglightweightblockciphersonx86architectures[C]//SelectedAreas编辑邹海彬收稿日2014-06-09inCryptography(SAC2013),2013:324–351.GUOJ,PEYRINT,POSCHMANNA,etal.TheLED[8]blockcipher[C]//CryptographicHardwareandEmbeddedSystems(CHES201),201:326–341.[9]LEANDERG,POSCHMANNA.Ontheclassificationof4bitS-boxes[C]//AIFI2007:159–176.[10]LALLEMAND,NA-PLASENCIAM.CryptanalysisofKLEIN[C]//FastSoftwareEncryption(FSE2014),2014.[1]GUOJ,PEYRINT,POSCHMANNA.ThePHOTONfamilyoflightweighthashfunctions[C]//AdvancesinCryptology(CYPO201),201:222–239.[12]MENDEL,RIJMEN,OZD,etal.DiferentialanalysisoftheLEDblockcipher[C]//AdvancesinCryptology(ASIACYPT2012),2012:190–207.[13]WUSB,ANGMS,WUWL.Recursivedifusionlayersfor(lightweight)blockciphersandhashfunctions[C]//Selected技术研究与应用AreasinCryptography(SAC2012),2012:355–371.[14]KNEZEVICM,NIKOV,ROMBOUTS.Low-latencyencryption–i“Lightweight=Light+ait?[C]//CryptographicHardwareandEmbeddedSystems(CHES2012),2012:426–446.[15]BORGHOFFJ,CANTEAUTA,GUNEYSU,etal.PRINCE–Alow-latencyblockcipherforpervasivecomputingReseachonLEDLightweightBlockCipherDesignandItsImpovementsGUOChun1,XUXing-kun2(1.Insti