具有定点自由排列的加密算法是否固有存在缺陷？

#1 楼

所有具有定点自由排列的加密算法是否都固有存在缺陷？可知和可检测。

这违反了多个现代语义安全性定义。例如，这意味着具有重复符号的明文与没有明文的明文很有可能区分开。这意味着您很有可能确定不包括明文的内容，尤其是在您可以观察到多种通信的情况下。 />


是否可以通过数学证明所有定点自由置换算法都可以通过“比强力更快”的攻击来破坏？



它总是使猜测明文更加容易（根据问题1的答案），但是并不一定使获得原始密钥（bruteforce通常指的是）更容易。您通常不能肯定地说出没有密钥的原始明文是什么，但是通常您可以接受有根据的猜测。

#2 楼

所有具有定点自由排列的加密算法是否本身就有缺陷？



不，它们不是固有缺陷。 br />请考虑以下密码：假设$ k_0 $是AES-256的密钥，而$ k_1 $是假设的高级排列标准ADS-256的密钥。要加密$ n ^ {\ mathit {th}} $消息$ m $，密文为$$ c = m \ oplus \ bigl [\ operatorname {ADS} _ {k_1}（\ operatorname {AES} _ {k_0 }（n \ mathbin \ | 0））\ mathbin \ | \ operatorname {ADS} _ {k_1}（\ operatorname {AES} _ {k_0}（n \ mathbin \ | 1））\ mathbin \ | \ cdots \ bigr]。$$也就是说，我们使用AES256-CTR加密$ m $，但是我们也首先使用ADS置换CTR模式垫的每个块。

如果广告128-正如我为AES256-CTR所做的广告所述，此密码的比特安全级别，这意味着破坏任何数量的目标之一的攻击的预期成本至少为$ 2 ^ {128} $比特操作，*显然，这可以实现只要AES256-CTR都能达到安全级别：我们还以独立的排列方式再次置换每个块这一事实并不能降低攻击成本。

当然，这并不意味着使用排列方式是设计密码系统的有效方法！同样，使用像AES256-CTR这样的置换方法不一定是设计流密码的有效方法：使用非置换函数便宜得多，因为反方向并不重要。 >用排列代替置换可以有所作为吗？显然是的：如您所见，这直接导致了对现实世界中的密码系统的实际攻击，并带来了严重的后果，如果排列不限于乱序，这种攻击是不适用的。但是，它能带来多大的不同呢？与AES相比，Enigma使用的字母非常小，例如AES，其128位块的“字母”具有$ 2 ^ {128} $个“字母”。如果我们将128位置换的协议替换为128位置换，它会变得不安全吗？

很难知道$ \ operatorname {AES} _k $是否是任何置换的一种$ k $-在理想密码模型中，基本上可以保证存在一些$ k $，使得$ \ operatorname {AES} _k $是一个排列，因为所有排列中的大约$ 1 / e $是排列；但是一种确定$ \ operatorname {AES} _k $是否是任何特定$ k $的错位的方法，在AES上是一项了不起的理论发展，即使它没有导致攻击。

由于很难确定$ \ operatorname {AES} _k $是否是任何特定键$ k $的排列，因此从直观上看，对具有较大随机排列的系统的攻击不会比对具有较大随机排列的系统；如果可以的话，那么我们可以判断输入是旧的排列还是排列。我们可以将这种直觉形式化并量化。事实证明，用置换来代替排列不会对安全造成太大的损害，除非像Enigma这样的安全性已经非常低了，它对安全性的危害远不像对实例化协议时所做的那样将置换替换为函数一样具有像AES这样的分组密码。


量化对安全性的影响。
假设$ \ pi $是$ b $位字符串的统一随机排列，而$ \ delta是统一随机排列。我们是否可以为所有随机决策算法$ A $设置$ \ Pr [A（\（delta）] $的界限，以$ \ Pr [A（\ pi）] $表示-攻击涉及置换或重排的密码系统，使得对Oracle的查询数量有限的$ q $？

考虑$ F $与$ q $查询有关的事件，$ \ pi $有一个固定点。如果没有发生$ \ lnot F $，那么就好像我们已经提交了所有查询，但显然$ \ Pr [A（\ pi）\ mid \ lnot F] = \ Pr [A （\ delta）] $。因此，

\开始{align}
\ Pr [A（\ pi）]
＆= \ Pr [A（\ pi）\ mid F] \，\ Pr [F]
+ \ Pr [A（\ pi）\ mid \ lnot F] \，\ Pr [\ lnot F] \\
＆= \ Pr [A（\ pi）\ mid F ] \，\ Pr [F]
+ \ Pr [A（\ delta）] \，\ Pr [\ lnot F] \\
＆\ leq \ Pr [F] + \ Pr [A （\ delta）]。
\ end {align}

因此，$ \ Pr [A（\ pi）]-\ Pr [A（\ delta）] \ leq \ Pr [ F] $。相反，$ B = \ lnot A $也是进行$ q $查询的任意随机算法，其中$ \ Pr [B（\ mathcal O）] = 1-\ Pr [A（\ mathcal O）] $对于任何Oracle $ \ mathcal O $，因此该范围也适用于$ B $，因此$$ \ lvert \ Pr [A（\ pi）]-\ Pr [A（\ delta）] \ rvert \ leq \ Pr [F] 。$$

