3

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)
0

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
  • 1
    This is more vulnerable to timing attacks than a simple string comparison. Generating the padding takes a different amount of time per string. – Robert Fraser Nov 12 '16 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.