c - 这个 prefetch256() 函数是否提供任何针对 AES 缓存定时攻击的保护？

Question

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

我在 C/C++ 中实现了 AES 算法。由于在没有硬件支持的情况下执行 GF(28) 乘法在计算上是昂贵的，因此我已经优化为使用 AES S-box 的查找表。但不幸的是，基于查找表的实现容易受到 cache-timing attacks 的影响。 .因此，由于对 CPU 缓存非常天真，我开始学习它的工作原理，以及如何在不增加任何计算成本的情况下规避这种攻击。

我意识到实际上有 AES NI 指令和 Bit Slice AES 实现，但它们远远超出了我目前的理解。

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

在 C implementation reference guide of OpenSSL - 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增加 8如果 sizeof(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..  

Answer 1

In the for loop i is incremented by 8 if sizeof(t[0]) is 4.

But I don't understand the reasons why we skip 32 bytes, and not read it fully (to protect against cache timing attacks)?

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

What is the motivation behind sum ^= t[i] and setting ret = sum ?

一个好的编译器会注意到你正在读取的数据没有被使用，并且会避免进行“不必要的”(为了“C 抽象机”的正确性)读取以提高性能而不知道“不必要的”读取是必要的编译器无法知道的原因。为了防止编译器像这样优化，你需要欺骗它认为数据被实际使用，或者使用 volatile . OpenSSL 作者正在做这两项(试图通过执行 sum ^= t[i] 和 ret sum 来欺骗编译器不进行优化；并且还使用 volatile )，可能是因为(历史上)很多旧编译器都有涉及 volatile 的错误.
还要注意，仍然有一个非常小的计时问题 - 在预取数据之后但在表的一部分用于 AES 之前，可以刷新缓存(例如，通过任务切换等)；因此，攻击者仍有(极小的)机会可以使用缓存计时攻击来确定使用了表 AES 的哪一部分。请参阅“对缓存定时攻击预防的信心”(下文)。

Will this following simpler code help me:

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

Are there other simpler solutions to protect my implementation from cache timing attacks?

一切都是复杂性、便携性、安全性、特性和性能之间的折衷； “更简单”几乎总是意味着“更差的便携性”和/或“更差的质量”和/或“更差的功能”和/或“更差的性能”。您不能在防止缓存定时攻击的同时使质量或功能变差。你不能让性能更糟，因为它已经很简单了。
您可能(也可能不会)通过牺牲可移植性来使其更简单。例如;如果您知道整个表适合一台计算机上的单个缓存行(并且与缓存行边界对齐)，那么您就不能为那台计算机做任何事情，并说该代码不应用于任何其他计算机。
对缓存定时攻击预防的信心
防范缓存定时攻击的关键因素之一是攻击者拥有多少控制权。典型的场景是攻击者充斥缓存(用已知数据污染它以导致其先前的内容因“最近最少使用”而被驱逐)，然后让受害者做一些事情，然后测量它可以多快地访问其已知数据以确定该已知数据是否仍在缓存中或已被逐出。如果已知数据的缓存线被驱逐，攻击者就会知道受害者访问了与被驱逐的缓存线在缓存中具有相同位置的内容。
最糟糕的情况是攻击者能够非常频繁地执行此操作(例如，对于受害者执行的每条指令)，缓存没有关联性(直接映射)，并且攻击者要么知道有关受害者如何使用虚拟地址的所有信息，并且受害者的虚拟地址和缓存中的位置之间的关系(可能包括虚拟地址和物理地址之间的关系)或在同一个进程中(例如共享库，他们可以自己访问表以确定它是否被访问而不是依赖关于驱逐其他数据)。在这种情况下，唯一的防御是确保所有内存访问模式始终相同(从不依赖于任何数据)。这非常困难，但并非不可能 - 例如如果您想从表中读取一个字节(例如“ byte = table[index] ”，您不希望攻击者知道有关 index 的任何信息)，您可以读取所有前面的缓存行，然后读取您想要的字节，然后读取所有后面的缓存行(这样它总是看起来像整个表的顺序读取)并以固定的速率进行这些访问(没有“读取你想要的字节之前暂停”和“读取你想要的字节后暂停”) ，包括“没有由分支错误预测引起的暂停”)。如果你这样做；那么您可以对自己抵御缓存时序攻击的能力有极高的信心(直到保证您的代码不受所有可能的缓存时序攻击的影响)。
然而;攻击者几乎不可能获得那种程度的控制，编写这样的代码极其困难，而且这样的代码会产生很大的性能开销。
在另一个极端；您无能为力，并且对您防止缓存定时攻击的能力没有信心。其他一切都介于这些极端之间。
那么问题是；什么是好的妥协？这取决于太多因素——攻击者拥有多少控制权，攻击者是否处于同一进程中，攻击者是否可以重复攻击(并使用概率方法来击败任何“噪音”)，数据值(value)多少对攻击者(理智的小偷不会花费超过 2 美元来试图窃取值(value) 2 美元的东西给小偷)，数据对受害者的值(value)(没有人每天花费 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); )，但它们取决于编译器和 objective-c PU。