字符串的时序安全比较

Question

Tcl 是否有任何内置函数以时序安全的方式比较字符串，所以不会因为短路而泄露秘密？

string equal从左边开始，returns在第一个差值上，所以不适合比密。

具体来说，我想比较两个 sha256 HMAC。 Double HMAC也能解决leakage，不过我想找一个timing safe comparison function

Answer 1

一个选项是使用通常的按位 or 结合每个字符 xor。

# Timing safe comparision of two hashes.
# 
# 
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 2

如果字符串相等，这个速度会快一点，但是第一个差异是在开头还是结尾在时间上并不重要。

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

这也有效（它仍然是一个散列 table）：

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

Answer 3

假设您正在处理两个长度相同的字符串（例如 HMAC），那么您可以对每个字符进行比较并累加结果：

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

字符串的时序安全比较

Timing safe comparison of strings

string

security

tcl

hmac