海绵函数

密码学海绵函数(sponge function)或者海绵建构(sponge construction)是一种算法。它使用有限的状态,接收任何长度的输入比特流,然后可以满足任何长度的输出。海绵函数可以在理论上面或者实做上面应用,用来架构或者实做密码学的原始函数,像是加密散列函数(cryptographic hash,参考散列函数)等等。

Illustration of the sponge construction
散列函数的海绵建构。这里pi是输入的分段,zi则是输出的分段

结构

海绵函数是由三个部分组成:[1]

  • 一个内存状态 ,包含 个比特
  • 一个能置换或者转换内存状态,固定大小的转换函数 
  • 一个填充函数(padding function) 

内存状态会分成两个区块, (大小为 比特)与 (大小为 比特)。这里的参数 又叫做转换率(bitrate),而 叫做容量(capacity)。

填充函数会在输入里面增加足够的长度,让输入的比特流长度变成 的整数倍。因此填充过后的输入可以被切成长度为 的数个分段。

然后,海绵函数运作如下:

  •  先初始化为零
  • 输入经过填充函数处理
  • 填充后输入的前面 个比特会与R进行XOR运算
  •  经过函数 转换成 
  • 如果填充后输入还有剩余,下一 比特的分段与 进行XOR运算
  • S转换成 

这过程一直重复到所有的输入都用完为止(在海棉的譬喻里面,被函数“吸收”了)。

现在海绵函数可以依照如下的过程输出(“挤出”内容):

  • 此时 里面的资料是输出的前面 个比特
  • 如果需要更多输出,先把 转换成 
  • 此时R里面的资料是输出的下面 个比特

这过程会重复到满足输出所需要的长度为止。

这里值得注意的地方是,输入绝对不会与 这部分的存储器作XOR运算,而且 这一部分存储器也不会直接被输出。 这一部分的存储器仅仅只和转换函数 相关。在散列里面,防止撞击攻击(Collision attack)或者原像攻击(preimage attack)是依靠 这段存储器作到的。一般实做上 的大小会是所希望防止等级的两倍。

应用

海绵函数可以在理论上面或者实做上面应用。在密码分析理论上,随机海绵函数(random sponge function)是一个转换函数f为随机置换的海绵函数。随机海绵函数比起经常使用的随机预言(有关预言的部分请参考预言机)满足更多加密基元(cryptographic primitives)的限制,像是有限大小的内存状态。[2]

海绵函数也可以用来建造实际的加密基元。例如,Keccak散列函数就是以海绵函数的方式创建的。Keccak散列函数使用1600比特大的版本被国家标准技术研究所(NIST)在SHA-3竞赛之中选为赢家。Keccak算法的特点在于作者所开发复杂、多次的置换函数。[3]

参考资料

  1. ^ Guido Bertoni; Joan Daemen; Michaël Peeters; Gilles Van Assche. Sponge Functions. Ecrypt Hash Workshop 2007. [2012-10-09]. (原始内容存档于2016-10-23). 
  2. ^ Guido Bertoni; Joan Daemen; Michaël Peeters; Gilles Van Assche. On the Indifferentiability of the Sponge Construction. EuroCrypt 2008. [2012-10-09]. (原始内容存档于2016-10-23). 
  3. ^ NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. NIST. 2012-10-02 [2012-10-04]. (原始内容存档于2012-10-05).