重复键异或汉明距离

#1 楼

是的，您没有记错。是的，这是找到密钥长度的一种合理方法。

之所以起作用，是因为通常，明文不是统一随机的。例如，明文可以是一些以ASCII编码的英文文本，而不是随机的位字符串。如果$ X，Y $表示以ASCII编码的两个随机英语字母，则汉明距离$ \ text {wt}（X \ oplus Y）$的期望值可能是2-3位。相反，如果$ U，V $是两个随机的8位字节，则汉明距离$ \ text {wt}（U \ oplus V）$的期望值为4位，明显更大。如果您查看多个字符的序列，而不是一次查看单个字母，则差异会变得更大。

这如何适用于您的情况？


好吧，如果您正确地猜出了密钥长度，那么您的密文将由$ X \ oplus K $和$ Y \ oplus K $组成（正如Dilip Sarwate解释的那样），其中$ X，Y $来自明文分布。现在注意，这两者之间的汉明距离与$ X $和$ Y $之间的汉明距离相同，即，它是$ \ text {wt}（X \ oplus Y）$。正如我们之前所解释的那样，您可以预期这可能是$ X $长度（以字节为单位）的2-3位。
相反，如果您错误地猜出了密钥长度，那么您正在查看的密文形式$ X \ oplus K $和$ Y \ oplus K'$。两者之间的汉明距离基本上可以归结为$ U $和$ V $之间的汉明距离，其中$ U $和$ V $是均匀随机分布的（因为$ K，K'$是均匀随机分布的），因此是$ \ text {wt}（U \ oplus V）$。如前所述，您可以预期这应该是$ X $长度（以字节为单位）的大约4比特。

因此，如您所见，当您猜到汉明距离时，汉明距离要短得多密钥长度正确。

对于类似的模糊方法，请阅读巧合索引；您可以期望它在某些情况下会更有效，而在另一些情况下会更低。

#2 楼

我最近发起了Matasano加密挑战赛（又名Cryptopals），在这项练习中提出了基本相同的原则。具体来说，如果您想破坏重复密钥异或密码，请尝试找到n的值，该值可使密码文本的任意两个n长度块之间的汉明距离最小化，并且n通常对应于密码密钥的大小。

虽然该策略在特定情况下有效，但对我来说为什么它应该起作用并不明显。我已经从第一条原则进行了推理，并得出了一些结论。注意：我绝不是密码学方面的专家，而且这种说法很可能是似是而非，或者我使用的术语不正确。

从总体上讲...我相信这基本上是可行的在这种情况下，因为您要使用8位字节对英语密文进行编码，并且英语的熵远低于所有8位可能组合的熵。也就是说，英语只有26个字母，但是有256种可能的8位组合。熵似乎是通过重复键异或来保留的，因此您实质上是在寻找使它最小化的块大小。将纯文本转换为字母数字密文，此方法将无效。

更具体地讲...我认为汉明距离是一个度量标准，它可以通过重复键异或来保护基础文本的转换，因为它适用于与密码密钥长度匹配的文本块。对于较小的块和密钥，这很容易显示。例如，假设纯文本为001010，密钥为010，因此密文为011000。纯文本的两半之间的汉明距离为2，并且密文的两半之间的汉明距离也为2.我相当确定这可以缩放到任何文本和键长，再次假设您使用的是与键大小相同的块之间的距离。

现在考虑一下我上面说的话，与整个可能的字节空间的熵相比，英语的熵相当低。这意味着两个英文文本块之间的汉明距离通常小于两个随机字节块之间的汉明距离。

结合这些原理，很明显，至少在理论上，如果您选择正确的块大小/密钥大小，则密文的汉明距离将被最小化（因为明文的汉明距离已被最小化，并且可以通过xor转换幸存）。如果您没有选择正确的密钥大小，那么您所采用的汉明距离实际上是随机字节，通常会高得多。

#3 楼

