Soreat_u's Blog

Notes on Black Hat USA 2021 Talk - Timeless Timing Attack

 Notes

Introduction

这是看的第二篇Black Hat USA 2021 的议题演讲，主题是侧信道攻击领域里有关于时序攻击（timing attack）的一种新型技巧——并行时序攻击（concurrency-based timing attacks）。

以往的时序攻击受限于网络抖动（network jitter）等诸多因素的影响，无法在时间差很小的场景下实施攻击。而并行时序攻击则可以"无视"网络抖动的影响，可近似于在本地（localhost）发起的时序攻击，要比传统的时序攻击要强上100倍。

Timing Attack

一个典型的可被时序攻击的代码案例：

1
2
3

for i in range(len(SECRET)):
    if request_data[i] != SECRET[i]:
		break

在这段代码中，用户输入的数据request_data会和服务端的秘密数据SECRET逐字节对比。如果当前下标i的两个字节不一样，程序会直接跳出这个循环。

不同的输入，会使得循环执行的次数不同。如果request_data第1个字节和SECRET不一样，那么循环只会执行1次；如果request_data第1个字节正确，但第2个字节不正确，那么循环则会执行2次；依次类推。

循环执行次数的不同，也就意味着其执行时间也会不同。攻击者可以利用这一点，不断尝试每一个字节值，并测量程序的执行时间，如果有一次猜测所对应的执行时间较长，则意味着猜测的字节是正确的，循环成功进入到了下一轮中。通过这样不断的猜测和测量，攻击者就可以一个字节一个字节地恢复出服务端的秘密数据SECRET。

当然，一个字符串比较所需的执行时间是极短的，网络抖动足以将其淹没，所以在很多情况下，这样的时序攻击都认为是不可行的（infeasible）。

影响传统时序攻击很大的一部分因素在于网络抖动（jitter），而并行时序攻击则可以克服这一点，在下一节中将会使用理论模型来定量分析网络抖动对于时序攻击的影响。

在进入下一节之前，我们可以先来看看这两个时序攻击的攻击流程：

  • 在传统时序攻击（classical timing attacks）中，攻击者发送大量的特定请求给服务端，测量并记录从发送请求到接受响应的间隔时间，再结合一些统计学的方法来分析这些时间数据，攻击者就可以获取到服务端的一些秘密信息。

    classical_timing_attack_with_jitterclassical timing attack from talk video

  • 在并行时序攻击（concurrency timing attacks）中，攻击者仅利用两次并行处理的请求所对应的响应包顺序来进行攻击。通过某些技巧，攻击者可以将两个请求封装在一个TCP包中，这两个请求会同时到达服务端并被并行处理，如果两个请求的处理时间有差别，则可以通过响应包的顺序（response order）识别出来，从而可以借此获取到服务端泄漏的秘密信息。

    concurrency_timing_attackconcurrency timing attack from talk video

Modelling

在本节中，将会把整个间隔时间拆解为多个更小的组成部分，并借助理论模型来数学化表述时序攻击。

Classical timing attack model

攻击者所能测量的时间是，从发送请求包一直到接受响应包的这一段间隔时间，我们将其记做$R$。

这段可测量的间隔时间$R$可以拆分为两个部分：处理时间（processing time，$T$）和传输时间（propagation time，$B$），即 $$ R = T + B $$ 其中，处理时间$T$表示的是，服务端应用层程序处理请求并生成响应的这一段时间（⚙️转圈的时间）：

processing_time_3processing time from talk video

而传输时间$B$指的则是，请求包在和响应包在网络中传输所需要的时间（数据包移动的时间）：

propagation_time_2propagation time from talk video

由于多变的网络环境，以及服务端负载的动态性，$T, B$实际上都是随机变量。对于随机变量，我们可以取其数学期望$t = E[T]$和$b = E[B]$，从而可以把$R$重写为： $$ R = t + b + J $$ 其中，$J$表示在处理和传输的过程中所出现的各种随机抖动的时间总和。

这样子就可以把$R$的动态性（每次请求的间隔时间都是不一样的）归结为各种随机抖动$J$的动态性；而处理时间和传输时间都可以用一个固定的均值$t$和$b$来表示。

