Cross-language primitives against string comparison timing attacks?

Question

Related, not a duplicate: Timing Safe String Comparison - Avoiding Length Leak

• I know about cache misses, let's assume we fit in a cache line swimmingly.
• Thomas' excellent answer doesn't talk about jitter except that introduced by GC, nor does it touch upon asynchronous execution.
• We can assume a low-level implementation (assembler, C, F77, Forth) that can be used in any higher-level language (e.g. Python)

Please correct me if I'm mistaken:

1. We are talking about comparing two strings of unequal length. The first one is chosen by Eve, the second belongs to Alice. Alice wants to prevent Eve from learning length and/or content of the second string.

2. No existing mainstream programming language has constant-time string comparison routines in its standard library.

3. To avoid leaking length information, do we

   • precompute hash of Victoria'sAlice's secret (hash function itself must be not vulnerable to timing attacks)
   • compute hash of Eve's evil string
   • compare hashes (equal-length strings by definition of the hash function) in constant time

   or

   • simply compare Eve's string byte by byte to Alice's secret, incrementing a counter (or two counters, one each for matching and not matching bytes?) until the end of Eve's string?

4. Is introduction of cryptographically random jitter a valid defense-in-depth measure? (Please assume this happens across a LAN at a quiet time when natural timing noise is at a minimum).

5. Is asynchronous execution of comparisons (with some hard realtime guarantees) a viable defense? (Yeah, I know another side channel may be leaking)

What I'm not soliciting:

• language/product recommendations
• answers 'it depends on your threat model' (my threat is hiding in another server across the room, with an unlimited number of tries)

Answer 1

Community wiki for further information on the subject:

• In Ruby, you can use Rack::Utils.secure_compare or ActiveSupport::SecurityUtils.secure_compare. Source: http://codahale.com/a-lesson-in-timing-attacks/ via https://github.com/thoughtbot/til/blob/master/security/constant-time-comparison.md

• https://crypto.stackexchange.com/questions/5529/stopping-timing-attacks-on-aes-why-is-it-important-to-prevent-the-os-from-inter and DJB's 2004 paper.

Answer 2

You can implement your own quite easily. Below is Python but can be adapted to any language. This assumes that the '\0' character cannot be within the string. The problem becomes more interesting if the '\0' character is allowed. Also could argue that len is not pre-calculated in other languages, but for our sake I think this is as good as it'll get.

def timing_resistent_compare(str1, str2):
    # Get the length of each string.
    len1 = len(str1)
    len2 = len(str2)

    # Find the maximum of the two lengths, add 1 to force padding.
    max_len = max(len1, len2) + 1

    # Pad each string, at least one character is padded on due to above.            
    str1 = str1 + ('\0' * (max_len - len1))
    str2 = str2 + ('\0' * (max_len - len2))

    # Do an OR sum of all the XORs of each character.
    differences = 0
    for ch1, ch2 in zip(str1, str2):
        differences |= ord(ch1) ^ ord(ch2)

    # If there are no differences, then the two strings are equal.
    return differences == 0