密码学中恒定时间设计(译文)

本文翻译自 chosen plaintext 的博客,原文题目为 A beginner’s guide to constant-time cryptography。

很多刚刚接触密码学的萌新会被眼花缭乱的技术名词吓到,比如椭圆曲线,随机预言机和超长的英文缩略词(
RSASSA-PKCS-v1_5 ),这些复杂的算法真的能让网络变得更安全嘛?

问:请找出下面代码中的漏洞?(这里使用的是
JavaScript,但在 Python,Ruby和大多数其他语言中都会出现同样的漏洞)

// 参数 inputKey 和 correctKey 都是字符串。
// inputKey 和 correctKey 不相同则报错。
function checkApiKey(inputKey, correctKey) {
if (inputKey !== correctKey) {
throw new Error("密钥错误");
}
}

也许你已经发现问题了,这就是我们要讨论的,比较字符串运算符“!==”易受定时攻击。

比较字符串实际上就是两个字符串从第一位开始逐一进行比较,发现不同的字节立即停止。假如输入的两个密钥开头有一部分相同,判断字符串比较的耗时就会相应变长。这时候你的报错就像告诉攻击者“密钥错误, 但是你对了 2 个字节!”

让攻击者看到密钥有多少字节匹配似乎并不重要,实际上这对安全性来说是致命的。攻击者可以尝试所有 256 种可能性,并观察哪一种导致比较字符串耗费更长时间,以此破解密钥的第一个字节。然后使用第一个字节,他们可以对第二个字节和第三个字节执行相同操作,依此类推,直到他们得到整个密钥。

对于一个 16 字节的密钥,正常的暴力穷举攻击需要大约 1.7 x 10 ^ 38 次,在大多数情况下是不可能的。然而,通过定时攻击,只需几千次尝试即可得到整段密钥。

但是像这样的攻击是否实用呢?是的,特别是如果您在 EC2 或 DigitalOcean 等共享托管环境中,允许攻击者建立与您的服务器的低延迟连接。有关实际利用此漏洞的详细信息,请参阅本文(pdf)

解决方案一

一般我们可以想到的解决方案是:

  • checkApiKey(inputKey, correctKey);
  • 随机延时一段时间
  • 继续其他任务…

程序随机休眠一段时间,攻击者现在无法获得精确的定时测量。攻击被挫败了!

不幸的是,这并没有真正奏效。您的攻击者可能拥有 Statistics™ ,我们为攻击者的测量结果添加了随机性,但攻击者可以通过收集更多测量值并使用统计分类器(pdf) 来看透随机性。当然我们还可以添加更多随机,这会迫使攻击者收集更多样本,但现在我们的代码很慢。

解决方案二

  • 设定一个 finishTime = now(当前时间) + ESTIMATED_DURATION_OF_COMPUTATION(估算代码运行的时间)
  • checkApiKey(inputKey, correctKey);
  • 延时到 finishTime
  • 继续其他任务…

程序会在调用 checkApiKey 之前确定好结束时间。如果定义 ESTIMATED_DURATION_OF_COMPUTATION 为一个常量,那么这段代码应该总是运行相同的时间。

但是这种方法也存在问题。首先,我们应该如何设置常量 ESTIMATED_DURATION_OF_COMPUTATION 的值?过高会导致性能的问题,过低可能不足以隐藏计算的时间。

那么,我们是否可以将程序中的延时修改成一段忙碌等待呢?这样 CPU 就可以利用 checkApiKey 到 finishTime 的时间处理其他任务。攻击者也无法从测量时间中得到任何信息。。。吗?

不一定。现代 CPU 大多都有多个物理核心和类似超线程的技术。即使某个线程100%占用了一个逻辑核心,其他任务依然会在其他核心上并行运行。你的代码会对同一硬件上的其他线程和进程的性能上产生微妙但可测量的干扰模式。

假设您的代码花费大部分时间等待内存加载。CPU可以自由地将更多执行单元安排到另一个硬件线程,而其他进程的CPU计算将在很大程度上不受您的进程的影响。但是,如果另一个进程也需要访问内存,它将与您的进程竞争内存带宽,运行速度可能会因此变慢。

相反,如果您的代码是CPU密集型,其他进程拥有系统的内存总线,但CPU执行单元将被您的代码占用。

