AES-128的密钥中比特检测及分析

万刘蝉，韦永壮

(桂林电子科技大学 信息与通信学院，广西 桂林　541004)



AES-128的密钥中比特检测及分析

万刘蝉，韦永壮

(桂林电子科技大学 信息与通信学院，广西 桂林541004)

针对分组密码算法AES-128的安全性分析，评估了AES-128算法内部结构对密钥比特的混淆和扩散性，根据算法的密钥编排特点和轮函数结构，利用FPGA测试平台设计了一种AES-128的密钥中比特检测算法。测试结果表明，在立方变元取17～24维时，3轮简化AES-128的输出位容易捕获密钥中比特，但4轮以上AES-128的输出位均无法捕获密钥中比特。

AES密码；密钥中比特；立方测试；FPGA

1997年，比利时密码专家Daemen等[1]设计了一种新的分组密码算法——Rijndael算法，并于2001年被美国国家标准技术研究所(NIST)选为高级加密标准(AES)。AES分组密码算法采用SPN结构及宽轨迹设计策略，具有安全性高、加解密速度快、灵活适用于各种软硬件平台等特点。鉴于AES的广泛使用，AES的安全性一直备受关注。AES经受了多种密码分析，包括平方攻击[2]、碰撞攻击[3]、不可能差分攻击[4-8]、飞来器攻击[9]、中间相遇攻击[10-12]、Biclique攻击[13]等，这些攻击与AES的密钥编排特点及轮函数结构紧密相关。2009年，Dinur等提出了一种新型的代数攻击方法，称为立方攻击[14]。随后Aumasson等[15]将立方攻击推广为立方测试，立方测试的核心思想是检测局部布尔函数的非随机性，以判定加密算法的整体安全强度。

为了使AES的密钥比特与轮函数的迭代组合最佳，并检测AES算法内部结构对密钥比特的混淆和扩散性程度，利用AES算法内部结构及密钥编排特点，结合立方测试的基本思想，在FPGA平台上对简化轮AES-128算法的密钥中比特进行检测与分析。

1　AES结构简介

AES分组长度为128 bit，密钥长度分为128、192、256 bit三种，分别用AES-128、AES-192和AES-256表示，且分别需要迭代10轮、12轮和14轮。

1)字节替换。字节替换是AES算法中唯一的非线性变换，该变换按照一定的规则将状态的每个字节a映射为某一特定的字节b=S(a)，其中S：GF(28)→GF(28)。

2)行移位。行移位将状态矩阵的第j行循环左移j个字节，其中j=0，1，2，3。

4)轮密钥加。轮密钥加将轮密钥与中间状态进行异或，AddroundKeyki(A)=A⊕Ki。

2　立方测试

立方测试是在立方攻击的基础上提出的一种新的密码分析方法。

定义1[15]给定加密函数E(K,V)，K为密钥，V为初始集合，若存在密钥比特ki对E(K,V)的某位输出累加结果不产生影响，则称ki为密钥中比特。

假设一个8bit的输入加密函数为：

遍历I，而v3、v4不变，对加密函数进行累加，

则k3、k4为密钥中比特。

3　AES-128算法的密钥中比特检测算法设计

根据AES算法的结构，并结合密钥中比特检测的基本思想，AES-128算法的密钥中比特检测流程如图1所示。

假定AES-128加密函数为E(K,V)，其中，公开变量集合V={v1,v2,…,v128}，AES-128主密钥集合K={k1,k2,…,k128}。

1)任意选取V的子集U={v1,v2,…,vn}，n=17,18,…,24，作为n维立方变元集合，剩余的公开变量不变(如全取0)，随机生成40个主密钥串{K1,K2,…,K40}。

图1　AES-128密钥中比特检测流程Fig.1　Flow chart of key neutral-bit detection for AES-128

4)对步骤3)得到可能的密钥中比特ki再次检测，选取随机密钥K2重新执行步骤2)、3)，若ki仍为可能的密钥中比特，则选取下一个随机密钥K3继续检测，直到取完40个主密钥，ki仍为可能的密钥中比特，则ki为密钥中比特，检测失败的概率为2-40。

4　硬件实现

实验采用FPGA芯片AlteraEP2C8Q208CN，设计了多个并行AES-128算法的实例，实现了AES-128密钥中比特检测，成倍减少攻击时间。

4.1AES-128算法

AES-128算法在FPGA中采用移位寄存器、异或门、与门以及状态机实现AES算法。为了让代码高效可靠地运行，在AES算法整体布局时，对AES进行拆开分模块化处理，并将AES-128分成主加密模块(aes_cipher_top)、S盒模块(aes_sbox)、密钥扩展模块(aes_key_expand)。AES-128算法实现所需的逻辑资源如表1所示。

