Timing Attack

本节内容要从一个问题说起：

给出下列判断字符串相等的两段代码，在不查询资料的情况下说明两段代码有什么区别，分别在什么情况下适用。语言：Python

第一段：

def equals(str1, str2) -> bool:
    if len(str1) != len(str2):
        return False
    equal = True
    for i in range(len(str1)):
        equal &= str1[i] == str2[i]
    return equal

第二段：

def equals(str1, str2) -> bool:
    if len(str1) != len(str2):
        return False
    for i in range(len(str1)):
        if str1[i] != str2[i]:
            return False
    return True

均为7行

这是我作为本次算法文章的引子，要引出的内容是Timing Attack（时序攻击）

好像还没有人发现代码写的有点小问题（功能没写错，但是速度稍微慢了亿点）：

第一段应该是：

def equals(str1, str2) -> bool:
    if len(str1) != len(str2):
        return False
    equal = True
    for i in range(len(str1)):
        equal |= str1[i] ^ str2[i]
    return equal == 0

第二段应该是：

def equals(str1, str2) -> bool:
    if len(str1) != len(str2):
        return False
    for i in range(len(str1)):
        if str1[i] ^ str2[i] != 0:
            return False
    return True

改进后的两段代码功能与原版没有区别，但考虑到加进了位运算替换掉了==，速度上会有一个不小的提升

如果觉得改进后的版本不好理解，看改进前的即可，里面的思想相同。

---

以上代码其实是我转译过来的，原文为https://blog.csdn.net/ahyz9638/article/details/101561620，原文使用的语言是Java，但是还是不影响思想。

 

第一段代码，不像@rice0208说的毫无用处，它的特点在于：

比如比较password和pastword两个密码

第一段代码比较完了8个字母后才返回结果，也就是说，时间恒定为8个“单位”

第二段代码比较了4个字母后返回结果，时间随两个字符串变化而变化

这样，第一段代码的耗时是一个相对的“常量”，第二段代码的耗时是一个相对的“变量”，不知大家能否理解。

 

那么你可能会问为什么用“password”这个词作为例子？问的好。答案也很简单，这种思想正广泛运用于密码安全、密钥安全领域。

设想这样一个场景：

某个函数负责比较用户输入的密码和存放在系统内密码是否相同，如果该函数是从第一位开始比较，发现不同就立即返回，那么通过计算返回的速度就知道了大概是哪一位开始不同的，这样就实现了在某些科幻电影中经常出现的按位破解密码的场景。密码破解复杂度成千上万倍甚至百万千万倍的下降。

当然现实生活中很少会将密码明文存储在数据库中的例子，因为这样本身就很不安全。但是对于Web服务器的私钥来说，无法通过哈希存储检查，必须通过明文比较，在这种情况下，第一段代码就起到了防御Timing Attack的效果。

我们来看一个真实运用第一段代码的例子，选自Java语言的java.security.MessageDigest（注释经过翻译，原文请参考下面的图片）

public static boolean isEqual(byte[] digesta, byte[] digestb) {
   if (digesta == digestb) return true;
   if (digesta == null || digestb == null) {
       return false;
   }
   if (digesta.length != digestb.length) {
       return false;
   }
 
   int result = 0;
   // 常量时间的比较
   for (int i = 0; i < digesta.length; i++) {
       result |= digesta[i] ^ digestb[i];
   }
   return result == 0;
}

而且这段代码不是随意编出来的，有diff图为证（截图选自提到的原文），这是特意改出来的

引用原文结尾作为本文结尾：

论文Remote Timing Attacks are Practical指出：

计时攻击往往用于攻击一些性能较弱的计算设备，例如一些智能卡。我们通过实验发现，也能用于攻击普通的软件系统。本文通过实验证明，通过这种计时攻击方式能够攻破一个基于 OpenSSL 的 web 服务器的私钥。结果证明计时攻击用于进行网络攻击在实践中是可行的，因此各大安全系统需要抵御这种风险。