一 什么是Keccak
Keccak是一种被选定为SHA-3标准的单向散列函数算法。
Keccak可以生成任意长度的散列值,但为了配合SHA-2的散列值长度,SHA-3标准中规定了SHA3-224、SHA3-256、SHA3-384、SHA3-512这4种版本。在输入数据的长度上限方面,SHA-1为2的64次方-1比特,SHA-2为2的128次方-1比特,而SHA-3则没有长度限制。
此为,FIPS 202还规定了两个可输出任意长度散列值的函数,分别为SHAKE128和SHAKE256。据说SHAKE这个名字取自Secure Hash Algorithm与Keccak这几个单词。
顺便一提,Keccak的设计者之一Billes Van Assche在Github上发布了一款名为KeccakTools的软件。地址如下:https://github.com/KeccakTeam/KeccakTools
二 海绵结构
Keccak采用了与SHA-1、SHA-2完全不同的海绵结构,如下图:
Keccak的海绵结构中,输入的数据在进行填充之后,要经过吸收阶段和挤出阶段,最终生成输出的散列值。
“海绵结构”这个名字听上去有点奇怪,可以想象以下将一块海绵泡在水里吸水,然后再将里面的水挤出来的情形。同样地,Keccak的海绵结构是先将输入的消息吸收到内部状态,然后再根据内部状态挤出相应的散列值。
1 吸收阶段流程
将经过填充的输入消息按照每r比特为一组分割成若干个输入分组
首先,将“内部状态的r比特”与“输入分组1”进行XOR,将其结果作为“函数f的输入值”
然后,将“函数f的输出值r个比特”与“输入分组2”进行XOR,将其结果再次作为“函数f的输入值”
反复执行上述步骤,直到达到最后一个输入分组
等所有的输入分组处理完成后,结束吸收阶段,进入挤出阶段
函数f的作用是将输入的数据进行复杂的搅拌操作并输出结果(输入和输出的长度均为b=r+c个比特),其操作对象是长度为b=r+c个比特的内部状态,内部状态的初始值为0.也就是说,通过反复将输入分组的内容搅拌进来,整个消息就会被一点一点地“吸收”到海绵结构的内部状态中,就好像水分被一点点吸进海绵内部一样,每次被吸收的输入分组长度为r个比特,因此r被称为比特率。
通过上图可以看出,函数f的输入长度不是r个比特,而是r+c个比特,这意味着内部状态中有c个比特时不受输入分组内容直接影响的(但会通过函数f受到间接影响)。这里的c被称为容量。
2 挤出阶段流程
首先,将“函数f的输出值中的r个比特”保存为“输出分组1”,并将整个输出值(r+c个比特)再次输入到函数f中
然后,将“函数f的树池值中的r个比特”保存为“输出分组2”,并将整个输出值(r+c个比特)再次输入到函数f中
反复执行上面的步骤,直到获得所需长度的输出数据
无论是吸收阶段还是挤出阶段,函数f的逻辑本身是完全一样的,每执行一次函数f,海绵结构的内部状态都会被搅拌一次。
挤出阶段中实际上执行的是“对内部状态进行搅拌并产生输出分组(r比特)”的操作,也就是以比特率(r个比特)为单位,将海绵结构内部状态中的数据一点一点挤出来,就像从海绵里面把水挤出来一样。
在挤出阶段,内部状态r+c个比特中的容量(c个比特)部分是不会直接进入输出分组的,这部分数据值会通过函数f间接影响输出内容。因此,容量c的意义在于防止将输入消息中的一些特征泄露出去。
三 双工结构
作为海绵结构的变形,Keccak中还提出了一种双工结构,如下图:
在海绵结构中,只有将输入的消息全部吸收完毕之后才能开始输出,但在双工结构中,输入和输出是以相同的速率进行的。在双向通信中,发送和接收同时进行的方式称为全双工,Keccak的双工结构也代表同样的含义。
通过采用双工结构,Keccak不仅可用于计算散列值,还可以覆盖密码学家工具箱中的其他多种用途,如伪随机数生成器、流密码、认证加密、消息认证码等。