無線網絡機制中分組密碼標準安全性分析[權威資料]

無線網絡機制中分組密碼標準安全性分析 本文檔格式為 WORD,感謝你的閱讀。 摘要： 分組密碼算法憑借其在各種軟件和硬件平臺上的高效率特點，廣泛地應用在無線通信系統的安全認證及保密機制中。本文對幾種著名分組密碼標準（美國高級加密標準 AES 算法、韓國分組加密標準 SEED 算法、歐洲分組加密標準 Camellia 算法和中國商用密碼標準 SMS4 算法）的安全性進行了分析，通過研究分組密碼算法中的非線性結構 S 盒的密碼學性質，對比分組密碼算法抵抗插 入攻擊、差分密碼分析攻擊和線性密碼分析攻擊的能力，揭示各種算法的安全性。 Abstract： With the characteristics of high efficiency in a variety of software and hardware platforms， block ciphers are widely used in wireless communication systems security authentication and privacy. A detailed analysis of the cryptographic properties of several well-known block ciphers， such as AES， SEED， Camellia and SMS4， is made in this paper. S-box， which brings nonlinearity to block cipher， is well investigated and the attack capability resisting to insertion attacks， differential cryptanalysis and linear cryptanalysis is also provided. The security of AES， SEED， Camellia and SMS4 is revealed as compared with each other. 關鍵詞： 分組密碼； S 盒；布爾函數；差分密碼分析攻擊；線性密碼分析攻擊 Key words： block cipher； S-boxes； boolean function； differential cryptanalysis attack； linear cryptanalysis attack TP393 A 1006-4311（ 2013） 09-0196-04 0 引言 由于無線網絡能夠使用戶真正實現隨時、隨地、隨意地接入網絡，無線網絡的使用群體在不斷地擴大，用戶對無線網絡的要求也日益提高，例如，終端之間的安全認證、信息的安全傳輸等。無線網絡雖然具有易于實施、組網靈活、快捷高效的特點，但其所采用的無線技術缺乏固定的物理保護，容 易遭受多種網絡安全攻擊，且難以檢測。因此，無線網絡迅速發(fā)展的同時，對網絡的安全性也提出了更高的要求。分組密碼算法以其在各種軟件和硬件平臺上的高效率這一顯著特點成為無線網絡安全認證及保密機制的主要產品。 隨著美國數據加密標準 DES（ Data Encryption Standard）被攻破， 1997 年初，美國已經開始計劃建立高級加密標準 AES（ Advanced Encryption Standard），并在世界范圍內公開征集 AES 算法，經過歷時三年的遴選和評估，比利時密碼學家 Joan Daemen 和 Vincent Rijmen 提交的Rijndael 算法 1成為美國的高級加密標準。繼 AES 之后，韓國信息安全協會于 1998 年確定了 128 比特分組加密算法 SEED算法 2，并服務于很多安全系統。 2000 年 1 月 1 日，歐洲啟動了歐洲簽名、完整性和加密新方案計劃 NESSIE3，三年后確定了 Camellia 算法 4為其分組密碼標準算法之一。 2006年 1 月 6 日，中國國家密碼管理局發(fā)布第 7 號公告，將用于我國無線局域網產品的加密算法確定為 SMS4 算法 5，這是國內官方公布的第一個商用密碼算法。隨著各種分組加密算法 在實際生活中的不斷應用 6-9，算法的安全性值得我們深入探討與研究。 對于大多數分組密碼算法而言，安全性取決于一個重要組成部分，即， S 盒。這個非線性結構任何不好的性質都會影響到整個密碼算法的安全性。本文深入分析美國高級加密標準 AES 算法、韓國分組加密標準 SEED 算法、歐洲分組加密標準 Camellia 算法和中國商用密碼新標準 SMS4 算法 S 盒的密碼學性質，研究其平衡性、非線性、代數表達式、 Walsh 譜等性質，同時分析比較了各種加密標準在抵抗插入攻擊、差分密碼分析攻擊和線性密碼分析攻擊的能力。通過比較 ，在理論上揭示了各種分組密碼算法所具有的安全特性。 本文結構如下：第 1 節(jié)對各種分組密碼算法進行了簡單的介紹；第 2 節(jié)給出了各種分組密碼算法 S 盒布爾函數密碼學性質的比較；第 3 節(jié)分析對比了各種分組密碼算法抵抗各種攻擊的能力；最后第 4 節(jié)對全文進行總結。 1 分組密碼算法簡介 1.1 AES 算法 美國高級加密標準 AES 算法分組長度和密鑰長度均可取 128 比特、 192 比特和 256 比特三種不同長度，加密算法與密鑰擴展算法都采用非線性的迭代結構，不同的分組長度與密鑰長度的迭代次數是不同的，如表 1 所示。每一輪的迭代結構包含四個基本操作：非線性的字節(jié)替換，行移位，列混合和輪密鑰加。 1.2 SEED 算法 韓國分組加密標準 SEED 算法的分組明文長度為 128 比特，密鑰長度為 128 比特，生成 128 比特密文。加密算法與密鑰擴展算法都采用 16輪非線性迭代結構。解密過程與加密過程的結構相似，只是輪密鑰的使用順序相反。 1.3 Camellia 算法 歐洲分組加密標準 Camellia 算法的分組明文長度為 128 比特，密鑰長度可取 128 比特、 192 比特和 256 比特三種不同長度，生成 128 比特密文。 加密算法與密鑰擴展算法都采用 18輪（ 128 比特長度的密鑰）或者 24輪（ 192 或 256 比特長度的密碼）的 Feistel 結構。解密過程與加密過程的結構相似，只是輪密鑰的使用順序相反。 1.4 SMS4 算法 中國商用密碼新標準 SMS4 算法的分組長度為128 比特，密鑰長度為 128 比特，生成 128 比特密文。加密算法與密鑰擴展算法都采用 32輪非線性迭代結構。解密過程與加密過程的結構相似，只是輪密鑰的使用順序相反。 2 分組密碼算法安全性分析 S 盒是大多數分組密碼算法中唯一的非線性結構，其密碼 特性直接決定了密碼算法的好壞。本節(jié)對美國高級加密標準 AES 算法、韓國分組加密標準 SEED 算法、歐洲分組加密標準 Camellia 算法和中國商用密碼標準 SMS4 算法的 S 盒密碼學性質進行了深入分析，研究其平衡性、非線性、代數表達式、 Walsh 譜等性質，通過比較，揭示各種分組密碼算法的優(yōu)缺點。 2.1 S 盒布爾函數表達式 S 盒的布爾函數表達式給出了 S 盒的輸入比特與輸出比特之間的代數邏輯關系，這種表達式的次數和所含項數表明了 S 盒的代數復雜度。通常， S 盒的設計準則 10要求布爾函數表達式的次數盡可能高，項數盡可能多。 以我國無線局域網產品 SMS4 算法為例，我們求得 SMS4算法 S 盒第一個布爾函數為f0=x2+x1x2+x1x3+x2x3x4x5x6x7x8 ，全部的非零下表值列于表 2 中，其它布爾函數可類似計算。 由表 2 可知 f0中的項數為 134，最高次數為最大可能值 7。其它輸出比特的布爾函數 f1， ， f7的項數分別為130， 128， 123， 126， 124， 139， 124，代數次數均為 7。不難發(fā)現 SMS4 算法 S 盒每個布爾函數多項式表達式的次數均為最大可能值 7，項數均不少于 123 項，這在某種意義 上保證了SMS4 算法 S 盒的代數復雜度和安全強度。 通過計算，我們得到四種標準中的 8 個 S 盒（其中，AES 算法含有 1 個、 SEED 算法含有 2 個、 Camellia 算法含有4 個、 SMS4 算法含有 1 個）的布爾函數表達式的次數和項數，如表 3 所示。 通過比較，四種算法的 S 盒布爾函數表達式的次數都達到了最大上限 7。對于它們的 S 盒布爾函數表達式的最小項數而言， Camellia 算法的為 126， SMS4 算法的為 123，比SEED 算法的 111 和 AES 算法的 110 多，并且 SEED 算法的略大于 AES 算法的。從這個方面 而言， SEED 算法、 Camellia 算法和 SMS4 算法 S 盒布爾函數表達式復雜度略優(yōu)于 AES 算法。 2.2 S 盒布爾函數代數性質 一個好的 S 盒應該具有好的代數性質，良好的性質能保證算法能夠抵抗各種密碼分析的攻擊。對于大多數算法而言， S 盒是唯一的非線性結構，并在整個算法中多次使用，因此 S 盒任何不好的性質都將影響到整個算法的安全性。本節(jié)討論 SMS4 算法 S 盒的平衡性和非線性度等性質。 定義 110 對 n 元布爾函數 f： GF（ 2） nGF （ 2），若其真值表中 “1” 的個數等于 “0” 的個數，即均為 2n-1，則稱 f 滿足平衡性。 定義 210 設 f（ x）是一個 n 元布爾函數，記 Lnx為所有 n 元線性函數（包括仿射函數）之集。 f（ x）的非線性度定義 f（ x）與所有線性函數之最短距離 N=d （ f，l）， 若 f（ x）的非線性度滿足 N=2 -2 ，則稱 f（ x）為 Bent 函數，也稱完全非線性函數。 布爾函數 f（ x）的非線性度 Nf是用來衡量抵抗 “ 線性攻擊 ” 能力的一個非線性準則， Nf 越大，則在某種意義上布爾函數 f（ x）抵抗 “ 線性攻擊 ” 的能力越強；反之， Nf越小，則布爾函數 f（ x）抵抗 “ 線性攻擊 ” 的能力越弱。 通過計算可知，四種標準中的 8 個 S 盒的所有布爾函數均是平衡函數，非線性度均為 112，與完全非線性函數有6.67%的距離。 2.3 S 盒布爾函數 Walsh 循環(huán)譜 Walsh 循環(huán)譜衡量的是布爾函數表達式與線性函數 w x 的相符合程度。布爾函數的 Walsh 循環(huán)譜的數值越大，說明布爾函數的 Walsh 循環(huán)譜與線性函數越接近，對應的 S 盒就越容易被攻擊，算法性能就越壞。 以我國無線局域網產品 SMS4 算法為例，我們計算得到的 SMS4 算法 S 盒布爾函數 f0的 256 倍的 Walsh 循環(huán)譜如表 4所示，相應的譜圖如圖 1 所示。顯然，其各點譜值的絕對值大多在 4 到 30的范圍之內，最大不超過 32，處于較小的狀態(tài)，再次說明其與線性函數相似程度之小。 通過計算可知，我們得到四種標準中的 8 個 S 盒的布爾函數 Walsh 循環(huán)譜的性質，如表 5 所示。 通過比較，四種標準中的 S 盒布爾函數 Walsh 循環(huán)譜絕對值的 256 倍最大值均為 32，說明其與線性函數相似程度之小。由于零譜值過大將導致非線性度的下降 11，反之非線性度上升，通過計算可知各種算法的零譜值個數均較小，僅為 17，再次說明其與線性函數 相似程度之小。 3 分組密碼算法抵抗攻擊能力的分析 研究 AES算法、 SEED 算法、 Camellia 算法和 SMS4 算法抵抗插入攻擊、差分密碼分析攻擊和線性密碼分析攻擊的能力。 3.1 抵抗插入攻擊 插入攻擊 11， 12的攻擊者利用密碼的一些輸入 /輸出對來構造多項式，用于逼近密碼算法的加解密過程，此攻擊方法對變換代數次數和復雜度低的密碼尤為奏效。因此，在密碼設計中，為了防止插入攻擊，通常要求變換的代數式具有足夠高的次數和項數。 以我國無線局域網產品 SMS4 算法為例，當構 造的有限域為以不可約多項式 m（ x） =x8+x4+x3+x1+1 為生成多項式，以元素 =x+1 為生成元時（與 AES 的 S 盒保持一致），求得SMS4 算法 S 盒的代數表達式為 f（ x） =D6+53x+1Ex2+D9x253+02x254 ， 其中，各次項系數列于表 6。 因此，我們可以得到四種標準中 8 個 S 盒的代數表達式，如表 7 所示。 由表 7 可知，雖然 AES 算法、 SEED 算法、 Camellia 算法和 SMS4 算法 S 盒的代數表達式的次數均為 254，但 SMS4 算法、 SEED 算法和 Camellia 算法的項數多至 255，而 AES 算法的僅為 9?？梢?， SEED 算法、 Camellia 算法和 SMS4 算法 S 盒的代數表達式要比 AES 的更為復雜，在一定程度上更好地保證算法的安全性。 3.2 抵抗差分密碼分析 差分密碼分析 13是通過分析特定明文差對相應密文差的影響來獲得可能性最大的密鑰的一種攻擊方式。它是目前對分組密碼最為有效的攻擊方法之一。具有較小的差分均勻度是 S 盒抗擊差分攻擊的必要條件。 通過計算 AES 算法、 SEED 算法、 Camellia 算法、 SMS4算法中 S 盒的 256256 的差分 矩陣，我們發(fā)現四種算法中的8 個 S 盒的差分均勻度均為 4，且最大值在每一行每一列（首行首列除外）中出現且僅出現一次。因此，我們認為 AES 算法、 SEED 算法、 Camellia 算法和 SMS4 算法抵抗差分密碼分析的能力是相當的。 3.3 抵抗線性密碼分析 線性密碼分析 14是通過尋找并利用明文 P，密文 C 和密鑰 K 的若干位之間的一個線性表達式（ P ）？茌（ C ） =（ K ）進行的一種攻擊方式。該表達式成立的概率與二分之一的偏差大小是線性密碼分析成功的一個重要的衡量指標。各個算法 S 盒的輸入輸出比特之間的關系 可以衡量算法抵抗線性密碼分析的能力。 通過計算 AES 算法、 SEED 算法、 Camellia 算法、 SMS4算法中 S 盒的 256256 的線性分布矩陣，我們發(fā)現四種算法中的 8 個 S 盒中的矩陣元素最大絕對值都是 16，且最大值在每一行每一列（首行首列除外）中出現且僅出現五次，這意味著 S 盒的線性逼近概率較低（二百五十六分之十六），即線性性較弱，符合分組密碼非線性性較強的要求。因此，我們認為 AES 算法、 SEED 算法、 Camellia 算法和 SMS4 算法抵抗線性密碼分析的能力是相當的。 4 結束語 本文通過對無線網絡中的幾種主要分組密碼標準 S 盒密碼學性質的分析，以及對各種標準在抵抗插入攻擊、差分密碼分析攻擊和線性密碼分析攻擊能力的對比，理論上揭示了 SEED 算法、 Camellia 算法和 SMS4 算法的密碼學安全性在一定程度上優(yōu)于 AES 算法，而 SEED 算法、 Camellia 算法和SMS4 算法密碼學安全性是相當的。 參考文獻： 1Daemen J and Rijmen V. AES proposal： Rijndael Version 2EB/OL http： / .east. kuleuven.ac.be / rijmen/rijndael.1999. 2Network Working Group. Request for Comments： 4009. RFC 4269. 2005. 3European IST.NESSIE Project EB/OL. https：/.cosic.esat.kuleuven.be/nessie/.1999. 4Aoki K， Ichikawa T， Kanda M， et al， . Camellia： A 128-bit block cipher suitable for multiple platformsEB/OL. http：/info.isl.ntt.co.jp/camellia. 2000. 5國家密碼管理辦公室 .無線局域網產品使用的 SMS4密碼算法 EB/OL. http： /./Doc/6 /News_1106.htm. 2006. 6Li J， Gan L and Du F F. Research on encryption algorithm conforming to AES in WLAN C. Advanced Materials Research， 2012： 1517-1521. 7劉佳 . 基于密碼學的無線局域網認證協議設計與實現 J. 價值工程， 2012， 31（ 277）： 223-228. 8Lu Y， ONeill M P and McCanny J V. Differential power analysis resistance of Camellia and countermeasure strategy on FPGAsC. International Conference on Field-Programmable Technology， 2009： 183-189. 9Kitsos P and Skodras A N. An FPGA implementation and performance evaluation of the seed block cipherC. 17th International Conference on Digital Signal Processing （ DSP）， 2011： 1-5. 10溫巧燕，鈕心忻，楊義先 .現代密碼學中的布爾函數 M.北京：科學出版社， 2000. 11Jakobsen T and Kundsen L R. The Interpolation Attack on Block Ciphe