我如何理解我的 C 實現是否是恆定時間的（即抗定時攻擊）
我有一個多項式乘法的程式碼，它是用 C 語言編寫的。我聽說特定指令是否是“恆定時間”可能因架構和處理器型號而異，並且沒有任何官方文件說明這種行為。我如何理解我的程式碼是否是常數時間？
注意：“恆定時間”是指能夠抵抗定時攻擊的軟體或程式碼片段。我在 i7 第 10 代 PC 上使用 UBUNTU
不幸的是，在沒有 CPU 供應商提供的文件的情況下，您無法 100% 確定哪些算法將或不會是恆定時間。也就是說，肯定有一些經驗法則可以用來降低問題的風險。
- 任何涉及分支控制流或程式碼的條件執行的事情顯然都是一個問題。
- 即使比較操作不直接用於影響控制流，它們也可能是一個問題。問題是比較運算符通常將其結果儲存在標誌寄存器中，而從標誌寄存器中獲取單個結果的最簡單方法通常是分支或條件執行。
- 布爾值可能是一個問題，因為編譯器可能會選擇將涉及布爾值的操作替換為條件執行或分支。
- 記憶體訪問的時間可能會根據訪問的地址和記憶體的狀態而有所不同。這意味著涉及查找表的程式碼具有非恆定時間的高風險。
- 乘法和除法可以使用需要可變數量的周期才能完成的算法來實現，乘法通常在現代“應用程序”處理器上是安全的，但在微控制器上可能不安全。我不會認為任何處理器上的除法安全。
- 在某些 CPU 上，位移和旋轉可變數量的位置可能是一個問題，因為它們可能會轉化為循環（在軟體或硬體中）。
- 加法，減法，按位運算和常數移位通常是可以的。
您可能想查看https://www.bearssl.org/constanttime.html，其中更詳細地討論了這些問題。
請注意，這個出色的答案屬於他們停止貢獻的Squeamish Ossifrage ！我複制並粘貼，然後創建社區。投票這個答案不會對我產生任何影響。如果可以，請在Infosec上投票。
從提供的程式碼範例中，可以通過在給定各種輸入時對程式碼進行計時來確定正確的密碼。
首先，您實際上不應該直接檢查密碼！ 至少，您應該首先使用Argon2id之類的密碼雜湊對密碼進行雜湊處理，然後將輸入的密碼雜湊與您在使用者註冊期間（或使用者上次更改密碼時）儲存的密碼雜湊進行比較。
更好的是，您應該使用像 OPAQUE 這樣的密碼驗證密鑰協議協議，但目前這些可能超出您的薪酬等級，直到他們看到更廣泛的採用和實施。
我可以做些什麼來確保我的程式碼不會受到這種定時攻擊？
最好的開始方法是使用其他人已經編寫並有理由維護的庫常式或原語。 例如，在 NaCl/libsodium 中，您可以使用
crypto_verify_32比較兩個 32 字節的字元串，例如兩個 Argon2id 雜湊，或兩個 HMAC-SHA256 消息驗證碼。然後，回答這個問題的努力可以集中在一個地方，這個地方會受到很多關注和審查，並且會跟上進步的步伐。但是假設你沒有
crypto_verify_32，或者你想自己實現它。你能做什麼？首先，您需要了解哪些操作具有側通道。 很容易說——就像其他答案一樣——側通道的出現只是因為提前 abort。但這還不是全部。一般來說，有許多操作 （這裡用 C 來說明）可能需要一定的時間，這取決於輸入的值——我們將這些操作稱為可變時間操作，與恆定時間*形成對比：
for (i = 0; i < n; i++) if (x[i] == y[i]) return EFAIL;顯然需要更少的循環迭代，因此實際上可以保證根據 和 的秘密值在可變時間x[i]執行y[i]。即使循環沒有提前中止，一個僅僅依賴於秘密的條件
for (i = 0; i < n; i++) if (x[i]) bad++;，如果x[i]是秘密的，也可能在可變時間執行。為什麼？
- 這是一個粗略的近似。CPU 可能執行的機器指令如下所示：
0: tmp := x[i] branch to 1 if tmp is zero bad := bad + 1 1: i := i + 1 branch to 0 if i < n執行的指令數量取決於
x[i]每次迭代的值：我們跳過bad := bad + 1一些迭代。這是一個很好的模型，用於說明早期定時攻擊（例如，RSA）在Kocher 的關於定時攻擊的開創性論文中如何工作：主模冪循環無條件地計算（比如說）2048 位模平方，但計算 2048 位模乘有條件地取決於秘密指數的值。跳過乘法會大大改變整個操作所花費的時間。
- 不過，還有另一個原因，它與分支預測有關，這是使現代 CPU 在許多工作負載上執行如此之快的關鍵設計元素——即使您編寫相同數量的程式碼（例如，相同數量的機器指令，以及以某種方式保證它們在條件的每個分支中計算相同數量的周期），執行所需的時間可能取決於條件的方式。
- 一般來說，CPU 不擅長保密執行哪些指令，所以不要讓指令的選擇依賴於秘密。
表/數組查找可能需要不同的時間，具體取決於 CPU 記憶體中記憶體的記憶體。因此，如果您正在讀取的數組中的位置取決於一個秘密，那麼它所花費的時間可能取決於該秘密，該秘密已被利用通過記憶體定時恢復 AES 密鑰。
（回想起來，這使得 AES 成為一個相當有問題的設計，它有意使用依賴於密鑰的表查找！NIST公佈的理由（§3.6.2，對實現的攻擊：操作的角色）奇怪地聲稱表查找“不容易受到時間的影響儘管自那時以來已經報導了許多此類攻擊。）
x = y << z如果較大，則在某些 CPU 上，可變距離移位可能需要更多時間，如果z較小，則可能需要更少時間。（這使得RC5和 AES 決賽入圍者RC6回想起來相當有問題，因為它們有意使用與鍵相關的旋轉距離！）
- 在某些 CPU 上，乘法可能執行得更快或更慢，具體取決於輸入的上半部分是否為零。
- 原則上，32 位 CPU 上的 64 位整數加法可能需要更多時間，具體取決於是否有進位。這是因為，當
x,y和z, 是 64 位整數時，邏輯x = y + z可能看起來更像：int carry = 0; x[0] = y[0] + z[0]; if (the previous addition overflowed) carry = 1; x[1] = y[1] + z[1] + carry;因此，所花費的時間可能取決於是否存在從低 32 位的總和到高 32 位的總和的進位。（在實踐中，這通常只關心外來 CPU 或其他類型的側通道，例如與智能卡相關的功率分析，而不是筆記型電腦和手機。）
這聽起來可能有點壓倒性。我們能做什麼？
在大多數 CPU 上，有些操作通常會在恆定時間內執行。 他們是：
- 位運算:
x & y,x | y,x ^ y,~x, 和其他在 C 中沒有出現的運算，例如 AND-with-complement。- **恆定距離的移位和旋轉，**如移位
x << 3或旋轉x <<< 3（不是標準 C，但在密碼學中很常見；(x << 3) | (x >> (32 - 3))如果x是 32 位，則表示 ）。- 通常整數加法和減法:
x + y,x - y, whenx和y是（比如說）32 位 CPU 上的無符號 32 位整數，甚至在 32 位 CPU 上借助 ADD-with-carry 指令甚至是 64 位整數。- 有時整數乘法，但是關於乘法的故事很複雜，這對密碼學來說是不幸的，因為乘法很好地混合了比特並且具有有用的代數屬性。
需要說明的是：我並不是說如果您在 C 程序中使用這些操作， C 編譯器就可以保證這些操作在恆定時間內執行。我只是對CPU通常在恆定時間內執行的操作使用 C 表示法。 （稍後會詳細介紹此警告。）
“但是等等，”你抗議道，“我怎麼可能用這些操作寫出一個有用的程序呢？沒有條件？沒有循環？沒有陣列？
首先，您不必完全避開條件、循環或數組。他們就是不能依賴秘密。例如，
for (i = 0; i < 32; i++) ... x[i] ...很好。但是for (i = 0; i < m[0]; i++) ...如果m[0]應該是秘密的就不好，for (i = 0; i < m[0]; i++) ... tab[x[i]] ...如果應該是秘密的也不好x[i]。其次，你仍然可以建造這些東西！這只是有點棘手。例如，假設
buint32_t 為 0 或 1。則b - 1分別為 -1 = 0xffffffff 或 0，所以x = ((b - 1) & z) | (~(b - 1) & y);導致
x = yifb為 1 或x = zifb為 0——很像x = (b ? y : z)，但沒有分支。顯然，這需要計算和y，z因此會對性能產生一些影響！同樣，您可以通過查找表格的所有元素並使用這樣的按位運算選擇所需的元素來查找表格的元素。不如 快x[i]，但也沒有洩漏。通常，您可以將帶條件的程序轉換為不帶條件的邏輯電路，即使出於性能原因您不想這樣做。 您還可以使用其他各種類似的技巧。
crypto_verify_32假設 x 和 y 是 uint8_t 數組，您可能會像這樣草擬一個恆定時間的記憶體相等常式：uint32_t result = 0; for (i = 0; i < 32; i++) result |= x[i] ^ y[i]; return ((result - 1) >> 8) & 1;練習：這是否返回 0 表示相等而 1 表示不相等，或者 0 表示不等而 1 表示相等？
編寫這樣的程序——並採用像 X25519 這樣的密碼系統來鼓勵看起來像這樣的實現，而不是像 RSA 或 AES 這樣鼓勵涉及秘密相關分支或秘密相關表查找的實施的密碼系統——是一個很好的開始時間側渠道。
但是，有一個問題！還記得我說過 C 編譯器不保證恆定時間嗎？ 像 Clang/LLVM 這樣的智能 C 編譯器可能會認識到，通過提前中止
crypto_verify_32循環可以更有效地執行上述智能循環，並且可能會取消您為將其重寫為以恆定時間執行的邏輯電路所做的艱苦工作。（在其他情況下，它可能會對您有所幫助，例如通過轉換x = (b ? y : z);為不帶分支的條件移動指令 CMOV，但通常您不能依賴 C 編譯器的善意。）您可以採取一些技巧來阻止這種情況，例如內聯彙編片段，它會導致編譯器大致放棄所有優化假設：
uint32_t result = 0; for (i = 0; i < 32; i++) result |= x[i] ^ y[i]; asm volatile ("" ::: "memory"); return ((result - 1) >> 8) & 1;這可能適用於您的編譯器，也可能不適用於您的編譯器。為了有信心，您確實必須檢查編譯器生成的機器程式碼——即便如此，編譯器可能會執行即時優化，根據分析分析重寫機器程式碼，尤其是在 Java 等高級語言中。因此，您可能真的想用彙編語言編寫邏輯（或者使用像 qhasm 這樣的程式語言，它可以比 C 編譯器更可靠地生成經過微調的彙編語言），然後從 C 中呼叫它。
也許有一天 C 編譯器會採用一個
secret限定符，比如constorvolatile，它強制編譯器只生成已知的機器指令——在某些 CPU 模型中！——在對對象進行操作時以恆定時間執行，並阻止編譯器採取捷徑，例如從循環中依賴秘密的早期中止。但那一天還沒有到來。還有一個問題是哪些機器指令實際上在 CPU 上以恆定的時間執行，這有時是有記錄的，有時是可靠的。因此，除了進行工程以利用邏輯電路建構程序之外，您還需要進行科學以確定哪些操作實際上可以安全地在 CPU 上使用。
這讓我們回到了最初的觀點：您真的希望將維護它的工作集中在一個庫常式中，這樣每個程序員就不必在生成的程式碼和時序中跟踪變幻莫測的編譯器（和 CPU 設計！）他們自己，可以把它留給我們友好的鄰居熊。
除了恆定時間邏輯，還有其他對策嗎？有時候是的。
- 您可以將隨機雜訊注入您的邏輯，希望它會混淆攻擊者的測量。 但是他們的測量中已經存在雜訊，例如作業系統中的調度，因此他們只需要採集更多樣本——事實證明，雜訊並不是一種非常有效的側通道對策。
具體來說，人工雜訊最多會使攻擊者的成本提高大約人工雜訊與真實雜訊之比的平方，這遠低於通常認為的密碼學安全性可接受的差距。所以它主要是花費你很多時間什麼都不做。
- 您可以使用密碼系統的代數屬性對其進行隨機化，有時稱為“盲法”。 例如，您可以隨機選擇，計算where ，乘以得到，計算，然後除以，而不是計算
y^d mod nwhered是 RSA 中的秘密指數。r``s := r^e mod n``e*d ≡ 1 (mod 𝜆(n))``y``s``(y * r^e) mod n``(y * r^e)^d mod n = (r * y^d) mod n``r許多實現，例如 OpenSSL，都使用這種方法，因為它是一種簡單的方法來改進現有的加密系統（如具有必要代數結構的 RSA）實現。像隨機雜訊一樣，這不是一個壞主意，但它確實有成本：你必須為隨機化做額外的工作，你必須有模除法或反轉邏輯——而且側通道可能仍然會洩漏有關
r和的資訊d。例如，即使是盲目的模冪運算也會洩漏 Hamming 權重，除非您採取額外的對策，例如在firstd上添加隨機倍數，這可能會暴露額外的邊通道等。𝜆(n)``d
- 對於比較兩個字節串是否相等的特定情況（例如，兩個消息驗證碼），一種合理的選擇是在一次性密鑰下使用 HMAC-SHA256 等偽隨機函式族對它們進行雜湊處理
k，並檢查是否HMAC-SHA256_k(x) == HMAC-SHA256_k(y).誤報的機率是 1/2 256，這個機率比你擔心的要小。您可以安全地對 HMAC 使用可變時間相等，因為如果
x不等於，那麼y即使是在最簡單的字節字元串相等常式中的時間量（假設它不會在第一個零字節或類似的愚蠢的東西上退出！ ) 將獨立於xand的值y：有 255/256 的機率在一次迭代後停止，在兩次迭代後有 65535/65536 的機率，等等。當然，這只有在您可以在恆定時間內實現 HMAC-SHA256 時才真正有幫助！幸運的是，SHA-256 被設計為易於實現為恆定時間邏輯電路，因此 C 實現傾向於合理地抵抗側通道——但是，如果沒有別的原因，Python 會因為小的整數記憶體而給你帶來麻煩。
不幸的是，術語有點混亂。這裡的常數時間意味著時間量不會因輸入而變化*，並且與電腦科學中“常數時間”的漸近概念不同，通常寫成 O(1)，它僅表示時間量可能會因輸入而異，但受一個常數 的限制。對不起。我沒有發明術語。我可能會選擇“固定時間”與“可變時間”，但現在為時已晚——“恆定時間”已在文獻中根深蒂固。