前言
在学习Dan Boneh教授的线上免费密码学MOOC时，Boneh提到了一个有趣的攻击——验证计时攻击(Verification Timing Attacks)， 作为侧信道攻击的其中一种，验证计时攻击非常简单易懂，且十分常见，有时候程序员进行与密码学相关编程的时候很容易犯这个问题， 故记录下来警醒自己。
一句话概括该攻击，那就是：它是一种侧信道攻击，它利用影响执行时间的代码缺陷来挖掘其中的秘密信息。
注意字符串比较！
很多情况下，我们会直接使用==符号判断两个字符串是否一致，这不仅简单易懂，
而且很多语言的标准库也会使用各种匹配算法来优化比较效率。
然而，在密码学编程中，这个看起来没啥问题的使用方法会导致安全性的削弱，导致侧信道攻击有机可乘。 攻击者会充分利用这个时间差信息，通过精确测量算法运行的时间，感知算法终止在哪一个步骤，不断调整输入揭秘出秘密信息。 因此，了解攻击方法和相应的防御手段是十分必要的。
验证计时攻击方法
简单了解消息认证码（MAC）和HMAC
了解计时攻击方法之前，我们先回顾一下消息认证码和HMAC。
我们从下图可以看到，由于Alice所发送的信息被攻击者所截取、篡改，Bob会收到完全不一致的内容，此时，Bob并不知道这个信息是不是Alice的真实意思，很容易导致误会。
因此，消息认证码（Message authentication code，缩写为MAC）就派上用场了，它使用一个密钥，来为消息生成一个tag，以用于检查消息的完整性，即内容在传输的过程中是否被篡改过，保证消息的来源。
继续套用上面的例子，Alice发送信息的同时，使用只有双方知道的密钥(我们在这里不管密钥是如何传输的, 假定是双方面对面协商确定的吧)对消息生成一个tag(如图中所示的MAC值)，然后将消息和tag一并发送给Bob。Bob收到信息后，先不急着读这信息，而是要确认信息的来源是不是Alice：首先，Bob同样使用密钥对接收到的信息计算MAC值，然后再比对计算得到的MAC值和接收到的MAC值是不是一样的。如果一样，则Bob认为消息的来源的确是Alice，其他人没有篡改过消息。为什么会这样呢？因为攻击者没有密钥，它没办法对伪造后的消息伪造正确的MAC值。就如同古代的对口令，如果口令对不上，后面说的话就把它当成屁话就行了。
至于HMAC，我们不管它的原理，只要知道HMAC是MAC的一种就行了！更详细点，它使用密码散列函数(Hash)的特性来实现MAC。具体内容可以搜索谷歌或者百度就弄清楚啦。
一段有问题的代码
上面的做法是不是就没问题了呢？并不是！虽然攻击者不知道密钥，它同样有其他方法来伪造tag。这个方法就是利用最后MAC验证阶段时字符串or字节序列比较的漏洞——我们称之为验证计时攻击。
我们首先给出一段MAC验证代码，该代码来自于已不再维护的Keyczar Crypto Library，它使用Python语言实现。由于代码库已经被清空了，但大家可以查看History，还是能看到以前的代码的。
这个代码本质就短短一行，简单来说就是如下的伪代码
def Verify(key, msg, sig_bytes):
return HMAC(key, msg) == sig_bytes这个代码有问题吗？似乎就是一个简单的字节序列比较。
真的有问题！原因就出自于==。在Python中，这是一个典型的序列比较，一旦发现某处字节不匹配就会提前返回False。
这意味着根据第一个差异的位置，比较两个字符串的时间不尽相同。
这允许攻击者反复尝试各种HMAC值并测量服务器响应所需的时间。服务器花费的时间越长，攻击者试探出正确的前缀就越长。
针对字符串/字节序列比较的计时攻击
我们来看看攻击者是如何采取攻击的，如下图所示，该图来自于Boneh教授的课件，如果大家有兴趣的话可以自行移步到Coursera的Cryptography I的课程学习。
在这里，攻击者的目标是在不知道密钥k的情况下，伪造目标信息m的HMAC值tag，骗取服务器验证通过并返回accept。这本质上就是对MAC的攻击游戏。
如果我们直接使用穷举破解，假设tag的长度为n个字节，那需要多少次尝试呢？$256^n$次！如果n足够大的话，这基本是不可能完成的事情。但是，如果服务器的字节序列比较恰好就是上方有问题的代码，那么，攻击者可以采取图示的方法进行攻击。简单来说，就是：
-
对于tag的第一个字节，穷举256(即$2^8$)个值，其他字节则使用
0x00代替，记录服务器处理的时间。 -
如果攻击者发现对于某个值(0-255)，服务器处理的时间稍长一些，这时候有理由认为这个值就是tag第一个字节的正确值，因为只有匹配上，服务器才会继续尝试匹配第二个字节，因此处理的时间会长一些。
-
继续以上步骤，试探后续的字节直至破解完成。
这种攻击方法会将尝试次数降至多少呢？$256 * n$次！大大降低了破解的难度， 因此，如果程序员稍有不慎的时候，会导致这种攻击有机可乘，导致安全问题。
避免方法
我们可以采取恒定时间字符串比较（constant time string comparison）来抵御上述的攻击。
如下面的伪代码所示，当比较过程中发现不匹配的时候函数并不立即返回，而是设一个标志位，直到完全比较完两个字符串再返回。如此以来，函数的处理时间永远都不会有明显的差异，从而堵死了计时攻击的漏洞。当然，这样有可能会对性能有一定的影响，因为函数的执行时间永远都是最坏情况下的时间，但是，为了安全，忍一忍吧。
return false if sig_bytes has wrong length
result = 0
for x, y in zip( HMAC(key,msg) , sig_bytes):
result |= ord(x) ^ ord(y)
return result == 0现在活跃的开源库中，不少库（如Django的constant_time_compare等）的安全字符串比较采用以上方法，Python 3.3以上版本的标准库也采取了该方法（hmac.compare_digest）。
我们再回来说说Keyczar的处理方法，还是一样的思路，2009年5月底发布的Keyczar Python 0.716版本中对该问题进行了修复，我们可以在Github中看到这个修改过程：
最后
最后还是提醒我们：有时候你觉得没啥问题、看起来甚至觉得十分简单的代码，会隐藏如此严重的安全问题。 所以在进行密码学编程的过程中，一定要慎之又慎，充分权衡了安全性的前提下再优化代码。
参考资料
- 英文维基百科的Timing attack词条
- Timing Attacks against String Comparison. DEVELOPERS SECURITY BEST PRACTICES
- Python文档中对hmac.compare_digest的介绍
- Timing attack against HMAC in authenticated encryption?. StackExchange
- Simple string comparisons not secure against timing attacks
- Timing attack in Google Keyczar library. Threat Post
