SHA-3

对Keccak-512的原像攻击减少到8回合，需要$2^{511.5}$的时间复杂度和$2^{508}$的内存。完整的24回合Keccak-f 1600存在零和识别符，尽管它们不能用于攻击散列函数本身

SHA-3（第三代安全杂凑算法，Secure Hash Algorithm 3），之前名为Keccak（ˈ或k)）算法，设计者宣称在 Intel Core 2 的CPU上面，此算法的效能是12.6时钟周期每字节（cycles per byte）。

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

## 历史

- Keccak 是一个加密杂凑算法，由 Guido Bertoni，Joan Daemen，Michaël Peeters，以及Gilles Van Assche在RadioGatún上设计。
- 2012年10月2日，Keccak 被选为NIST杂凑函式竞赛的胜利者。SHA-2目前没有出现明显的弱点。由于对MD5、SHA-0和SHA-1出现成功的破解，NIST感觉需要一个与之前算法不同的，可替换的加密杂凑算法，也就是现在的 SHA-3。
- 2014年，NIST 发布了 FIPS 202 的草案 "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions"。
- 2015年8月5日，FIPS 202 最终被 NIST 批准。

## 设计

Keccak 使用海绵函数，此函数会将资料与初始的内部状态做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的三维阵列。令aijk代表内存状态的第(i×5 + j)×w + k个位元（使用小端序，little-endian，参见字节序）。

置换函数是五个子段落（sub-round）作12+2ℓ次的循环，每一个子段落都相当简单：

## 修改

在整个 NIST 杂凑函数比赛里面，参赛者允许稍微修改算法解决已经出现的问题。Keccak 的修改有：

- 循环的数目从12+ℓ变成12+2ℓ，以增加安全度。
- 填充函式使用比起上述10*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 家族函数的比较

在下面的表格中，“内部状态”指的是传递到下一个块的位数。

算法及其变体｜输出长度(位)｜内部状态大小(位)｜块大小(位)｜最大消息长度(位)｜循环｜操作｜安全性(位)｜示例的性能在 AMD Opteron 8354 2.2 GHz 处理器上运行64位 Linux(MiB/s)

MD5(作为参考)｜128｜128(4 × 32)｜512｜264 − 1｜64｜按位与, 按位异或, 循环移位, 填充(求模 232), 按位或｜(已发现碰撞)｜335

SHA-0｜160｜160(5 × 32)｜512｜264 − 1｜80｜按位与, 按位异或, 循环移位, 填充(求模 232),按位或｜(已发现碰撞)

SHA-1｜160｜160(5 × 32)｜512｜264 − 1｜80｜(已发现碰撞)｜192

SHA-2｜SHA-224 SHA-256｜224256｜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)

## 外部链接

- 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

## 基本资料

- 日语原文：SHA-3、(Keccak)
- 设计者：Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche.
- publish date：2015
- 系列：(SHA-0), SHA-1, SHA-2, SHA-3
- 认证：FIPS PUB 202
- 摘要长度：任意
- 结构：海绵函数
- 速度：在x86-64微架构的计算机上，Keccak-f 1600加上XORing 1024位的效率大约为12.6位元每时钟周期，接近于SHA2-256
- cryptanalysis：对Keccak-512的原像攻击减少到8回合，需要$2^{511.5}$的时间复杂度和$2^{508}$的内存。完整的24回合Keccak-f 1600存在零和识别符，尽管它们不能用于攻击散列函数本身