简单xor和s-box密码的安全性？

#1 楼

假设使用固定的S盒$ S $（即某些空间的排列）和密钥$ K $（与块大小相同）定义“块密码”，这样对块$ M $的加密为$ C = S [P \ oplus K] $。每个人都知道$ S $并可以应用和反转它（这是一个“ S-box”，而不是“ key”-如果S-box是“ key-dependent”，那么S-box本身就是一个分组密码）是的，这是另一个问题）。由于密钥具有一个块的大小，因此应该假定块足够大，足以打败对该密钥的详尽搜索（例如，我们使用128位块）。

因此，给定一个已知的纯文本块和相应的密文，攻击者可以轻松恢复$ K $：$ K = S ^ {-1} [C] \ oplus M $。除非您使用给定的密钥对单个块进行加密，否则这是很弱的，在这种情况下，这只是一次性垫。这里的S盒是一个红色的鲱鱼：作为一般规则，任何输入或输出已知的固定公共排列都可以随意“删除”，因此不会增加安全性。例如，在DES中，可以从安全性分析中抽象出“初始置换”和“最终置换”（在64位字中交换位），因为任何人都可以应用和不应用它们。如果没有S-box，我们将得到$ C = M \ oplus K $，这是OTP的著名方程。

由于固定的排列在已知值上运算的效果和消失一样好，并且因为我们通常认为攻击者知道一些明文/密文对，所以这意味着必须将S-box与明文和密文都“隔离”，才能有用。因此我们可以想象以下设计：

$$ C = K \ oplus S [M \ oplus K] $$

这是@Ethan建议作为练习研究的内容（除了他谈论16位块，因此是16位密钥，这通过穷举搜索被微不足道地撤消了；在这里，我们假设$ C $，$ M $和$ K $是128位的序列）。如果查看Ethan指向的幻灯片，您将了解到这是Even and Mansour更为通用的构造的特例，它像这样：

$$ C = K_2 \ oplus S [M \ oplus K_1] $$

，带有两个$ n $位密钥$ K_1 $和$ K_2 $。然后，John Daemen表明，尽管密钥材料的总长度为$ 2n $位，但您获得的安全性却少得多，实际上不超过$ 2 ^ {n / 2} $。 $ n = 128 $，即“ 64位安全性”，相对于当今的技术而言，它的价值是非常低的（64位穷举密钥搜索非常昂贵，但至少要用数千台计算机和5年的计算才能完成一次）。使用$ n = 256 $，我们可以希望具有128位安全性，尽管需要512位密钥材料。

但是，有两点很重要：


子键$ K_1 $和$ K_2 $应该不相关。对两者使用相同的密钥，或者仅使用允许简单代数关系的密钥，可能会导致许多其他攻击。
$ 2 ^ {n / 2} $绑定用于通用S盒，即在$ n $位块的所有排列中随机获取的排列。但是S-box是可计算的。有一段相当紧凑的代码可以同时在两个方向上运行。但是，$ n $位块有$ 2 ^ n！$个排列，这意味着，如果$ n = 256 $，则随机排列的最小表示平均至少需要$ 2 ^ {264} $位。 。这太高了（它不适合已知的Universe）。结论：该密码的实际实现将使用非常有限的S-box集合中的特定S-box，而不是通过适合几千字节操作码和常量数组的某些代码进行计算。 S盒必须具有某种结构。结构可能是可利用的，而且通常是可利用的。这样，在实践中可能很难达到$ 2 ^ {n / 2} $的理论强度。

因此，Even-Mansour方案不够“安全”。在这种情况下密码学家会做什么？他们增加了更多回合！因此，我们正在谈论的是这样的东西：

$$ C = K_5 \ oplus S [K_4 \ oplus S [K_3 \ oplus S [K_2 \ oplus S [K_1 \ oplus S [K_0 \ oplus M]] ]]]] $$

