如何在恒定时间内比较字符串？

Question

如何安全地比较两个有界长度的字符串，使得每次比较都花费相同的时间？不幸的是，散列有一个定时攻击漏洞。

有没有办法以不易受到定时攻击的方式比较两个字符串而不进行散列？

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 访问恒定时间实现的唯一方法是在汇编中编写所述实现。