计时攻击
Timing Attack
安全的实现（计时攻击无效）：
public class Test {
private boolean safeEqual(String a, String b) {
if (a.length() != b.length()){
return false;
}
int equal = 0;
for (int i = 0; i < a.length(); i++){
equal |= a.charAt(i) ^ b.charAt(i);
}
return equal == 0;
}
}
上面是判断两个字符串内容是否相同的实现，乍一看有点奇怪：
一开始先判断字符串长度是否相等，不相等直接返回。
之后遍历字符串，对每一位通过异或操作来比较，将每次的结果和 equal 变量进行或运算，如果两个字符串相等，最后存储累积的变量 equal 肯定为0，否则为1。
整体逻辑上是没什么问题，但是效率不够好，完全可以进一步优化——在遍历过程中，如果发现有一位不同就可以直接返回，而不是全部遍历一遍。
似乎可以优化成：
不安全的实现
public class Test1 {
private boolean safeEqual(String a, String b) {
if (a.length() != b.length()){
return false;
}
for (int i = 0; i < a.length(); i++){
int equal = a.charAt(i) ^ b.charAt(i);
if (equal !=0 ) {
return false;
}
}
return true;
}
}
但 JDK 中也有一个类似的实现（不安全的比较）：
package java.security;
……
public abstract class MessageDigest extends MessageDigestSpi {
……
public static boolean isEqual(byte[] digesta, byte[] digestb) {
if (digesta == digestb) return true;
if (digesta == null || digestb == null) {
return false;
}
int lenA = digesta.length;
int lenB = digestb.length;
if (lenB == 0) {
return lenA == 0;
}
int result = 0;
result |= lenA - lenB;
// time-constant comparison
for (int i = 0; i < lenA; i++) {
// If i >= lenB, indexB is 0; otherwise, i.
int indexB = ((i - lenB) >>> 31) * i;
result |= digesta[i] ^ digestb[indexB];
}
return result == 0;
}
……
注意注释 “time-constant comparison”（常量时间比较）。
现在来说说这两种实现有什么区别
不安全的实现
假设当前使用的是不安全的 equal 方法，比较的两个字符串是 用户输入密码 和 真正正确的密码，真正的密码是 “password”，
采用穷举的暴力破解方案时：
首先会不断地枚举第一位——
| axxxxxxx
1ms |
bxxxxxxx
3ms |
cxxxxxxx
5ms |
| dxxxxxxx
4ms |
exxxxxxx
15ms |
fxxxxxxx
7ms |
| …… | ||
| yxxxxxxx
5ms |
zxxxxxxx
7ms |
|
最终通过统计发现 “exxxxxxx”的运行时间比其他密码的尝试消耗时间长，很可能就是其他密码在判断第一位不同时方法就返回了
| a | x | x | x | x | x | x | x |
|---|---|---|---|---|---|---|---|
| ↑ |
而 e 开头的字符串要判断到第二位时才返回：
| p | x | x | x | x | x | x | x |
|---|---|---|---|---|---|---|---|
| ↑ |
这样攻击者就能判断出字符串的第一位很可能是 p，然后再不断一位一位迭代下去，最终破解出密码。
安全的现实
而当调用安全的实现时：就算两个文本内容不想等，但每一次两个字符串的比对耗费的时间都会是一样的，这样就可以防止攻击者通过大量的改变输入并通过统计运行时间来暴力破解出要比较的字符串。
存疑
这个例子不太合适：现在基本没有明文密码的比对（都是MD5+salt），暴力MD5碰撞也要能够预知什么样的字典可以暴力MD5碰撞。
计时攻击对于BS结构，这种基于网络的验证，网络环境（网速）不是恒定的，服务器端的字符串比对和 HTTP请求 的时长上下浮动比起来实在不算什么。
有没有别的更合适的例子？
本地MD5摘要的比较就是，所以 security 包里的实现是安全的。
似乎也有人对 openssl 的计时攻击成功了 https://eprint.iacr.org/2016/224.pdf