Constant time compares when array sizes are not equal?

Question

What is the preferred or recommended way to pursue contestant time compares when array lengths are not equal?

Should we exit as early as possible? Something like:

if (array1.size() != array2.size()) {
    return NOT_EQUAL;
}

int accum = 0;
for(int i = 0; i < array1.size(); i++) {
    accum |= array1[i] ^ array2[i];
}

return (accum == 0) ? EQUAL : NOT_EQUAL;

Or should we avoid the early exit, and compare as much as possible in hopes of masking as much as possible? Something like:

int size = min(array1.size(), array2.size());
int accum = (array1.size() ^ array2.size());

for(int i = 0; i < size; i++) {
    accum |= array1[i] ^ array2[i];
}

return (accum == 0) ? EQUAL : NOT_EQUAL;

Or something else?

Or is this question more appropriate for the folks on the Crypto.SE because its theoretical minutia?

---

EDIT: this seems to be related to Timing attacks on password hashes. But the cited question is a particular instance of the generalized problem (and I'm interested in the generalized question).

I'm not sure I agree with the cited question's answer or assertion that "Using timing attacks in this case will in no way tell an attacker more than what he would know if he had the actual stored hash and salt..." because the attacker could be trying to recover the hashed password though timing attacks. Given a hashed password, its only a leap back to the password in some cases.

Answer 1

Aborting early is fine, as it doesn't reveal timing for anything secret (unless you consider the length to be a secret, which doesn't seem plausible).

As for your edit, comparing password hashes in non-constant time is also fine. The attacker has no efficient mechanism to "choose" password hash outputs such that he can iterate through all possibilities for a byte at one position while holding the preceding bytes constant. So there is again no timing attack — not even to reveal the hashed password.

Answer 2

If the data against which you are comparing is not a secret, then it doesn't really matter what you do. Timing attacks are used to learn information to which you do not already have access. If you already have access, then the attack is unnecessary.

If you are protecting a secret, then it doesn't matter if it is a password or not. You should handle it the same way, with the same precautions. In order to avoid timing side channels, you ensure that the input length will be the same as the stored value's length by hashing them both and doing a constant time comparison. Of course, you should store the hashed value of the stored value in the database, so that you aren't recomputing it every time. See pseudocode below.

Pseudocode for constant time comparisons:

bool compareToSecret(input/* input from user*/)
  dbHash = getSecretFromDb()

  inHash = hash(input); // sha256, bcrypt or whatever. Attacker 
                        // knows how long this takes, but it 
                        // doesn't get her anything

  // at this point, both inhash and dbhash are the same length.

  // the following loop is constant order time. Hashes are always the
  // same length, and all values of the hashes are always compared
  bool result = true
  int len = strlen(inHash)
  for( int i=0; i<len; i++ )
     result &= (inHash[i] == dbHash[i])

  return result

aborting early during comparison

Aborting early during the comparison is problematic, as it leaks info about the comparison and can be used to learn the password directly.

1. Attacker tries secrets of length 1. One of these secrets will take a few milliseconds longer to return than the others, since there is one 1-length secret whose first character matches the stored secret. Attacker learns the first character of the secret.
2. Attacker tries 2 all character secrets with first letter beginning with known correct value. One of these secrets will be a few milliseconds faster, since the second character compares correctly.
3. Attacker repeats, separately attacking each character of the secret. Eventually, the attacker learns the stored secret.

This is quicker than a brute force attack, because the attacker can attack each character separately instead of the whole secret at once.

aborting early: before comparing

Aborting early, as mentioned by Steven Tousset, leaks the length of the secret. This doesn't look like a lot at first, but it lets the attacker speed up their attack by orders of magnitude. Let's say that the system accepts secrets of length 1-5. Keeping it very simple, the secret is composed only of digits. Thus, there are 10+100+1,000+10,000+100,000=111,110 possible values. A brute force attack needs to make about 100,000 tests to try every possible value.

If the system lets the attacker know the length of the secret, an attacker can dramatically reduce the number of values that s/he needs to test by first trying 5 values: '1', '12', '123', '1234', and '12345'. Now the attacker knows how long the secret is. If it's 1 character, s/he now only needs to make 10 tests instead of a hundred thousand. If it's 2 characters long, she only needs to make 100 tests. Without this key piece of information the attacker needs to make a lot more tests before they will find the secret.

another issue: recoverable storage

There's another issue, too. If the known secret can be compared against the input value, then you have to store the secret in recoverable form. Search this site for details related to passwords, but this is often considered a bad practice with storing passwords and should be avoided. In general - with any kind of secret - if you don't absolutely have to have the raw value, it should not be stored in recoverable form. Irrecoverable storage prevents several attacks - whether they matter for your secret depends upon how you use it.

one more thing: compiler optimization

The code, below, is pseudo code. If you were to pass its equvalent through a compiler or a runtime that does optimization, then you need to be very careful to ensure that the code does not get optimized. There are various tricks fir different languages, which are out of scope of this comment. Tha ks to @Polynomial for reminding of this

Answer 3

Problem: You want to compare two sequences, a user-provided sequence U[] and a secret sequence S[] whose length you want to keep secret. You don't want to disclose, through the elapsed time of comparison, whether S is shorter than U or the length of the common prefix of U and S.

You can't abort the comparison after reaching the end of S because that will disclose the length of S. Nor can you abort after the first mismatch because that will disclose the length of the common prefix. What you can do is repeat the last element in S until you reach the end of U. For example, if U is "goodbye" and S is "hello", you want to compare as if it were "hellooo".

The following (untested) code in Python should illustrate the concept:

def slow_seq_eq(userseq, secretseq):
    """Compare sequences without disclosing secretseq's length."""
    Silast = len(secretseq) - 1
    is_equal = True
    for Uidx in range(len(userseq)):
        Sidx = min(Uidx, Silast)  # Repeat the last element of S to len(U)
        if secretseq[Sidx] != userseq[Uidx]:
            is_equal = False
    if len(U) != len(S):
        is_equal = False
    return is_equal

This of course assumes that the comparison operator != takes constant time, as does the indexing operator. Arranging for S to be placed at a certain alignment relative to cache lines or virtual memory pages could in theory keep the timing attack alive.