为什么要通过计算字符的异或来比较两个字符串？

Question

前段时间我发现了这个比较两个字符串和 returns 布尔值的函数（不幸的是，我不记得它来自哪里，很可能来自某些 Python 框架） .很容易理解这里发生了什么。如果不匹配，则在 char returns 1 (True) 之间查找 xor。

def  cmp_strings(str1, str2):
    return len(str1) == len(str2) and sum(ord(x)^ord(y) for x, y in zip(str1, str2)) == 0

但是为什么要用到这个功能呢？和str1==str2不一样吗？

Answer 1

比较任何具有相同长度的字符串所花费的时间都差不多。当字符串敏感时，它用于安全性。通常用于比较密码哈希。

如果使用==，Python会在找到第一个不匹配的字符时停止比较字符。这对哈希不利，因为它可以揭示哈希与匹配的接近程度。这将有助于攻击者暴力破解密码。

这就是 hmac.compare_digest 的工作原理。

Answer 2

它似乎在字符串之间进行字符相关（XOR 和），因为它们的长度相同。在您需要知道 'similarity' 而不是相等的情况下可能需要它。也许这就是计划。作者可能想进一步扩展此功能。

Answer 3

通过 XOR 比较解决的安全问题被称为 定时攻击。 ...在这里您可以观察比较函数成功|失败需要多少时间，并利用该知识获得优于系统的优势。

有 95 个可打印的 ASCII 字符。如果您有一个 8 个字符的密码，则有 95^8 (6,634,204,312,890,625) 种可能的组合...如果正确的密码是您列表中的最后一个，并且您每秒可以尝试 10 亿个密码，则需要大约 77 天 暴力破解密码...太长了 - 所以我们需要一个快捷方式！

有无数种存储字符串的方法 - 可能有十几种常用的{长度前缀、nul 终止、...}{Unicode、UTF-8、ASCII、... }.对于这个工作示例，我将使用无处不在的 'NUL-terminated array of bytes using ASCII encoding' ...IE。 "ABC" 将存储为 "ABC"NUL 或 {65, 66, 67, 0} ...但是无论您使用什么 storage/encoding 标准，问题本质上都是相同的。

从句法上讲，有多少种语言就有多少种比较两个字符串的方法，例如。 if str1 == str2 或 if (strcmp(str1, str2) == 0) 等...但是当您查看它们的内部工作方式时，它们几乎都是一样的。下面是一些简单（但真实）的伪代码，用于执行经典（非安全）字符串比较：

index = 0
LOOP FOREVER {
    IF ( (str1[index] == 0) AND (str2[index] == 0) )  THEN  return 'same'
    IF (str1[index] != str2[index])  THEN  return 'different'
    index = index + 1
}

假设秘密密码是"BY3"NUL ...让我们尝试一些密码，并注意比较函数必须执行多少操作才能建立成功|失败。

1. "A"NUL    ... returns 'different' when 1st char is checked (A)   [zero chars are correct]
2. "B"NUL    ... returns 'different' when 2nd char is checked (NUL) [first char must be correct]
3. "BX"NUL   ... returns 'different' when 2nd char is checked (X)   [first char must be correct]
4. "BY"NUL   ... returns 'different' when 3rd char is checked (NUL) [first two chars must be correct]
5. "BY1"NUL  ... returns 'different' when 3rd char is checked (1)   [first two chars must be correct]
6. "BY2"NUL  ... returns 'different' when 3rd char is checked (2)   [first two chars must be correct]
7. "BY3"NUL  ... returns 'same' when the 4th character is checked (NUL) [all three chars are correct]

您可以看到猜测 1 在循环中第一次失败，猜测 2 和 3 在循环中第二次失败 ...猜测 4、5、6 在循环中第三次失败 ...和在循环中第 4 次猜 7 成功。

通过观察Compare函数失败所花费的时间，我们可以判断是哪个字符出错了！这意味着我们实际上可以一次猜一个字符。

同样，我们假设一个由 95 个可打印字符组成的 8 个字符的密码，我们最后的猜测将是正确的...因为我们现在可以一次猜一个字符的密码，这将需要 95*8 [760] 猜测。以每秒 10 亿次猜测的速度计算，大约需要 0.7 毫秒 才能找到密码 [眨眼大约需要 100 毫秒] ...这比 77 天具有显着优势 ...对于笑出 20 个字符密码的优势（95^20 对 95 * 20）。

那么我们如何阻止攻击者使用定时攻击呢？ [剧透：XOR]

我们需要做的第一件事是使两个字符串的长度相同；其次，我们必须始终在 returning 'same' 或 'different' 之前检查每个字符......如果不引入新的计时攻击，这将很难做到。但是，与其向您展示许多错误的方法，不如让我们看看正确的方法。

密码应（在可能的情况下）存储为哈希值...{DES、MD5、SHA-1、...} 现在已被证明存在密码缺陷，{SHA-256、SHA-3、Whirlpool , ...} 仍然很受欢迎 [2021 年 10 月] ...您可能知道所有哈希（由给定算法生成）的长度相同 ...因此，如果我们对猜测进行哈希运算并将猜测哈希与 Guess-Hash 进行比较存储哈希，我们已经解决了第一个问题 - 我们需要比较的 'strings'（字节数组）现在总是相同的长度。

其次。如何确保我们的比较函数总是花费相同的时间来做出决定......可能有很多方法可以做到这一点，但最常见的解决方案是像这样使用 XOR：

result = 0
index  = 0
LOOP WHILE (index < hashLength) {
    result = result OR ( secretHash[index] XOR guessHash[index] )
    index = index + 1
}
IF result == 0  THEN  return 'same'  ELSE  return 'different'

这样，所有对比较函数的调用都需要相同的时间运行 ...不再有时间攻击！

脚注： 对于不熟悉布尔逻辑的读者 - 继续阅读；但这里的本质是：

If A and B are the same, (A XOR B) gives a result of 0
If A and B are different, (A XOR B) gives a non-0 result

If A and B are both 0, (A OR B) gives a result of 0
If either A or B are non-0, (A OR B) gives a non-0 result

所以（看第二个代码块）第一次异或return非0（不同），结果变成非0（不同）并且永远无法return 0（相同）。

搜索“cve 定时攻击”将为您提供真实示例列表。

为什么要通过计算字符的异或来比较两个字符串？

Why compare two strings via calculating xor of their characters?

python

string

algorithm

string-comparison