，例如5个回合。我们需要几轮？这取决于$ S $的特定不可避免的结构，还取决于$ K_i $的“差异”（实际上，我们将从主键$ K $生成$ K_i $，称为“子键”）。确定性流程-“关键时间表”-本身将具有一些可能被利用的结构）。我们希望整个过程都具有较高的效率，因此我们不能添加数千个回合，并且必须处理相对简单的$ S $。

那条路就在……AES本身。 AES具有128位块和128位主密钥，它使用10轮运算，因此使用11个子密钥。每轮$ S $是一些操作的组合，一些操作是线性的（在给定的向量空间中超过$ \ mathbb {F} _ {256} $），以及在8位块上的内部固定置换（AES规范）称为“ S-box”，而不是本文中称为$ S $的内容！）。 AES被认为是安全的。它引起了有关“相关密钥”的一些担忧：成对的密钥使相应的AES实例以相关的方式运行，可以被检测到；对于加密来说，没有什么大不了的，但是如果您想使用AES作为哈希函数的一部分，则需要注意一些事情。这是由于关键时间表中的数学结构。 Whirlpool哈希函数是从AES派生的哈希函数，并且Whirlpool设计人员要做的第一件事是用具有较少可利用性的结构（但速度也较慢）替换AES密钥计划。将块密码设计为具有（子）密钥的XOR序列，并与整个块空间的固定排列混合在一起是一种有效的块密码设计。但是，只有一个“完美”的S-box和两个子密钥，您就无法获得值得的安全性（您最多只能获得$ n $位块的$ 2 ^ {n / 2} $美元）。而且由于S-box和关键进度表都不是“完美的”，因此您必须添加更多的回合，并对必须采用的数学结构非常小心。当前具有这种结构的同类最佳设计是AES，它花费了许多智能密码学家和大量时间来真正建立对其安全性的信任。

#2 楼

我将忽略问题的“ CBC”部分，重点关注“ s-box和异或密码的优缺点是什么。我将假设s-box的大小小于消息的大小。块大小，因为任何具有等于s-box大小的密码的密码都将具有足够小的块大小以致被强行强制使用。

使用xor和s-box我们需要一些将消息块中的信息“混合”或散布到密文块中的所有位的方法，通常这种方法是使用置换来完成的，就像在置换置换网络中所做的那样。在问题的范围内，不使用置换来混合跨替换边界的位的密码将很容易受到暴力破解，因为密文块可以分成多个块，并且每个块都可以独立地受到攻击。

编辑：对方案的这些攻击适用于原始方案（在问题的底部发布），可能不适用于他是新方案（尽管它们是通用的攻击方法）。

我非常喜欢这个问题，因为它是构成强分组密码和弱分组密码的核心。如果我在理解您的方案时犯了错误，请立即纠正我。以下是强大的分组密码可以防止的设计缺陷：

已知的明文攻击-假设存在反向s框$ S ^ {-1} $，那么最后步骤$ C_n = S [C_n] $始终是攻击者可逆的。倒数第二个步骤只有256种可能性，因为我们知道$ S ^ {-1} [C_n] $，我们可以检查所有可能性。现在我们知道了回合密钥的几位（这很糟糕，我们将在下面讨论），我们也知道$ S [M_n \ oplus k_r] \ oplus C_ {n-1} $的结果，我们将其称为$ R_n = S [M_n \ oplus k_r] \ oplus C_ {n-1} $。这确实很糟糕，因为密文$ C_ {n-1} $是公共知识，而$ S [M_n \ oplus k_r] $是可逆的。鉴于这两个事实，我们可以找到$ M_n \ oplus K_r $由

$$ S ^ {-1} [R_n \ oplus C_n] = M_n \ oplus K_r $$

给定一个已知的明文$ M_n $和$ M_n \ oplus K_r $，我们将学习循环键$ K_r $。正如我将在下面讨论的那样，回合密钥为我们提供了完整的$ K $密钥，它使我们可以解密其余消息。

弱密钥调度-旋转不会混淆回合键（$ k_r $）。请考虑以下三种攻击：


