AES-128的密鑰中比特檢測及分析

萬劉蟬，韋永壯

(桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林　541004)

?

AES-128的密鑰中比特檢測及分析

萬劉蟬，韋永壯

(桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林541004)

針對分組密碼算法AES-128的安全性分析，評估了AES-128算法內(nèi)部結(jié)構(gòu)對密鑰比特的混淆和擴(kuò)散性，根據(jù)算法的密鑰編排特點(diǎn)和輪函數(shù)結(jié)構(gòu)，利用FPGA測試平臺設(shè)計(jì)了一種AES-128的密鑰中比特檢測算法。測試結(jié)果表明，在立方變元取17～24維時(shí)，3輪簡化AES-128的輸出位容易捕獲密鑰中比特，但4輪以上AES-128的輸出位均無法捕獲密鑰中比特。

AES密碼；密鑰中比特；立方測試；FPGA

1997年，比利時(shí)密碼專家Daemen等[1]設(shè)計(jì)了一種新的分組密碼算法——Rijndael算法，并于2001年被美國國家標(biāo)準(zhǔn)技術(shù)研究所(NIST)選為高級加密標(biāo)準(zhǔn)(AES)。AES分組密碼算法采用SPN結(jié)構(gòu)及寬軌跡設(shè)計(jì)策略，具有安全性高、加解密速度快、靈活適用于各種軟硬件平臺等特點(diǎn)。鑒于AES的廣泛使用，AES的安全性一直備受關(guān)注。AES經(jīng)受了多種密碼分析，包括平方攻擊[2]、碰撞攻擊[3]、不可能差分攻擊[4-8]、飛來器攻擊[9]、中間相遇攻擊[10-12]、Biclique攻擊[13]等，這些攻擊與AES的密鑰編排特點(diǎn)及輪函數(shù)結(jié)構(gòu)緊密相關(guān)。2009年，Dinur等提出了一種新型的代數(shù)攻擊方法，稱為立方攻擊[14]。隨后Aumasson等[15]將立方攻擊推廣為立方測試，立方測試的核心思想是檢測局部布爾函數(shù)的非隨機(jī)性，以判定加密算法的整體安全強(qiáng)度。

為了使AES的密鑰比特與輪函數(shù)的迭代組合最佳，并檢測AES算法內(nèi)部結(jié)構(gòu)對密鑰比特的混淆和擴(kuò)散性程度，利用AES算法內(nèi)部結(jié)構(gòu)及密鑰編排特點(diǎn)，結(jié)合立方測試的基本思想，在FPGA平臺上對簡化輪AES-128算法的密鑰中比特進(jìn)行檢測與分析。

1　AES結(jié)構(gòu)簡介

AES分組長度為128 bit，密鑰長度分為128、192、256 bit三種，分別用AES-128、AES-192和AES-256表示，且分別需要迭代10輪、12輪和14輪。

1)字節(jié)替換。字節(jié)替換是AES算法中唯一的非線性變換，該變換按照一定的規(guī)則將狀態(tài)的每個(gè)字節(jié)a映射為某一特定的字節(jié)b=S(a)，其中S：GF(28)→GF(28)。

2)行移位。行移位將狀態(tài)矩陣的第j行循環(huán)左移j個(gè)字節(jié)，其中j=0，1，2，3。

4)輪密鑰加。輪密鑰加將輪密鑰與中間狀態(tài)進(jìn)行異或，AddroundKeyki(A)=A⊕Ki。

2　立方測試

立方測試是在立方攻擊的基礎(chǔ)上提出的一種新的密碼分析方法。

定義1[15]給定加密函數(shù)E(K,V)，K為密鑰，V為初始集合，若存在密鑰比特ki對E(K,V)的某位輸出累加結(jié)果不產(chǎn)生影響，則稱ki為密鑰中比特。

假設(shè)一個(gè)8bit的輸入加密函數(shù)為：

遍歷I，而v3、v4不變，對加密函數(shù)進(jìn)行累加，

則k3、k4為密鑰中比特。

3　AES-128算法的密鑰中比特檢測算法設(shè)計(jì)

根據(jù)AES算法的結(jié)構(gòu)，并結(jié)合密鑰中比特檢測的基本思想，AES-128算法的密鑰中比特檢測流程如圖1所示。

假定AES-128加密函數(shù)為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)，隨機(jī)生成40個(gè)主密鑰串{K1,K2,…,K40}。

圖1　AES-128密鑰中比特檢測流程Fig.1　Flow chart of key neutral-bit detection for AES-128

4)對步驟3)得到可能的密鑰中比特ki再次檢測，選取隨機(jī)密鑰K2重新執(zhí)行步驟2)、3)，若ki仍為可能的密鑰中比特，則選取下一個(gè)隨機(jī)密鑰K3繼續(xù)檢測，直到取完40個(gè)主密鑰，ki仍為可能的密鑰中比特，則ki為密鑰中比特，檢測失敗的概率為2-40。

4　硬件實(shí)現(xiàn)

實(shí)驗(yàn)采用FPGA芯片AlteraEP2C8Q208CN，設(shè)計(jì)了多個(gè)并行AES-128算法的實(shí)例，實(shí)現(xiàn)了AES-128密鑰中比特檢測，成倍減少攻擊時(shí)間。

4.1AES-128算法

