7

这是一个边缘话题。由于我想了解编程、CPU 缓存、读取 CPU 缓存行等，所以我将其发布在这里。

我在 C/C++ 中实现 AES 算法。由于在没有硬件支持的情况下执行 GF(2 8 ) 乘法计算成本很高，因此我已优化为使用 AES S-box 的查找表。但不幸的是，基于查找表的实现容易受到缓存定时攻击。因此，由于对 CPU 缓存非常幼稚，我开始了解它是如何工作的，以及如何在不增加任何计算成本的情况下规避此类攻击。

我意识到在实践中存在 AES NI 指令和 Bit Slice AES 实现，但它们远远超出了我目前的理解。

我从 crypto.SE 了解到，最简单的方法是在查找之前读取所有缓存行或读取整个表。（这也影响了我的表现）但是我不知道如何在软件中实现它，也不知道它背后的复杂概念。

在OpenSSL 的 C 实现参考指南中——aes-x86core.c 作者实现了一个函数：

static void prefetch256(const void *table)
{
    volatile unsigned long *t=(void *)table,ret;
    unsigned long sum;
    int i;

    /* 32 is common least cache-line size */
    for (sum=0,i=0;i<256/sizeof(t[0]);i+=32/sizeof(t[0]))   sum ^= t[i];

    ret = sum;
}
  • 在for循环i中，8ifsizeof(t[0])为 4。由于 AES sbox 是一个unsigned char包含 256 个元素的数组，当我们调用 时prefetch256(sbox)，sbox 指针被强制转换为一个unsigned long指针，因此使用取消引用的每个元素t[i]都是 4 个字节。但我不明白为什么我们跳过 32 个字节，而不是完全读取它（以防止缓存定时攻击）？

  • 背后的动机sum ^= t[i]和背景是ret = sum什么？

  • 是否有其他更简单的解决方案来保护我的实现免受缓存定时攻击？以下更简单的代码会对我有帮助吗：

       unsigned char tmp[256];
   memcpy(tmp, sbox, 256); // memcpy reads the full sbox table quickly..
4

1 回答 1

6

在 for 循环中，如果 sizeof(t[0]) 为 4，则 i 增加 8。

但我不明白为什么我们跳过 32 个字节，而不是完全读取它（以防止缓存定时攻击）？

在 for 循环中，i递增相当于 32char秒（不管sizeof(t[0])发生了什么），因为“32char秒”（或 32 字节）是作者确定的他们关心的所有 CPU 的最小缓存行大小。请注意，您只需读取缓存行的 1 个字节，以确保将整个缓存行提取到缓存中。

sum ^= t[i] 和设置 ret = sum 背后的动机是什么？

一个好的编译器会注意到您正在读取的数据没有被使用，并且会避免执行“不必要的”（为了“C 抽象机”的正确性）读取以提高性能，而无需知道“不必要的”读取是必要的编译器无法知道的原因。为了防止编译器像那样优化，你需要欺骗它认为数据是实际使用的，或者使用volatile. OpenSSL 的作者正在做这两个（试图通过做sum ^= t[i]and来欺骗编译器不进行优化ret sum；并且还使用volatile），可能是因为（历史上）很多旧编译器都有涉及volatile.

另请注意，仍然存在一个非常小的时序问题 - 在预取数据之后但在表的一部分用于 AES 之前，缓存可能会被刷新（例如，通过任务切换等）；所以攻击者仍然有一个（非常小的）机会可以使用缓存定时攻击来确定 AES 使用了表的哪一部分。请参阅“对缓存定时攻击预防的信心”（下文）。

以下更简单的代码会对我有帮助吗：

编译器很可能会把你的代码变成什么都没有（如果没有，它会遇到同样的问题，prefetch256()并且可能会更慢，因为你正在写入内存而不是仅仅读取）。

是否有其他更简单的解决方案来保护我的实现免受缓存定时攻击？

