SHA-3
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
概述 | |
---|---|
設計者 | Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. |
首次發布 | 2015 |
系列 | (SHA-0), SHA-1, SHA-2, SHA-3 |
認證 | FIPS PUB 202 |
細節 | |
摘要長度 | 任意 |
結構 | 海綿函式 |
速度 | 在x86-64微架構的計算機上,Keccak-f [1600]加上XORing 1024位元的效率大約為12.6位元每時鐘周期[1],接近於SHA2-256 |
最佳公開破解 | |
對Keccak-512的原像攻擊減少到8回合,需要的時間複雜度和的主記憶體[2]。完整的24回合Keccak-f [1600]存在零和識別符,儘管它們不能用於攻擊雜湊函式本身[3] |
SHA-3(第三代安全雜湊演算法,英語:Secure Hash Algorithm 3),之前名為Keccak(/ˈkɛtʃæk/或/kɛtʃɑːk/))演算法,[4][5][6]設計者宣稱在 Intel Core 2 的CPU上面,此演算法的效能是12.6時鐘周期每位元組(cycles per byte)[1][7]。
SHA-3 在2015年8月5日由 NIST 通過 FIPS 202 正式發表。[8][9]
歷史
- Keccak 是一個加密雜湊演算法,由 Guido Bertoni,Joan Daemen,Michaël Peeters,以及Gilles Van Assche在RadioGatún上設計。
- 2012年10月2日,Keccak 被選為NIST雜湊函式競賽的勝利者[10]。SHA-2目前沒有出現明顯的弱點。由於對MD5、SHA-0和SHA-1出現成功的破解,NIST感覺需要一個與之前演算法不同的,可替換的加密雜湊演算法,也就是現在的 SHA-3。
- 2014年,NIST 發布了 FIPS 202 的草案 "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions"。[11]
- 2015年8月5日,FIPS 202 最終被 NIST 批准。[12]
設計
Keccak 使用海綿函式[13][14],此函式會將資料與初始的內部狀態做XOR運算,這是無可避免可置換的(inevitably permuted)。在最大的版本,演算法使用的主記憶體狀態是使用一個5×5的二維陣列,資料型態是64位元的位元組,總計1600位元 。縮版的演算法使用比較小的,以2為冪次的位元組大小w為1位元,總計使用25位元。除了使用較小的版本來研究加密分析攻擊,比較適中的大小(例如從w=4使用100位元,到w=32使用800位元)則提供了比較實際且輕量的替代方案。
Keccak 的置換
置換方法是先定義字的長度為二的某次方,w = 2ℓ位元。SHA-3的主要應用使用64位元的字長,ℓ = 6。
主記憶體狀態可以被視為5×5×w的三維陣列。令a[i][j][k]代表主記憶體狀態的第(i×5 + j)×w + k個位元(使用小端序,little-endian,參見位元組序)。
置換函式是五個子段落(sub-round)作12+2ℓ次的迴圈,每一個子段落都相當簡單:
修改
在整個 NIST 雜湊函式比賽裡面,參賽者允許稍微修改演算法解決已經出現的問題。Keccak 的修改有:
- 迴圈的數目從12+ℓ變成12+2ℓ,以增加安全度。
- 填充函式使用比起上述10*1的方式更加複雜的作法。
- 吸收比率r增加到安全限制,而非向下捨入到最接近某個2的冪次。
SHA-3 範例
- 空字串的雜湊值:
SHA3-224("") 6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7 SHA3-256("") a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a SHA3-384("") 0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004 SHA3-512("") a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26 SHAKE128("", 256) 7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26 SHAKE256("", 512) 46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be
- 由於雪崩效應,即使一個很小的改變都會產出幾乎完全不同的雜湊值。舉例來說,把 dog 改成 dof:
SHAKE128("The quick brown fox jumps over the lazy dog", 256) f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66e SHAKE128("The quick brown fox jumps over the lazy dof", 256) 853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c
SHA 家族函式的比較
在下面的表格中,「內部狀態」指的是傳遞到下一個塊的位數。
演算法及其變體 | 輸出長度 (位) |
內部狀態大小 (位) |
塊大小 (位) |
最大訊息長度 (位) |
迴圈 | 操作 | 安全性 (位) |
範例的效能[16] (MiB/s) | |
---|---|---|---|---|---|---|---|---|---|
MD5 (作為參考) |
128 | 128 (4 × 32) |
512 | 264 − 1 | 64 | 按位元與, 按位元互斥或, 迴圈移位, 填充(求模 232), 按位元或 | <18 (已發現碰撞) |
335 | |
SHA-0 | 160 | 160 (5 × 32) |
512 | 264 − 1 | 80 | 按位元與, 按位元互斥或, 迴圈移位, 填充(求模 232),按位元或 | <34 (已發現碰撞) |
- | |
SHA-1 | 160 | 160 (5 × 32) |
512 | 264 − 1 | 80 | <63 (已發現碰撞[17]) |
192 | ||
SHA-2 | SHA-224 SHA-256 |
224 256 |
256 (8 × 32) |
512 | 264 − 1 | 64 | 按位元與, 按位元互斥或, 迴圈移位, 填充(求模 232), 按位元或, 移位 | 是 112/128 |
139 |
SHA-384 SHA-512 SHA-512/224 SHA-512/256 |
384 512 224 256 |
512 (8 × 64) |
1024 | 2128 − 1 | 80 | 按位元與, 按位元互斥或, 迴圈移位, 填充(求模 264), 按位元或, 移位 | 是 192/256/112/128 |
154 | |
SHA-3 | SHA3-224 SHA3-256 SHA3-384 SHA3-512 |
224 256 384 512 |
1600 (5 × 5 × 64) |
1152 1088 832 576 |
無限制 | 24 | 按位元與, 按位元互斥或, 迴圈移位, 取反 | 是 112/128/192/256 |
- |
SHAKE128 SHAKE256 |
d (可變長) d (可變長) |
1344 1088 |
是 min (d/2, 128) min (d/2, 256) |
- |
參考資料
- ^ 1.0 1.1 Keccak implementation overview Version 3.2 (頁面存檔備份,存於網際網路檔案館), section 3.1
- ^ Morawiecki, Paweł; Pieprzyk, Josef; Srebrny, Marian. Moriai, S , 編. Rotational Cryptanalysis of Round-Reduced Keccak (PDF). Fast Software Encryption Lecture Notes in Computer Science. Lecture Notes in Computer Science. 2013, 8424: 241–262 [2019-02-08]. ISBN 978-3-662-43932-6. doi:10.1007/978-3-662-43933-3_13. (原始內容存檔 (PDF)於2013-01-08) (英語).
- ^ Bertoni, Guido; Daemen, Joan; Peeters, Michaël; van Assche, Giles. The Keccak SHA-3 submission (PDF). keccak.noekeon.org. January 14, 2011 [February 9, 2014]. (原始內容存檔 (PDF)於2011-08-19).
- ^ NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. NIST. 2012-10-02 [2012-10-02]. (原始內容存檔於2012-10-05).
- ^ Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. The Keccak sponge function family: Specifications summary. [2011-05-11]. (原始內容存檔於2016-08-06).
- ^ Keccak: The New SHA-3 Encryption Standard. Dr. Dobbs. [2016-07-24]. (原始內容存檔於2016-07-14).
- ^ Guo, Xu; Huang, Sinan; Nazhandali, Leyla; Schaumont, Patrick, Fair and Comprehensive Performance Evaluation of 14 Second Round SHA-3 ASIC Implementations (PDF), NIST 2nd SHA-3 Candidate Conference, Aug 2010: 12 [2011-02-18], (原始內容存檔 (PDF)於2010-09-10)Keccak is second only to Luffa, which did not advance to the final round.
- ^ 存档副本. [2015-08-18]. (原始內容存檔於2015-08-17).
- ^ 存档副本. [2015-08-18]. (原始內容存檔於2015-08-12).
- ^ NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. NIST. 2012-10-02 [2012-10-02]. (原始內容存檔於2012-10-05).
- ^ SHA-3 standardization. NIST. [2015-04-16]. (原始內容存檔於2015-04-05).
- ^ National Institute of Standards and Technology. Federal Information Processing Standards: Permutation-Based Hash and Extendable-Output Functions, etc.. Aug 5, 2015 [5 Aug 2015].
- ^ Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. Sponge Functions. Ecrypt Hash Workshop 2007. [2012-10-20]. (原始內容存檔於2012-09-04).
- ^ Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. On the Indifferentiability of the Sponge Construction. EuroCrypt 2008. [2012-10-20]. (原始內容存檔於2012-09-04).
- ^ Crypto++ 5.6.0 Benchmarks. [2013-06-13]. (原始內容存檔於2016-10-14).
- ^ 在 AMD Opteron 8354 2.2 GHz 處理器上執行64位元 Linux[15]
- ^ Google Security Blog - Announcing the first SHA1 collision. [2017-02-23]. (原始內容存檔於2017-04-24).
外部連結
- Keccak網站(英文)(頁面存檔備份,存於網際網路檔案館)
- Keccak官方C語言代碼包(頁面存檔備份,存於網際網路檔案館)
- Keccak官方C++語言工具集(頁面存檔備份,存於網際網路檔案館)
- A Java implementation of Keccak
- A Cryptol implementation of Keccak
- A VHDL source codes developed in the Cryptographic Engineering Research Group (CERG) at George Mason University(頁面存檔備份,存於網際網路檔案館)
|