表1　AES-128算法实现所需的逻辑资源

4.2密钥中比特检测

在AES-128密钥中比特检测中，除了AES-128加密模块，还设计了另外3个模块：第一个模块为每个实例提供伪随机密钥K和含有立方变元V*的初始明文V(除立方变元外，其他为0)；第二个模块收集检测到的密钥中比特；第三个模块为传输单元。根据FPGA芯片的内部资源的数量及AES-128算法消耗资源的大小，将128位密钥分为2个部分，各占64bit，采用17～24个立方变元，并行运行2个AES-128算法实例。攻击的硬件结构如图2所示，控制模块为每个AES-128加密实例提供密钥K和含有立方变元V*的初始明文V。AES-128加密实例对V进行加密，加密后V*+1，再次加密，直到遍历V*。设立方变元的维度为n，计算2d次加密后，更新ki⊕K，更新后的密钥再次给AES-128实例加密，直到128位密钥更新完毕。若所有实例完成所需操作，组合模块将从每个实例收集128位密钥并发送给传输模块。传输模块负责顶层模块和底层模块之间的联系。

实验采用FPGA并行运行2个AES-128实例，每个实例检测64位密钥，共计128位。立方变元的维度越多，需要的时间越长。PC配置为IntelCoreI7-2600 3.4GHz,4GBRAM，在不同立方变元维度下，FPGA和PC耗时见表2、3。由表2、3可知，采用FPGA实现密钥中比特检测比个人电脑耗时少，且FPGA成本更低。

图2　攻击的硬件结构Fig.2　Structure of attack hardware

表2　FPGA耗时

表3　PC耗时

5　攻击结果及分析

1)固定立方变元取对角线，使其经过变换后到达第一列，即第1字节，第1、6字节，第1、6、11字节，第1、6、11、16字节的前2位和最后2位，分别对3轮、4轮AES-128进行测试，检测输出的第一位。在对3轮AES-128检测中，固定立方变元的输出结果均为0，而在对4轮AES-128检测中，不存在密钥中比特。

2)随机立方变元维度取17～24，分别对简化到6轮、5轮、4轮、3轮的AES-128进行测试，检测输出的第一位。在对6轮、5轮，4轮的AES-128检测中无法找到密钥中比特，而在对3轮AES-128的检测中，均能发现密钥中比特，如表4所示。

从表4可看出，对于简化到3轮的AES-128算法，在立方变元维度为17～24时，均能检测到密钥中比特，且均在40～80。AES-128在对密钥的混淆扩散的过程中，对40～80的密钥扩散混淆性较差，但4轮迭代后AES-128算法迅速修复了这些漏洞。全轮的AES-128算法具有稳固的密钥信息扩散及混淆性。

表43轮AES-128密钥中比特检测结果

Tab.4Keyneutral-bitdetectionresultsof3-roundAES-128

维度立方变元密钥中比特179,18,23,25,26,28,29,30,43,45,46,96,104,108,114,125,12643,45,46172,12,13,15,26,38,39,41,52,56,59,82,86,93,95,96,11241186,18,21,22,27,30,33,61,68,73,76,77,84,88,99,107,110,11373,76,77185,8,13,25,31,38,41,58,62,69,73,78,81,101,109,110,114,11941,73,78196,10,13,16,17,18,21,31,36,46,49,56,58,75,78,79,84,88,10346,75,78,79196,15,17,18,24,31,52,55,56,62,64,67,72,76,89,92,99,101,12372,762013,14,15,19,20,41,45,48,62,69,70,74,78,81,91,93,105,109,12441,45,74,75,78204,6,13,24,28,36,45,54,62,70,83,84,85,86,96,98,102,108,113,11645211,4,6,7,16,17,34,37,38,49,60,63,66,77,87,100,107,110,114,119,12277215,7,10,22,26,34,35,43,46,47,48,74,75,97,99,100,108,112,115,11843,46,47,74,752216,21,24,28,37,42,46,47,50,56,57,59,78,83,91,95,97,110,115,116,118,12042,46,47,782213,17,31,36,41,43,46,49,50,52,53,54,58,62,71,74,75,82,85,104,107,11741,43,46,74,75232,4,6,25,39,42,53,60,63,74,77,79,80,86,90,94,101,108,112,114,121,12342,74,77,79230,8,12,18,19,23,30,42,48,53,59,63,66,70,71,72,73,78,80,81,108,121,12642,72,73,78241,3,5,10,11,13,16,35,36,40,45,47,61,65,70,76,78,79,80,92,96,118,123,12740,45,47,76,78,79240,2,17,24,34,35,40,44,51,61,64,68,69,72,77,78,87,90,92,99,100,111,123,12640,44,72,77,78