对于多个不同的请求$m$来说，其期望的传输时间$b$可以视为都是相同的，而每个请求的处理时间$t_m$并不会相同（有些请求很快就处理完了，而有些请求可能需要更多的时间），且每次的随机抖动$J_m$也会变化，因此其间隔时间$R_m$也都是不一样的，有 $$ R_m = t_m + b + J_m $$ 在这里可以看到，传输时间$b$是独立于请求$m$的，这是因为，在一个特定的客户端和一个特定的服务端之间的网络传输总是固定的，并不会因为请求的不同（这次是GET /1，下次是 GET /2）而改变。

接下来，我们还可以再对$J_m$更进一步分解。$J_m$是所有随机抖动的总和，那么随机抖动究竟有哪些呢？

一个数据包在网络中进行传输，再到数据包被接受并被处理，再到处理后返回响应，期间进行了一大堆的子运算，包括但不限于：

  • （网络）在网络数据包传输路径中，数据包会经过很多跳（hop）
  • （主机）网络协议栈里一层一层组装数据包
  • （主机）收到数据包之后，在网路协议栈里脱掉TLS层时，需要进行解密运算
  • （主机）解码/解密后的明文HTTP报文，需要转交给相关的上层应用
  • etc.

对于所有的这些子运算$k \in \{1…K\}$，$R_m$的表达式可以写为： $$ R_m = t_m + \sum_{k=1}^{K}{(b_k + J_{m,k})} $$ 其中，处理时间的抖动部分，可以由某些子运算$p \in \{1…K\}$所对应的抖动$J_{m,p}$来表示，且这些子运算所对应的传输时间$b_p$视为0（处理期间无传输时间）。

作为攻击者，我们可以测量到两个不同的请求$x$和$y$所对应的间隔时间$R_x$和$R_y$。我们现在想知道，在哪些情况下，间隔时间的差值可以用来确定处理时间的先后顺序。比如说，现在测量得出，请求$x$的间隔时间$R_x$比请求$y$的间隔时间$R_y$要长一些，那么在哪些情况下，借助这一点就可以确定请求$x$所需要的处理时间必然要比请求$y$长一些呢？（并不是所有情况下，间隔时间长，就一定意味着处理时间长；还有可能是由于随机抖动比较大，所以导致的间隔时间比较长。我们现在就是想定量去分析，随机抖动对于这个判断的影响程度）

Q：为什么想要知道处理时间的先后顺序呢？

A：利用处理时间的不同，攻击者就可以精心构造多个特定的请求，来获取到服务端的一些秘密信息。

我们可以做如下推导： $$ \begin{aligned} R_x > R_y &\Leftrightarrow t_x + \sum_{k=1}^{K}{(b_k + J_{x,k})} > t_y + \sum_{k=1}^{K}{(b_k + J_{y,k})} \newline &\Leftrightarrow t_x - t_y > \sum_{k=1}^{K}{(J_{y,k} - J_{x,k})} \end{aligned} $$

$J_{y,k}, J_{x,y}$都是变量；

$R_x, R_y$是因变量，随着$J_{y,k}, J_{x,y}$的变化而变化；

$t_x, t_y$都是定量。

从中我们可以看出，当两次请求期望的处理时间的固定差值，要比这两次请求中所遇到的所有抖动总和还大时，那么此时测量到的间隔时间之间的大小关系就等价于处理时间的先后顺序。

其实上，每个子运算中的抖动分布都可认为是互相独立、正态分布的，其方差有如下关系： $$ Var[J_{y,k} + J_{x,k}] = Var[J_{y,k}-J_{x,k}] = Var[J_{y,k}] + Var[J_{x,k}] $$

在实际操作中，我们可以通过多次测量，来搞到一次所有抖动都非常小（离期望值较近）的情况，从而能够减轻抖动的干扰，让间隔时间$R$的差值能够尽可能正确地反映处理时间$t$的差值。很多传统时序攻击都是根据这一点来操作的，所以可以看到有些攻击需要成千上万次的测量，才能确定一次时间差。

以上就是有关于传统时序攻击相关理论模型的推导，借助理论模型，可以帮助我们更好地去理解时序攻击中的具体细节，以及量化相关的影响因子。

Concurrency timing attack model