弱密钥-有人选择了在某些或所有旋转下都是相同密钥的密钥，例如，考虑密钥$ 00000 ... 000 $或键$ 010101010 ... 01010 $。在这种情况下，每一轮或一定比例的轮次使用相同的密钥，使攻击变得更加容易。
圆键可转换为完整键-给定圆键$ K_r $，我们可以轻松地进行反向旋转以获得完整键$ K $。因此，打一轮（最后一轮）会打断所有回合。
相关按键攻击-相关按键具有相关的圆形按键，只是固定旋转不同，因此它们具有相同的1，这些1之间的距离相同等等...这很糟糕。

舍入密钥的数量与消息块的数量有关-如果我正确阅读您的方案，则每个舍入密钥将用于不同的消息块。即$ K_0 $用于$ M_0 $，$ K_1 $用于$ M_1 $，依此类推。如果仅加密一个块，则仅执行一轮。这是非常危险的，因为您不会对每个密文块执行16个密码回合，而是每个密文块执行1个回合，这意味着从输出位确定输入位的方程将非常短且易于求解。我也怀疑您会在这么多回合中获得足够的有源S盒。和最安全的方案，尽管实际上仍然不安全。

$$ C_n = S [K \ oplus M_n] \ oplus K $$

其中$ S $是16位s-box，块大小也为16位。

#3 楼

正如我在评论中已经说过的，这里您所拥有的并不是通常所说的分组密码。

（标准）分组密码是一对函数$$ E：K \ times M \ to M \ text {and} D：K \ times M \ to M $$
这意味着$ E $将$ K $的元素和$ M $的元素作为输入，并给出$的元素M $作为输出–与$ D $相同。
（其中$ K $称为键空间，$ M $称为“块空间”），这样对于$ y \ in K $和$ x \ in M $，我们有$$ D（y，E（y，x））= x。$$

通常$ K $和$ M $是形式为$ K = \ {的有限集0,1 \} ^ k $和$ M = \ {0,1 \} ^ m $，其中$ k $被称为密钥大小，$ m $被称为块大小。 （但是可以从中构造其他块类型的块密码，请参阅“保留格式的加密”。）

然后我们评估原始$（E，D）$的安全性（考虑密钥）秘密），然后再将分块密码调整为一种操作模式（然后它本身就可以独立于密码进行安全评估）。

您正在使用的是功能对signature
$$ E，D：K \ times I \ times M \ times M \ to M $$
（这里我是一些索引空间–在您的情况下$ I = \ mathbb Z_m = \ { 0，...，m-1 \} $就足够了，其中$ m = 256 $是块大小，但是我们也可以使用$ I = \ mathbb N $，这是所有自然数的集合。） >
即加密函数$ E $和解密函数$ D $都以一个密钥，一个索引和两个消息块作为输入，并输出一个消息块。这些函数应具有以下属性：
$$ D（y，n，c，E（y，n，c，x））= x \ qquad \ forall y \ in K，n \ in I，c \ in M，x \ in M 。$$

为加密和解密功能提供相同的密钥，索引和“附加块”，解密功能只是将提供给加密功能的原始明文退还给您。

诸如此类的功能对称为可调整块密码，尽管通常该调整小于密钥和块。 （在您的情况下，调整将是对$（n，c）$。）一个已知的可调整分组密码的示例是Threefish密码，该密码被用作Skein哈希函数（SHA-3中的一个）内部的基元。然后在特殊模式下使用（不是CBC，虽然看起来相似），其中块号用作$ n $输入，前一个密文块用作$ c除了密钥$ y $外，$输入（用于加密和解密）–我们可以将其称为“密文-调整链”模式。

现在，您有很多事情要做：


为您的密码类型定义一个合适的安全性概念。
确保您的具体密码具有这些安全性
使您可以确信，您提供的链接模式密码本身是安全的，具有将其用于消息加密的必要属性。

，这比定义分组密码（通常意义上）和使用标准密码模式要复杂得多。操作（已经带有安全证明），因此成功的可能性较小。此外，由于这是非标准模型，因此您可能会较少地进行密码分析。