先进安全密码模组分析报告

156987785542055先進安全密碼模組分析報告曾享煥、劉燦雄、單懷靈、歐崇明、王鯨洋中華電信研究所‧應用科技研究室1.AES介紹及現況1.1源由最近美國國家技術標準局(NIST)已經在招攬繼DES演算法之後，有關於先進的加密標準(AES)的候選者。他們要求加密區塊的明文長度為128位元，可接受的密鑰長度為128位元、192位元和256位元(含以上)。判定的標準為安全性、效率與適應性三方面。NIST希望在這個世紀結束之前，能夠預備好一個新的加密標準。AdvancedEncryptionStandard(AES)-二十一世紀的一種加密演算法。在1998年8月20日第一次AES候選者的研討會中，NIST正式宣布十五個加密標準：CAST-256,CRYPTON,DEAL,DFC,E2,FROG,HastyPuddingCipher(HPC),LOKI97,MARS,Magenta,RC6,RIJNDAEL,SAFER+,SERPENT,TWOFISH。正式官方的評論：如有任何公開的意見可mail至[e-mail]，經採納後於99/4/15公布結果，非正式（網路線上）的評論：進入AES站內的公開討論版上刊載意見，99/3/22-23NIST在義大利羅馬的奎爾諾飯店召開第二次AES候選者的研討會，根據第一回合的評論及結果選出最後的五個候選者。網站內容包括：(1)AES候選者演算法的介紹；(2)網路上的資料包括演算法的提出者及作者、摘要、內容及規格、提案等相關文件；(3)可下載的測試表（包括由不同的金鑰長度做加(解)密等各種的中間值及測試值）；(4)註冊名稱；文件；作者的簽名、提出者的版權登記、專利書；美國聯邦政府的註冊及評論、提案的正式評論、公開的分析及勘誤表。1.2介紹AES的需求：經由公開的程序對外徵求；是對稱性的金鑰加密法；秘密金鑰的長度是可變的；可以同時由硬體及軟體來實作；沒有專利的限制或必須符合ANSI的專利政策，可以自由的使用；AES的評選標準：安全性：必須通過現有的密碼攻擊法；效率：執行必須有效率；記憶體的需求；是否適合硬體及軟體來實作；演算法必須簡單易懂；156987785542056可變性：金鑰長度必須是可變更的；專利的問題；網站中有談到DEAL,FROG,LOKI97,MARS,Magenta等五種具有攻擊法（訊息更新於98/11/23）。目前對各AES演算法的攻擊有下列五種〔備註1〕：名稱攻擊法類型參考DEALS.Lucks,``OntheSecurityofthe128-bitBlockCipherDEAL''FROG差分和線性攻擊法(Differentialandlinearattacks)D.Wagner,N.Ferguson,andB.Schneier,CryptanalysisofFrog,LOKI97K=56bits,C=56bitsV.Rijmen,L.R.Knudsen,``WeaknessesinLOKI97''K:56/./.,C:56/./.〔備註2〕Magenta選擇明文攻擊法(Chosenplaintextattack)E.Biham,A.Biryukov,N.Ferguson,L.Knudsen,B.Schneier,A.Shamir,CryptanalysisofMAGENTAMARS有weakkeysM-J.Saarinen,EquivalentkeysinMARS備註：[1]參考網站~larsr/aes.html.TheBlockCipherLounge–AES：TheAESProposals（資料更新於1998/9/24）。[2]K:a/b/c：表示最佳的已知明文攻擊法需要2a個明文/密文對，有2b個加密的工作量，並且需要。Hasaworkloadof2bencryptionsandrequires2cwordsofmemory.[3]C:a/b/c：denotesthatthebestchosenplaintextattackrequires2aplaintext/ciphertexts,Hasaworkloadof2bencryptionsandrequires2cwordsofmemory.[4]A`.'：表示資料的來源不是很重要或是我們不知道的。[5](r)：表示攻擊法運算的回合數，如果是空白，則r=Rounds。[6][SA]：表示在文章內有描述攻擊法。[7]?：表示沒有已知的攻擊法。1569877855420571.3演算法結構表由於AES是希望能夠在未來的二十年內能夠完全取代DES成為新的對稱式形加密演算法，因此對於明文大小、金鑰(key)長度、演算法的運算回合數、以及所使用的演算法技巧都被廣泛的加以討論，並針對不同的狀況提出實做的數據加以比較，或針對不同的模組提出有效的攻擊，期望能夠真正找到一個兼顧安全與效能的演算法。我們在下表提供15個入圍的AES候選演算法的相關資料，包括運算回合數、區塊資料大小、金鑰長度以及在每一個演算法所用到的特殊技巧。AEScandidates的結構表AlgoRithmSerialnumberDatasize(bits)Block(Subdata)size(bits)Keysize(bits)Subkeysize(bits)NumberofsubkeysMemoryofsubkeys(bytes)On-the-FlykeySpeedofdifferentkeylengths.NonlinearlyFunctionFeistelNetworkWhiteningNumberofRoundsMin.SecureRoundsRIJNDAEL12128,192,2568128,192,25632Nb(Nr+1)160(Nb=4,Nr=4)Two-wayIncreasingS-BoxNoYes[Table2]8RC611128320~255bytes3244176NotavailableConstantDR,IRYesYes2020TWOFISH1512832128,192,25632(words)40160Two-wayIncreasingS-BoxYesYes1612MARS1012832128~12483240160NotavailableConstantDR,IR,S-BoxYesYes8,8,8,810SERPENT141283225612833528ForwardConstantDR,S-BoxNoNo3217E2512864128,192,2561616256NotavailableConstantS-BoxYesYes1210CAST-2561128(2~4blocks,64bits/block)32128~256Rotatekey:5Maskkey:321255.5ForwardConstantDR,S-BoxYesNo32(Opts:48)10SAFER+131288128,192,2562bytes2r+1272(r=8)Two-wayIncreasingFunctionTableNoYes128:8192:12256:167DFC4128640~2561288128ForwardConstantS-BoxYesNoKey:4Crypt89CRYPTON21283240~25632452208Two-wayConstantS-BoxNoYes1211DEAL3128322128,192,25664(DESkey)128/192:6256:848ForwardIncreasingS-BoxYesYes128/192:6256:86HPC7隨意35,35~64,65~128,129~512,513隨意256(words)128010240NotavailableConstantRotateYesNo88MAGENTA9128Increasing10FROG6128(64~1024)128(64~1024)40~100028882304NotavailableConstantS-BoxNoNo88LOKI97812864128,192,2566448384ForwardDecreasingS-BoxYesNo1636156987785542058[1]Datasize：表示此一Blockcipher可以一次看待資料的的長度，也就是加密資料一次的單位長度，以位元(bits)為單位。[2]Blocksize：表示在內部加密時，以多大的資料段來處理，可以視其為以此大小為導向的cipher，如：Blocksize=8:Byte-oriented、Blocksize=32:Word-oriented、Blocksize=64:Doubleword-oriented。[3]Keysize：為秘密鑰匙(Secretkey)的長度，以位元(bits)為單位。對單一加密演算法而言，長度越長表示越安全，但相對地也要付出更多的加解密時間。[4]Subkey：由秘密鑰匙所算出，在每一個round中真正參予與資料運算的子密鑰，除於後標出長度單位者，其餘皆以位元(bits)為單位。[5]Numberofsubkeys：全部所需的子密鑰的數量。[6]Memoryofsubkeys(bytes)：所有子密鑰所佔用的記憶體，當子密鑰越多、越長就越佔記憶體，若應用在chip、smartcard時，會提高成本與設計製造的難度。[7]On-the-Flykey：所有的子密鑰可以到了加解密時才造出，及每一個Round加解密所需的子密鑰都是到了當時才即時產生出來，如此可以節省已用過/尚未用的子密鑰；又可以分為單向產生(Forward)或雙向/隨意產生(Two-way)。[8]Speedofdifferentkeylengths：不同鑰匙長度時，加密所需的時間。大部分都為定值，但也有些會隨著鑰匙長度變化而有正反比的關係。(這兩項資料參考自)[9]NumberofRounds：AEScandidates在其演算法中所建議的Rounds數。[10]DR：資料相依於旋轉(DataDependentRotation)；IR：資料和旋轉無關(DataIndependentRotation)。[11]Whitening：這個技巧是在第一個round函數前，先將明文與key做運算（exclusive-OR或byteaddition），在最後一個round函數之後，再將所得結果與key做運算（exclusive-OR或byteaddition）成為密文。Whitening隱藏第一個round的輸入與與最後一個round輸出之間的關係，這可以增加攻擊的困難度，因為通常攻擊法都是針對第一個round的輸入至最後一個round的輸出作分析，而第一個round的輸入與最後一個round的輸出的實際值已經被隱藏。這個方法對於chosenplaintextattack亦非常有效。1.4相關網站~larsr/aes.html~larsr/aes.htmlAES_15_AlgorithmDslab.cis.nctu.edu.tw/project/AES:8000/cast://://info.internet.isi.edu/in-notes/rfc/fil