作者就在想，除了多次测量之外，有没有其他法子可以减少抖动$J_{y,k}$的影响呢？

有的。

就比如说，如果我们能让两个包在同一个时间到达服务端，并在之后的一系列子运算（包括传输时间和处理时间）中，都被并行处理。在这种情况下，对于一开始的这些$S$个子运算（client发包到server）来说，由于两个并行的请求$x$和$y$都经历了相同的网络抖动，所以有： $$ \forall s \in \{1…S\} : J_{x,s} = J_{y,s} $$ 从而前S个子运算的抖动相减，就可以抵消掉了，只剩下从第$S+1$个子运算开始的抖动： $$ R_x - R_y \Leftrightarrow t_x - t_y > \sum_{k=S+1}^{K}{(J_{y,k} - J_{x,k})} $$ 因此，通过将两个并行的请求封装在同一个网络数据包中，攻击者就可以减少大约一半抖动的干扰。这样，处理时间的固定差值只要大于服务端接收到数据包之后的所有网络抖动总和，就可以借助$R$的大小来确定性地推测出$t$的顺序。

从client至server的传输过程中，我们可以做到并行，但是在数据包到达服务器主机上之后的子运算，我们却并不一定能保持并行。例如，网卡会一字节一字节地从物理层读取数据包，经过TLS加密的数据包需要按照顺序来解密等等，这些子运算都是顺序处理的，无法并行。

因此，第二个数据包会稍微晚一点点被上层应用程序处理，我们定义这一段延迟为$D_y$，也就是说第二个数据包的处理时间相较于第一个数据包要晚$D_y$的时间。$D_y$也是一个随机变量，我们定义其数学期望为$d_y = E[D_y]$，并用$J_{y,d}$表示相关的随机抖动，即$D_y = d_y + J_{y,d}$，从而有： $$ R_x - R_y \Leftrightarrow t_x - t_y > \sum_{k=S+1}^{K}{(J_{y,k} - J_{x,k})} + (d_y + J_{y,d}) $$

现在只剩下从server至client这一段的传输过程需要考虑了，有没有办法也可以尽可能减少这一段抖动的影响呢？

也是有的。

TCP协议中，所有传输的数据包，其序列号$SN$是单调递增的。这意味着，先处理结束的请求，其对应的TCP响应包的序列号相较而言是小的；而后处理结束的请求，其TCP响应包的序列号则是大的。借助TCP序列号的大小，而非绝对的时间差，我们就可以判断是哪一个请求先结束的，从而直接忽视从server至client传输过程中的所有抖动。结合上面的封装技巧，所有传输过程中的抖动干扰就都可以无视了，只剩下处理过程中的抖动$J_{x,p},J_{y,p}$+主机上一些预处理（网卡、网络协议栈等）的差值$d_y + J_{y_d}$： $$ R_x - R_y \Leftrightarrow t_x - t_y > (J_{y,p} - J_{x,p}) + (d_y + J_{y,d}) $$ 上式表明，并行时序攻击不会受到网络抖动（不管是上行还是下行）的任何影响，后续的实验案例也证实了这一点，并行时序攻击可以近似于在localhost发起的时序攻击，完全无视网络抖动。

这一节有关于并行时序攻击的理论模型，是个人认为从paper 里学到的最重要的知识，所以用大量篇幅对其进行了复述。接下来的一节，将会介绍具体的攻击场景。

Attack Scenarios

作者阐述了4种可能的攻击场景（实际可行的攻击场景可不止这4种）：

  1. Direct attacks
  2. Cross-site attacks
  3. Tor
  4. Wi-Fi authentication

本节将会简单地介绍第一个场景：direct attacks（另外几个场景的还挺复杂的，就偷懒只写一个了）

direct attacks就是直接跟服务端交互，利用HTTP/2的多路复用（multiplexing）功能把两个请求塞到一个TCP数据包里，然后这两个请求就会同时达到服务端，并被并行处理。

但是在应用层程序（例如：套Spring、Gin、Flask等框架写的代码）并行处理之前，这两个数据包会先过一遍网络协议栈。由于HTTP/2需要开启TLS，所以两个HTTP应用报文会有对应的2个TLS Record层，这两个TLS Record层并不会被并行处理，而是交给TLS相关的处理程序顺序解密。这样就会导致，第二个HTTP报文会稍微比第一个慢一点，即存在延迟$d_y + J_{y,d}$。

