定時安全地比較字符串

Question

Tcl是否有任何內置函數用於以時間安全的方式比較字符串，所以沒有祕密由於短路而泄漏？

string equalstring equal從左邊開始，返回第一個差異，所以它不適合比較機密。

具體來說，我想比較兩個sha256 HMAC。 Double HMAC也可以解決泄漏問題，但我想找到一個時間安全的比較功能。

Answer 1

假設你正在處理的兩個相同長度的字符串（例如，HMACs），那麼你可以申請一個比較每個字符和積累的結果：

proc safeequal {s1 s2} { 
    set equal 1 
    foreach c1 [split $s1 ""] c2 [split $s2 ""] { 
     set equal [expr {$equal & ($c1 eq $c2)}] 
    } 
    return $equal 
} 

現在，有可能是由於split一些定時效果做角色共享，但他們將真很難利用來確定弦的內容，因爲定時不能用位置來識別，並且在任何情況下都會降低噪音。我無法將我的系統安置在任何接近安靜的地方，甚至在比較兩個字符串（大約HMAC長度）在每個字符處相同並比較兩個在每個字符處不同的字符串之間看到差異。

% time {safeequal qwertyuiopasdfghjklzxcvbnm qwertyuiopasdfghjklzxcvbnm} 100000 
9.847818689999999 microseconds per iteration 
% time {safeequal qwertyuiopasdfghjklzxcvbnm QWERTYUIOPASDFGHJKLZXCVBNM} 100000 
9.78685247 microseconds per iteration 
% time {safeequal qwertyuiopasdfghjklzxcvbnm qwertyuiopasdfghjklzxcvbnm} 100000 
9.72245421 microseconds per iteration 
% time {safeequal qwertyuiopasdfghjklzxcvbnm QWERTYUIOPASDFGHJKLZXCVBNM} 100000 
9.88214891 microseconds per iteration 

Answer 2

一個選項是使用通常的按位or結合每個字符xor。

# Timing safe comparision of two hashes. 
# 
# http://stackoverflow.com/q/35090706/2373138 
proc hash_equals {hash1 hash2} { 
    # Get length of strings a single time. 
    set hash1_length [string length $hash1] 
    set hash2_length [string length $hash2] 

    # If the length is not equal, return false. 
    # Short circuit if they have different lengths. 
    # Length of the hashes is anyway known and length information 
    # will always be leaked because of caching effects. 
    if {$hash1_length != $hash2_length} { 
     return 0 
    } 

    set result 0 

    # Loop through the entire string and compare each single character. 
    # We compare using XOR to avoid timing effects on if branches. 
    for {set i 0} {$i < $hash1_length} {incr i} { 
     set char1 [string index $hash1 $i] 
     set char2 [string index $hash2 $i] 

     # Convert character to its ordinal value. 
     set ord1 [scan $char1 %c] 
     set ord2 [scan $char2 %c] 

     # Wil be 0 as long as they're the same. 
     set xor [expr {$ord1^$ord2}] 

     # Once $result is not equal to 0, it will stay not equals 0. 
     set result [expr {$result | $xor}] 
    } 

    # Strings are exactly equal if $result is exactly 0. 
    return [expr {$result == 0}] 
} 

Answer 3

這一個是快了些，如果兩個字符串相等，但如果第一次不同的是在開始或結束不要緊時間明智。

proc compare {a b} { 
    set ary($b) 0 
    set ary($a) 1 
    set ary($b) 
} 

這工作太（它仍然是一個哈希表）：

proc compare {a b} { 
    dict get [dict create $b 0 $a 1] $b 
}