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.