如何检查排列是否随机

#1 楼

$ \ mathbb Z / n \ mathbb Z $的排列最多$ n \ cdot（n-1）$形式为$ x \ mapsto ax + b $：如果$ n $是素数，则有$ n- $ a $的1 $选择和$ b $的$ n $选择，这是一个排列。 $ \ mathbb Z / n \ mathbb Z $总共有$ n！$个排列。因此，即使$ n $大小适中，均匀随机排列具有这种形式的概率也可以忽略不计-概率最大为$ n \ cdot（n-1）/ n！ = 1 /（n-2）！$，随着$ n $的增长，它很快变得很小。例如，对于$ n = 64 $，此概率已经小于$ 1/2 ^ {256} $，以密码学术语来说，该概率不是平方的平方。



只需在两个不同的输入上查询并求解$ a $和$ b $，然后在第三个点上对其进行检查，您就可以放心地验证它是否具有这种形式，从而使oracle可以访问该排列第四点，等等，以查看它们是否匹配。当然，在$ x \ mapsto ax + b $形式的替代假设下，检验的统计功效是最大可能的：1.


您可以放心地说您的朋友关于具有这种形式的排列（例如8位排列，您可以验证所有256个输出），他们还不是很满意。但是他们声称他们是随机选择的。

对于8位排列，如果他们实际上确实确实随机地均匀选择了排列（错误警报率或“统计意义”），则错误地指责您的朋友的概率低于$ 1/2 ^ {256} $，相当于'$ p <.0000…00001 $'（77个零）。


但是，如果您在不了解排列的情况下设计了测试，则仅适用于此特定测试。如果您的朋友给您一个排列，并且您根据排列设计了一个失败的测试，那可能并不意味着什么-对于任何特定的排列选择，许多错误警报率较低的测试都将失败。而且，如果将许多测试串联在一起，以便其中任何一个都会发出警报，那么虚假警报率就会上升，这是“ $ p $值黑客”或“分叉路径的花园”的标准结果。 >

此问题类似于围绕散列函数Стрибог（Streebog）的问题，该函数来自俄罗斯联邦政府标准ГОСТР34.11-2012（也是RFC 6986）和分组密码Кузнечик（Kuznyechik） ，来自ГОСТР34.12-2015（英语；也为RFC 7801）。

2015年，Alex Biryukov，LéoPerrin和Aleksei Udovenko在S盒中发现了一种非凡的结构-排列为8-当Perrin等人（美国）将Streebog设计人员维护的位串通过在统一随机S盒（存档）上进行拒绝采样来随机选择时。确定了结构，他们认为设计师的故事是不可信的，因为这里有256美元！ \ approx \ sqrt {2 \ pi \，256 \，}（256 / e）^ {256} \ approx 2 ^ {1684} $可能的S盒，其中只有大约$ 2 ^ {82} $简洁明了具有特殊结构的描述。

'但是，您反对，'知道我的置换，即使我确实确实随机地均匀选择它，也可以发明任何包含置换的微小置换。然后，您可以使用班级的低概率声称我必须从该班级中故意选择了我的排列，而不是靠运气猜测！这根本没有任何意义！”（本质上，这是设计师在几周前的一次ISO标准化会议上，根据LéoPerrin的说法声称他们不是在撒谎。） >
因此，Perrin将其放入codegolf.SE，其参与者提出了各种排列的简短描述，包括一个78字节（或624位）的AMD64指令序列。

一个编码高尔夫球的练习很有趣并不是那么多，因为可以发明一个较短的程序（例如，用于计算机的1位程序，如果该程序为0，则计算S-box；如果该程序为1，则返回零），但是因为据推测，AMD64指令集是在不了解所选S-box的情况下进行设计的-如果Streebog设计人员确实确实从随机排列的样本中随机抽样以选择S-box，则有可能获得一个接受78字节/ 624位的信号AMD64指令集中的描述最多为$ 2 ^ {624} \！/ 2 ^ {1684} = 1/2 ^ {1060} $。当然，Streebog设计师有一些拒绝采样的标准，但是即使他们以这种方式经历了五百亿个候选项目（小规模，大约$ 2 ^ {60} $），概率仍然会小于$ 1/2 ^ {1000} $。


另一种查看方式是：



想象一下写下所有$ {\ approx}的序列2 ^ {1684} $个8位排列，将它们标记为$ 1，$ $ 2，$ $ \ dotsc，$ $ 2 ^ {1684}-\ mathit {whatever} $。放入它们的顺序无关紧要；您可以按照自己想要的顺序放置它们，只要您这样做就可以了，而不必考虑我将来要做的事情。

如果然后我随机地均匀地选择一个排列，则有1/2的机会会出现在序列的前半部分。它有1/4的机会会出现在序列的上半部分（即第一季度）中。一般而言，上半年的上半场有$ 1/2 ^ n $的机会……上半年的上半场（$ n $倍）—与掷硬币$ n $倍的可能性相同每次都会浮出水面。如果我想通过随机地均匀地尝试直到一个工作而在该区域中找到一个排列，则我必须尝试的排列的预期数目约为$ 2 ^ n $。


现在假设写出所有字节字符串：（空），0x00，0x01，0x02，…，0xff，0x00 0x00，0x01 0x00，0x02 0x00，…，0x00 0x01，0x01 0x01，0x02 0x01等。其中一些是有效的AMD64指令序列。一些有效的AMD64指令序列实现置换（例如，置换AL的值，而忽略所有其他体系结构状态）。

