字節數組相等性測試的時序漏洞？

以下用於測試 MAC 相等性的程式碼會洩漏時序資訊嗎？

bool equal(unsigned char *a, unsigned char *b, int len) {
   unsigned char c = 0;
   for (int i = 0; i < len; i++) {
       c |= a[i] ^ b[i];
   }
   return c == 0;
}

更準確地說，最後一個表達式是否c == 0洩漏了計時資訊？

我不這麼認為，因為它不允許知道不匹配的位置。

為什麼一些加密庫使用複雜的表達式將 c 轉換為 1 或 0 值，而不是稍後簡單地將該值與簡單的 == 與 1 (或 0) 進行比較？

MAC不匹配和相同MAC條件之間的時間差異是否相關？

c == 0與您的其他程式碼一樣，比較可能會在恆定時間內執行。

但是，不能保證它會，而且很難想像可能會有一些編譯器和 CPU 組合在那裡它可能不會。當然，對於任何不是針對特定 CPU 型號和版本的彙編編寫的程式碼，基本上都是如此。

畢竟，C 語言標準實際上並沒有提供任何關於執行時間的保證，對於一個足夠聰明的編譯器來查看你的程式碼來說，這是完全有效的，去“嘿！看起來你正在嘗試比較兩個字節數組為了平等！” 並決定用呼叫memcmp()或等效的方法替換您的程式碼。而且，正如您從下面的結果中看到的那樣，現代編譯器實際上已經接近這種聰明程度，如果它們還沒有完全達到的話。

實際上，我懷疑您的程式碼沒有像那樣優化的真正原因是因為編譯器作者或多或少有意識地決定不讓他們的編譯器將其辨識為記憶體比較，假設如果您正在編寫您的比較程式碼以如此復雜的方式進行，您可能正在做一些不尋常的事情，並且不希望將其替換為memcmp().

---

您可以使用Godbolt Compiler Explorer查看常見的編譯器如何將您的程式碼轉換為程序集。事實證明，即使在相同的 CPU 架構上，結果很大程度上取決於編譯器和選擇的優化級別。

（我在下面對各種編譯器生成的 x86-64 程序集進行了相當長的討論，因為它本身有點有趣，但它實際上只是作為說明編譯器輸出變化的一個例子。隨意跳過它.)

作為一個相當典型的例子，當告訴你優化你的程式碼以獲得最小尺寸（-Os）時，GCC 7.2 會生成一段相當漂亮和簡單的彙編程式碼：

equal(unsigned char*, unsigned char*, int):
 xor eax, eax
 xor ecx, ecx
.L3:
 cmp edx, eax
 jle .L2
 mov r8b, BYTE PTR [rdi+rax]
 xor r8b, BYTE PTR [rsi+rax]
 inc rax
 or ecx, r8d
 jmp .L3
.L2:
 test cl, cl
 sete al
 ret

彙編的最後三行對應於您的return (c == 0)語句，實際上，對於所有編譯器（即對於 x86-64 平台）和優化級別，輸出的那部分看起來幾乎相同（模寄存器選擇）。我確實希望它以恆定的時間執行，假設時間test不依賴於數據，它確實不應該依賴於數據。

（在最壞的情況下，如果在某些 CPU 架構上不是恆定時間，我預計最可能的時序差異很可能在 casec == 0和之間c != 0，無論如何程式碼都會通過其返回值顯示出來。當然，如果你不希望該返回值通過時間洩漏，例如因為它僅用作更複雜條件的一個輸入，其各個輸入應該是秘密的，那麼即使洩漏也可能太多了。）

當然，典型的時序攻擊目標不是最終字節測試，而是比較循環本身。這就是編譯器差異真正出現的地方。例如，在優化級別 1或級別 2中，GCC 的輸出看起來與上面的程式碼非常相似。（主要區別在於循環條件測試移到了末尾，len <= 0而是在程式碼頂部插入了一個顯式測試。）然而，在優化級別 3 中，發生了一些奇怪的事情，輸出變成了這個展開的怪物：

