Is this constant-time comparison secure?

Question

I was thinking about constant-time comparison and how it differs from "==", when I thought of a simple way that's could be constant-time. Being a beginner in cryptography, I'd like to know if my method is secure. This method is probably insecure, but I'd like to know where it's weak. It's really simple.

1. Take the two strings to compare, convert them each to a list of numbers (0-255)
2. Set totalDifference = 0
3. Take the first number from the first list and subtract it from the first number in the second list. Take this difference and add it to totalDifference.
4. Do 4. for each character/number in both list.
5. If totalDifference is 0 after going through each number, then both strings are equal.

Example:

 [1,3,5,9,7,8]
-[1,3,5,5,7,8]
--------------
  0,0,0,4,0,0


0+0+0+4+0+0!=0, so strings not equal

Are there any problems with this constant-time comparison scheme?

Answer 1

Are there any problems with this constant-time comparison scheme?

One obvious issue is that it'll claim the strings "AB" and "BA" are the same; during the first character, it'll see 'A'-'B' = -1, for the second character, it'll see 'B'-'A' = 1; those two sum to 0.

On the other hand, that's actually fairly close to the standard way to do constant-time compare of equal strings, but instead of summing the differences, we bit-wise or them, as in:

total_difference = 0;
for (i=0; i<len_strings; i++) {
    int this_difference = a[i] - b[i];
    total_difference = total_difference | this_difference;
          /* | is the bit-wise or operator */
}
if (total_difference == 0) {
    /* The strings are the same */
}

The idea here is that the 'or' operation can set bits in total_difference, but never clear them. Hence, the only way total_difference is 0 at the end is if in every iteration, this_difference was always 0, that that happens if each character of string a was the same as the character in string b.

Often, you'll see this_difference being computed by the bitwise-xor rather than subtraction; the algorithm works the same either way.