您肯定需要至少211个字节来覆盖所有置换，因为如果只有210个字节= 1680位，则8位排列比210个字节的序列要多。您几乎肯定也需要超过211个字节，因为大多数AMD64指令序列不计算置换-但您不需要超过256个字节，因为您可以使用ROM和ROM中所有输入和输出的256字节表然后使用一两个MOV指令。

因此，您现在已经通过枚举AMD64指令序列来列出了所有8位置换的序列。通过某种方式，据称通过对8位排列的统一随机选择进行拒绝采样，设计人员发现一个位于上半部分上半部分的前半部分…此序列上半部分中，迭代了1000次，一个事件的概率小于$ 1/2 ^ {1000} $-即使他们首先拒绝了五百亿候选人。


如果您写出任何一千次抛硬币的结果（THTTHHHTHT…），然后看着赌徒在看硬币的时候将硬币掷出一千次，精确地符合您的序列，您是否会相信他们正在抛硬币，还是您会开始怀疑它们可能擅长倒硬币以达到他们想要的方式？


当然，原则上，这仍然可以幸灾乐祸：通过在分叉路径的花园中四处逛逛不同的语言，我们也许可以找到一种语言，其中偶然发生的排列偶然出现在序列中……通过大约$ 2 ^ {990} $美元的不同编程来购物语言将错误警报的可能性从$ 2 ^ {-1000} $增加到千分之一$ 2 ^ {-10} $。但是（a）codegolf.SE尝试使用$ 2 ^ {990} $种不同的编程语言是不合理的，并且（b）除了AMD64指令外，现在还用许多语言对同一S-box进行了描述，所有这些语言都是小于200个字节，包括C，C＃，JavaScript，Rust和Python。

还有一个假设：像一个赌徒，他们可以按照自己的方式制作硬币（实际上很容易！），Streebog设计人员可能使用了一种生成S-box的方法，该方法可以实现紧凑，高效的实现，而他们只是没有告诉任何人。这种方法的结果，即使是随机的，也很可能在现有的编程语言中有许多简短的描述。在贝叶斯分析中，无论我们为假设$ \ text {结构化} $和$ \ text {均匀随机} $分配的先验优势比（即，两个先验假设的相对合理性），我们都可以写出后验优势按照贝叶斯规则的先验比值比和似然比的比率：

\ begin {multline *}
\ frac {\ Pr [\ text {structured} \ mid \文本{78字节代码高尔夫}]}}
{\ Pr [\ text {均匀随机} \ mid \文本{78字节代码高尔夫}]}} \\
= \ frac {\ Pr [\ text {结构化}]} {\ Pr [\ text {均匀随机}]}}
\ cdot
\ frac {\ Pr [\ text {78字节代码} \ mid \ text {结构化}]}
{\ Pr [\ text {78字节代码高尔夫} \ mid \ text {均匀随机}]} ..
\ end {multline *}

显然很难量化$ \ Pr [\ text {78字节代码golf} \ mid \ text {structured}] $在没有明确了解Streebog设计师可能考虑的结构的情况下，但是，我们可以说存在一种合一（$ 10 ^ {100} \ approx 2 ^ {332} $）的可能性，这是一种78字节代码的高尔夫解决方案，采用一种广为人知的广泛编程语言Streebog设计人员使用的方法。在这种情况下，我们可能会测量代码高尔夫的幅度，以此作为结构假设在统一随机假设上的证据-似然比，即后验优势比与先验优势比的比率，以分贝为单位- />
\开始{multline *}
10 \ log_ {10}
\ frac {\ Pr [\ text {78字节代码高尔夫}} \ mid \ text {structured}]}
{\ Pr [\ text {78个字节的代码，高尔夫}} \ mid \ text {均匀随机}]} \\
\ leq 10 \ log_ {10} \ frac {2 ^ {-332} } {2 ^ {-1000}}
= 10 \ log_ {10} 2 ^ {790}
\ approx 2000 \，\ mathrm {dB}。
\ end {multline *}

为了清楚地看待这个数字，我们在接受典型的消息身份验证代码中的消息而不是将其视为伪造消息之前在加密中要求的证据数量超过$ 300 \，\ mathrm {dB} $ -请记住，分贝是对数刻度。 （有关测量以分贝为单位的两个假设之间的证据权重的更多信息，请参阅Jaynes的书，特别是第4章。）

当然，这是对证据的非常启发式的量化-实际上，它主要应作为对贝叶斯推理形式的说明。也许还有其他一些假设没有被该分析考虑-例如，Streebog的设计师在据称执行Fisher-Yates随机排列以生成排列时仅使用了特别糟糕的PRNG，而没有意识到他们正在探索子空间与AMD64指令集有有趣的关系。

练习：假设Streebog设计人员可能使用的合理的PRNG，并将其扩展到多假设贝叶斯分析。


有关背景和参考的更多信息，请参阅LéoPerrin的网站以及到目前为止在ASIACRYPT 2019上的故事。

#2 楼

鉴于俄罗斯密码库兹涅奇克（Kuznyechik）的S盒中存在可疑图案，最近出现了这个精确问题。请参阅：


Xavier Bonnetain和LéoPerrin和Tian Shizhu：异常和向量空间搜索：S-Box分析工具，Asiacrypt 2019


作者选择量化这种排列偶然发生的可能性的一种方法是找到实现排列的最小程序。在这种情况下，排列在8位上，所以有256美元！ \ approx 2 ^ {1684} $可能的排列。但是，由于该排列有624位机器代码实现，因此在代码大小的度量范围内，只有$ 2 ^ {625} $个排列非常简单（或更简单）。换句话说，随机采样排列具有如此小的实现的机会小于$ 2 ^ {-1000} $。