equal(unsigned char*, unsigned char*, int):
 test edx, edx
 jle .L9
 mov rcx, rdi
 lea r8d, [rdx-1]
 mov r9d, 17
 neg rcx
 push rbp
 push rbx
 and ecx, 15
 lea eax, [rcx+15]
 cmp eax, 17
 cmovb eax, r9d
 cmp r8d, eax
 jb .L10
 test ecx, ecx
 je .L11
 movzx r8d, BYTE PTR [rdi]
 movzx r10d, BYTE PTR [rsi]
 xor r10d, r8d
 cmp ecx, 1
 je .L12
 movzx eax, BYTE PTR [rdi+1]
 xor al, BYTE PTR [rsi+1]
 or r10d, eax
 cmp ecx, 2
 je .L13
 movzx eax, BYTE PTR [rdi+2]
 xor al, BYTE PTR [rsi+2]
 or r10d, eax
 cmp ecx, 3
 je .L14
 movzx eax, BYTE PTR [rdi+3]
 xor al, BYTE PTR [rsi+3]
 or r10d, eax
 cmp ecx, 4
 je .L15
 movzx eax, BYTE PTR [rdi+4]
 xor al, BYTE PTR [rsi+4]
 or r10d, eax
 cmp ecx, 5
 je .L16
 movzx eax, BYTE PTR [rdi+5]
 xor al, BYTE PTR [rsi+5]
 or r10d, eax
 cmp ecx, 6
 je .L17
 movzx eax, BYTE PTR [rdi+6]
 xor al, BYTE PTR [rsi+6]
 or r10d, eax
 cmp ecx, 7
 je .L18
 movzx eax, BYTE PTR [rdi+7]
 xor al, BYTE PTR [rsi+7]
 or r10d, eax
 cmp ecx, 8
 je .L19
 movzx eax, BYTE PTR [rdi+8]
 xor al, BYTE PTR [rsi+8]
 or r10d, eax
 cmp ecx, 9
 je .L20
 movzx eax, BYTE PTR [rdi+9]
 xor al, BYTE PTR [rsi+9]
 or r10d, eax
 cmp ecx, 10
 je .L21
 movzx eax, BYTE PTR [rdi+10]
 xor al, BYTE PTR [rsi+10]
 or r10d, eax
 cmp ecx, 11
 je .L22
 movzx eax, BYTE PTR [rdi+11]
 xor al, BYTE PTR [rsi+11]
 or r10d, eax
 cmp ecx, 12
 je .L23
 movzx eax, BYTE PTR [rdi+12]
 xor al, BYTE PTR [rsi+12]
 or r10d, eax
 cmp ecx, 13
 je .L24
 movzx eax, BYTE PTR [rdi+13]
 xor al, BYTE PTR [rsi+13]
 or r10d, eax
 cmp ecx, 14
 je .L25
 movzx eax, BYTE PTR [rsi+14]
 xor al, BYTE PTR [rdi+14]
 or r10d, eax
 mov eax, 15
.L4:
 mov ebp, edx
 pxor xmm1, xmm1
 sub ebp, ecx
 mov r8d, ecx
 xor r9d, r9d
 mov ebx, ebp
 lea r11, [rdi+r8]
 xor ecx, ecx
 shr ebx, 4
 add r8, rsi
.L6:
 movdqu xmm0, XMMWORD PTR [r8+rcx]
 add r9d, 1
 pxor xmm0, XMMWORD PTR [r11+rcx]
 add rcx, 16
 cmp ebx, r9d
 por xmm1, xmm0
 ja .L6
 movdqa xmm0, xmm1
 mov ecx, ebp
 and ecx, -16
 psrldq xmm0, 8
 por xmm1, xmm0
 add eax, ecx
 movdqa xmm0, xmm1
 psrldq xmm0, 4
 por xmm1, xmm0
 movdqa xmm0, xmm1
 psrldq xmm0, 2
 por xmm1, xmm0
 movdqa xmm0, xmm1
 psrldq xmm0, 1
 por xmm1, xmm0
 movaps XMMWORD PTR [rsp-40], xmm1
 movzx r8d, BYTE PTR [rsp-40]
 or r8d, r10d
 cmp ebp, ecx
 je .L7
.L3:
 cdqe
.L8:
 movzx ecx, BYTE PTR [rdi+rax]
 xor cl, BYTE PTR [rsi+rax]
 add rax, 1
 or r8d, ecx
 cmp edx, eax
 jg .L8
.L7:
 test r8b, r8b
 sete al
 pop rbx
 pop rbp
 ret
