ruby - Ruby 中更快的常量时间字符串比较

Question

我正在尝试将用户提供的身份验证 token 与存储在我的服务器上的身份验证 token 进行比较。

最明显的方法就是使用 == ，但这可能会造成定时攻击。

为了缓解这种情况，我编写了这个安全比较函数:

# string comparison that leaks no information about the strings.
# loosely based on https://github.com/rack/rack/blob/master/lib/rack/utils.rb
# and http://security.stackexchange.com/questions/49849/timing-safe-string-comparison-avoiding-length-leak
def secure_compare(a, b)
  l = a.unpack("C*")

  i = 0
  r |= a.length - b.length # fail if the lengths are different
  b.each_byte do |v|
    r |= v ^ l[i]
    i = (i + 1) % a.length # make sure we compare on all bytes of b, even if a is shorter.
  end
  r == 0
end

唯一的问题是这真的很慢:它在 60-80 毫秒的页面加载上增加了 180 毫秒。

是否有更快的方法来进行恒定时间字符串比较？有更标准化的方法吗？

编辑:我正在使用以下脚本来对不同的解决方案进行基准测试，fwiw - https://gist.github.com/daxtens/a3a59f163f08f9b447bb - 它显示了如何 ==能否提早纾困，泄露信息，又如何secure_compare比 == 慢几个数量级.

编辑 2:为了完全清楚，我想要实现的是一个函数 secure_compare(secret, untrusted_input) ，执行时间完全取决于 untrusted_input , 而不是 secret .我还希望这个函数不比 == 差几个数量级。 .提供的函数具有所需的时间依赖性，但速度太慢。

Answer 1

为了在保持简单的同时加快速度，我用 C 语言重新实现了该函数，并且 made it available as a gem .

源代码位于 GitHub ( https://github.com/daxtens/fast_secure_compare ) 上，但其关键在于以下非常简单的 C 例程。

int secure_compare_bytes(const unsigned char * secret, unsigned int secret_len, 
                     const unsigned char * input, unsigned int input_len) {

    int input_pos;
    int secret_pos = 0;
    int result = secret_len - input_len;
    // make sure our time isn't dependent on secret_len, and only dependent
    // on input_len
    for (input_pos = 0; input_pos < input_len; input_pos++) {
        result |= input[input_pos] ^ secret[secret_pos];
        secret_pos = (secret_pos + 1) % secret_len;
    }

    return result;
}

```

还有一些 FFI 粘合剂可以让它与 Ruby 对话。

它比原始的纯 Ruby 快得多，并且比散列法快一些(也简单得多)。为了简洁起见，我删除了彩排。这是在 2008 年的 MacBook 上。您可以使用演示目录中的 timing.rb 复制它。

==== Long text ====
                                         user     system      total        real
==, early fail                       0.000000   0.000000   0.000000 (  0.000028)
==, late fail                        0.000000   0.000000   0.000000 (  0.000710)
Pure Ruby secure_compare, 'early'    1.730000   0.040000   1.770000 (  1.777258)
Pure Ruby secure_compare, 'late'     1.730000   0.050000   1.780000 (  1.774144)
C-based FastSecureCompare, 'early'   0.040000   0.000000   0.040000 (  0.047612)
C-based FastSecureCompare, 'late'    0.040000   0.000000   0.040000 (  0.045767)
SHA512-then-==, 'early'              0.050000   0.000000   0.050000 (  0.048569)
SHA512-then-==, 'late'               0.050000   0.000000   0.050000 (  0.046100)

==== Short text ====
                                         user     system      total        real
==, early fail                       0.000000   0.000000   0.000000 (  0.000028)
==, late fail                        0.000000   0.000000   0.000000 (  0.000031)
Pure Ruby secure_compare, 'early'    0.010000   0.000000   0.010000 (  0.010552)
Pure Ruby secure_compare, 'late'     0.010000   0.000000   0.010000 (  0.010805)
C-based FastSecureCompare, 'early'   0.000000   0.000000   0.000000 (  0.000556)
C-based FastSecureCompare, 'late'    0.000000   0.000000   0.000000 (  0.000516)
SHA512-then-==, 'early'              0.000000   0.000000   0.000000 (  0.000780)
SHA512-then-==, 'late'               0.000000   0.000000   0.000000 (  0.000812)