SHA-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
(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比特每时钟周期[1],接近于SHA2-256
最佳公开破解
对Keccak-512的原像攻击减少到8回合,需要的时间复杂度和的内存[2]。完整的24回合Keccak-f [1600]存在零和识别符,尽管它们不能用于攻击散列函数本身[3]

SHA-3 在2015年8月5日由 NIST 通过 FIPS 202 正式发表。[8][9]

历史

  • Keccak 是一个加密散列算法,由 Guido BertoniJoan DaemenMichaël Peeters,以及Gilles Van AsscheRadioGatún上设计。
  • 2012年10月2日,Keccak 被选为NIST散列函数竞赛的胜利者[10]。SHA-2目前没有出现明显的弱点。由于对MD5SHA-0SHA-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 + jw + 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 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. ^ 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). 
  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). 
  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.
  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). 

外部链接