这个 prefetch256() 函数是否提供任何保护来防止对 AES 的缓存定时攻击？
Does this prefetch256() function offer any protection against cache timing attacks on AES?
这是一个边缘话题。因为我想了解编程、CPU 高速缓存、读取 CPU 高速缓存行等，所以我将其张贴在这里。
我在 C/C++ 中实现 AES 算法。由于在没有硬件支持的情况下执行 GF(28) 乘法在计算上非常昂贵，因此我优化了对 AES S-box 使用查找 tables。但不幸的是，基于查找 table 的实现容易受到 cache-timing attacks 的攻击。因此，由于对 CPU 缓存非常天真，我开始了解它的工作原理，以及如何在不增加任何计算成本的情况下规避此类攻击。
我意识到在实践中有 AES NI 指令和位片 AES 实现，但它们超出了我目前的理解范围。
我从 crypto.SE 那里了解到，最简单的方法是读取所有缓存行，
或者在我进行查找之前阅读整个 table。 （这也会影响我的表现）
但是我不知道如何在软件中实现它，或者它背后的复杂概念。
在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 循环中，如果 sizeof(t[0]) 为 4，则 i 递增 8。因为 AES sbox 是一个包含 256 个元素的 unsigned char 数组当我们调用 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..
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 chars（不管 sizeof(t[0]) 恰好是什么）因为“32 chars "（或 32 字节）是作者确定的他们关心的所有 CPU 的最小缓存行大小。注意只需要从cache line的1个字节开始读取，保证整个cache line都被fetch到cache中。
What is the motivation behind sum ^= t[i] and setting ret = sum ?
一个好的编译器会注意到您正在读取的数据没有被使用，并且会避免进行“不必要的”（为了“C 抽象机”的正确性）读取以提高性能而不知道“不必要的” " read 是必要的，因为编译器不能期望知道的原因。为防止编译器像那样进行优化，您需要欺骗它认为数据已实际使用，或使用 volatile。 OpenSSL 的作者正在做这两件事（试图通过 sum ^= t[i] 和 ret sum 来欺骗编译器不进行优化；并且还使用 volatile），可能是因为（历史上）很多旧的编译器有涉及 volatile.
的错误
另请注意，仍然存在一个非常小的时序问题 - 在预取数据之后但在 table 的一部分用于 AES 之前，缓存可能会被刷新（例如通过任务切换等）；因此，攻击者仍然有可能（极小）使用缓存定时攻击来确定使用了 table AES 的哪一部分。请参阅“对缓存定时攻击预防的信心”（下文）。
Will this following simpler code help me:
编译器很可能会将您的代码变成字面上的任何内容（如果没有，它会遇到与 prefetch256() 相同的问题，并且可能会更慢，因为您正在写入内存而不仅仅是阅读）。
Are there other simpler solutions to protect my implementation from cache timing attacks?
一切都是复杂性、便携性、安全性、功能和性能之间的折衷；而“更简单”几乎总是意味着“更差的便携性”and/or“更差的质量”and/or“更差的功能”and/or“更差的性能”。你不能让质量或功能变差，同时仍然防止缓存定时攻击。你不能让性能变得更糟，因为它已经尽可能简单了。
您可能（或可能不会）通过牺牲可移植性来使其更简单。例如;如果你知道整个 table 适合一台计算机上的单个缓存行（并且与缓存行边界对齐），那么你不能对那台计算机做任何事情并说代码永远不应该用于任何其他电脑。
对缓存定时攻击预防的信心
防范缓存定时攻击的关键因素之一是攻击者拥有多少控制权。典型的场景是攻击者淹没缓存（用已知数据污染它以导致其以前的内容由于“最近最少使用”而被驱逐），然后让受害者做一些事情，然后测量它访问其已知数据的速度以确定该已知数据是否仍在缓存中或已被逐出。如果已知数据的缓存行被驱逐，则攻击者知道受害者访问了缓存中与被驱逐的缓存行具有相同位置的内容。
最坏的情况是攻击者能够非常频繁地执行此操作（例如，对于受害者执行的每条指令），缓存没有关联性（直接映射），并且攻击者要么知道关于受害者的一切使用虚拟地址和受害者的虚拟地址与缓存位置之间的关系（可能包括虚拟地址与物理地址之间的关系）或在同一进程中（例如共享库，他们可以在其中访问 table 自己以确定它是否被访问而不是依赖于其他数据的驱逐）。在这种情况下，唯一的防御措施是确保所有内存访问模式始终相同（从不依赖于任何数据）。这非常困难，但并非不可能 - 例如如果你想从 table 中读取一个字节（例如“byte = table[index]”，你不希望攻击者知道任何关于 index 的信息），你可以读取所有前面的缓存行，然后读取你想要的字节，然后读取所有后续缓存行（这样它看起来总是像整个 table 的顺序读取）并以固定速率进行这些访问（在读取你想要的字节之前没有“暂停” ”并且没有“在读取你想要的字节后暂停”，包括“没有由分支预测错误引起的暂停”）。如果你这样做；那么您可以对自己防范缓存时序攻击的能力充满信心（直至保证您的代码不受所有可能的缓存时序攻击）。
但是；攻击者几乎不可能获得那种级别的控制，编写这样的代码极其困难，而且这样的代码会有很大的性能开销。
另一个极端；您无能为力，也对您防止缓存时序攻击的能力没有信心。其他一切都介于这些极端之间。
接下来的问题是；什么是好的妥协？这取决于太多因素——攻击者拥有多少控制权，攻击者是否处于同一进程中，攻击者是否可以重复攻击（并使用概率方法来击败任何“噪音”），数据的价值有多大对攻击者来说（理智的小偷不会花费超过 2 美元试图窃取对小偷来说价值 2 美元的东西），数据对受害者来说有多少价值（没有人每天花费 100 美元来保护可以更换的东西$2），还有哪些其他缓解措施（例如，大多数操作系统现在提供“地址 space 布局随机化”）等
为了妥协；出于您的目的，我个人喜欢“让它看起来像对整个 table 的顺序读取”方法，但是一个非常简单的版本不太关心固定访问速率（或“暂停 before/after 阅读你想要的片段”并且不关心缓存行大小（如果 table 只有 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.
这是一个边缘话题。因为我想了解编程、CPU 高速缓存、读取 CPU 高速缓存行等，所以我将其张贴在这里。
我在 C/C++ 中实现 AES 算法。由于在没有硬件支持的情况下执行 GF(28) 乘法在计算上非常昂贵，因此我优化了对 AES S-box 使用查找 tables。但不幸的是，基于查找 table 的实现容易受到 cache-timing attacks 的攻击。因此，由于对 CPU 缓存非常天真，我开始了解它的工作原理，以及如何在不增加任何计算成本的情况下规避此类攻击。
我意识到在实践中有 AES NI 指令和位片 AES 实现，但它们超出了我目前的理解范围。
我从 crypto.SE 那里了解到，最简单的方法是读取所有缓存行， 或者在我进行查找之前阅读整个 table。 （这也会影响我的表现） 但是我不知道如何在软件中实现它，或者它背后的复杂概念。
在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循环中，如果sizeof(t[0])为 4，则i递增8。因为 AES sbox 是一个包含 256 个元素的unsigned char数组当我们调用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..
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 chars（不管 sizeof(t[0]) 恰好是什么）因为“32 chars "（或 32 字节）是作者确定的他们关心的所有 CPU 的最小缓存行大小。注意只需要从cache line的1个字节开始读取，保证整个cache line都被fetch到cache中。
What is the motivation behind sum ^= t[i] and setting ret = sum ?
一个好的编译器会注意到您正在读取的数据没有被使用，并且会避免进行“不必要的”（为了“C 抽象机”的正确性）读取以提高性能而不知道“不必要的” " read 是必要的，因为编译器不能期望知道的原因。为防止编译器像那样进行优化，您需要欺骗它认为数据已实际使用，或使用 volatile。 OpenSSL 的作者正在做这两件事（试图通过 sum ^= t[i] 和 ret sum 来欺骗编译器不进行优化；并且还使用 volatile），可能是因为（历史上）很多旧的编译器有涉及 volatile.
另请注意，仍然存在一个非常小的时序问题 - 在预取数据之后但在 table 的一部分用于 AES 之前，缓存可能会被刷新（例如通过任务切换等）；因此，攻击者仍然有可能（极小）使用缓存定时攻击来确定使用了 table AES 的哪一部分。请参阅“对缓存定时攻击预防的信心”（下文）。
Will this following simpler code help me:
编译器很可能会将您的代码变成字面上的任何内容（如果没有，它会遇到与 prefetch256() 相同的问题，并且可能会更慢，因为您正在写入内存而不仅仅是阅读）。
Are there other simpler solutions to protect my implementation from cache timing attacks?
一切都是复杂性、便携性、安全性、功能和性能之间的折衷；而“更简单”几乎总是意味着“更差的便携性”and/or“更差的质量”and/or“更差的功能”and/or“更差的性能”。你不能让质量或功能变差，同时仍然防止缓存定时攻击。你不能让性能变得更糟，因为它已经尽可能简单了。
您可能（或可能不会）通过牺牲可移植性来使其更简单。例如;如果你知道整个 table 适合一台计算机上的单个缓存行（并且与缓存行边界对齐），那么你不能对那台计算机做任何事情并说代码永远不应该用于任何其他电脑。
对缓存定时攻击预防的信心
防范缓存定时攻击的关键因素之一是攻击者拥有多少控制权。典型的场景是攻击者淹没缓存（用已知数据污染它以导致其以前的内容由于“最近最少使用”而被驱逐），然后让受害者做一些事情，然后测量它访问其已知数据的速度以确定该已知数据是否仍在缓存中或已被逐出。如果已知数据的缓存行被驱逐，则攻击者知道受害者访问了缓存中与被驱逐的缓存行具有相同位置的内容。
最坏的情况是攻击者能够非常频繁地执行此操作（例如，对于受害者执行的每条指令），缓存没有关联性（直接映射），并且攻击者要么知道关于受害者的一切使用虚拟地址和受害者的虚拟地址与缓存位置之间的关系（可能包括虚拟地址与物理地址之间的关系）或在同一进程中（例如共享库，他们可以在其中访问 table 自己以确定它是否被访问而不是依赖于其他数据的驱逐）。在这种情况下，唯一的防御措施是确保所有内存访问模式始终相同（从不依赖于任何数据）。这非常困难，但并非不可能 - 例如如果你想从 table 中读取一个字节（例如“byte = table[index]”，你不希望攻击者知道任何关于 index 的信息），你可以读取所有前面的缓存行，然后读取你想要的字节，然后读取所有后续缓存行（这样它看起来总是像整个 table 的顺序读取）并以固定速率进行这些访问（在读取你想要的字节之前没有“暂停” ”并且没有“在读取你想要的字节后暂停”，包括“没有由分支预测错误引起的暂停”）。如果你这样做；那么您可以对自己防范缓存时序攻击的能力充满信心（直至保证您的代码不受所有可能的缓存时序攻击）。
但是；攻击者几乎不可能获得那种级别的控制，编写这样的代码极其困难，而且这样的代码会有很大的性能开销。
另一个极端；您无能为力，也对您防止缓存时序攻击的能力没有信心。其他一切都介于这些极端之间。
接下来的问题是；什么是好的妥协？这取决于太多因素——攻击者拥有多少控制权，攻击者是否处于同一进程中，攻击者是否可以重复攻击（并使用概率方法来击败任何“噪音”），数据的价值有多大对攻击者来说（理智的小偷不会花费超过 2 美元试图窃取对小偷来说价值 2 美元的东西），数据对受害者来说有多少价值（没有人每天花费 100 美元来保护可以更换的东西$2），还有哪些其他缓解措施（例如，大多数操作系统现在提供“地址 space 布局随机化”）等
为了妥协；出于您的目的，我个人喜欢“让它看起来像对整个 table 的顺序读取”方法，但是一个非常简单的版本不太关心固定访问速率（或“暂停 before/after 阅读你想要的片段”并且不关心缓存行大小（如果 table 只有 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.