如何检查函数是否提供完全扩散？

Question

在“Skein Hash函数家族”一文中，作者写道：

混合/置换结构已被设计为提供完全扩散9轮3-256，10轮3-512，和11轮3-1024。

他们怎么知道的？是否有这样的结构设计规则，可以保证一定程度的扩散，并在那里使用(然后他们可以直接估计所需的子弹数)？或者他们用实验测量扩散？

顺便说一句，他们还写道：

我们设计了Skein，使每个级别的扩散最大化，并且定义了足够高的子弹数量，以便允许许多完全扩散。对于Skein-512 ( Skein-256为9轮，Skein-1024为11轮)，每个输入位位置都会影响到每个输出位位置，因此该算法被指定为7-8个全扩散。相比之下，AES-128和Twofish只有5个完全扩散.

所以也许他们就是这么想出来的。但是如果不进行精确的分析，我仍然不清楚这一点，特别是因为混合函数在Threefish中是如此的简单，并且没有比混合更多的东西。

Answer 1

扩散和混合一样。

请按建议阅读第8.3节。对于这一简单的结构，它的大部分依赖于旋转常数的选择，而这些参数是用进化算法进行实验优化的。

在AES中，MDS码的使用意味着8个字节中的5个总是“活动的”(参数[n,k]=[8,4]的MDS码的最小重量/距离是d=n-k+1=5.)，这意味着您得到了该类型的扩散(在线性混合下，由于MDS在d上的界限而可能达到最大)。

• 一个非零字节( (a_{i,j})_{i=1,\ldots,4})将至少变成4个非零字节( (b_{i,j})_{i=1,\ldots,4})
• 2个非零字节( (a_{i,j})_{i=1,\ldots,4})将至少为3个非零字节( (b_{i,j})_{i=1,\ldots,4})
• 3个非零字节( (a_{i,j})_{i=1,\ldots,4})至少为2个非零字节( (b_{i,j})_{i=1,\ldots,4})
• 4个非零字节( (a_{i,j})_{i=1,\ldots,4})将至少为1个非零字节( (b_{i,j})_{i=1,\ldots,4})

在MixColumns中的每个列中。

为了进一步解释，单例界维基百科指出，对于符号字母表上的任何具有q元素的代码，最小距离(因此，对于线性码的最小权重，即非零分量的数目)满足d\leq n-k+1 ，其中n是码字的长度，k是代码的维数。MDS是最大距离可分的，即最优，即给定n,k参数的最大可能最小距离。

这里有q=2^8,，因为我们认为每个字节都是一个代码符号。由于b's的列是通过将a's列与MDS矩阵相乘而得到的，因此该码中的两列构成了码字，从而保证了d=n-k+1=5中至少有5个字节在b‘D31列和相应的a’列中是非零的。

这是代数设计。在Skein规范中，他们为AES使用了一些奇怪的表达式5完全扩散，大概与这个5个非零字节的值有关。

有关AES混合设计的更多细节，请参见这里。