.L14:
 mov eax, 3
 jmp .L4
.L9:
 mov eax, 1
 ret
.L12:
 mov eax, 1
 jmp .L4
.L13:
 mov eax, 2
 jmp .L4
.L10:
 xor eax, eax
 xor r8d, r8d
 jmp .L3
.L15:
 mov eax, 4
 jmp .L4
.L16:
 mov eax, 5
 jmp .L4
.L19:
 mov eax, 8
 jmp .L4
.L17:
 mov eax, 6
 jmp .L4
.L11:
 xor eax, eax
 xor r10d, r10d
 jmp .L4
.L18:
 mov eax, 7
 jmp .L4
.L20:
 mov eax, 9
 jmp .L4
.L21:
 mov eax, 10
 jmp .L4
.L22:
 mov eax, 11
 jmp .L4
.L23:
 mov eax, 12
 jmp .L4
.L24:
 mov eax, 13
 jmp .L4
.L25:
 mov eax, 14
 jmp .L4

看起來 GCC 已經使用SSE指令對 XOR/OR 循環進行了矢量化處理，以一次處理 16 個字節，並使用一堆額外的特殊情況程式碼來處理可能不是 16 的倍數的可能性。乍一看，我懷疑這一點可能仍然以恆定的時間執行（對於任何給定的值），但我不會超過它的零錢。len``len

FWIW，用len常量替換參數16擺脫了所有特殊情況的處理，並產生了這個非常優雅的彙編程式碼，沒有任何跳轉或循環。從字面上翻譯回C / C ++，它的基本作用是：

bool equal(unsigned char *a, unsigned char *b) {
   uint128_t c = *(uint128_t *)a ^ *(uint128_t *)b;
   c |= (c >> 64);
   c |= (c >> 32);
   c |= (c >> 16);
   c |= (c >>  8);
   return (unsigned char)c == 0;
}

至於其他編譯器，Clang 的輸出在低優化級別看起來與 GCC 非常相似，但在優化級別-O2及以上，事情變得比 GCC 更奇怪。同樣，這顯然是用 SSE 向量化的，但是（如果我正確解析程式碼）它一次只讀取輸入 4 個字節，並做一些非常奇怪的寄存器內字節洗牌。

ICC 輸出的核心循環-O3看起來與 GCC 的矢量化相似，儘管其餘程式碼完全不同。FWIW，如果您將長度固定為 16 個字節，ICC根本不會對程式碼進行矢量化，儘管它會展開它。此外，ICC at-O2及更高版本是我發現的唯一一個不使用test+sete組合進行最終c == 0測試的 x86-64 編譯器；它使用test+cmove代替：

 mov edx, 1
 test al, al
 mov eax, 0
 cmove eax, edx

---

無論如何，在實踐中，真正確信您的程式碼在恆定時間內執行的唯一方法是（首先檢查程序集輸出中是否存在潛在時序問題的任何跡象，然後）對其進行測試。

例如，這是一個快速而骯髒的線上基準測試，顯示（至少對於使用的特定平台、編譯器、選項和參數）您的程式碼似乎是恆定時間的：

前兩個測試（AllDifferent 和 AllSame）是一般的基線時序測試，接下來的兩個（FirstHalfSame 和 LastHalfSame）執行比較循環，看它的執行時間是否取決於匹配的前綴/後綴的長度，最後兩個（CaseFlipped和 LSBFlipped）c == 0通過比較兩個字元串來進行最終測試，這兩個字元串的不同之處僅在於每個字節中的特定位被翻轉。

當然，在實踐中，您應該使用您所針對的特定編譯器和硬體（或者盡可能廣泛地選擇兩者，如果您沒有特定目標）並使用實際輸入（例如只是常量字元串）以減少編譯器優化弄亂您的基準的機會。

（例如，在進行上面的快速基準測試時，我注意到將比較的輸出分配給全域變數是必要的，以阻止編譯器完全優化所有比較（！）並使它們都以與“Noop”基線循環。此外，在 AllSame 測試中，我發現 Clang 實際上足夠聰明，如果兩個輸入都指向相同的地址，則可以優化比較，所以我必須使用兩個具有相同內容的單獨字元串才能正確測試它。基準測試可能會像那樣棘手。）

引用自：https://crypto.stackexchange.com/questions/51433