SHA-3

SHA-3
(Keccak)
概述
設計者	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位元每時鐘周期，接近於SHA2-256
最佳公開破解
	對Keccak-512的原像攻擊減少到8回合，需要的時間複雜度和的記憶體。完整的24回合Keccak-f [1600]存在零和識別符，儘管它們不能用於攻擊雜湊函數本身

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 家族函數的比較[編輯]

在下面的表格中，「內部狀態」指的是傳遞到下一個塊的位數。

SHA 家族函數的比較
演算法及其變體		輸出長度 (位)	內部狀態大小 (位)	塊大小 (位)	最大訊息長度 (位)	迴圈	操作	安全性 (位)	範例的效能^[16] (MiB/s)
MD5 (作為參考)		128	128 (4 × 32)	512	2⁶⁴ − 1	64	按位元與, 按位元異或, 迴圈移位, 填充(求模 2³²), 按位元或	<18 (已發現碰撞)	335
SHA-0		160	160 (5 × 32)	512	2⁶⁴ − 1	80	按位元與, 按位元異或, 迴圈移位, 填充(求模 2³²),按位元或	<34 (已發現碰撞)	-
SHA-1		160	160 (5 × 32)	512	2⁶⁴ − 1	80	按位元與, 按位元異或, 迴圈移位, 填充(求模 2³²),按位元或	<63 (已發現碰撞^[17])	192
SHA-2	SHA-224 SHA-256	224 256	256 (8 × 32)	512	2⁶⁴ − 1	64	按位元與, 按位元異或, 迴圈移位, 填充(求模 2³²), 按位元或, 移位	是 112/128	139
SHA-2	SHA-384 SHA-512 SHA-512/224 SHA-512/256	384 512 224 256	512 (8 × 64)	1024	2¹²⁸ − 1	80	按位元與, 按位元異或, 迴圈移位, 填充(求模 2⁶⁴), 按位元或, 移位	是 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	-
SHA-3	SHAKE128 SHAKE256	d (可變長) d (可變長)	1600 (5 × 5 × 64)	1344 1088	無限制	24	按位元與, 按位元異或, 迴圈移位, 取反	是 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）.

外部連結[編輯]

[ksoftimpl-1] 1.0 ^1.1 Keccak implementation overview Version 3.2 （頁面存檔備份，存於互聯網檔案館）, section 3.1

[2] 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）（英語）.

[3] 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-4] NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. NIST. 2012-10-02 [2012-10-02]. （原始內容存檔於2012-10-05）.

[5] Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. The Keccak sponge function family: Specifications summary. [2011-05-11]. （原始內容存檔於2016-08-06）.

[drdobbs-6] Keccak: The New SHA-3 Encryption Standard. Dr. Dobbs. [2016-07-24]. （原始內容存檔於2016-07-14）.

[7] 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.

[nist.gov-8] 存档副本. [2015-08-18]. （原始內容存檔於2015-08-17）.

[9] 存档副本. [2015-08-18]. （原始內容存檔於2015-08-12）.

[10] NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. NIST. 2012-10-02 [2012-10-02]. （原始內容存檔於2012-10-05）.

[11] SHA-3 standardization. NIST. [2015-04-16]. （原始內容存檔於2015-04-05）.

[12] National Institute of Standards and Technology. Federal Information Processing Standards: Permutation-Based Hash and Extendable-Output Functions, etc.. Aug 5, 2015 [5 Aug 2015].

[13] Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. Sponge Functions. Ecrypt Hash Workshop 2007. [2012-10-20]. （原始內容存檔於2012-09-04）.

[14] 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）.

[15] Crypto++ 5.6.0 Benchmarks. [2013-06-13]. （原始內容存檔於2016-10-14）.

[16] 在 AMD Opteron 8354 2.2 GHz 處理器上執行64位元 Linux^[15]

[17] Google Security Blog - Announcing the first SHA1 collision. [2017-02-23]. （原始內容存檔於2017-04-24）.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[16]

[17]

[15]