本文來自讀者“程序猿石頭”的投稿文章《 這 10 行比較字符串相等的代碼給我整懵了，不信你也來看看 》，原文寫的很好，但不夠直接了當，信息密度不夠高，所以我對原文進行大量的刪減、裁剪、改寫和添加，主要刪除了一些沒有信息的段落，主要加入瞭如何實施計時攻擊相關的其它內容，讓這篇文章中的知識更系統一些，並且還指出了其它的一些問題。所以，我把標題也改成了《計時攻擊》。

另類的字符串比較

在 Java 的 Play Framework 裏有 一段代碼 用來驗證cookie(session)中的數據是否合法（包含簽名的驗證）的代碼，如下所示： 

boolean safeEqual(String a, String b) {
   if (a.length() != b.length()) {
       return false;
   }
   int equal = 0;
   for (int i = 0; i < a.length(); i++) {
       equal |= a.charAt(i) ^ b.charAt(i);
   }
   return equal == 0;
}

相信剛看到這段源碼的人會感覺挺奇怪的，這個函數的功能是比較兩個字符串是否相等，如果要判斷兩個字符串是否想等，正常人的寫法應該是下面這個樣子的（來自JDK8 的 String.equals() -有刪減）： 

public boolean equals(Object anObject) {
    String anotherString = (String)anObject;
    int n = value.length;
    if (n == anotherString.value.length) {
        char v1[] = value;
        char v2[] = anotherString.value;
        int i = 0;
        while (n-- != 0) {
            if (v1[i] != v2[i]) // <- 遇到第一個不一樣的字符時退出
                return false;
            i++;
        }
        return true;
    }
    return false;
}

我們可以看到，在比較兩個字符串是否相等的正常寫法是：

  1. 先看一下兩個字符串長度是否相等，如果不等直接返回 false。
  2. 如果長度相等，則依次判斷每個字符是否相等，如果不等則返回 false。
  3. 如果全部相等，則返回 true。

然而，Play Framework裏的代碼卻不是這樣的，尤其是上述的第2點，用到了異或，熟悉位操作的你很容易就能看懂，通過異或操作 1^1=0 , 1^0=1 , 0^0=0 ，來比較每一位，如果每一位都相等的話，兩個字符串肯定相等，最後存儲累計異或值的變量 equal 必定爲 0，否則爲 1。

但是，這種異或的方式不是遇到第一個不一樣的字符就返回 false 了，而是要做全量比較，這種比較完全沒有效率，這是爲什麼呢？原因是爲了安全。

計時攻擊(Timing Attack)

計時攻擊（ Wikipedia ）是 旁道攻擊 (或稱”側信道攻擊”， Side Channel Attack， 簡稱SCA) 的一種， 旁通道攻擊 是指基於從計算機系統的實現中獲得的信息的任何攻擊 ，而不是基於實現的算法本身的弱點（例如，密碼分析和軟件錯誤）。時間信息，功耗，電磁泄漏甚至聲音可以提供額外的信息來源，可以加以利用。在很多物理隔絕的環境中（黑盒），往往也能出奇制勝，這類新型攻擊的有效性遠高於傳統的密碼分析的數學方法。（注：企圖通過社會工程學欺騙或強迫具有合法訪問權限的人來破壞密碼系統通常不被視爲旁道攻擊）

計時攻擊是最常用的攻擊方法。那麼，正常的字符串是怎麼被進行時間攻擊的呢？

我們知道，正常的字符件比較，一旦遇到每一個不同的字符就返回失敗了，所以，理論上來說，前面只有2個字符相同字符串比較的耗時，要比前面有10個字符相同的比較要長。你會說，這能相差多少呢？可能幾微秒吧。但是，我們可以放大這個事。比如，在Web應用時，記錄每個請求的返回所需趕時間（一般是毫秒級），如果我們重複50次，我們可以查看平均時間或是p50的時間，以瞭解哪個字符返回的時間比較長，如果某個我們要嘗試的字符串的時間比較長，我們就可以確定地得出這個這字符串的前面一段必然是正確的。

這個事情，可以用來做HMAC的攻擊，所謂HMAC，你可以參看本站的《 HTTP API 認證授權術 》文章瞭解更多的細節。簡單來說，HMAC，就是客戶端輸來一個字符串和其簽名字符串（HMAC），然後，後端的程序用一個私鑰來對客戶端輸來的字符串進行簽名得到簽名字符串，然後再比較這個簽名字符串（所謂簽名，也就是使用MD5或SHA這樣的哈希算法進行編碼）

寫成僞代碼大概是這個樣子：

