不同長度數組的恆定時間比較
我從Bouncy Castle C# library中找到了以下程式碼片段，它似乎聲稱它是恆定時間，即使數組具有不同的長度。
/// <summary> /// A constant time equals comparison - does not terminate early if /// test will fail. /// </summary> /// <param name="a">first array</param> /// <param name="b">second array</param> /// <returns>true if arrays equal, false otherwise.</returns> public static bool ConstantTimeAreEqual(byte[] a, byte[] b) { if (null == a || null == b) return false; if (a == b) return true; int len = System.Math.Min(a.Length, b.Length); int nonEqual = a.Length ^ b.Length; for (int i = 0; i < len; ++i) { nonEqual |= (a[i] ^ b[i]); } for (int i = len; i < b.Length; ++i) { nonEqual |= (b[i] ^ ~b[i]); } return 0 == nonEqual; }但是，我聽說不可能在恆定時間內比較不同大小的數組。例如，Go crypto ConstantTimeCompare() 函式在比較之前檢查數組的長度。有人抱怨這會洩露秘密的長度。
func ConstantTimeCompare(x, y []byte) int { if len(x) != len(y) { // <--- here return 0 } var v byte for i := 0; i < len(x); i++ { v |= x[i] ^ y[i] } return ConstantTimeByteEq(v, 0) }比較不同長度的數組時應該採用哪種方法？或者你應該只是散列數據然後進行比較（因為長度相同）？
假設第一個程式碼提取被直接翻譯成機器程式碼（可能通過阻止一些編譯器優化，或使用相對愚蠢的編譯器）並在沒有進行開創性執行時優化的 CPU 上執行，執行時間與數組中的數據，除了可能在 final 中
0 == nonEqual（如果函式結果將用作條件運算符的參數，則剩餘時間依賴性不是問題，這在上下文中似乎很可能）。可以通過查看生成的程式碼和CPU 的特性來確定這一點，和/或通過仔細的檢測來確認。但是執行時間幾乎可以肯定地取決於數組的長度，在幾個方面：
- 正如另一個答案中所述，
System.Math.Min可能會。- 優化編譯器可能會處理大量第二個
for循環，因為(b[i] ^ ~b[i])總是~0. 整體nonEqual |= (b[i] ^ ~b[i]);可以換成nonEqual = ~0。完全有可能將整個循環簡化為至少執行一次的測試和有條件的nonEqual = ~0.- 即使以某種方式使上述情況不發生，也沒有理由相信第二個循環的每次執行都與第一個循環持續相同的時間：程式碼不一樣；在某些架構上，程式碼對齊很重要；數據記憶體或其他一些 CPU 優化可能會使兩個引用
b[i]比對a[i]和的引用更快b[i]；在某些架構上，這是~有代價的……- 當第二個循環根本不執行時，可能沒有獲取程式碼，並且當兩個數組的長度完全相同時它可以節省一些時間。
我們可以修復它嗎？不可移植，在 C# 或任何我知道的針對多個 CPU 的語言中。
有關係嗎？也許，但前提是這是對數組長度的最小時序依賴性。這不太可能，也很難評估：沒有可移植的方法來及時設置陣列，而不管它的大小！
比較不同長度的數組時應該採用哪種方法？
嘗試重新制定問題/方法，以便在恆定時間內執行此類比較的需要消失。例如，如果我們想隱藏密碼的長度，我們可以在攻擊者無法對雜湊操作計時的情況下將密碼轉換為雜湊一次，然後對要比較的字元串進行雜湊，並在常量中比較等長雜湊時間。如果即使這很困難（編譯器、JIT 甚至 CPU 架構優化都可以將循環優化
ConstantTimeCompare為具有數據時序依賴性的東西），我們也許可以比較使用相同秘密隨機密鑰計算的雜湊的 (H)MAC。更一般地說，很難證明沒有時間依賴性。如果沒有對編譯器和執行時環境的精細控制，就不可能從高級語言中獲得。最好的做法是將程式碼中必要的地方減少到絕對最低限度。或者將問題轉移到專用於該環境的環境中，例如安全 CPU，它旨在防止時序側通道（包括使用具有精心設計和指定時序特性的 CPU，使執行時間可精確預測）和其他側通道（功率分析，故障注入……）。
你的問題是
min.constant time min如果你有一個恆定時間減法器和加法器，這是一種製作方法，
- 讓 $ Sub(x,y) $ 是一個常數時間減法器。
- 讓 $ Add(x,y) $ 是一個常數時間加法器。
- 讓 $ MSB(x) $ 返回符號位。
//Inputs x and y are arrays with length property //Returns the min of x and y in constant time constantTimeMin(x,y) A = Sub(x.length, y.length) return Add(MSB(A)*x,~MSB(A)*y)