今天看了罗岚师姐的一篇关于SHA3算法第二轮点评的文章，其中对于Shabal赞赏有佳。Check了一下NIST他们自己的第二阶段总结报告，看来对于Shabal的总评价都是“大家手笔、设计优雅、创意出众、教科书般的可证明安全”。正好最近在搞一个轻量级one-way function的设计，就花些时间看看吧。
值得一提的是，Shabal提交的设计文档那就是与众不同，沉甸甸的300多页啊~~~ 不愧是背后有法国众多财团支持的设计。研究这玩意儿就是这样，只有让researcher们吃饱了喝足了他们才能干出好的活儿来。
书归正传。这份设计文档写的非常不错，第一章基本可以作为hash设计的一个survey了，非常适合我这种没有怎么搞过hash设计的人学习、思考。这里总结如下：他们首先提了一个通用的“iterative hash function construction”。这个提纲挈领的图（列在下面，源自Shabal提交的设计文档，下同）做了一个非常到位的总结，基本上概括了现在所有已知hash function的设计方法。剩下的工作不外乎是如何把R、F、T这三个函数优化优化，提高hash的吞吐量而已。
比如说，很有名的Damgard Merkle结构（下图）其实就是这个通用框架的简化版（但不安全，已经不能用了）。后续有一些工作就是improve DM框架的，思路不外乎三个输入、中间环节和输出。对于输入，我们不能全部padding “0”了， 那样太不安全；对于中间环节，加个counter计数（像block cipher的counter mode），再有就是最后几轮迭代用不同的函数来产生“Discontinuity”的性质；对于输出，能truncated的就一定要truncated。
顺便搜了一下才发现Merkel有多牛。我们经常使用他发明的Merkel Tree, Merkel’s Puzzles, Damgard Merkel Construciton, 但搞了半天这哥们儿竟然是做纳米材料的或者说现在转行做纳米材料了~~~。还有关于Merkel的一个有趣的小故事（引自）：
关于背包算法，Tanenbaum的《Computer Networks》（4th）中讲述了一个有趣的故事：背包算法设计这Merkle曾悬赏100美金破解该算法，RSA组合中的S，即Shamir迅速破解算法并领走奖金。Merkle于是增强了算法，再次悬赏破解，奖金加到1000美金。RSA组合中的R，即Rivest又迅速破解领走奖金。此后Merkle就没再悬赏了，因此RSA组合中的另外一个人A，即Adleman也就没能拿到预期的10000美金了。从这个故事可以看出RSA这个信息安全领域的黄金组合的确超级牛叉！
除了DM结构，欧米会上有几个老外提出来了“密码学海绵函数（Cryptographic Sponges）”的概念~~~ 说这个函数有两个过程“吸收”和“挤出”跟海绵似的。本质上所有hash function都是有这两个阶段的，前面若干轮都是通过自反馈提高Linear Span，最后几轮才输出。这些老外还真是会包装自己、炒作概念啊！！
Cryptographic Sponges 结构如下图。其实我们不难看出它实际上也被包括在那个general construction里面，而且也其实是DM结构的一种变形。他用T去模仿压缩函数。实际应用中可用作hash校验、MAC、流密码。然后他们证明了一下“Indifferentiability”。 具体的可以看看他们的网页，图和slides做的不错：http://sponge.noekeon.org/。 SHA3征集的算法里面，我大致浏览了一下，也有4、5个采用了这种设计思想。
