c++ - 通过时间比较猜测字符串。是否可以？

Question

我想知道一个奇怪的想法:给你一个算法，它接受一个输入字符串并将它与一个你不知道的字符串进行比较。该算法只是一个微不足道的比较，一次一个字符。当找到不匹配的一对时，返回 0。否则返回 1。

你能用提供的算法在多项式时间内猜出 secret 字符串吗？

当字符串不匹配时，给出答案 0 所用的时间少于返回 1 所用的时间，因为需要进行的比较更少。涉及的时间非常少，因此您可以多次尝试单个实例以获得更准确的估计。估计所花费的时间，我们可以获得有关 secret 字符串的信息。如果这正常工作，我们可以在多项式时间内一次猜测字符串一个字符。因此，如果这可能发生，我们可以尝试某种逐个字符的暴力攻击。

这有意义吗？还是我误解了什么？

提前致谢。

Answer 1

如果您可以输入自己的字符串进行比较，或者只是观察足够多的字符串(不是您选择的)与 secret 字符串进行比较，则您可以猜出 secret 字符串，如果字符串比较已经写在以使其执行时间揭示有关 secret 字符串的信息的方式。

这是加密软件可能存在的一个已知弱点，现在编写的所有严肃的加密软件都避免了这个弱点。

例如，为了避免泄露有关其参数的信息，可以编写一个函数来测试两个缓冲区是否相同或不同:

int crypto_memcmp(const char *s1, const char *s2, size_t n)
{
  size_t i;
  int answer;
  for (i=0; i<n; i++)
    answer = answer | (s1[i] != s2[i]);
  return answer;
}

您可以使用多种技术来检查一段代码是否通过定时攻击泄露 secret 。我写了如何用静态分析来做 here但这是基于之前使用 Valgrind 的想法(动态分析)here .

请注意，它远不止于此。 This article展示了您甚至不需要执行路径来依赖泄漏信息的 secret 。在随后访问的一些数组索引的计算中使用该 secret 就足够了。在现代计算机上，这会改变执行时间，因为缓存将使对相似索引的两次连续访问比对彼此相距较远的索引的两次连续访问更快，从而揭示有关 secret 的信息。