查看“︁SHA-3”︁的源代码

{{noteTA
|G1=IT
}}
{{Infobox cryptographic hash function
| name           = SHA-3<br/>(Keccak)
| image          =
| caption        =
<!-- General -->
| designers      = Guido Bertoni, [[Joan Daemen]], Michaël Peeters, and [[Gilles Van Assche]].
| publish date = 2015
| series         = ([[SHA-0]]), [[SHA-1]], [[SHA-2]], SHA-3
| derived from   =
| derived to     =
| related to     =
| certification  = [[Federal Information Processing Standard|FIPS]] PUB 202
<!-- Detail -->
| digest size    = 任意
| structure      = [[海绵函数]]
| speed          =在x86-64微架构的計算機上，Keccak-f [1600]加上XORing 1024位的效率大約為12.6位元每时钟周期<ref name="ksoftimpl">[http://keccak.noekeon.org/Keccak-implementation-3.2.pdf Keccak implementation overview Version 3.2] {{Wayback|url=http://keccak.noekeon.org/Keccak-implementation-3.2.pdf |date=20131014172014 }}, section 3.1</ref>，接近于SHA2-256
| cryptanalysis  = 對Keccak-512的原像攻擊減少到8回合，需要<math>2^{511.5}</math>的時間复杂度和<math>2^{508}</math>的内存<ref>{{cite journal |last1=Morawiecki |first1=Paweł |last2=Pieprzyk |first2=Josef |last3=Srebrny |first3=Marian |editor1-last=Moriai |editor1-first=S |title=Rotational Cryptanalysis of Round-Reduced Keccak |journal=Fast Software Encryption Lecture Notes in Computer Science |date=2013 |volume=8424 |pages=241–262 |doi=10.1007/978-3-662-43933-3_13 |url=https://eprint.iacr.org/2012/546.pdf |language=en |archive-url=https://web.archive.org/web/20130108011253/https://eprint.iacr.org/2012/546.pdf |archive-date=2013-01-08 |access-date=2019-02-08 |df= |series=Lecture Notes in Computer Science |isbn=978-3-662-43932-6 |dead-url=no }}</ref>。完整的24回合Keccak-f [1600]存在零和識別符，儘管它們不能用於攻擊散列函數本身<ref>{{cite web |url=http://keccak.noekeon.org/Keccak-submission-3.pdf |title=The Keccak SHA-3 submission |last1=Bertoni |first1=Guido |last2=Daemen |first2=Joan |last3=Peeters |first3=Michaël |last4=van Assche |first4=Giles |date=January 14, 2011 |website=keccak.noekeon.org |archive-url=https://web.archive.org/web/20110819084908/http://keccak.noekeon.org/Keccak-submission-3.pdf |archive-date=2011-08-19 |access-date=February 9, 2014 |dead-url=no }}</ref>
}}

'''SHA-3'''（第三代安全雜湊演算法，{{lang-en|Secure Hash Algorithm 3}}），之前名為'''Keccak'''（{{IPAc-en|ˈ|k|ɛ|t|ʃ|æ|k|}}或{{IPAc-en|k|ɛ|t|ʃ|ɑː|k}})）演算法，<ref name="nist">{{cite web|url=http://www.nist.gov/itl/csd/sha-100212.cfm|title=NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition|date=2012-10-02|publisher=[[NIST]]|accessdate=2012-10-02|archive-url=https://web.archive.org/web/20121005031201/http://www.nist.gov/itl/csd/sha-100212.cfm|archive-date=2012-10-05|dead-url=no}}</ref><ref>{{cite web|title=The Keccak sponge function family: Specifications summary|url=http://keccak.noekeon.org/specs_summary.html|accessdate=2011-05-11|authors=Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche|archive-url=https://web.archive.org/web/20160806192717/http://keccak.noekeon.org/specs_summary.html|archive-date=2016-08-06|dead-url=no}}</ref><ref name="drdobbs">{{cite web|url=http://www.drdobbs.com/security/keccak-the-new-sha-3-encryption-standard/240154037|title=Keccak: The New SHA-3 Encryption Standard|website=Dr. Dobbs|access-date=2016-07-24|archive-url=https://web.archive.org/web/20160714153605/http://www.drdobbs.com/security/keccak-the-new-sha-3-encryption-standard/240154037|archive-date=2016-07-14|dead-url=no}}</ref>設計者宣稱在 [[Intel Core 2]] 的CPU上面，此演算法的效能是12.6时钟周期每位元組（cycles per byte）<ref name="ksoftimpl"/><ref>{{Citation |title=Fair and Comprehensive Performance Evaluation of 14 Second Round SHA-3 ASIC Implementations |url=http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SCHAUMONT_SHA3.pdf |first1=Xu |last1=Guo |first2=Sinan |last2=Huang |first3=Leyla |last3=Nazhandali |first4=Patrick |last4=Schaumont |journal=NIST 2nd SHA-3 Candidate Conference |accessdate=2011-02-18 |page=12 |date=Aug  2010 |archive-url=https://web.archive.org/web/20100910145512/http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SCHAUMONT_SHA3.pdf |archive-date=2010-09-10 |dead-url=no }}Keccak is second only to Luffa, which did not advance to the final round.</ref>。

SHA-3 在2015年8月5日由 NIST 通过 FIPS 202 正式发表。<ref name="nist.gov">{{Cite web |url=http://www.nist.gov/itl/csd/201508_sha3.cfm |title=存档副本 |access-date=2015-08-18 |archive-url=https://web.archive.org/web/20150817005537/http://www.nist.gov/itl/csd/201508_sha3.cfm |archive-date=2015-08-17 |dead-url=no }}</ref><ref>{{Cite web |url=http://www.nist.gov/manuscript-publication-search.cfm?pub_id=919061 |title=存档副本 |access-date=2015-08-18 |archive-url=https://web.archive.org/web/20150812222834/http://www.nist.gov/manuscript-publication-search.cfm?pub_id=919061 |archive-date=2015-08-12 |dead-url=no }}</ref>

== 历史 ==
* Keccak 是一個[[加密雜湊演算法]]，由 [[Guido Bertoni]]，[[Joan Daemen]]，[[Michaël Peeters]]，以及[[Gilles Van Assche]]在[[RadioGatún]]上设计。
* 2012年10月2日，Keccak 被選為[[NIST雜湊函式競賽]]的勝利者<ref>{{cite web |url = http://www.nist.gov/itl/csd/sha-100212.cfm |title = NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition |date = 2012-10-02 |publisher = [[NIST]] |accessdate = 2012-10-02 |archive-url = https://web.archive.org/web/20121005031201/http://www.nist.gov/itl/csd/sha-100212.cfm |archive-date = 2012-10-05 |dead-url = no }}</ref>。SHA-2目前沒有出現明顯的弱點。由於對[[MD5]]、[[SHA-0]]和[[SHA-1]]出現成功的破解，NIST感覺需要一個與之前演算法不同的，可替換的加密雜湊演算法，也就是現在的 SHA-3。
* 2014年，[[NIST]] 发布了 [[FIPS]] 202 的草案 "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions"。<ref>{{cite web | url=http://csrc.nist.gov/groups/ST/hash/sha-3/sha-3_standardization.html | title=SHA-3 standardization | publisher=NIST | accessdate=2015-04-16 | archive-url=https://web.archive.org/web/20150405120503/http://csrc.nist.gov/groups/ST/hash/sha-3/sha-3_standardization.html | archive-date=2015-04-05 | dead-url=no }}</ref>
* 2015年8月5日，FIPS 202 最终被 NIST 批准。<ref>{{cite web|url=https://federalregister.gov/a/2015-19181|title=Federal Information Processing Standards: Permutation-Based Hash and Extendable-Output Functions, etc.|date=Aug 5, 2015|accessdate=5 Aug 2015|author=National Institute of Standards and Technology}}</ref>

== 设计 ==
Keccak 使用[[海綿函數]]<ref>{{cite web |url=http://sponge.noekeon.org/ |title=Sponge Functions |publisher=Ecrypt Hash Workshop 2007 |authors=Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche |access-date=2012-10-20 |archive-url=https://www.webcitation.org/6AQLAQuz4?url=http://sponge.noekeon.org/ |archive-date=2012-09-04 |dead-url=no }}</ref><ref>{{cite web |url=http://sponge.noekeon.org/ |title=On the Indifferentiability of the Sponge Construction |publisher=EuroCrypt 2008 |authors=Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche |access-date=2012-10-20 |archive-url=https://www.webcitation.org/6AQLAQuz4?url=http://sponge.noekeon.org/ |archive-date=2012-09-04 |dead-url=no }}</ref>，此函數會將資料與初始的內部狀態做XOR運算，這是無可避免可置換的（inevitably permuted）。在最大的版本，演算法使用的內存狀態是使用一個5×5的二維陣列，資料型態是64位元的字節，總計1600位元 。縮版的演算法使用比較小的，以2為冪次的字節大小''w''為1位元，總計使用25位元。除了使用較小的版本來研究加密分析攻擊，比較適中的大小（例如從''w''=4使用100位元，到''w''=32使用800位元）則提供了比較實際且輕量的替代方案。

== Keccak 的置換 ==

置換方法是先定義[[字 (計算機)|字]]的長度為二的某次方，''w''&nbsp;=&nbsp;2<sup>ℓ</sup>位元。SHA-3的主要應用使用64位元的字長，ℓ&nbsp;=&nbsp;6。

內存狀態可以被視為5×5×''w''的三維陣列。令''a''[''i''][''j''][''k'']代表內存狀態的第(''i''×5 + ''j'')×''w'' + ''k''個位元（使用小端序，little-endian，參見[[位元組序]]）。

置換函數是五個子段落（sub-round）作12+2ℓ次的迴圈，每一個子段落都相當簡單：
<!--
; ''θ''
: Compute the [[Parity (mathematics)|parity]] of each of the 5''w'' (320, when {{nowrap|1=''w'' = 64}}) 5-bit columns, and exclusive-or that into two nearby columns in a regular pattern.  To be precise, {{nowrap|''a''[''i''][''j''][''k''] ← ''a''[''i''][''j''][''k''] ⊕ parity(a[''i''][''j''−1][''k'']) ⊕ parity(a[''i''][''j''+1][''k''−1])}}
; ''ρ''
: [[Circular shift|Bitwise rotate]] each of the 25 words by a different [[triangular number]] 0, 1, 3, 6, 10, 15, ....  To be precise, ''a''[0][0] is not rotated, and for all {{nowrap|0 ≤ ''t'' < 24}}, ''a''[''i''][''j''][''k''] ← ''a''[''i''][''j''][''k''−(''t''+1)(''t''+2)/2], where <math>\begin{pmatrix} i \\ j \end{pmatrix} = \begin{pmatrix} 3 & 2 \\ 1 & 0 \end{pmatrix}^t \begin{pmatrix} 0 \\ 1 \end{pmatrix}</math>.
; ''π''
: Permute the 25 words in a fixed pattern.  {{nowrap|''a''[''j''][2''i''+3''j''] ← ''a''[''i''][''j'']}}
; ''χ''
: Bitwise combine along rows, using {{nowrap|1=''a'' ← ''a'' ⊕ (¬''b'' &amp; ''c'')}}.  To be precise, {{nowrap|''a''[''i''][''j''][''k''] ← ''a''[''i''][''j''][''k''] ⊕ ¬''a''[''i''][''j''+''1''][''k''] &amp; ''a''[''i''][''j''+''2''][''k'']}}.  This is the only non-linear operation in SHA-3.
; ''ι''
: Exclusive-or a round constant into one word of the state.  To be precise, in round ''n'', for {{nowrap|0 ≤ ''m'' ≤ ℓ}}, ''a''[0][0][2<sup>''m''</sup>−1] is exclusive-ORed with bit {{nowrap|''m'' + 7''n''}} of a degree-8 [[LFSR]] sequence.  This breaks the symmetry that is preserved by the other sub-rounds.

==Hashing variable-length messages==
[[Image:SpongeConstruction.svg|thumb|upright=1.35|right|alt=Illustration of the sponge construction |The sponge construction for hash functions.  ''p<sub>i</sub>'' are input, ''z<sub>i</sub>'' are hashed output.  The unused "capacity" ''c'' should be twice the desired resistance to [[Collision attack|collision]] or [[preimage attack]]s.]] SHA-3 uses the "sponge construction", where input is "absorbed" into the hash state at a given rate, then an output hash is "squeezed" from it at the same rate.

To absorb ''r'' bits of data, the data is XORed into the leading bits of the state, and the block permutation is applied.  To squeeze, the first ''r'' bits of the state are produced as output, and the block permutation is applied if additional output is desired.

Central to this is the "capacity" of the hash function, which is the {{nowrap|1=''c'' = 25''w'' − ''r''}} state bits that are not touched by input or output.  This can be adjusted based on security requirements, but the SHA-3 proposal sets a conservative {{nowrap|1=''c'' = 2''n''}}, where ''n'' is the size of the output hash.  Thus ''r'', the number of message bits processed per block permutation, depends on the output hash size. The NIST submission sets the rate ''r'' as 1152, 1088, 832, or 576 (144, 136, 104 and 72 bytes) for 224, 256, 384 and 512-bit hash sizes, respectively. In April 2014, NIST pubished a draft that confirms these values. <ref name="draft201404">{{cite web |url=http://csrc.nist.gov/publications/drafts/fips-202/fips_202_draft.pdf |title=SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions |publisher=NIST |author=NIST Computer Security Division (CSD)}}</ref>

To ensure the message can be evenly divided into ''r''-bit blocks, padding is required. The submission proposes the bit pattern 10<sup>*</sup>1: a 1 bit, zero or more 0 bits (maximum {{nowrap|''r'' − 1}}), and a final 1 bit.  The final 1 bit is required because the sponge construction security proof requires that the rate is encoded in the final block ("multi rate padding"). The current draft includes adding bits 01 to the message before the applying the padding.<ref name="draft201404"/> This provides domain separation from the SHAKE's, the other sponge modes included in the draft. For byte granularity data, this never increases the message size, since we have six unused bits anyways.

To compute a hash, initialize the state to 0, pad the input, and break it into ''r''-bit pieces.  Absorb the input into the state; that is, for each piece, XOR it into the state and then apply the block permutation.

After the final block permutation, the leading ''n'' bits of the state are the desired hash.  Because ''r'' is always greater than ''n'', there is actually never a need for additional block permutations in the squeezing phase.  However, arbitrary output length may be useful in applications such as [[optimal asymmetric encryption padding]].  In this case, ''n'' is a security parameter rather than the output size.

Although not part of the SHA-3 competition requirements, smaller variants of the block permutation can be used, for hash output sizes up to half their state size, if the rate r is limited appropriately.  For example, a 256-bit hash can be computed using 25 32-bit words if {{nowrap|1=''r'' = 800 − 2×256 = 288}} (36 bytes per iteration).
-->

== 修改 ==
在整個 NIST 雜湊函數比賽裡面，參賽者允許稍微修改演算法解決已經出現的問題。Keccak 的修改有：
* 迴圈的數目從12+ℓ變成12+2ℓ，以增加安全度。
* 填充函式使用比起上述10<sup>*</sup>1的方式更加複雜的作法。
* 吸收比率''r''增加到安全限制，而非向下捨入到最接近某個2的冪次。

== SHA-3 範例 ==
* 空字串的雜湊值：

 <span style="color: green;">SHA3-224("")</span>
 6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7
 <span style="color: green;">SHA3-256("")</span>
 a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a
 <span style="color: green;">SHA3-384("")</span>
 0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004
 <span style="color: green;">SHA3-512("")</span>
 a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26
 <span style="color: green;">SHAKE128("", 256)</span>
 7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26
 <span style="color: green;">SHAKE256("", 512)</span>
 46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be

* 由於[[雪崩效应]]，即使一個很小的改變都會產出幾乎完全不同的雜湊值。舉例來說，把 dog 改成 dof：

 <span style="color: green;">SHAKE128("The quick brown fox jumps over the lazy dog", 256)</span>
 f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66e
 <span style="color: green;">SHAKE128("The quick brown fox jumps over the lazy dof", 256)</span>
 853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c

== SHA 家族函数的比较 ==
在下面的表格中，“内部状态”指的是传递到下一个块的位数。

{| class="wikitable" style="margin-top: 0px;"
|+ SHA 家族函数的比较
|-
! colspan="2" | 算法及其变体
! 输出长度<br/ >(位)
! 内部状态大小<br/ >(位)
! 块大小<br/ >(位)
! 最大消息长度<br/ >(位)
! 循环
! 操作
! 安全性<br/ >(位)
! 示例的性能{{refn|在 [[AMD Opteron]] 8354 2.2 GHz 处理器上运行64位 Linux<ref>{{cite web|url=http://www.cryptopp.com/benchmarks-amd64.html|title=Crypto++ 5.6.0 Benchmarks|accessdate=2013-06-13|archive-url=https://web.archive.org/web/20161014211419/http://www.cryptopp.com/benchmarks-amd64.html|archive-date=2016-10-14|dead-url=no}}</ref>}}<br/ >([[Mebibyte|MiB]]/s)
|- style="text-align:center;"
| colspan="2" | '''[[MD5]]'''<br />(作为参考) || 128 || 128<br>(4 × 32) || 512 || 2<sup>64</sup> − 1 || 64 || 按位与, 按位异或, 循环移位, 填充(求模 2<sup>32</sup>), 按位或 || {{Bad|&lt;18<br/ >(已发现碰撞)}} || 335
|- style="text-align:center;"
| colspan="2" | '''[[SHA-0]]''' || 160 || 160<br>(5 × 32) || 512 || 2<sup>64</sup> − 1|| 80 || rowspan="2" | 按位与, 按位异或, 循环移位, 填充(求模 2<sup>32</sup>),按位或 || {{Bad|&lt;34<br/ >(已发现碰撞)}}  || -
|- style="text-align:center;"
| colspan="2" | '''[[SHA-1]]''' || 160 || 160<br>(5 × 32) || 512 || 2<sup>64</sup> − 1 || 80 || {{Bad|&lt;63<br/ >(已發現碰撞<ref>{{cite web |url=https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html |title=Google Security Blog - Announcing the first SHA1 collision |accessdate=2017-02-23 |archive-url=https://web.archive.org/web/20170424012912/https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html |archive-date=2017-04-24 |dead-url=no }}</ref>}}) || 192
|- style="text-align:center;"
| rowspan="2" | '''[[SHA-2]]''' || ''SHA-224'' <br/> ''SHA-256'' || 224<br/>256 || 256<br>(8 × 32) || 512 || 2<sup>64</sup> − 1 || 64 || 按位与, 按位异或, 循环移位, 填充(求模 2<sup>32</sup>), 按位或, 移位 || {{Yes}}<br />112/128 || 139
|- style="text-align:center;"
| ''SHA-384'' <br/> ''SHA-512'' <br/> ''SHA-512/224'' <br/> ''SHA-512/256'' ||  384 <br/> 512 <br/> 224 <br/> 256 || 512<br>(8 × 64) || 1024 || 2<sup>128</sup> − 1 || 80 || 按位与, 按位异或, 循环移位, 填充(求模 2<sup>64</sup>), 按位或, 移位 || {{Yes}}<br />192/256/112/128 || 154
|- style="text-align:center;"
| rowspan="2" | '''SHA-3''' || ''SHA3-224'' <br/> ''SHA3-256'' <br/> ''SHA3-384'' <br/> ''SHA3-512'' || 224 <br/> 256 <br/> 384 <br/> 512 || rowspan="2" | 1600<br>(5 × 5 × 64) || 1152 <br/> 1088 <br/> 832 <br/> 576 || rowspan="2" | 无限制 || rowspan="2" | 24 || rowspan="2" | 按位与, 按位异或, 循环移位, 取反 || {{Yes}}<br />112/128/192/256 || -
|- style="text-align:center;"
| ''SHAKE128'' <br/> ''SHAKE256'' || ''d'' (可变长) <br/> ''d'' (可变长) || 1344 <br/> 1088 || {{Yes}}<br />min (''d''/2, 128)<br/>min (''d''/2, 256) || -
|}

== 參考資料 ==
{{reflist|2}}

== 外部連結 ==
* [http://keccak.noekeon.org/ Keccak網站(英文)]{{Wayback|url=http://keccak.noekeon.org/ |date=20161012055221 }}
* [https://github.com/gvanas/KeccakCodePackage Keccak官方C语言代码包]{{Wayback|url=https://github.com/gvanas/KeccakCodePackage |date=20141013191624 }}
* [https://github.com/gvanas/KeccakTools Keccak官方C++语言工具集]{{Wayback|url=https://github.com/gvanas/KeccakTools |date=20141013191724 }}
* [https://github.com/kocakosm/pitaya/blob/master/src/org/kocakosm/pitaya/security/Keccak.java A Java implementation of Keccak]
* [https://web.archive.org/web/20130407154409/http://plaintext.crypto.lo.gy/article/495/untwisted-a-cryptol-implementation-of-keccak-part-1 A Cryptol implementation of Keccak]
* [http://cryptography.gmu.edu/athena/index.php?id=source_codes A VHDL source codes developed in the Cryptographic Engineering Research Group (CERG) at George Mason University]{{Wayback|url=http://cryptography.gmu.edu/athena/index.php?id=source_codes |date=20120425083429 }}

{{密碼學|hash}}

[[Category:密码散列函数]]
[[Category:密碼學理論]]
[[Category:带有源代码的公共领域软件]]
[[Category:NIST散列函数竞赛]]