如何在Java中实现字符串比较,无论它们是匹配还是发生不匹配(如果有),都需要相同的时间？

Question

我想实现一个String比较函数,它不会占用不同的时间,具体取决于匹配的字符数或第一个不匹配的位置.我假设那里必须有一个提供此功能的库,但我无法通过快速搜索找到它.

到目前为止,我得到的最好的想法是将每个字符的XOR相加并返回是否为和0.但是,我很确定这对Unicode不会那么好用.我也有一个模糊的担忧,即HotSpot会做一些可以改变我的常数时间属性的优化,但我想不出一个特定的优化可以做到这一点.

谢谢.

更新:对不起,我不相信我很清楚.我不是在寻找O(1),我正在寻找一些不会泄漏时间信息的东西.这将用于比较散列密码值,如果比较所花费的时间根据第一次不匹配的位置而有所不同,那么这将泄露信息给攻击者.

Answer 1

我想实现一个字符串比较函数,它不会占用不同的时间,具体取决于匹配的字符数或第一个不匹配的位置.我假设那里必须有一个提供此功能的库,但我无法通过快速搜索找到它.

到目前为止,我得到的最好的想法是总结每个角色的异或

你看到了矛盾吗？

更新:

对于更新的,因此不同的问题:

您是否可以获得一次信息,根据两个字符串的长度,花费多少时间来比较2个字符串,根据常量和时间？

a + b*s(1).length + c*s(2).length + d*f(s(1), s(2))? 

字符串1和2是否有字符的上限？

如果时间是,取决于机器的因素,例如最长的字符串,您期望0.01ms.您可以测量对字符串进行编码的时间,并保持空闲状态,直到达到该时间,或许是兰德(10%)的时间因素.

如果输入的长度不受限制,您可以通过某种方式计算时序,这将适合典型输入的99%,99.9%或99.99%,具体取决于您的安全需求和机器的速度.如果程序与用户交互,通常会出现延迟高达0.2秒的即时反应,因此如果您的代码在0.19994秒内休眠,而在0.00006s时进行实际计算,则不会使用户烦恼.

Answer 2

我认为不及时泄露密码相关信息有两种直接可能性：

1/ 使用已知的固定字符（例如A）将密码字符串和候选字符串填充到 1K。然后运行以下命令（伪代码）：

match = true
for i = 0 to 1023:
    if password[i] != candidate[i]:
        match = false

这样，无论匹配在哪里，您总是采用相同数量的循环来进行比较。

没有必要浪费时间，xor因为您仍然可以进行简单的比较，但无需提前退出循环。

如果发现不匹配，只需将匹配标志设置为 false 即可继续。一旦退出循环（无论密码和候选的大小或内容如何，​​都花费相同的时间），然后检查它是否匹配。

2/ 只需在比较结束时添加一个大的（相对于正常比较时间）但稍微随机的延迟。例如，0.9 到 1.1 秒之间的随机值。比较所花费的时间应该被延迟淹没，并且随机性应该完全掩盖任何信息泄漏（当然，除非您的随机性算法泄漏信息）。

这还具有防止暴力攻击的额外优势，因为密码检查至少需要一秒钟左右的时间。