这一点延迟不能忍，我们还是很希望两个HTTP报文是能够在同一时间被应用层程序并行处理的。那怎么办呢？

实际上，在脱完TLS层之后，赤裸裸的HTTP报文并不会原封不动地直接交给应用层程序去处理，而是会过一道中间件（nginx/apache等）的预处理。预处理会解析HTTP报文，然后生成上下文context，再交给应用层去处理。作者就想在预处理这边做点文章。

怎么搞呢？第二个HTTP报文由于各种原因会比第一个慢那么一点点点点。我们就想着在预处理的时候，适当地延缓一下第一个报文，让第一个报文预处理多耗点时间，等跟第二个报文一致时，再一起交给应用层程序去处理。一个办法就是，给第一个HTTP报文多填点params，预处理解析这些填充的params会消耗额外的时间（这些额外的params并不会对后续处理有任何影响）。这样，就可以把微倾的天平校验至水平位，然后两个HTTP请求就可以在同一个起跑线上，被并行处理啦。具体要填充多少的params，也可以自行实验得出，一般来说大概几十个即可。

这个技巧 最早是由Wälde和Klink在07年提出来的。

作者用大学（位处Belgium）里的机器做客户端，再租了9个Amazon的云服务器（分别在3个地区：EU、East US、South-East Asia）作为服务端，并使用了一个极简的示例程序，来做了多组的实验，实验数据如下：

image-20220420012630004

从实验数据中可以看出，并行时序攻击确实比传统时序攻击强了100倍，作者并没有吹牛；而且，在互联网里发起的并行时序攻击居然跟在localhost发起的时序攻击差不多？？？

不得不说，确实🐮，不愧是Timeless Timing Attack

Discussion

当然，这么🐮的攻击手法，其要求和限制也比较多。

Requirements

要能够实施并行时序攻击，至少需要满足以下3个条件：

  • 两个请求包要在相同时间到达服务端

    • Multiplexing
      • HTTP/2协议允许多路复用，在一个TCP包中携带多个HTTP/2请求包
    • Encapsulation
      • Tor网络中允许将多个数据流封装在一个TCP包中

    当然，不止这两种方式可以实现并行，还有很多其他的方式，这是一个可以拓展延伸的研究方向。

    image-20220418005311039multiplexing && encapsulation

  • 服务端要并行处理这两个请求

    • 服务端应用层程序多线程处理
    • 可能的例外：2个HTTP/2包对应有2个TLS Record层，在TLS层解密时的操作是顺序的，两个包会有先后顺序，从而引入了一些延迟

  • 响应顺序要能反映出运行时间的不同

    • 绝大多数应用处理完之后，立马就会生成响应包发给client
    • TLS的加密顺序、TCP序列号、TCP时间戳也会反映响应包生成的前后顺序

Limitations

  • 并行时序攻击只利用到了响应包的顺序（先/后），而没有使用具体的时间数据（xx.xxx秒），信息的使用粒度不高。
  • 对于一些必然是顺序执行的情况（例如TLS协议），无法并行操作，所以并行时序攻击里的一些技巧很可能无法用在这些情况里。

Conclusion

之前我也出过一个有关于时序攻击的CTF小题目 ，当时主要是想考察代码审计+这么一个攻击面，程序的时间差设得非常大（110ms），算是非常友好了。

看了这个Timeless Timing Attack，我才发现原来还有这种骚操作？这几天的学习，不仅仅是深入了解了Timeless Timing Attack的原理，更多的是思路的打开：一个朴实无华的时序攻击，居然还能不断地优化，突破极限，把infeasible变成feasible。

此外，作者还在paper里提出了一个很有前景的研究方向：

We consider it an interesting avenue for future work to perform a comprehensive survey of network protocols to evaluate whether they provide or enable these prerequisites, and thus make applications susceptible to concurrency-based timing attacks.

也确实有大师傅去做了一些探索：漂亮侧信道：从timeless attack到pipeline的放大攻击

以及，一些Timeless Timing Attack相关的ctf题目：