6　结束语

为了分析分组密码算法AES-128的安全性，设计了一种基于FPGA的高效密码分析平台，并对AES-128进行了密钥中比特检测。在立方变元取17～24维时，3轮简化AES-128的输出位容易捕获密钥中比特，但4轮以上AES-128的输出位均无法捕获密钥中比特。对于高级加密标准AES-128，其初始轮数必须4轮以上才能保证安全。

[1]DAEMENJ,RIJMENV.Rijndael/AES[M]//HENKCA.EncyclopediaofCryptographyandSecurity,US：Springer,1997:520-524.

[2]FERGUSONN,KELSEYJ,LUCKSS,etal.ImprovedCryptanalysisofRijndael[C]//FastSoftwareEncryption,2000:213-230.

[3]GILBERTH,MINIERM.Acollisionsattackonthe7-roundsRijndael[C]//AESCandidateConference,2000:1-11.

[4]BIHAME,KELLERN.CryptanalysisofreducedvariantsofRijndael[C]//3rdAESConference,2000:11-15.

[5]CHEONJH,KIMMJ,KIMK,etal.ImprovedimpossibledifferentialcryptanalysisofRijndaelandCrypton[C]//InformationSecurityandCryptology-ICISC2001,2001:39-49.

[6]ZHANGW,WUW,FENGD.NewresultsonimpossibledifferentialcryptanalysisofreducedAES[C]//InformationSecurityandCryptology-ICISC2007,2007:239-250.

[7]LUJ.Cryptanalysisofblockciphers[R].RoyalHolloway:UniversityofLondon,2008.

[8]LUJ,DUNKELMANO,KELLERN,etal.NewimpossibledifferentialattacksonAES[C]//ProgressinCryptology-INDOCRYPT2008,2008: 279-293.

[9]BIRYUKOVA.Theboomerangattackon5and6-roundreducedAES[M]//AdvancedEncryptionStandard-AES.SpringerBerlinHeidelberg,2004:11-15.

[10]WEIY,LUJ,HUY.Meet-in-the-middleattackon8roundsoftheAESblockcipherunder192keybits[M]//InformationSecurityPracticeandExperience.SpringerBerlinHeidelberg,2011:222-232.

[11]DUNKELMANO,KELLERN,SHAMIRA.Improvedsingle-keyattackson8-roundAES-192andAES-256[J].JournalofCryptology,2015,28(3):397-422.

[12]DERBEZP,FOUQUEPA,JEANJ.Improvedkeyrecoveryattacksonreduced-roundAESinthesingle-keysetting[M]//AdvancesinCryptology-EUROCRYPT2013.SpringerBerlinHeidelberg,2013:371-387.

[13]BOGDANOVA,KHOVRATOVICHD,RECHBERGERC.BicliquecryptanalysisofthefullAES[M]//AdvancesinCryptology-ASIACRYPT2011.SpringerBerlinHeidelberg,2011: 344-371.

[14]DINURI,SHAMIRA.Cubeattacksontweakableblackboxpolynomials[M]//AdvancesinCryptology-EUROCRYPT2009.SpringerBerlinHeidelberg,2009:278-299.

[15]AUMASSONJP,DINURI,MeierW,etal.Cubetestersandkeyrecoveryattacksonreduced-roundMD6andtrivium[C]//FastSoftwareEncryption,2009:1-22.

编辑：曹寿平

Detection and analysis of key neutral-bit for AES-128

WAN Liuchan, WEI Yongzhuang

(school of Information and Communication Engineering, Guilin University of Electronic Technology, Guilin 541004, China)

Focusing on the safety analysis of the AES-128 block cipher, AES-128 algorithm internal structure on key bit confused and diffusivity is evaluated. Based on the key scheme and the round function structure,a key neutral-bit detection algorithm is designed for AES-128 by using FPGA test platform. Simulation results show that the output bits of 3-round AES-128 always have neutral key bits when the cubic variables are fixed in the range of 17 to 24 dimensions. However, the neutral key bits for the any output of 4-round AES-128 are not found if the cubic variables are fixed in the range of 17 to 24 dimensions.

advanced encryption standard; key neutral-bit; cube test; FPGA

2015-11-24

国家自然科学基金(61100185)；桂林电子科技大学研究生教育创新计划(YJCXS201525)

韦永壮(1976-)，男(壮族)，广西田阳县人，教授，博士，研究方向为信息安全。E-mail:walker_wyz@guet.edu.cn

TP309.7

A

1673-808X(2016)04-338-03

引文格式：万刘蝉，韦永壮.AES-128的密钥中比特检测及分析[J].桂林电子科技大学学报，2016,36(4):338-341.