檢視時序攻擊的原始碼

在密碼學中，時間攻擊（timing attack）是一種旁路攻擊（side-channel attack），攻擊者試圖透過分析執行密碼學演算法所需的時間來破解密碼系統。電腦中的每一個邏輯運算都需要時間來執行，而這個時間會因輸入的不同而有所差異；透過精確測量每個運算的時間，攻擊者或許能夠反推出輸入的內容。

系統回應特定查詢所需時間的測量，可能會洩漏資訊。這些資訊對攻擊者的幫助有多大，取決於許多變數，例如密碼系統的設計、執行系統的 CPU、所使用的演算法、各種實作細節、時間攻擊的應對措施，以及時間測量的精確度。任何具有資料相依時間變化的演算法都容易受到時間攻擊。移除時間相依性是困難的，因為執行時間的變化可能發生在任何層級上。

對時間攻擊的脆弱性在設計階段常被忽視，且可能因編譯器最佳化而被無意中引入。應對措施包括盲化（blinding）和常數時間函數（constant-time functions）。

== 常數時間的挑戰 ==
許多密碼學演算法可以透過減少或消除資料相依的時間資訊的方式來實作（或由代理遮罩），這被稱為常數時間演算法（constant-time algorithm）。此類演算法的實作有時被稱為時間安全實作（timing-safe implementation）。考慮一種實作，其中每次對子程式的呼叫總是在恰好 x 秒內返回，x 是該常式在所有可能的授權輸入下執行所需的最長時間。在這樣的實作中，演算法的執行時間較不可能洩漏關於該次調用所提供資料的資訊。這種方法的缺點是，所有執行的時間都變成了該函數最差情況下的效能。

時間的資料相依性可能源於以下之一：
* 非本地記憶體存取，因為 CPU 可能會快取資料。在具有資料快取的 CPU 上執行的軟體，會因記憶體查詢快取而表現出資料相依的時間變化。
* 條件跳躍。現代 CPU 會嘗試透過猜測來推測執行（speculatively execute）過條件跳躍。猜錯（對於基本上是隨機的秘密資料而言並不少見）會導致可測量的巨大延遲，因為 CPU 需要嘗試回溯。這需要編寫無分支程式碼。
* 某些「複雜的」數學運算，取決於實際的 CPU 硬體：
** 整數除法幾乎總是非恆定時間。CPU 使用一個微碼迴圈，當除數或被除數較小時，會使用不同的程式碼路徑。
** 沒有桶形移位器（barrel shifter）的 CPU 會在迴圈中執行移位和旋轉，一次一個位置。因此，移位的量不能是秘密。
** 較舊的 CPU 以類似除法的方式執行乘法。

== 範例 ==

用於模冪運算的平方乘演算法，其執行時間與金鑰中「1」位元的數量成線性關係。雖然僅「1」位元的數量遠不足以輕易找到金鑰，但使用相同金鑰和不同輸入的重複執行，可用於對時間資訊進行統計相關性分析，從而完全恢復金鑰，即使是被動攻擊者也能做到。觀察到的時間測量通常包含雜訊（來源如網路延遲、或每次存取磁碟機的差異，以及用於從傳輸錯誤中恢復的錯誤修正技術）。儘管如此，時間攻擊對於一些加密演算法是可行的，包括 RSA、ElGamal 和數位簽章演算法。

2003年，Boneh 和 Brumley 展示了一種針對啟用 SSL 的網頁伺服器的實用網路時間攻擊，該攻擊基於一個不同的漏洞，與使用中國剩餘定理最佳化的 RSA 有關。在他們的實驗中，實際的網路距離很小，但攻擊在數小時內成功恢復了伺服器的私鑰。這次演示導致了 SSL 實作中盲化技術的廣泛部署和使用。在此情境下，盲化旨在消除金鑰與加密時間之間的關聯。

某些版本的 Unix 使用一種相對昂貴的 crypt 程式庫函數實作，將一個 8 字元的密碼雜湊成一個 11 字元的字串。在舊硬體上，這個計算刻意地需要一段可測量的長時間：在某些情況下長達二至三秒。早期版本的 Unix 中的登入程式僅在系統識別出登入名稱時才執行 crypt 函數。這透過時間洩漏了關於登入名稱有效性的資訊，即使密碼不正確。攻擊者可以利用這種洩漏，首先應用暴力破解來產生一個已知有效的登入名稱列表，然後僅將這些名稱與大量已知經常使用的密碼結合，嘗試取得存取權限。若沒有任何關於登入名稱有效性的資訊，執行這種方法所需的時間將增加數個數量級，使其基本上無用。後來的 Unix 版本修復了這個漏洞，無論登入名稱是否有效，都會執行 crypt 函數。

在單一系統上運行的兩個原本安全隔離的行程，若使用快取記憶體或虛擬記憶體，可以透過在一個行程中故意引發分頁錯誤及／或快取失誤，然後監測另一個行程存取時間的變化來進行通訊。同樣地，如果一個應用程式是受信任的，但其分頁／快取受到分支邏輯的影響，第二個應用程式可能可以透過監測存取時間的變化來確定與分支條件比較的資料值；在極端例子中，這可以恢復密碼學金鑰的位元。

2017 年的 Meltdown 和 Spectre 攻擊迫使 CPU 製造商（包括 Intel、AMD、ARM 和 IBM）重新設計其 CPU，這兩種攻擊都依賴於時間攻擊。截至 2018 年初，世界上幾乎所有的電腦系統都受到 Spectre 的影響。

在 2018 年，許多網際網路伺服器仍然對原始 RSA 時間攻擊的輕微變種存有漏洞，這距離最初的漏洞被發現已過了二十年。

=== 字串比較演算法 ===
以下 C 程式碼展示了一種典型的不安全字串比較，它在字元不匹配時立即停止測試。例如，比較 "ABCDE" 與 "ABxDE" 時，它會在 3 次迴圈迭代後返回：

<syntaxhighlight lang="c">
bool insecure_string_compare(const void *a, const void *b, size_t length) {
  const char *ca = a, *cb = b;
  for (size_t i = 0; i < length; i++)
    if (ca[i] != cb[i])
      return false;
  return true;

}
</syntaxhighlight>

相比之下，以下版本透過測試所有字元並使用位元運算來累積結果，以常數時間執行：
<syntaxhighlight lang="c">
bool constant_time_string_compare(const void *a, const void *b, size_t length) {
  const char *ca = a, *cb = b;
  bool result = true;
  for (size_t i = 0; i < length; i++)
    result &= ca[i] == cb[i];
  return result;

}
</syntaxhighlight>

在 C 程式庫函數的世界中，第一個函數類似於 `memcmp`，而後者類似於 NetBSD 的 `consttime_memequal` 或 OpenBSD 的 `timingsafe_bcmp` 和 `timingsafe_memcmp`。在其他系統上，可以使用像 OpenSSL 和 libsodium 這樣的密碼學程式庫中的比較函數。

== 註釋 ==

==參考資料==

==延伸閱讀==
* Paul C. Kocher. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. CRYPTO 1996: 104–113

*  &nbsp; 描述了 dudect，一個用來對不同資料計時一段程式碼的簡單程式。

Category:旁路攻擊

[[分類: 待校正]]