bool verify(message, digest) {
    my_digest = HMAC(key, message);
    return my_digest.equals(digest) ;
}

於是，攻擊者在不知道簽名算法，但是知道API的調用時，就可以通過一邊窮舉簽名，一邊統計調用時間的方式來非常有效率的破解簽名。在這篇文章《 HMAC Timing Attacks 》中記錄了整個攻擊的過程。文章中記載：

如果一個簽名有40個長度，如： f5acdffbf0bb39b2cdf59ccc19625015b33f55fe 攻擊者，從 0000000000000000000000000000000000000000 開始窮舉，下面是窮舉的時間統計。 

0 0.005450913
1 0.005829198
2 0.004905407
3 0.005286876
4 0.005597611
5 0.004814430
6 0.004969118
7 0.005335884
8 0.004433182
9 0.004440246
a 0.004860263
b 0.004561121
c 0.004463188
d 0.004406799
e 0.004978907
f 0.004887240

可以看到，第一次測試通過的計時結果（以秒爲單位），而值“ f”與樣品的其餘部分之間沒有較大的變化量。所有結果看起來都非常接近。換句話說，有很多噪聲掩蓋了信號。因此，有必要進行多個採樣（對測試進行縮放）並使用統計工具從噪聲中濾除信號。爲了將信號與噪聲分開，我們必須按任意常數對測試進行縮放。通過實驗，作者發現500是一個很好的數字。換句話說：運行測試500次，並記錄500個試驗中每個試驗的結果。然後，通過人的肉眼觀察可以可能看到 f 的調用明顯比別的要長，但是這種方法很難自動化。

所以，作者給了另一個統計算法，這個算法向服務器分別從 0 到 f 發出16個請求，並記錄每個請求的響應時間，並將它們排序爲1-16，其中1是最長（最慢）的請求，而16是最短（最快的請求），分別記錄 0 – f 的名次，然後重複上述的過程 500 次。如下所示（僅顯示25個樣本，字符“ 0”首先被排名7、1、3，然後再次排名3……）：

{
"0"=>[7, 1, 3, 3, 15, 5, 4, 9, 15, 10, 13, 2, 14, 9, 4, 14, 7, 9, 15, 2, 14, 9, 14, 6, 11...],
"1"=>[13, 4, 7, 11, 0, 4, 0, 2, 14, 11, 6, 7, 2, 2, 14, 11, 8, 10, 5, 13, 11, 7, 4, 9, 3...],
"2"=>[14, 5, 15, 5, 1, 0, 3, 1, 9, 12, 4, 4, 1, 1, 8, 6, 9, 4, 9, 5, 8, 3, 12, 8, 5...],
"3"=>[15, 2, 9, 7, 2, 1, 14, 11, 7, 8, 8, 1, 4, 7, 12, 15, 13, 0, 4, 1, 7, 0, 3, 0, 0...],
"4"=>[12, 10, 14, 15, 8, 9, 10, 12, 10, 4, 1, 13, 15, 15, 3, 1, 6, 8, 2, 6, 15, 4, 0, 3, 2...],
"5"=>[5, 13, 13, 12, 7, 8, 13, 14, 3, 13, 2, 12, 7, 14, 2, 10, 12, 5, 8, 0, 4, 10, 5, 10, 12...]
"6"=>[0, 15, 11, 13, 5, 15, 8, 8, 4, 7, 12, 9, 10, 11, 11, 7, 0, 6, 0, 9, 2, 6, 15, 13, 14...]
"7"=>[1, 9, 0, 10, 6, 6, 2, 4, 12, 9, 5, 10, 5, 10, 7, 2, 4, 14, 6, 7, 13, 11, 6, 12, 4...],
"8"=>[4, 0, 2, 1, 9, 11, 12, 13, 11, 14, 0, 15, 9, 0, 0, 13, 11, 13, 1, 8, 6, 5, 11, 15, 7...],
"9"=>[11, 11, 10, 4, 13, 7, 6, 3, 2, 2, 14, 5, 3, 3, 15, 9, 14, 7, 10, 3, 0, 14, 1, 5, 15...],
"a"=>[8, 3, 6, 14, 10, 2, 7, 5, 1, 3, 3, 0, 0, 6, 10, 12, 15, 12, 12, 15, 9, 13, 13, 11, 9...],
"b"=>[9, 12, 5, 8, 3, 3, 5, 15, 0, 6, 11, 11, 12, 8, 1, 3, 1, 11, 11, 14, 5, 1, 2, 1, 6...],
"c"=>[6, 7, 8, 2, 12, 10, 9, 10, 6, 1, 10, 8, 6, 4, 6, 4, 3, 2, 7, 11, 1, 8, 7, 2, 13...],
"d"=>[2, 14, 4, 0, 14, 12, 11, 0, 8, 0, 15, 3, 8, 12, 5, 0, 10, 1, 3, 4, 12, 12, 8, 14, 8...],
"e"=>[10, 8, 12, 6, 11, 13, 1, 6, 13, 5, 7, 14, 11, 5, 9, 5, 2, 15, 14, 10, 10, 2, 10, 4, 1...],
"f"=>[3, 6, 1, 9, 4, 14, 15, 7, 5, 15, 9, 6, 13, 13, 13, 8, 5, 3, 13, 12, 3, 15, 9, 7, 10...]
}