遵循DW的答案，这是一个实际证明，$ \ text {wt}（X \ oplus K \ oplus Y \ oplus K'）\ geqslant \ text {wt}（X \ oplus K）$。

我们假设纯文本（分别是键）的字符是用字母$ A $（分别为$ A'$）和该字母$ D_A $（分别为$ D_ {A'} $）。
（例如小写字母和英语字母分布）。

这使我们可以将期望的规范化汉明距离写为：

$ H_R = E [\ text {wt}（X_1 \ oplus X_2）] $，如果正确猜出了密钥长度。

$ H_W = E [\ text {wt}（X_1 \ oplus X_2 \ oplus X'_1 \ oplus X'_2）] $否则。

其中$ X_i $（分别为$ X'_i $）是分布为$ D_A $（分别为$ D__）的独立随机变量{A'} $）。

现在，让我们放大一下位。

第k位$ b_ {的概率$ p_k $ i，k} $的随机变量$ X_i $设置为1是从$ D_A $提取第k位为1的字符的概率，因此pro的总和所有此类字符的能力。
（例如字母[qz]的第5位设置为1，因此$ p_5 $为$ 10/26 $（用于均匀分布）。

事实2：
n位的XOR将具有值如果位1出现奇数次则为1，否则为0。

根据这两个事实，我们可以计算第k位的预期汉明距离：


当我们对$ X_1 $和$ X_2 $进行XOR运算时：

$$ h_ {R，k} = h_ {2，k} = E [\ text {wt}（b_ {1， k} \ oplus b_ {2，k}）] = E [b_ {1，k} \ oplus b_ {2，k}] = p（\ text {1 bit set}）= 2p_k（1-p_k）$$


类似，当我们对$ X'_1 $和$ X'_2 $进行XOR运算时：当我们对$ X_1 $进行XOR运算时，b'_ {1，k} \ oplus b'_ {2，k}] = 2p'_k（1-p'_k）$$


，$ X_2 $，$ X'_1 $和$ X'_2 $，请注意，要将奇数位设置为1，您必须具有（前2位为奇数，而前2位为偶数）后2位）或（前2位为偶数，后2位为奇数）：

$$ h_ {W，k} = E [b_ {1，k} \ oplus b_ {2，k} \ oplus b'_ {1，k} \ oplus b'_ {2，k}] = h_ {2 ，k}（1-h'_ {2，k}）+ h'_ {2，k}（1-h_ {2，k}）= h_ {2，k} + h'_ {2，k} （1-2h_ {2，k}）$$

如果绘制$ h_ {2，k} $，您会看到它不超过0.5，因此$（1-2h_ {2 ，k}）$是正数，因此$ h_ {W，k} \ geqslant h_ {R，k} $。

由于期望的归一化汉明距离$ H_R $（分别是$ H_W $ ）只是每个位的预期距离$ h_ {R，k} $（分别为$ h_ {W，k} $）的总和，我们证明了当正确猜出密钥长度时，为什么它会更短=）


注1.现在，对于（$ A $，$ D_A $）和（$ A'$， $ D_ {A'} $）。

例如：
-如果纯文本和密钥是随机的小写字母，则$ H_R \约2.47位$和$ H_W \约2.50位$ 。
-如果我们改为使用英文字母频率，则$ H_R \约2.36位$和$ H_W \约2.49位$。
-如果我们在空格中添加（可能有用）〜19％怪异的ncy，$ H_R \约2.54位$和$ H_W \约2.88位$。

注2。$ h_ {W，k} $也不能超过0.5，因此如果$ h_ {R，k } $（即$ p_k $）的所有位都接近0.5，因此密钥长度检测无法正常工作。好处是“ $ p_k $所有位都接近0.5”并不意味着文本中没有统计信息。对于给定的（$ A $，$ D_A $），可以为每个字符设计一组不同的字节，以使$ p_k $每k个接近0.5，以便使密钥长度猜测更加困难=）