在阅读了这个出色的答案后,我了解到了侧信道攻击的存在。
从提供的代码示例中,可以通过在给定各种输入时对代码进行计时来确定正确的密码。
for (i = 0; i < n; i++) {
if (password[i] != input[i]) {
return EFAIL;
}
}
我可以做些什么来确保我的代码不会受到这种定时攻击?我特意保留了这个开放式答案,以便为各种常见软件配置提供示例和最佳实践。
在阅读了这个出色的答案后,我了解到了侧信道攻击的存在。
从提供的代码示例中,可以通过在给定各种输入时对代码进行计时来确定正确的密码。
for (i = 0; i < n; i++) {
if (password[i] != input[i]) {
return EFAIL;
}
}
我可以做些什么来确保我的代码不会受到这种定时攻击?我特意保留了这个开放式答案,以便为各种常见软件配置提供示例和最佳实践。
从提供的代码示例中,可以通过在给定各种输入时对代码进行计时来确定正确的密码。
首先,您实际上不应该直接检查密码! 至少,您应该首先使用Argon2id之类的密码哈希对密码进行哈希处理,然后将输入的密码哈希与您在用户注册期间(或用户上次更改密码时)存储的密码哈希进行比较。
更好的是,您应该使用像 OPAQUE 这样的密码验证密钥协议协议,但目前这些可能超出您的薪酬等级,直到他们看到更广泛的采用和实施。
我可以做些什么来确保我的代码不会受到这种定时攻击?
最好的开始方法是使用其他人已经编写并有理由维护的库例程或原语。 例如,在 NaCl/libsodium 中,您可以使用crypto_verify_32
比较两个 32 字节的字符串,例如两个 Argon2id 哈希,或两个 HMAC-SHA256 消息验证码。然后,回答这个问题的努力可以集中在一个地方,这个地方会受到很多关注和审查,并且会跟上进步的步伐。
但是假设你没有crypto_verify_32
,或者你想自己实现它。你能做什么?
首先,您需要了解哪些操作具有侧通道。 很容易说——就像其他答案一样——侧通道的出现只是因为提前 abort。但这还不是全部。一般来说,有许多操作 (这里用 C 来说明)可能需要一定的时间,这取决于输入的值——我们将这些操作称为可变时间操作,与恒定时间*形成对比:
for (i = 0; i < n; i++) if (x[i] == y[i]) return EFAIL;
显然需要更少的循环迭代,因此实际上可以保证根据 和 的秘密值在可变时间x[i]
运行y[i]
。
即使循环没有提前中止,一个仅仅依赖于秘密的条件for (i = 0; i < n; i++) if (x[i]) bad++;
,如果x[i]
是秘密的,也可能在可变时间运行。为什么?
这是一个粗略的近似。CPU 可能执行的机器指令如下所示:
0: tmp := x[i]
branch to 1 if tmp is zero
bad := bad + 1
1: i := i + 1
branch to 0 if i < n
执行的指令数量取决于x[i]
每次迭代的值:我们跳过bad := bad + 1
一些迭代。这是一个很好的模型,用于说明早期定时攻击(例如,RSA)在Kocher 的关于定时攻击的开创性论文中如何工作:主模幂循环无条件地计算(比如说)2048 位模平方,但计算 2048 位模乘有条件地取决于秘密指数的值。跳过乘法会大大改变整个操作所花费的时间。
不过,还有另一个原因,它与分支预测有关,这是使现代 CPU 在许多工作负载上运行如此之快的关键设计元素——即使您编写相同数量的代码(例如,相同数量的机器指令,以及以某种方式保证它们在条件的每个分支中计算相同数量的周期),执行所需的时间可能取决于条件的方式。
一般来说,CPU 不擅长保密执行哪些指令,所以不要让指令的选择依赖于秘密。
表/数组查找可能需要不同的时间,具体取决于 CPU 缓存中缓存的内存。因此,如果您正在读取的数组中的位置取决于一个秘密,那么它所花费的时间可能取决于该秘密,该秘密已被利用通过缓存定时恢复 AES 密钥。
(回想起来,这使得 AES 成为一个相当有问题的设计,它有意使用依赖于密钥的表查找!NIST公布的理由(§3.6.2,对实现的攻击:操作的作用)奇怪地声称表查找“不易受时间的影响尽管自那时以来已经报道了许多此类攻击。)
x = y << z
如果较大,则在某些 CPU 上,可变距离移位可能需要更多时间,如果z
较小,则可能需要更少时间。
在某些 CPU 上,乘法可能运行得更快或更慢,具体取决于输入的上半部分是否为零。
原则上,32 位 CPU 上的 64 位整数加法可能需要更多时间,具体取决于是否有进位。这是因为,当x
,y
和z
, 是 64 位整数时,逻辑x = y + z
可能看起来更像:
int carry = 0;
x[0] = y[0] + z[0];
if (the previous addition overflowed)
carry = 1;
x[1] = y[1] + z[1] + carry;
因此,所花费的时间可能取决于是否存在从低 32 位的总和到高 32 位的总和的进位。(在实践中,这通常只关心外来 CPU 或其他类型的侧通道,例如与智能卡相关的功率分析,而不是笔记本电脑和手机。)
这听起来可能有点压倒性。我们能做什么?
在大多数 CPU 上,有些操作通常会在恒定时间内运行。 他们是:
x & y
, x | y
, x ^ y
, ~x
, 和其他在 C 中没有出现的运算,例如 AND-with-complement。x << 3
或旋转x <<< 3
(不是标准 C,但在密码学中很常见;(x << 3) | (x >> (32 - 3))
如果x
是 32 位,则表示 )。x + y
,x - y
, whenx
和y
(比如说)在 32 位 CPU 上是无符号的 32 位整数,在 ADD-with-carry 指令的帮助下,通常甚至是 32 位 CPU 上的 64 位整数。需要说明的是:我并不是说如果您在 C 程序中使用这些操作, C 编译器就可以保证这些操作在恒定时间内运行。我只是对CPU通常在恒定时间内执行的操作使用 C 表示法。 (稍后会详细介绍此警告。)
“但是等等,”你抗议道,“我怎么可能用这些操作写出一个有用的程序呢?没有条件?没有循环?没有阵列?
首先,您不必完全避开条件、循环或数组。他们就是不能依赖秘密。例如,for (i = 0; i < 32; i++) ... x[i] ...
很好。但是for (i = 0; i < m[0]; i++) ...
如果m[0]
应该是秘密的就不好,for (i = 0; i < m[0]; i++) ... tab[x[i]] ...
如果应该是秘密的也不好x[i]
。
其次,你仍然可以建造这些东西!这只是有点棘手。例如,假设b
uint32_t 为 0 或 1。则分别b - 1
为 -1 = 0xffffffff 或 0,所以
x = ((b - 1) & z) | (~(b - 1) & y);
导致x = y
ifb
为 1 或x = z
ifb
为 0——很像x = (b ? y : z)
,但没有分支。显然,这需要计算两个 y
和z
,所以有一定的性能影响!同样,您可以通过查找表格的所有元素并使用这样的按位运算选择所需的元素来查找表格的元素。不如 快x[i]
,但也没有泄漏。
通常,您可以将带条件的程序转换为不带条件的逻辑电路,即使出于性能原因您不想这样做。 您还可以使用其他各种类似的技巧。crypto_verify_32
假设 x 和 y 是 uint8_t 数组,您可能会像这样草拟一个恒定时间的内存相等例程:
uint32_t result = 0;
for (i = 0; i < 32; i++)
result |= x[i] ^ y[i];
return ((result - 1) >> 8) & 1;
练习:这是否返回 0 表示相等而 1 表示不相等,或者 0 表示不等而 1 表示相等?
编写这样的程序——并采用像 X25519 这样的密码系统来鼓励看起来像这样的实现,而不是像 RSA 或 AES 这样鼓励涉及秘密相关分支或秘密相关表查找的实施的密码系统——是一个很好的开始时间侧渠道。
但是,有一个问题!还记得我说过 C 编译器不保证恒定时间吗? 像 Clang/LLVM 这样的智能 C 编译器可能会认识到,通过提前中止crypto_verify_32
循环可以更有效地执行上面的智能循环,并且可能会取消您为将其重写为以恒定时间运行的逻辑电路所做的艰苦工作。(在其他情况下,它可能会对您有所帮助,例如通过转换x = (b ? y : z);
为不带分支的条件移动指令 CMOV,但通常您不能依赖 C 编译器的善意。)
您可以采取一些技巧来阻止这种情况,例如内联汇编片段,它会导致编译器大致放弃所有优化假设:
uint32_t result = 0;
for (i = 0; i < 32; i++)
result |= x[i] ^ y[i];
asm volatile ("" ::: "memory");
return ((result - 1) >> 8) & 1;
这可能适用于您的编译器,也可能不适用于您的编译器。为了有信心,您确实必须检查编译器生成的机器代码——即便如此,编译器可能会执行即时优化,根据分析分析重写机器代码,尤其是在 Java 等高级语言中。因此,您可能真的想用汇编语言编写逻辑(或者使用像 qhasm 这样的编程语言,它可以比 C 编译器更可靠地生成经过微调的汇编语言),然后从 C 中调用它。
也许有一天 C 编译器会采用一个secret
限定符,比如const
or volatile
,它强制编译器只生成已知的机器指令——在某些 CPU 模型中!——在对对象进行操作时以恒定时间运行,并阻止编译器采取捷径,例如从循环中依赖秘密的早期中止。但那一天还没有到来。
还有一个问题是哪些机器指令实际上在 CPU 上以恒定的时间运行,这有时是有记录的,有时是可靠的。因此,除了进行工程以利用逻辑电路构建程序之外,您还需要进行科学以确定哪些操作实际上可以安全地在 CPU 上使用。
这让我们回到了最初的观点:您真的希望将维护它的工作集中在一个库例程中,这样每个程序员就不必在生成的代码和时序中跟踪变幻莫测的编译器(和 CPU 设计!)他们自己,可以把它留给我们友好的邻居熊。
除了恒定时间逻辑,还有其他对策吗?有时候是的。
您可以将随机噪声注入您的逻辑,希望它会混淆攻击者的测量。 但是他们的测量中已经存在噪声,例如操作系统中的调度,因此他们只需要采集更多样本——事实证明,噪声并不是一种非常有效的侧信道对策。
具体来说,人工噪声最多会使攻击者的成本增加大约人工噪声与真实噪声之比的平方,这远低于通常认为的密码学安全性可接受的差距。所以它主要是花费你很多时间什么都不做。
您可以使用密码系统的代数属性对其进行随机化,有时称为“盲法”。 例如,您可以随机选择,计算where ,乘以得到,计算,然后除以,而不是计算y^d mod n
whered
是 RSA 中的秘密指数。r
s := r^e mod n
e*d ≡ 1 (mod 𝜆(n))
y
s
(y * r^e) mod n
(y * r^e)^d mod n = (r * y^d) mod n
r
许多实现,例如 OpenSSL,都使用这种方法,因为它是一种简单的方法来改进现有的加密系统(如具有必要代数结构的 RSA)实现。像随机噪声一样,这不是一个坏主意,但它确实有成本:你必须为随机化做额外的工作,你必须有模除法或反转逻辑——而且边信道可能仍然会泄露关于r
和的信息d
。例如,即使是盲目的模幂运算也会泄漏 Hamming 权重,d
除非您采取额外的对策,例如将随机倍数添加𝜆(n)
到d
first,这可能会暴露额外的边信道等。
对于比较两个字节串是否相等的特定情况(例如,两个消息验证码),一种合理的选择是在一次性密钥下使用 HMAC-SHA256 等伪随机函数族对它们进行哈希处理k
,并检查是否HMAC-SHA256_k(x) == HMAC-SHA256_k(y)
.
误报的概率是 1/2 256,这个概率比你担心的要小。您可以安全地对 HMAC 使用可变时间相等,因为如果x
不等于,那么y
即使是在最简单的字节字符串相等例程中的时间量(假设它不会在第一个零字节或类似的愚蠢的东西上跳出! ) 将独立于x
and的值y
:有 255/256 的概率在一次迭代后停止,在两次迭代后有 65535/65536 的概率,等等。
当然,这只有在您可以在恒定时间内实现 HMAC-SHA256 时才真正有帮助!幸运的是,SHA-256 被设计为很容易实现为恒定时间逻辑电路,因此 C 实现倾向于合理地抵抗侧通道——但是,如果没有别的原因,Python 会因为小的整数缓存而给你带来麻烦。
*不幸的是,术语有点混乱。这里的常数时间意味着时间量不会因输入而变化,并且与计算机科学中“常数时间”的渐近概念不同,通常写成 O(1),它仅表示时间量可能会因输入而异,但受一个常数 的限制。抱歉。我没有发明术语。我可能会选择“固定时间”与“可变时间”,但现在为时已晚——“恒定时间”已在文献中根深蒂固。
众所周知,侧通道攻击难以检测,因为攻击者可以寻找许多侧通道。这包括但不限于:
维基百科有一个很好的列表,这只是一个摘录。由于存在许多不同的侧信道,因此每个侧信道都需要独立处理。
您的代码容易受到定时攻击,但您已经知道这一点。问题是,你怎么能解决它?解决方案是进行恒定时间比较。一个例子是这样的代码:
difference = 0;
for (i = 0; i < n; i++) {
difference |= (password[i] ^ input[i]);
}
return difference == 0 ? E_OK : E_FAIL;
该代码假定password
和input
是相同的长度,例如因为它们是散列函数的输出。该代码将累积每对元素之间的位差,然后根据差值是否为零返回结果。另请注意,您友好的优化 C 编译器可以自由地发现它在做什么,并生成它会为您的原始(损坏的)代码生成的程序集。您需要检查实际的生成汇编器(或使用为此设计的库函数)。
当然,这只能防止一种侧信道攻击,而不是其他的。
这完全取决于您关注的侧信道。有些,例如功耗,需要物理访问(或其他测量功耗的方法),因此如果攻击者距离很远,它们可能不会成为问题。
通常,为了防御侧信道攻击,您需要:
我假设问题中的代码只是为了说明而故意简化的示例,因为在现实世界的系统中,您永远不会以纯文本形式存储密码。但是,如果您想用不易受到计时攻击的实现替换这个虚构的代码,那么您将确保算法不会在第一个错误字符上终止,但总是进行相同数量的比较:
bool isCorrect = true;
for (i = 0; i < PASSWORD_MAX_LENGTH; i++) {
if (password[i] != input[i]) {
isCorrect = false;
}
}
return isCorrect;
但是,这也不能完全证明可以抵御定时攻击,因为根据 CPU 处理此代码的方式,失败可能仍需要更长或更短的时间。时间差异的一种可能来源可能是分支预测。
过于简单化:当 CPU 注意到它在 for 循环中处理一个 if 条件并且 if 条件在大多数情况下结果为假时,CPU 将在假设它总是结果为假的情况下优化自己。这允许它更快地处理该 for 循环。但是,如果这个 if 语句突然变成了真的,那么它会在 CPU 流水线内部造成相当混乱,需要几个时钟周期才能清理干净。因此,由分支预测失败引起的时序差异可能是另一个可能的时序旁道。这很难避免,因为它是 CPU 的一个特性,对开发人员来说是完全不透明的,甚至可能取决于 CPU 的确切型号。有关更多信息,请对Spectre 漏洞进行一些研究。
但是还有一种不同的方法可以避免定时攻击,这种方法粗略简单但有效:在每次密码比较后添加随机延迟。如果延迟的长度来自加密安全的伪随机数生成器,那么它会破坏攻击者所依赖的时间测量的准确性。