Hacker News Reader

Comment by sjducb | Hacker News Reader

What’s the exact algorithm you would write for that?

Let’s say you have a bool, $is_match then whenever two chars of the string don’t match you write false to it.

It takes slightly longer to write false than do nothing. You’re still leaking the total number of matching characters.

I think speculative execution on the CPU would amplify this effect. For example:

aaaaaaaaa != ccccccccc will be much faster than ababababa != aaaaaaaaa because in the first example the cpu will correctly guess and speculatively execute that the two characters are different. They were different last time. They’ll probably be different again.

View on HN

As a naive approach something like this:

    // Throw an error if inputKey is not correct.
    // inputKey and correctKey are both strings
    function checkApiKey(inputKey, correctKey) {
      var isMatch = true;
      for (var i = 0; i < inputKey.length; i++)
        if (inputKey.charAt(i) !== correctKey.charAt(i)) {
          isMatch = false;
        }
      }
      if (!isMatch) {
        throw new Error("wrong key");
      }
    }

So what I meant is, don't return early when isMatch = false, instead walk the entire key regardless.

> isMatch = false;

That instruction is executed conditionally, you can time it.

Maybe eliminate the if completely an do something like this

    ...
      for (var i = 0; i < inputKey.length; i++)
        isMatch = isMatch && (inputKey.charAt(i) !== correctKey.charAt(i)
      }
    ...

But if you have an incorrect key, you'll always execute the whole for loop & one write to `isMatch`.

I'm assuming the function would take the same amount of time to run regardless for which value of "i" the write occurs at. Wouldn't that then protect the attack vector of enumerating keys and checking the time?

As in, the only input that would cause the write to `isMatch` to be skipped would be the correct key, in which case you don't need to brute force the solution.

Branch prediction and speculative execution can affect that. For instance failing on the first byte could cause more iterations to be thrown away and re-executed than failing on the last byte.

ah cool I understand what you mean now. Thanks for the explanation!

Quick take, assuming equal length of a and b:

For each byte index i:

x[i] = a[i] XOR b[i]

return sum(x) == 0

I think that’s still affected by speculative execution. The CPU will process the step ahead assuming that a[i] != b[i] while it is doing the a[i] XOR b[i] check.

So it’ll be faster if: most characters match, most characters don’t match or there are runs of matching characters.

Have a read of this: https://stackoverflow.com/questions/11227809/why-is-processi...

There is no branch here, so nothing for the CPU to speculate on.

There is no obvious branch, but the compiler is allowed to implement the as-if rule and insert a branch if it figures out what you are doing.

In theory that would work but compilers and toolchains are far too clever now and always liable to change, so there's no way to know that in the future it won't be optimised back into shortcutting and revealing the timings.

Reply on news.ycombinator.com