如何在常量时间内比较字符串？

Question

如何安全地比较两个有限长度的字符串，以保证每次比较都花费同样的时间？哈希具有时序攻击漏洞，无法使用。

有没有一种不使用哈希算法的方式来比较两个字符串，同时又不容易受到时序攻击的威胁呢？

- RoundSauce3

---

@LukasKalbertodt 这个维基百科帮了我很大忙 ^^ https://en.wikipedia.org/wiki/Timing_attack - Stargateur

为什么你认为哈希容易受到时间攻击？这难道不取决于具体使用的哈希算法吗？ - Matthieu M.

Answer 1

TL;DR: 使用汇编语言。

---

常数时间代码真的很难实现。要真正实现常数时间，你需要：

• 一个常数时间算法
• 对该算法进行常数时间实现

---

什么是“常数时间算法”？

字符串比较的例子很好。大多数情况下，你希望比较所需的时间尽可能短，这意味着在发现第一个不同之处时立即退出：

fn simple_compare(a: &str, b: &str) -> bool {
    if a.len() != b.len() { return false; }

    for (a, b) in a.bytes().zip(b.bytes()) {
        if a != b { return false; }
    }

    true
}

然而，常数时间版本的算法应该无论输入如何都具有恒定的时间：

• 输入始终应具有相同的大小，
• 计算结果所需的时间应相同，无论差异在哪里（如果有的话）。

Lukas提供的算法几乎正确：

/// Prerequisite: a.len() == b.len()
fn ct_compare(a: &str, b: &str) -> bool {
    debug_assert!(a.len() == b.len());

    a.bytes().zip(b.bytes())
        .fold(0, |acc, (a, b)| acc | (a ^ b) ) == 0
}

---

"常数时间实现"是什么意思？

即使算法是常数时间的，实现也可能不是。

如果没有使用完全相同的CPU指令序列，则在某些体系结构上，其中一个指令可能更快，而另一个指令可能更慢，那么该实现将失败。

如果算法使用表格查找，则可能会出现更多或更少的缓存未命中。

---

你能在Rust中编写字符串比较的常数时间实现吗？

不能。

Rust语言可能适用于此任务，但是其工具链却不适合：

• LLVM优化器将破坏您的算法，使其短路，消除不必要的读取，现在或将来，
• LLVM后端将破坏您的实现，选择不同的指令。

简而言之，今天，从Rust访问常数时间实现的唯一方法是在汇编中编写该实现。

- Matthieu M.

---

除了汇编语言，您认为还有哪种语言适合这样的任务吗？ - Shepmaster

@Shepmaster：我认为这不是语言问题，而是工具链的问题。我非常确定，C、C++或Rust代码的简单翻译很容易做到恒定时间...但今天的编译器很少进行简单的翻译。 - Matthieu M.

请注意：我已删除了我的答案，因此您可能需要更新提到我的答案的部分。 - Lukas Kalbertodt

Answer 2

自己编写一个安全的字符串比较算法，理论上来说相当容易。网络上有很多其他语言的实现方式可以参考。重要的是要防止优化器对你的代码进行不希望出现的优化。这里提供了一个 Rust 实现的例子，使用了这里描述的算法。

fn ct_compare(a: &str, b: &str) -> bool {
    if a.len() != b.len() {
        return false;
    }

    a.bytes().zip(b.bytes())
        .fold(0, |acc, (a, b)| acc | (a ^ b) ) == 0
}

(Playground)

当然，这个算法可以轻松地推广到所有实现了AsRef<[u8]>的内容。这留给读者作为练习；-）

---

看起来已经有一个crate提供了这种类型的比较：consistenttime。我没有测试过，但文档看起来非常好。

- Lukas Kalbertodt

---

注意：尽管编写常数时间比较很容易，但问题在于编译器优化会造成严重影响。因此，通常这种函数是用汇编语言编写的。 - Matthieu M.

@MatthieuM。非常正确，谢谢！但是这个奇怪的异或算法已经被设计成防止优化器优化东西。不幸的是，我现在没有时间验证Rust是否会以我们不想要的方式进行优化。我还是太慢了，看汇编 :< ... 请随意（使用稍微简化/不那么花哨的版本） - Lukas Kalbertodt

该代码允许攻击者通过不断变化输入，直到函数稍微变慢来恢复目标字符串的长度（该代码已经通过了第一个检查）。这缩小了继续查找的范围。 - Shepmaster

Answer 3

如果您正在寻找提供这种实现的箱子，您可以使用rust-crypto，它提供了功能fixed_time_eq。

该实现与Lukas Kalbertodt的实现非常相似。

- Elrendio