然後將每個字符的500個排名進行平均，得出以下示例輸出：

"f", 5.302
"0", 7.17
"6", 7.396
"3", 7.472
"5", 7.562
"a", 7.602
"2", 7.608
"8", 7.626
"9", 7.688
"b", 7.698
"1", 7.704
"e", 7.812
"4", 7.82
"d", 7.826
"7", 7.854
"c", 7.86

於是， f 就這樣脫穎而出了。然後，再對剩餘的39個字符重複此算法。

這是一種統計技術，可讓我們從噪聲中濾除信號。因此：16 * 500 * 40 = 320,000個請求，而蠻力窮舉需要花費16 ^ 40個請求。

另外，學術界的這篇論文就宣稱用這種計時攻擊的方法破解了 OpenSSL 0.9.7 的RSA加密算法了。這篇 Remote Timing Attacks are Practical （PDF） 論文中指出（我大致翻譯下摘要，感興趣的同學可以通過鏈接去看原文）：

計時攻擊往往用於攻擊一些性能較弱的計算設備，例如一些智能卡。我們通過實驗發現，也能用於攻擊普通的軟件系統。本文通過實驗證明，通過這種計時攻擊方式能夠攻破一個基於 OpenSSL 的 web 服務器的私鑰。結果證明計時攻擊用於進行網絡攻擊在實踐中可行的，因此各大安全系統需要抵禦這種風險。

參考資料：

各語言的對應函數

下面，我們來看看各個語言對計時攻擊的對應函數

PHP: https://wiki.php.net/rfc/timing_attack 

bool hash_equals ( string $known_string , string $user_string )

boolean password_verify ( string $password , string $hash )

Java:  Java 在1.6時是有問題的，其在 1.6.0._17(6u17)才Fix了這個問題（ 相關的fix patch ），下面是 JDK8源碼 – MessageDigest.isEqual() 

public static boolean MessageDigest.isEqual(byte[] digesta, byte[] digestb) {
    if (digesta == digestb) return true;
    if (digesta == null || digestb == null) {
        return false;
    }
    if (digesta.length != digestb.length) {
        return false;
    }

    int result = 0;
    // time-constant comparison
    for (int i = 0; i < digesta.length; i++) {
        result |= digesta[i] ^ digestb[i];
    }
    return result == 0;
}

C/C++：沒有在常用的庫中找到相關的函數，還是自己寫吧。 

int util_cmp_const(const void * a, const void *b, const size_t size) 
{
  const unsigned char *_a = (const unsigned char *) a;
  const unsigned char *_b = (const unsigned char *) b;
  unsigned char result = 0;
  size_t i;

  for (i = 0; i < size; i++) {
    result |= _a[i] ^ _b[i];
  }

  return result; /* returns 0 if equal, nonzero otherwise */
}

Python– 下面的代碼摘自Django 

#Taken from Django Source Code

def constant_time_compare(val1, val2):
    """
    Returns True if the two strings are equal, False otherwise.

    The time taken is independent of the number of characters that match.

    For the sake of simplicity, this function executes in constant time only
    when the two strings have the same length. It short-circuits when they
    have different lengths.
    """
    if len(val1) != len(val2):
        return False
    result = 0
    for x, y in zip(val1, val2):
        result |= ord(x) ^ ord(y)
    return result == 0

One More Thing

在文章結束前，再提一個事。

上面的所有的代碼都還有一個問題——他們都要判斷字符串的長度是否一致，如果不一致就返回了，所以，通過時間攻擊是可以知道字符串的長度的。比如：你的密碼長度。理論上來說，字符串的長度也應該屬於“隱私數據”。

(全文完)

關注CoolShell微信公衆賬號和微信小程序

（轉載本站文章請註明作者和出處 酷 殼 – CoolShell ，請勿用於任何商業用途）

——=== 訪問 酷殼404頁面 尋找遺失兒童。 ===——

相關文章