AES-128算法在FPGA中采用移位寄存器、異或門、與門以及狀態(tài)機(jī)實(shí)現(xiàn)AES算法。為了讓代碼高效可靠地運(yùn)行，在AES算法整體布局時(shí)，對AES進(jìn)行拆開分模塊化處理，并將AES-128分成主加密模塊(aes_cipher_top)、S盒模塊(aes_sbox)、密鑰擴(kuò)展模塊(aes_key_expand)。AES-128算法實(shí)現(xiàn)所需的邏輯資源如表1所示。

表1　AES-128算法實(shí)現(xiàn)所需的邏輯資源

4.2密鑰中比特檢測

在AES-128密鑰中比特檢測中，除了AES-128加密模塊，還設(shè)計(jì)了另外3個(gè)模塊：第一個(gè)模塊為每個(gè)實(shí)例提供偽隨機(jī)密鑰K和含有立方變元V*的初始明文V(除立方變元外，其他為0)；第二個(gè)模塊收集檢測到的密鑰中比特；第三個(gè)模塊為傳輸單元。根據(jù)FPGA芯片的內(nèi)部資源的數(shù)量及AES-128算法消耗資源的大小，將128位密鑰分為2個(gè)部分，各占64bit，采用17～24個(gè)立方變元，并行運(yùn)行2個(gè)AES-128算法實(shí)例。攻擊的硬件結(jié)構(gòu)如圖2所示，控制模塊為每個(gè)AES-128加密實(shí)例提供密鑰K和含有立方變元V*的初始明文V。AES-128加密實(shí)例對V進(jìn)行加密，加密后V*+1，再次加密，直到遍歷V*。設(shè)立方變元的維度為n，計(jì)算2d次加密后，更新ki⊕K，更新后的密鑰再次給AES-128實(shí)例加密，直到128位密鑰更新完畢。若所有實(shí)例完成所需操作，組合模塊將從每個(gè)實(shí)例收集128位密鑰并發(fā)送給傳輸模塊。傳輸模塊負(fù)責(zé)頂層模塊和底層模塊之間的聯(lián)系。

實(shí)驗(yàn)采用FPGA并行運(yùn)行2個(gè)AES-128實(shí)例，每個(gè)實(shí)例檢測64位密鑰，共計(jì)128位。立方變元的維度越多，需要的時(shí)間越長。PC配置為IntelCoreI7-2600 3.4GHz,4GBRAM，在不同立方變元維度下，F(xiàn)PGA和PC耗時(shí)見表2、3。由表2、3可知，采用FPGA實(shí)現(xiàn)密鑰中比特檢測比個(gè)人電腦耗時(shí)少，且FPGA成本更低。

圖2　攻擊的硬件結(jié)構(gòu)Fig.2　Structure of attack hardware

表2　FPGA耗時(shí)

表3　PC耗時(shí)

5　攻擊結(jié)果及分析

1)固定立方變元取對角線，使其經(jīng)過變換后到達(dá)第一列，即第1字節(jié)，第1、6字節(jié)，第1、6、11字節(jié)，第1、6、11、16字節(jié)的前2位和最后2位，分別對3輪、4輪AES-128進(jìn)行測試，檢測輸出的第一位。在對3輪AES-128檢測中，固定立方變元的輸出結(jié)果均為0，而在對4輪AES-128檢測中，不存在密鑰中比特。

2)隨機(jī)立方變元維度取17～24，分別對簡化到6輪、5輪、4輪、3輪的AES-128進(jìn)行測試，檢測輸出的第一位。在對6輪、5輪，4輪的AES-128檢測中無法找到密鑰中比特，而在對3輪AES-128的檢測中，均能發(fā)現(xiàn)密鑰中比特，如表4所示。

從表4可看出，對于簡化到3輪的AES-128算法，在立方變元維度為17～24時(shí)，均能檢測到密鑰中比特，且均在40～80。AES-128在對密鑰的混淆擴(kuò)散的過程中，對40～80的密鑰擴(kuò)散混淆性較差，但4輪迭代后AES-128算法迅速修復(fù)了這些漏洞。全輪的AES-128算法具有穩(wěn)固的密鑰信息擴(kuò)散及混淆性。

表43輪AES-128密鑰中比特檢測結(jié)果

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　結(jié)束語

為了分析分組密碼算法AES-128的安全性，設(shè)計(jì)了一種基于FPGA的高效密碼分析平臺，并對AES-128進(jìn)行了密鑰中比特檢測。在立方變元取17～24維時(shí)，3輪簡化AES-128的輸出位容易捕獲密鑰中比特，但4輪以上AES-128的輸出位均無法捕獲密鑰中比特。對于高級加密標(biāo)準(zhǔn)AES-128，其初始輪數(shù)必須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

國家自然科學(xué)基金(61100185)；桂林電子科技大學(xué)研究生教育創(chuàng)新計(jì)劃(YJCXS201525)

韋永壯(1976-)，男(壯族)，廣西田陽縣人，教授，博士，研究方向?yàn)樾畔踩?。E-mail:walker_wyz@guet.edu.cn

TP309.7

A

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

引文格式：萬劉蟬，韋永壯.AES-128的密鑰中比特檢測及分析[J].桂林電子科技大學(xué)學(xué)報(bào)，2016,36(4):338-341.