一切都是复杂性、可移植性、安全性、特性和性能之间的折衷；而“更简单”几乎总是意味着“更差的可移植性”和/或“更差的质量”和/或“更差的功能”和/或“更差的性能”。您不能在防止缓存定时攻击的同时使质量或功能变差。你不能让性能变得更糟，因为它已经很简单了。

您可能（或可能不会）通过牺牲可移植性来使其更简单。例如; 如果您知道整个表适合一台计算机上的单个缓存行（并且与缓存行边界对齐），那么您可以对那台计算机什么都不做，并说代码永远不应该用于任何其他计算机。

对缓存定时攻击预防的信心

防范缓存定时攻击的关键因素之一是攻击者拥有多少控制权。典型的场景是攻击者淹没缓存（用已知数据污染缓存，导致其先前的内容由于“最近最少使用”而被驱逐），然后让受害者做某事，然后测量它访问其已知数据的速度以确定该已知数据是否仍在缓存中或已被驱逐。如果已知数据的缓存行被驱逐，攻击者就知道受害者访问了与被驱逐的缓存行在缓存中具有相同位置的东西。

最坏的可能情况是攻击者能够非常频繁地执行此操作（例如，对于受害者执行的每条指令），缓存没有关联性（直接映射），并且攻击者要么知道受害者如何使用虚拟地址和受害者的虚拟地址和缓存中的位置之间的关系（可能包括虚拟地址和物理地址之间的关系）或者在同一个进程中（例如共享库，他们可以自己访问表来确定它是否被访问而不是依赖关于驱逐其他数据）。在这种情况下，唯一的防御措施是确保所有内存访问模式始终相同（从不依赖于任何数据）。这非常困难，但并非不可能 - 例如，如果您想从表中读取一个字节（例如“byte = table[index]“你不想让攻击者知道任何事情的地方index），你可以读取所有前面的缓存行，然后读取你想要的字节，然后读取所有后面的缓存行（这样它总是看起来像整个表的顺序读取) 并以固定速率进行这些访问（没有“在读取所需字节之前暂停”，也没有“在读取所需字节后暂停”，包括“没有由分支错误预测引起的暂停”）。如果你这样做；那么你可以对您防范缓存定时攻击的能力有极高的信心（直到保证您的代码对所有可能的缓存定时攻击免疫）。

然而; 攻击者几乎不可能获得这种级别的控制，编写这样的代码非常困难，而且这样的代码会产生很大的性能开销。

在另一个极端；你什么都做不了，对你防止缓存定时攻击的能力没有信心。其他一切都介于这些极端之间。

那么问题是；什么是好的妥协？这取决于太多的因素——攻击者有多少控制权，如果攻击者在同一个进程中，如果攻击者可以重复攻击（并使用概率方法来击败任何“噪音”），数据价值多少对于攻击者（理智的小偷不会花费超过 2 美元来试图窃取对小偷来说价值 2 美元的东西），数据对受害者来说价值多少（没有人每天花费 100 美元来保护可以替换的东西$2），还有哪些其他缓解措施（例如，大多数操作系统现在提供“地址空间布局随机化”）等。

为了一个好的妥协；出于您的目的，我个人喜欢“让它看起来像整个表的顺序读取”方法，但是一个非常简单的版本，它不太关心固定的访问率（或“暂停之前/after reading the piece you want”并且不关心缓存行的大小（如果表只有 256 个字节，访问每个字节不会花费太多，部分原因是大多数访问将是“缓存命中”）。一个例子可能：

uint16_t fetch_byte_from_table(int index) {
    size_t table_entries = sizeof(table)/sizeof(table[0]);
    uint8_t dummy = 0;
    uint8_t data = 0;

    for(i = 0; i < table_entries; i++) {
        if(i == index) {
            data ^= table[i];
        } else {
            dummy ^= table[i];
        }
    }
    return ((uint16_t)dummy << 8) | data;        // Caller can ignore the higher 8 bits
}

当然，您可以使用一些技巧来尝试隐藏或避免分支（例如data ^= table[i] * (i == index); dummy = data ^= table[i] * (i != index);），但它们取决于编译器和目标 CPU。

于 2020-05-09T18:18:52.020 回答