事情变得更棘手

您的代码有可能向运行在同一硬件上的其他线程和进程泄漏信息。进程/线程在相同的CPU缓存中竞争空间,缓存新的数据,删除旧的数据。CPU缓存会泄漏您的代码正在访问内存中哪些位置。另外整数算术、逻辑与浮点运算使用不同的执行单元,特定执行单元的争用可以揭示正在发生什么类型的计算。现实中已经出现利用这种微架构实现细节进行攻击的案例,最近的 Meltdown(熔断)Spectre(幽灵) 则是更高级的案例。

这一切都发生在硬件层面?这些干扰甚至会反应在同一台机器上运行的其他容器和VM。研究人员已经证明(pdf) 这种信息泄漏不能被EC2和Azure等云计算环境中的租户隔离措施所阻止。修复硬件漏洞很难。

恒定时间

我们应该如何应对呢?我们如何防止攻击者通过计时获得秘密信息?

过去十年中的最佳实践是编写“恒定时间”的代码。我们无法真正隐藏我们正在进行的计算,但我们可以编写“恒定时间”的代码,使得秘密信息不会影响我们如何使用硬件资源。换句话说,即使攻击者能够准确地看到我们的程序使用的硬件资源以及何时使用,他们仍然得不到任何秘密信息。

你可能“恒定时间”上的引号。我不太喜欢这个词,因为我发现这个词很容易让人误解:

  • 执行时间不需要是恒定的。执行时间的变化对安全性没有影响,只要这些变化与秘密信息没有任何关系。
  • 执行时间不是信息泄露的唯一方式。如前所述,您的代码在此期间所做的事情也非常重要。

“秘密无关的资源使用”可能是一个更准确的术语。对不起,我离题了。

以下是编写“恒定时间”代码的黄金法则:

只有当一条指令的输入对将要使用的资源和使用时间没有影响时,才能在输入中包含秘密信息。

还有一些实战中的注意点:

  • 秘密信息不能用于决定接下来要执行的代码(即它不能用作分支的条件)
  • 秘密信息不能用于决定要访问的内存地址。
  • 秘密信息不能作为 x86 上例如 DIV 等可变时间指令的输入(较小的数字除以更快)

如果您在汇编中编写所有代码,请仔细跟踪哪些值是秘密的,并遵循黄金法则,您应该确保您的代码不会通过计时泄漏秘密信息。

另外,特定指令是否是“恒定时间”可能因架构和处理器模型而异,并且没有任何相关的官方文档,我们之后再讨论这个。

汇编?高级语言?

有些人可能喜欢直接编写汇编。但对于我们其他人来说,直接编写汇编是痛苦的。那么我们该如何编写高级语言中的代码?这些代码在编译后仍然遵循黄金法则吗?

答案很复杂。现代的语言和编译器并不是真的为此而建,所以这是一个挑战。

通常的方法是编写看起来恒定时间的代码。时刻关注您要保密的变量,避免在 if 语句和循环条件中使用这些变量。在计算数组索引时避免使用这些变量(因为数组索引确定要访问的数组中的内存地址)。注意某些操作可能编译成可变时间指令(例如除法或模数)避免在这些操作中使用秘密的变量。

但这些方法不一定有用。编译器为了让您的代码更快可能会改用可变时间指令。甚至有些时候,编译器会发现您正在尝试避免使用if语句,并将 if 语句重新放入来提高效率。

鉴于缺乏语言和编译器支持,了解高级语言中的代码是否能够抵御定时攻击的唯一可靠方法是检查编译器的输出。常见的方法有:

  • 不要在敏感函数中使用内联。内联会增加您检查代码的难度。
  • 阅读编译器输出的相关部分,看它是否符合您的预期。
  • 更新编译器或更改代码中不相关的部分都可能会改变编译器的输出。

Adam Langley 在谷歌做了一些有趣的工具,通过注入 Valgrind 来检查函数是否是恒定时间。

我认为,最终最好的解决方案是教会编译器如何生成不易受时序攻击影响的代码。现在,对于高级别的加密代码而言,最实用的解决方案是仔细编码并手动或自动验证编译器输出。

发表评论

电子邮件地址不会被公开。 必填项已用*标注