SHA-3
| 概述 | |
|---|---|
| 设计者 | 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]。
历史
- 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（页面存档备份，存于互联网档案馆）
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.
Cover photo is available under {{::mainImage.info.license.name || 'Unknown'}} license.
Cover photo is available under {{::mainImage.info.license.name || 'Unknown'}} license.
Credit:
(see original file).
