Hash函数的核心在于设计压缩函数。可以证明，如果压缩函数具有抗碰撞能力，那么迭代Hash函数也具有抗碰撞能力。
2007年起，NIST开始向全球征集新的安全Hash算法SHA-3，最后的优胜者是Keccak。Keccak以及SHA-3在正式成为标准之前有很多不同程度的更改，我想这也是网上有关Keccak和SHA-3算法的资料都多多少少不太一致的原因。本文仅介绍Keccak-224/256/384/512，以当前Keccak官网中的算法描述为准。参考文献中列出了该算法的一些详细描述，需要说明的是，除官网外的参考文献都与官网中的描述有些出入，请仔细甄别。
整体描述
Keccak算法采用海绵结构（sponge construction），在预处理（padding并分成大小相同的块）后，海绵结构主要分成两部分：
- 吸入阶段（absorbing phase）：将块x_i传入算法并处理。
- 挤出阶段（squeezing phase）：产生一个固定长度的输出。
Keccak算法的整体结构如图：
High-level view on Keccak
在这两个阶段要是使用同一个压缩函数Keccak-f，下图展示了算法“吸入”一个块x_i并处理，最后挤出输出的过程：
吸入和挤出阶段
从图中我们可以归纳出大致的流程：
- 对输入串x做padding，使其长度能被r整除，将padding后分割成长度为r的块，即x=x_0||x_1||x_2||...||x_t-1。
- 初始化一个长度为r+c bit的全零向量。
- 输入块x_i，将x_i和向量的前r个bit亦或，然后输入到Keccak-f函数中处理。
- 重复上一步，直至处理完x中的每个块。
- 输出长为r的块作为y_0，并将向量输入到Keccak-f函数中处理，输出y_1，以此类推。得到的Hash序列即为y=y_0||y_1||y_2||...||y_u。在Keccak-224/256/384/512中，只需要在y_0中取出对应长度的前缀即可。
针对图中的参数，做出如下定义：
- r：比特率（bit rate），其值为每个输入块的长度。
- c：容量（capacity），其长度为输出长度的两倍。
- b：向量的长度，b=r+c。b的值依赖于指数l，即b=25*(2^l)。当l=0,1时，b=25,50。由于这时b太小，通常不能作为实际算法使用。在本文中，取l=6，b=1600。
在Keccak-224/256/384/512中，b、r、c及输出长度的取值见下表。
| b/bits | r/bits | c/bits | 输出长度/bits | 安全级别/bits |
|---|---|---|---|---|
| 1600 | 1152 | 448 | 224 | 112 |
| 1600 | 1088 | 512 | 256 | 128 |
| 1600 | 832 | 768 | 384 | 192 |
| 1600 | 576 | 1024 | 512 | 256 |
Padding
由于目前计算机大多按照字节寻址，输入的最小单位为字节，因此以下的描述中默认输入bit长度能整除8。
按照官网的描述，padding伪代码如下：
P = Mbytes || d || 0x00 || … || 0x00
P = P xor (0x00 || … || 0x00 || 0x80)
Mbytes为输入串，“||”符号表示比特串串联。在SHA3的标准中，d为0x06。由于Keccak中按照字节序为小端，以上描述相当于在输入比特串后接0110*1以将长度补齐到能被r整除。关于Keccak中字节序的问题可以参考官网中的Bits and bytes in Keccak。
压缩函数Keccak-f
压缩函数以b比特作为输入，b比特作为输出。内部结构如下：
Internel structure of Keccak-f
Keccak-f包含n_r轮。n_r的取值与我们之前计算b时用到的指数l有关，具体地，n_r=12+2*l。Keccak-224/256/384/512中，取l=6，因此n_r=24。在每一轮中，要以此执行五步，即θ(theta)、ρ(rho)、π(pi)、χ(chi)、ι(iota)。在处理过程中，我们把b=1600个比特排列成一个5*5*w的矩阵，其中w=2^l=64比特，如图：
比特排列方式
接下来，我们来描述这五步的具体内容。
Theta Step (θ)
C[x] = A[x,0] xor A[x,1] xor A[x,2] xor A[x,3] xor A[x,4], for x in 0…4
D[x] = C[x-1] xor rot(C[x+1],1), for x in 0…4
A[x,y] = A[x,y] xor D[x], for (x,y) in (0…4,0…4)
该步骤的输入输出均存在A矩阵中。额外说明一点是，rot(num, offset)表示将w比特的num向z轴正方向循环移动offset位。具体实现中，可以当成循环左移offset位，我在代码中的实现如下：
uint64_t Keccak::rot(uint64_t num, int offset) {
if (offset == 0) {
return num;
}
return (num << offset) | (num >> (64 - offset));
}
（一个玄学问题：zp同学向我指出，如果不加offset==0的特判，当offset==0时，num>>64的值不一定为0，而是一个不确定的值，这会导致该函数的输出错误。但是我加不加特判对结果的正确性没有影响。为了保险起见，这里还是将特判加上了。）
Rho (ρ) and Pi (π) Steps
B[y,2*x+3*y] = rot(A[x,y], r[x,y]), for (x,y) in (0…4,0…4)
该步的输入为A数组，输出为B数组。rot含义同上一步，其中作为offset的r数组定义如下：
| x=3 | x=4 | x=0 | x=1 | x=2 | |
|---|---|---|---|---|---|
| y=2 | 25 | 39 | 3 | 10 | 43 |
| y=1 | 55 | 20 | 36 | 44 | 6 |
| y=0 | 28 | 27 | 0 | 1 | 62 |
| y=4 | 56 | 18 | 14 | 2 | 61 |
| y=3 | 21 | 8 | 41 | 45 | 15 |
代码中定义如下：
const int R_CONS[MAT][MAT] = {
{0, 36, 3, 41, 18},
{1, 44, 10, 45, 2},
{62, 6, 43, 15, 61},
{28, 55, 25, 21, 56},
{27, 20, 39, 8, 14}};
Chi (χ) Step
A[x,y] = B[x,y] xor ((not B[x+1,y]) and B[x+2,y]), for (x,y) in (0…4,0…4)
该步骤中，输入为B矩阵，输出为A矩阵。
Iota (ι) Step
A[0,0] = A[0,0] xor RC
该步骤输入和输出均为A矩阵。RC值与轮数有关，RC在24轮中的定义如下：
const uint64_t RC[nr] = {
0x0000000000000001, 0x0000000000008082, 0x800000000000808A, 0x8000000080008000,
0x000000000000808B, 0x0000000080000001, 0x8000000080008081, 0x8000000000008009,
0x000000000000008A, 0x0000000000000088, 0x0000000080008009, 0x000000008000000A,
0x000000008000808B, 0x800000000000008B, 0x8000000000008089, 0x8000000000008003,
0x8000000000008002, 0x8000000000000080, 0x000000000000800A, 0x800000008000000A,
0x8000000080008081, 0x8000000000008080, 0x0000000080000001, 0x8000000080008008};
输出
通过海绵结构中的挤出阶段，可以获得任意长度的输出。在Keccak-224/256/384/512中，我们只需要获得y0中的前224/256/384/512个bit作为输出即可。
具体实现
最后，附上Keccak的代码实现。在使用时，通过Keccak("224")（或"256" "384" "512"）来指定Keccak的类型并初始化。通过uint8_t* encrypt(uint8_t *seq, int len);函数来获得Hash序列。其中seq为输入串（以字节为单位），len为输入的长度（以字节为单位）。
keccak.h：
#include <cstdio>
#include <string>
#include <cstdint>
#include <iostream>
class Keccak {
const int b = 200;
int r, c; // In bytes
uint8_t P;
static const int nr = 24;
const int w = 64;
int output_len;
static const int MAT = 5;
const int R_CONS[MAT][MAT] = {
{0, 36, 3, 41, 18},
{1, 44, 10, 45, 2},
{62, 6, 43, 15, 61},
{28, 55, 25, 21, 56},
{27, 20, 39, 8, 14}};
const uint64_t RC[nr] = {
0x0000000000000001, 0x0000000000008082, 0x800000000000808A, 0x8000000080008000,
0x000000000000808B, 0x0000000080000001, 0x8000000080008081, 0x8000000000008009,
0x000000000000008A, 0x0000000000000088, 0x0000000080008009, 0x000000008000000A,
0x000000008000808B, 0x800000000000008B, 0x8000000000008089, 0x8000000000008003,
0x8000000000008002, 0x8000000000000080, 0x000000000000800A, 0x800000008000000A,
0x8000000080008081, 0x8000000000008080, 0x0000000080000001, 0x8000000080008008};
const int MIN_PAD = 1;
uint64_t theta_C[MAT];
uint64_t theta_D[MAT];
uint64_t after_theta[MAT][MAT];
uint64_t after_rho_pi[MAT][MAT];
uint64_t after_chi[MAT][MAT];
uint64_t after_f[MAT][MAT];
public:
Keccak(std::string type) {
if (type == "224") {
output_len = 28;
c = 56;
// P = 0xCC;
} else if (type == "256") {
output_len = 32;
c = 64;
// P = 0xEC;
} else if (type == "384") {
output_len = 48;
c = 96;
// P = 0xCC;
} else if (type == "512") {
output_len = 64;
c = 128;
// P = 0xEC;
} else {
printf("Wrong type!\n");
}
P = 0x06;
r = b - c;
}
private:
uint64_t rot(uint64_t num, int offset);
void theta(uint64_t input[MAT][MAT], uint64_t output[MAT][MAT]);
void rho_pi(uint64_t input[MAT][MAT], uint64_t output[MAT][MAT]);
void chi(uint64_t input[MAT][MAT], uint64_t output[MAT][MAT]);
void iota(uint64_t input[MAT][MAT], int round);
void keccak_f(int round);
public:
uint8_t result[64];
uint8_t* encrypt(uint8_t *seq, int len);
};
keccak.cpp：
#include "keccak.h"
#include <cstring>
#include <cstdio>
uint64_t Keccak::rot(uint64_t num, int offset) {
if (offset == 0) {
return num;
}
return (num << offset) | (num >> (64 - offset));
}
void Keccak::theta(uint64_t input[MAT][MAT], uint64_t output[MAT][MAT]) {
for (int i = 0; i < MAT; ++i) {
theta_C[i] = 0x0;
for (int j = 0; j < MAT; ++j) {
theta_C[i] ^= input[i][j];
}
}
for (int i = 0; i < MAT; ++i) {
theta_D[i] = theta_C[(i - 1 + MAT) % MAT] ^ rot(theta_C[(i + 1) % MAT], 1);
}
for (int i = 0; i < MAT; ++i) {
for (int j = 0; j < MAT; ++j) {
output[i][j] = input[i][j] ^ theta_D[i];
}
}
}
void Keccak::rho_pi(uint64_t input[MAT][MAT], uint64_t output[MAT][MAT]) {
for (int i = 0; i < MAT; ++i) {
for (int j = 0; j < MAT; ++j) {
output[j][(2 * i + 3 * j) % MAT] = rot(input[i][j], R_CONS[i][j]);
}
}
// printf("%lld\n", output[0][0]);
}
void Keccak::chi(uint64_t input[MAT][MAT], uint64_t output[MAT][MAT]) {
for (int i = 0; i < MAT; ++i) {
for (int j = 0; j < MAT; ++j) {
output[i][j] = input[i][j] ^ ((~input[(i + 1) % MAT][j]) & input[(i + 2) % MAT][j]);
}
}
}
void Keccak::iota(uint64_t input[MAT][MAT], int round) {
input[0][0] ^= RC[round];
}
void Keccak::keccak_f(int round) {
theta(after_f, after_theta);
rho_pi(after_theta, after_rho_pi);
chi(after_rho_pi, after_f);
iota(after_f, round);
}
uint8_t* Keccak::encrypt(uint8_t *seq, int seq_len) {
uint8_t *pad_seq;
int block;
int pad_zero = 0;
if ((seq_len + MIN_PAD) % r != 0) {
pad_zero = r - (seq_len + MIN_PAD) % r;
}
block = (seq_len + MIN_PAD + pad_zero) / r;
pad_seq = new uint8_t[seq_len + MIN_PAD + pad_zero];
memcpy(pad_seq, seq, seq_len);
pad_seq[seq_len] = P;
if (pad_zero > 0) {
memset(pad_seq + seq_len + 1, 0, pad_zero);
}
pad_seq[seq_len + MIN_PAD + pad_zero - 1] |= 0x80;
for (int i = 0; i < MAT; ++i) {
for (int j = 0; j < MAT; ++j) {
after_f[i][j] = 0;
}
}
for (int i = 0; i < block; ++i) {
int pos = 0;
for (int j = i * r; j < (i + 1) * r; j += 8) {
uint64_t t = 0;
for (int k = j + 7; k >= j; --k) {
t = (t << 8) | pad_seq[k];
}
after_f[pos % MAT][pos / MAT] ^= t;
pos++;
}
for (int j = 0; j < nr; ++j) {
keccak_f(j);
}
}
for (int i = 0; i < output_len; ) {
for (int j = 0; j < 8; ++j) {
result[i] = after_f[(i / 8) % MAT][(i / 8) / MAT] & 0xff;
after_f[(i / 8) % MAT][(i / 8) / MAT] >>= 8;
i++;
if (i >= output_len) {
break;
}
}
}
return result;
}
参考文献
- Keccak官网
- Keccak算法介绍与分析 （注：本文中的padding方法和官网不一致）
- SHA-3 and The Hash Function Keccak（注：本文中的r、c的设置以及padding方法和官网不一致）
文中图片均来自参考文献[3]，伪代码均来自参考文献[1]。
