计时攻击

哈喽，大家好，我是指北君。

最近世界杯看了几场球赛，克罗地亚淘汰巴西，摩洛哥淘汰葡萄牙。两场都非常精彩，克罗地亚的坚韧令人佩服，绝境逆袭。总之这一届世界杯绝对会影响以后足球的战术打法。

言归正传哈，最近依然在搬砖哈，看到了关于计时攻击的内容，而这个又和我们常用的equals方法关系密切。然后就迫不及待的去扒一扒了。

Timing Attack ，时序攻击，是一种侧信道攻击，攻击者尝试分析加密算法的时间执行顺序来推导出密码。每个逻辑运算都需要执行时间，但是根据不同的输入值，精确测量执行时间，根据执行时间反推出密码的一些区域。

简单理解，就是破解密码的人，通过不同的输入策略组合尝试去验证密码，得到不同的执行时间，从而反推出密码的区域，从而降低破解密码的难度。

下面可以使用Java简单描述一下。

我们看一下Java中的String equals方法（Java17）

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    return (anObject instanceof String aString)
            && (!COMPACT_STRINGS || this.coder == aString.coder)
            && StringLatin1.equals(value, aString.value);
}

//StringLatin1.equals
@IntrinsicCandidate
public static boolean equals(byte[] value, byte[] other) {
    if (value.length == other.length) {
        for (int i = 0; i < value.length; i++) {
            if (value[i] != other[i]) {
                return false;
            }
        }
        return true;
    }
    return false;
}

以上方法中字符串比较一旦遇到不同的字符，那么就直接返回失败。

"adfg".equals("abcd");
"abfg".equals("abcd");
"abcg".equals("abcd");

以上的3个字符串比较方法执行时间是不同的。

执行时间第一行 < 第二行 < 第三行

假如现在我们要猜出另外一个字符串，那么如果我们去暴力穷举猜出字符串，则根据不同的字符串组合，得到的执行时间是不一样的，那么根据不同的执行时间分析，就可以知道前面几个字符串是否正确，从而缩小范围。

以上是一个计时攻击的简单例子，实际密码加密，公私钥加密算法是比较复杂的，但是也要考虑计时攻击的影响。

多年前斯坦福的教授们专门针对这些问题发表过相关的论文，下面这篇于2005年发表在《Computer networks》的期刊论证了远程网络计时攻击的可能性。

计时攻击的防御

那么对于计时攻击这种要如何防止呢，大部分的做法是使得单向加密，或者密码验证的算法执行时间不会随着输入值的不同而规律变化。换句话说就是不同的输入值的执行时间相同，或者执行时间随机分布，无法又规律判断。

2009年jdk6的一个升级中就有相关的优化来防止计时攻击。MessageDigest是java.security包里面的类，主要用于SHA或 MD5 等密码上安全的报文摘要功能而设计。最终会用到其equals方法。而这个改动就是针对equals方法。

其中关键的改动就是判断字符串相等时，不再看到不相等的字符就返回false。而是对比完所有的字符之后再返回结果。这样代码的执行时间就大致相同。

同时2021年jdk8的补丁也有相关的优化，

乍一看上面的代码已经比较完美了。但是。。。。

密码字符串的信息还有长度信息

还是有坑哈。。。。。

其实上述中的代码还有一个问题，就是不同长度的字符串的执行时间也不一样，那么如果我搞一轮不同长度字符串穷举之后，可以根据运行计算时间的不同可以推出密码的长度。再进行破解相对容易一点。

再看如今Java17中的这个方法，长度不同时也不会立马返回false，而是照常执行整个代码，这样就避免了根据执行时间先得到密码的长度。

//MessageDigest
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;
}

小结

以上就是计时攻击的一些简单内容，网络安全中的冰山一角。再次致敬这些维护JDK源码的大师们！

不断防范，不断升级才有了我们越来越安全的代码。