定时安全地比较字符串

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 
}