什么是$ \ Pr [F] $，即在$ q $查询中的固定点绊到统一随机置换的概率？假设它们都是截然不同的-显然重复查询只能减少$ \ Pr [F] $，我们正在寻找一个上限。假设$ F_i $是$ i ^ {\ mathit {th}} $查询为固定点的事件：$ \ pi（x_i）= x_i $。假设$ N_i $是第一个$ i-1 $查询都不是固定点的事件：$ \ pi（x_1）\ ne x_1，\ dots，\ pi（x_ {i-1}）\ ne x_ {i -1} $。对于单个输入，输出是均匀分布的，因此我们有$$ \ Pr [F_i] = \ Pr [\ pi（x_i）= x_i] = 1/2 ^ b。$$事件$ F $可以写为：$ N_1 $和$ F_1 $，或者$ N_2 $和$ F_2 $，或者$ N_3 $和$ F_3 $，等等。按照链式规则，$$ \ Pr [F_i，N_i] = \ Pr [F_i \ Mid_N_i] \，\ Pr [N_i]。$$现在让我们找到$ \ Pr [F_i \ mid N_i] $：在这种情况下，给定$ N_i $，则有$ i-1 $可能的$ \ pi（ x_i）$排除了$ b $位的$ 2 ^ b $字符串中的字符串，因为它们已被$ \ pi（x_1），\ dots，\ pi（x_ {i-1}）$覆盖。因此，假设先前没有查询到，则$ x_i $是$ \ pi $的固定点的条件概率为$$ \ Pr [F_i \ mid N_i] = \ frac {1} {2 ^ b-（i- 1）}，$$，因此

\ begin {align}
\ Pr [F]
＆= \ sum_ {i = 1} ^ q \ Pr [F_i， N_i] \\
＆= \ sum_ {i = 1} ^ q \ Pr [F_i \ mid N_i] \，\ Pr [N_i] \\
＆\ leq \ sum_ {i = 1} ^ q \ Pr [F_i \ mid N_i] && \ text {（因为$ 0 \ leq \ Pr [N_i] \ leq 1 $）} \\
＆= \ sum_ {i = 1} ^ q \ frac { 1} {2 ^ b-（i-1）}。
\ end {align}

因此只要$ q \ leq 2 ^ {b-1} $ $$ \ lvert \ Pr [A（\ pi）]-\ Pr [A（\ delta）] \ rvert \ leq \ Pr [F] \ leq \ frac {2 q} {2 ^ b} $$给予较高的信心（如果我在上面的数学中没有犯任何错误），将统一的随机排列替换为统一的随机排列不能将安全性降低的程度不超过查询数量呈线性的一小部分排列。

为了正确理解这一点，我们经常使用AES（排列家族）来实例化为统一随机函数设计的协议，这些函数不限于排列。有一个标准定理，$$ \ lvert \ Pr [A（\ pi）]-\ Pr [A（f）] \ rvert \ leq \ frac {q ^ 2} {2 ^ b}，$$其中$ f $是一个统一的随机函数，但在标准应用（例如AES-CCM和AES-GCM认证密码）中，我们可以容忍更大的二次边界。换句话说，使用排列而不是排列比使用排列而不是函数要少得多。

当然，对于块大小$ b = 5 $，您可能会习惯于最多可将32个字母置换成拉丁字母，如果您有超过16个查询，此界限将不会产生高置信度，也不会产生任何置信度-您显示的表有31个！


*密钥长于128位的事实并不重要-就像任何具有128位密钥的分组密码一样，AES-128本身也不提供128位安全级别，因为通用密钥的成本只要您有多个目标，对具有128位密钥的分组密码的攻击就基本上少于$ 2 ^ {128} $，这就是为什么我建议如果必须使用AES，则使用AES-256获得128位安全级别。重要的是安全性要求，而不是密钥大小。

#3 楼

将加密运算符从$ \ {0,1 \} ^ n \到\ {0,1 \} ^ n $进行分组。每个密钥在所有可能的排列$ n！$中选择一个排列，如果将$ 2 ^ {128} $与$ 128 ^ {128} $比较，对于AES这样的分组密码来说，这是很小的。 br />

其中之一是身份，我们不知道该选择哪个密钥。我们甚至不知道它是否可以通过键空间$ 2 ^ {128}，2 ^ {196}，$或$ 2 ^ {256} $之一选择。

其中许多键值很小固定的元素。仍然，我们不知道...
他们中的许多人只有一个固定点，即，输出只有一个输入是相同的，我们不知道可以通过按键选择。

到目前为止，还没有人找到与AES类似的东西。如果发现这是一篇好文章。如果您将好的分组密码与随机的密码区分开，那也是一篇不错的文章。例如；


根据Kaliski等。 Bosdanov等人的话，DES就像一组随机选择的排列一样。
al：完整AES的Biclique密码分析。

当时的Enigma的设计者可能认为，对于基于字母的加密具有身份是一个弱点。除其他缺陷外，它还用于密码分析中。仅使用此缺陷无法在蛮力方面帮助您。最好忽略if条件。很难进行攻击。此属性是分组密码的密码（完整回合）属性。线性和差分攻击在回合功能上起作用，并尝试将偏见带入更多回合。因此，相反的方式。如果有人可以使用它来执行攻击，这是另一篇文章。

#4 楼

这里有三个不错的答案，每个答案都经过深思熟虑的论点支持。在我看来，不仅很难区分无定点的加密映射和非定点的加密映射，如@SqueamishOssifrage的答案所示，而且不是纯加密映射$ E（k，x）$用于在许多情况下，但偏移量为$$ E（k，x + a）$$，其中$ a $源自IV，取决于操作模式等。即使纯映射图是不带固定点的，派生图也可能不是（由于非线性）。