String algorithms where runtime doesn't depend on data contents

Question

There is classic algorithm to check whether two same length strings are equal while preventing a timing attack.

foldl bitwiseOr 0 (zipWith bitwiseXor firstString secondString) == 0

In such a scenario, a malicious user gets the machine to compare a hidden, secret string with an input string, and report whether they're the same. For example, consider a brute-force password attack where the passwords are encrypted but not hashed. It takes longer to determine that the passwords don't match if more initial characters match, and if the user can measure the effect, they can progressively guess the password from beginning to end.

But is there any common algorithm that answers which string is greater, or if they're equal, resisting such an attack?

Answer 1

It should be possible to adjust any common algorithm with early exit to satisfy the requirement. But it's tricky, because the CPU will execute code faster if it can figure out that you're just spinning uselessly.

The safest design is to eliminate all branches inside the loop. No if, &&, or || allowed, just bitwise operators.

For a collating strcmp, we want to remember the first difference between the strings and which side was greater. So the algorithm naturally does completely different things depending on whether the difference has been found or not. We can simulate a branch using a bit mask.

int obscure_strcmp( char const *l, char const *r ) {
    int result = 0;

    do {
        // compute result in case we need it
        int diff = * r - * l; // positive if l < r, negative if r < l
        int diff_pos = diff > 0; // 1 if l < r
        int diff_neg = - ( diff < 0 ); // -1 if r < l

        // assign result if it was still zero
        unsigned mask = - ( result == 0u ); // all 1's if waiting for a diff
        result |= ( diff_pos | diff_neg ) & mask;

    } while ( * l ++ && * r ++ );
    return result;
}