常数时间等于

Question

为了防止时序攻击，有时需要使用恒定时间equals。MessageDigest.isEqual没有文档说明是一个恒定时间方法，guava HashCode.equals和其他一些方法也是如此。它们都会执行以下操作：

boolean areEqual = true;
for (int i = 0; i < this.bytes.length; i++) {
    areEqual &= (this.bytes[i] == that.getBytesInternal()[i]);
}
return areEqual;

或者

    int result = 0;
    for (int i = 0; i < digesta.length; i++) {
        result |= digesta[i] ^ digestb[i];
    }
    return result == 0;

但是，谁说 JIT 在优化时不能引入短路呢？很容易发现例如areEqual永远不会再次变为真并打破循环。

---

我通过计算所有输入位的值，并将其馈送到自制的 Blackhole 中，尝试了一下 CR。

- maaartinus

Answer 1

你无法预知未来

从根本上讲，你无法预测任何语言中未来的优化器可能会或不会做什么。

为了展望未来，最好的方法是操作系统本身提供定时常量测试，这样它们可以在所有环境中得到适当的测试和使用。

这已经持续了相当长的时间。例如，libc中的timingsafe_bcmp()函数首次出现在OpenBSD 4.9中（发布于2011年5月）。

显然，编程环境需要采用这些方法并/或提供自己的函数，以确保它们不会被优化掉。

检查汇编代码

有一些关于优化器的讨论here。虽然它是针对C（和C++）的，但它实际上是与语言无关的，你只能看看当前优化器能做什么，而不能预测未来的优化器会做什么。 无论如何，他们正确地建议检查汇编代码以了解你的优化器的工作方式。

对于Java来说，由于其性质，这并不像C或C++那样“容易”，但对于特定的安全功能来说，为当前环境实际执行这些操作应该并不是不可能的。

可能可以避免

您可以尝试避免时序攻击。

E.g.:

• 双重随机化 HMAC 验证： 本质上，它为要比较的两个字符串添加了加密级别的随机性，计算输入的新哈希值，并将其与普通比较进行比较。即使最终比较泄漏了整个比较对象，加密级别的随机性结合哈希保护了您真正想要比较的内容。这里存在哈希冲突的明显风险，但它们应该非常罕见。 另请参阅：https://www.nccgroup.trust/us/about-us/newsroom-and-events/blog/2011/february/double-hmac-verification/

尽管直觉上添加随机时间似乎是正确的做法，但它不起作用：攻击者已经在时序攻击中使用统计分析，你只是增加了更多噪音。

https://security.stackexchange.com/questions/96489/can-i-prevent-timing-attacks-with-random-delays

尽管如此：如果您的应用程序足够慢，即等待足够长的时间，那么您仍然可以实现时间常数实现。例如：您可以等待计时器触发，然后才继续处理比较结果，从而避免时序攻击。

检测

使用时间常数比较的实现，应该可以将时序攻击漏洞的检测编写到应用程序中。

例如：

• 在初始化期间运行某些测试
• 作为正常操作的一部分定期运行相同的测试。

优化器可能会很棘手，因为它甚至可以改变执行顺序。但是，例如使用程序中没有的输入（例如外部文件），并运行两次：一次进行正常比较和相同的字符串，一次使用完全不同的字符串（例如异或）然后再次使用这些输入进行常数时间比较。现在您有4个时间：正常比较不应该相同，常数时间比较应该更慢且相同。如果失败：警告用户/应用程序维护者，常数时间的东西在生产使用中可能已经损坏。

一个理论的选项是自己收集实际的计时数据（同时记录失败/成功），并进行统计分析。但实际操作起来会很棘手，因为你的测量需要非常准确，而且不能进行数百万次循环，你只能处理一个比较，并且没有足够的分辨率来进行足够精确的测量...。

- user3277192

Answer 2

JIT不仅允许进行此类优化，有时它确实会这样做。这里是我在JMH中发现的一个示例错误，短路优化导致基准分数不稳定。尽管使用了&而不是&&，即使bool1和bool2被声明为volatile，JIT也优化了(bool == bool1 & bool == bool2)的评估。JIT不保证它会进行哪些优化以及哪些不会。即使您验证它按照您想要的方式工作，未来的JVM版本可能会打破这些假设。理想情况下，核心JDK库中应该有内部方法来处理这些重要的安全原语。您可以尝试通过某些技术来避免不需要的优化，例如：涉及易失性字段；应用增量累积；产生副作用，例如写入共享内存等。

但是它们也不是百分之百的防弹，因此您需要验证生成的汇编代码，并在每次重大Java更新后进行检查。

- apangin

Answer 3

您可以并且应该使用java.security.MessageDigest.isEqual(byte[], byte[])，它（至少在较新的Java版本中）被记录为用于此目的：

* @implNote
* All bytes in {@code digesta} are examined to determine equality.
* The calculation time depends only on the length of {@code digesta}.
* It does not depend on the length of {@code digestb} or the contents
* of {@code digesta} and {@code digestb}.

- eckes

Answer 4

确实，你无法预测优化器会做什么。然而，在这种情况下，你可以合理地执行以下操作：

1. 计算被比较值的异或。所需时间仅取决于值的长度。
2. 计算结果字节的哈希值。使用返回单个整数的哈希函数。
3. 将此哈希值与相同长度的零序列的预计算哈希值进行异或运算。

我认为哈希函数不是会被优化掉的东西，这是一个相当安全的赌注。而且，两个整数之间的异或运算速度是相同的，不受结果影响。

- nugae

---

返回一个 int 将导致与概率为 2**-32，即 2.3e-10 的冲突，这对于任何安全敏感的东西来说都太多了。你会将猜测秘密（像 2**-256，即不可能的机会）降低到猜测碰撞。 +++ 使用 long 将更好（并且在 64 位 JVM 上也是恒定时间），但仍然不够好。 - maaartinus

Answer 5

可以这样防止优化：

int res = 0;
for (int i = 0; i < this.bytes.length; i++) {
    res |= this.bytes[i] ^ that.getBytesInternal()[i];
}
Logger.getLogger(...).log(FINEST, "{0}", res);
return res == 0;

但是在原始代码中：

使用旧代码，可能需要使用javap进行反汇编以查看是否进行了优化。对于另一个Java编译器（如Java 9），则需要重复此操作。

JIT启动较晚，但然后您是正确的，可以进行优化：它需要在循环中进行额外的测试（这本身会减慢每个周期的速度）。

所以您是正确的。人们只能希望整个测量过程中影响微乎其微。如果有其他安全保障，则会有所帮助，即使仅是一个随机延迟失败的不等式，这总是一个很好的绊脚石。

- Joop Eggen

---

在条件语句之外加日志语句如何避免短路？ - Sleiman Jneidi

@SleimanJneidi 由于结果“res”已被记录，因此必须计算到最后，因此循环可能不会短路。 - Joop Eggen

除非你在某个时刻得到 res == -1，然后你可以退出循环。但这将是一个不同的测试，我无法想象编译器会这样做。 - maaartinus

如果结果不相等，res 将在大约 log2 的位数（约为 4）内收敛。因此，可能存在某种潜在的优化。/ 对于 32 位 ARM，我相信一个足够先进的优化器可以反转 res，使用 BICS（对反转 rhs 进行按位与并设置标志位），并利用条件指令进行优化，而不增加内部循环指令计数。 - Tom Hawtin - tackline

@TomHawtin-tackline 的一个非常好的反驳是，res 变成了 0b111...111。当然，还有经典的汇编语言。 - Joop Eggen