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

先進安全密碼模組分析報告曾享煥、劉燦雄、單懷靈、歐崇明、王鯨洋中華電信研究所應用科技研究室1. AES介紹及現況1.1 源由 最近美國國家技術標準局(NIST)已經在招攬繼DES演算法之後，有關於先進的加密標準 (AES) 的候選者。他們要求加密區塊的明文長度為128位元，可接受的密鑰長度為128位元、192位元和256位元(含以上)。判定的標準為安全性、效率與適應性三方面。NIST希望在這個世紀結束之前，能夠預備好一個新的加密標準。Advanced Encryption Standard (AES)-二十一世紀的一種加密演算法。在1998年8月20日第一次AES候選者的研討會中，NIST正式宣布十五個加密標準：CAST-256, CRYPTON, DEAL, DFC, E2, FROG, Hasty Pudding Cipher(HPC) , LOKI97, MARS, Magenta, RC6, RIJNDAEL, SAFER+, SERPENT, TWOFISH。 正式官方的評論：如有任何公開的意見可mail至 AESFirstR ，經採納後於 99/4/15 公布結果，非正式（網路線上）的評論： 進入 AES 站內的公開討論版上刊載意見，99/3/22-23 NIST在義大利羅馬的奎爾諾飯店召開第二次AES候選者的研討會，根據第一回合的評論及結果選出最後的五個候選者。網站內容包括：(1) AES候選者演算法的介紹；(2) 網路上的資料包括演算法的提出者及作者、摘要、內容及規格、提案等相關文件；(3) 可下載的測試表（包括由不同的金鑰長度做加(解)密等各種的中間值及測試值）；(4) 註冊名稱；文件；作者的簽名、提出者的版權登記、專利書； 美國聯邦政府的註冊及評論、提案的正式評論、公開的分析及勘誤表。1.2 介紹 AES的需求：經由公開的程序對外徵求； 是對稱性的金鑰加密法； 秘密金鑰的長度是可變的； 可以同時由硬體及軟體來實作； 沒有專利的限制或必須符合ANSI的專利政策，可以自由的使用； AES的評選標準：安全性：必須通過現有的密碼攻擊法；效率：執行必須有效率；記憶體的需求；是否適合硬體及軟體來實作；演算法必須簡單易懂；可變性：金鑰長度必須是可變更的； 專利的問題；網站 /encryption/aes/aes_home.htm 中有談到 DEAL, FROG, LOKI97, MARS, Magenta 等五種具有攻擊法（訊息更新於98/11/23）。目前對各AES演算法的攻擊有下列五種備註1：名稱攻擊法類型參考DEALS. Lucks, On the Security of the 128-bit Block Cipher DEALFROG差分和線性攻擊法(Differential and linear attacks)D. Wagner, N. Ferguson, and B. Schneier, Cryptanalysis of Frog,LOKI97K=56 bits, C=56 bitsV. Rijmen, L.R. Knudsen, Weaknesses in LOKI97 K:56/./., C:56/./.備註2Magenta選擇明文攻擊法(Chosen plaintext attack)E. Biham, A. Biryukov, N. Ferguson, L. Knudsen, B. Schneier, A. Shamir, Cryptanalysis of MAGENTAMARS有weak keysM-J. Saarinen, Equivalent keys in MARS備註：1 參考網站 http:/www.ii.uib.no/larsr/aes.html.The Block Cipher Lounge AES：The AES Proposals（資料更新於1998/9/24）。2 K:a/b/c：表示最佳的已知明文攻擊法需要2a個明文/密文對，有2b個加密的工作量，並且需要。Has a workload of 2b encryptions and requires 2c words of memory.3 C:a/b/c：denotes that the best chosen plaintext attack requires 2a plaintext/ciphertexts,Has a workload of 2b encryptions and requires 2c words of memory.4 A . ：表示資料的來源不是很重要或是我們不知道的。5 (r)：表示攻擊法運算的回合數，如果是空白，則r = Rounds。6 SA：表示在文章內有描述攻擊法。7 ?：表示沒有已知的攻擊法。1.3 演算法結構表 由於AES是希望能夠在未來的二十年內能夠完全取代DES成為新的對稱式形加密演算法，因此對於明文大小、金鑰(key)長度、演算法的運算回合數、以及所使用的演算法技巧都被廣泛的加以討論，並針對不同的狀況提出實做的數據加以比較，或針對不同的模組提出有效的攻擊，期望能夠真正找到一個兼顧安全與效能的演算法。我們在下表提供15個入圍的AES候選演算法的相關資料，包括運算回合數、區塊資料大小、金鑰長度以及在每一個演算法所用到的特殊技巧。AES candidates的結構表AlgoRithmSerial numberData size (bits)Block(Sub data) size (bits)Key size (bits)Subkey size (bits)Number of subkeysMemory of subkeys (bytes)On-the-Fly keySpeed of different key lengths.Nonlinearly FunctionFeistel NetworkWhiteningNumber of RoundsMin. Secure RoundsRIJNDAEL12128,192,2568128,192,25632Nb(Nr+1)160(Nb=4,Nr=4)Two-wayIncreasingS-BoxNoYesTable28RC611128320255 bytes3244176Not availableConstantDR,IRYesYes2020TWOFISH1512832128,192,25632(words)40160Two-wayIncreasingS-BoxYesYes1612MARS101283212812483240160Not availableConstantDR,IR,S-BoxYesYes8,8,8,810SERPENT141283225612833528ForwardConstantDR, S-BoxNoNo3217E2512864128,192,2561616256Not availableConstantS-BoxYesYes1210CAST-2561128(24 blocks, 64bits/block)32128256Rotate key:5Mask key:321255.5ForwardConstantDR,S-BoxYesNo32 (Opts:48)10SAFER+131288128,192,2562 bytes2r+1272(r=8)Two-wayIncreasingFunction TableNoYes128:8192:12256:167DFC41286402561288128ForwardConstantS-BoxYesNoKey:4Crypt 89CRYPTON2128324025632452208Two-wayConstantS-BoxNoYes1211DEAL3128322128,192,25664(DES key)128/192:6256:848ForwardIncreasingS-BoxYesYes128/192:6256:86HPC7隨意35,3564, 65128,129512,513隨意256(words)128010240Not availableConstantRotateYesNo88MAGENTA9128Increasing10FROG6128(641024)128(641024)40100028882304Not availableConstantS-BoxNoNo88LOKI97812864128,192,2566448384ForwardDecreasingS-BoxYesNo16361 Data size：表示此一Block cipher可以一次看待資料的的長度，也就是加密資料一次的單位長度，以位元(bits)為單位。2 Block size：表示在內部加密時，以多大的資料段來處理，可以視其為以此大小為導向的cipher，如：Block size=8: Byte-oriented、Block size=32:Word-oriented、Block size=64: Double word-oriented。3 Key size：為秘密鑰匙(Secret key)的長度，以位元(bits)為單位。對單一加密演算法而言，長度越長表示越安全，但相對地也要付出更多的加解密時間。4 Subkey：由秘密鑰匙所算出，在每一個round中真正參予與資料運算的子密鑰，除於後標出長度單位者，其餘皆以位元(bits) 為單位。5 Number of subkeys：全部所需的子密鑰的數量。6 Memory of subkeys (bytes)：所有子密鑰所佔用的記憶體，當子密鑰越多、越長就越佔記憶體，若應用在chip、smart card時，會提高成本與設計製造的難度。7 On-the-Fly key：所有的子密鑰可以到了加解密時才造出，及每一個Round加解密所需的子密鑰都是到了當時才即時產生出來，如此可以節省已用過/尚未用的子密鑰；又可以分為單向產生(Forward)或雙向/隨意產生(Two-way)。8 Speed of different key lengths：不同鑰匙長度時，加密所需的時間。大部分都為定值，但也有些會隨著鑰匙長度變化而有正反比的關係。(這兩項資料參考自/AES-performance.html)9 Number of Rounds：AES candidates 在其演算法中所建議的Rounds數。10 DR：資料相依於旋轉 ( Data Dependent Rotation)；IR：資料和旋轉無關 ( Data Independent Rotation )。11 Whitening：這個技巧是在第一個round函數前，先將明文與key做運算（exclusive-OR 或 byte addition），在最後一個 round 函數之後，再將所得結果與 key 做運算（exclusive-OR 或 byte addition）成為密文。Whitening 隱藏第一個 round 的輸入與與最後一個 round 輸出之間的關係，這可以增加攻擊的困難度，因為通常攻擊法都是針對第一個 round的輸入至最後一個 round 的輸出作分析，而第一個 round的輸入與最後一個 round 的輸出的 實際值已經被隱藏。這個方法對於 chosen plaintext attack 亦非常有效。1.4 相關網站 Www.ii.uib.no/larsr/aes.htmlhttp:/www.ii.uib.no/larsr/aes.htmlAES_15_Algorithm D.tw/project/AES.tw/project/AESAdonis.ee.quensu.ca:8000/casthttp:/adonis.ee.queensu.ca:8000/cast/AES/aesCast128Paperrfc2144.txt/in-notes/rfc/files/rfc2144.txtCryptographic Algorithmshttp:/www.cs.hut.fi/ssh/crypto/algorithms.html#asymmetricA Cryptographic Compendiumhttp:/fn2.freenet.edmonton.ab.ca/jsavard/jscrypt.html AES Candidate Algorithms Architecture.tw/project/AES/AES_Architecture.htmlFTP Directoryftp:/ftp.funet.fi/pub/crypt/cryptography/symmetric/AES_Cipher_Speedhttp:/home.cyber.ee/helger/aes/Test_EBC_ival.txt/ecb_ival.txtTwofishTwofish.html/twofish.html1.5 時程總表AES時程總表 ( AES Timeline Summary )April 15, 1999Round 1 Comment period closes.第一評論回合結束May 15, 1999Explanation/justification of proposed weaks and updated spec. are due.說明題案的補充及更新的規格書Summer 1999Announcement of Finalists.公佈決賽選手Announcement of Finalists + 1 monthUpdated code for Round 2 is due.更新第二回合題案的程式碼January 15, 2000Papers due for AES3.提出AES3的論文Week of April 10, 2000AES3 (New York City)在紐約的AES3選拔會May 15, 2000Round 2 Comment period closes.第二評論回合結束August 2000Announcement of AES Winner(s)公佈AES最後候選者1.6 現況 AES2會議結束後，NIST發出問卷調查，由參加者選出五種演算法。結果如下表： 2.五種演算法的介紹以下是最後五個候選者的演算法：2.1 Rijndael 演算法 Rijndael是一種對稱式的區塊加密法，它提供加密的明文區塊為和金匙長度範圍都為128、192、256位元。Rijndael的設計原理不同於一般的對稱式加密演算法，它並未採用Feistel結構來做為演算法的主要架構，而是使用三個函數運算來做加密的動作，其安全性是沒有問題的，能夠抵擋差分攻擊法與線性攻擊法。而在實做速度方面來說，如果以32-bits的處理器使用C語言來撰寫程式的話，其加密速度大約為27 Mbit/s。2.2 RC6 演算法 RC6演算法是由RC5演變出來的，它是被設計成為了符合 Advanced Encryption Standard (AES) 的要求。RC6也像RC5一樣大量使用資料相依旋轉。而RC6新的特色是輸入的明文由原先兩個區塊擴展為四個亦即有128bits 的輸入，另外在運算方面則是使用了整數乘法，而整數乘法的使用則在每一個運算回合中增加了擴散(diffusion)的行為，並且使得即使很少的回合數也有很高的安全性。RC6是一個安全、架構完整而且簡單的區塊加密法。它提供了好的測試結果和參數方面相當大的彈性，而且由於它的簡單易懂使得我們能夠很快做一個完整的分析報告來增加我們對它的安全性做一個估計的準確性。因此RC6可以說是近幾年來相當優秀的一種加密法。 RC6和RC5在加解密方面是不一樣的，RC6把明文分為四個區塊A、B、 C、D，它們剛開始分別包含明文的初使值，經過加密運算後則為四個密文的輸出值。一般而言，我們把明文或密文第一個位元組放在區塊A的第一個位元組，而把明文或密文最後一個位元組放在區塊D的最後一個位元組。 另外我們也使用(A, B, C, D) = ( B, C, D, A)來做為區塊之間的平行轉換，其加密演算法如下： B = B + S0 ; D = D + S1 ; for i = 1 to r do t = B*( 2B + 1 ) ) lgw u = D*( 2D + 1 ) ) lgw A = ( ( A t ) u ) + S2*i ; C = ( ( C u ) t ) + S2*i+1 ; (A, B, C, D) = ( B, C, D, A) A = A + S2r + 2 ; C = C + S2r + 3 ;最後演算法則輸出A、B、C、D將其合併為密文。而解密演算法則可由加密法反向推演出來。2.3 Twofish 演算法 Twofish是一種可改變金匙長度(最大可到256 bits)的區塊加密法。這種加密法是一個16回合的Feistel network，每個回合中包含了一個bijective函數F，它是由四個與密鑰有關的88-bit之 S-box、一個44 的MDS( maximum distance separable)矩陣、一個PHT( pseudo-Hadamard transform)所組成，另外再加上位元旋轉和一個無缺點的金鑰產生過程。假如我們將Twofish完全充分運用於加密，在實作平台為Pentium Pro時，每一個位元組(byte)加密須要17.8 clock cycles，而在8-bit的智慧卡(smart card)上執行則須1820 clock cycles。事實上針對Twofish已經有廣泛的密碼分析，針對5回合的Twofish差分攻擊法須要222.5明文對而且複雜度須要到251，因此對16回合的Twofish來說是不受差分攻擊法的威脅。2.4 MARS 演算法 MARS 是一種對稱式的區塊加密法，它提供加密的明文區塊為 128 位元，金匙長度的範圍：128 1248位元。MARS 的設計原理主要是利用到現今電腦提供的一些高效率的運算，在現有的加密法中成為更先進的安全 / 效能方法。MARS 提供比3-DES 更佳的安全性，並且速度顯著地比 DES 更快。如用 C 語言的程式實作速率在 200 MHz Pentium-Pro 上約為 65 Mbit/sec；在 200 MHz PowerPC 上則為 85 Mbit/sec。MARS 在軟硬體上的實作皆相當簡潔且容易適用在智慧卡及其他有限資源的環境。由於高度的安全、速度及適應性，使得 MARS 成為下一世紀資訊網路加密需求的聰明抉擇。2.5 Serpent 演算法 Serpent是一種為了符合AES標準而設計的區塊加密法，它雖然是一種很傳統的設計，但是在運算速度上仍然非常有效率。它使用了一種類似DES所使用的S-boxes在一個新的結構上，並且有非常迅速的雪崩效應(avalanche)和有效率的位元運算，同時也使得我們在安全性的分析方面能夠很簡單提出論證來說明它能夠有效的抵擋目前已知的攻擊法。這一個演算法所輸入的明文區塊為128-bits，密鑰長度為256-bits。雖然它在Intel Pentium/MMX的作業平臺上的速度表現是和DES一樣快，但是我們相信它在安全性的表現上會比triple-DES更好。3.結論 目前從網站及相關論文可蒐集到AES十五個加密演算法有關的資料：包含演算法的原理、步驟、分析、特性、程式碼、攻擊法、測試表等，可下載及測試並將資料儲存於設定之目錄下。俟美國國家技術標準局 (NIST) 於 2000/8/15宣布結果後，即可立即將獲選之加密演算法提供出來並建立完整之資料。緊接著我們提供一些關於最後五個AES候選者的一些相關資料以做為參考。 六種演算法的比較 明 文 (bits) 密 鑰 (bits) 替 換 盒 個 數 運 算 回 合 數 DES 64 64 8 16 MARS 128 1281248 1 32 RC6 128 02048 none 20 Rijndael 128 128256 1 10,12,14 Serpent 128 128 8 32 Twofish 128 128256 1 16 加 密 速 度 之 比 較 演算法 加密128 bits明文所須之clock cycle DES 5600 MARS 376 RC6-32/16/20 243 Rijndael 284 Serpent 992 Twofish 258 數據(除DES外)參考自NIST所公布之報告中 攻 擊 法 之 比 較 差 分 攻 擊 法 線 性 攻 擊 法 DES(16 round) 258 247 MARS 2190 2128 RC6(20 round) 2264 2182 Rijndael 2300 2150 Serpent 2120 2240 Twofish 2131 2120 由以上所提供的數據我們可以得知:最後五個AES候選者無論在效率或安全性來講都能滿足目前有關資訊安全方面的需求。因此我們可以很確定只要最後AES選出來必定可以滿足未來二十年內有關對稱式加密方面的需求。4.其他特殊技巧 接下我們將介紹一些在對稱式加密演算法常用到的特殊技巧，我們將其簡略的介紹一下，以便做為參考。 4.1 Feistel Networks Feistel Network的架構於1973年在Horst Feistel所設計的Lucifer 加解密演算法中提出，至今已廣泛的運用在大多數加解密演算法的設計原則之中，包含DES、FEAL、GOST、LOKI、CAST-128等知名的加解密演算法，都是採用這個架構。在Feistel network最基本的架構中(見圖一)，每一個輸入的區塊(長度n)被分為左右兩個區塊(長度n/2)，在每一個round中，右邊的區塊為下一個round的左區塊，而右邊的區塊經由一個由金鑰值所控制且非線性的函數f運算後，其輸出與左區塊做exclusive-OR所得到的值為下一個round的右邊區塊。也就是說 Li+1=Ri Ri+1= Li f(Ri Ki )其中函數f是任一個與key相關的對應，通常為非線性的，其定義如下: f : 0,1n/2 0,1N 0,1n/2n為區塊的長度，N為所輸入key的長度。 Ri Lif one round Ki Ri+1 Li+1 One cycle f Ki+1 one round Ri+2 Li+2 圖一. Feistel Network 的基本架構 Feistel network的優點是不論函數f是什麼形式，每一個round都是可逆的(reversible)。這是因為以下式子恆成立 : Li f(Ri Ki ) f(Ri Ki )= Li區塊(長度n)經過一個round所得到的兩個區塊(長度n/2)左右位置對調後，再重新做為round的輸入即可得到和原來相同的區塊。這樣的優點使得採用Feistel network架構的加解密演算法有著加密與解密可使用同一套演算法的好處，這種加解密相同性(“encryption/decryption similarity”)的優點，使得一個加解密演算法在硬體的實作上可以加密與解密使用同一個元件，此便利性對於演算法的推廣是很有幫助的。4.2 S-boxes 在大部分的區塊加密演算法中常常利用S-boxes來執行非線性替換的運算，S-boxes它的輸入和輸出大小是不同的，並且能夠用隨機的方法或是演算法生成。S-boxes第一次被使用是在Lucifer演算法中，接著DES和其他大部份的加密演算法也大量的使用。它實際上是一種置換(substitution)，故又稱為substitution box或表格(table)。一個mn位元的S-box就是將m位元的輸入對應到相對應的n位元輸出，例如DES使用八個64位元的S-box。4.3 MDS 矩陣 MDS(maximum distance separable)是一個作用在體(field)上的線性映射，從一個包含a個元素的體映射到有b個元素的體，會產生一個含有a+b個元素的合成向量，而這個向量有一個性質為:任何非零的向量它的非零元素個數至少有b+1個。換句話說，假如有兩組不同的向量是經由MDS運算後所產生出來的，則這兩組向量的元素至少有b+1個是不同的，我們稱b+1為兩個向量的最小差值(minimum distance)，並且也能夠證明不會有其他種的線性映射能夠使得兩個向量的最小差值大於b+1。一般我們會將MDS映射表示成含有ab個元素的矩陣型態。4.4 Pseudo-Hadamard Transforms (PHT) PHT是一個能夠很快速的在軟體上執行的簡單混合運算。假如我們給兩個輸入值a、b，則32-bit的PHT是被定義為: a a+b mod 232 PHT在加解密演算法中用來擔任diffusion的工作，因為PHT的轉換實際上是一個矩陣相乘，所以每一個輸入都會影響到每一個輸出。SAFER+採用3層的 PHT來達到所謂的Fast diffusion。4.5 Whitening(隱藏) 這個計巧是在第一個round函數之前，先將明文與key做運算(exclusive-OR或byte addition)成為密文。Whitening隱藏第一個round的輸入與最後一個round輸出之間的關係，這可以增加攻擊的困難度，因為通常攻