3 ms·
Could you just iterate through the entire key even if you know it's not a match after 1 byte? Then it would always take the same amount of time to return `true
by another-dave 3y ago
Could you just iterate through the entire key even if you know it's not a match after 1 byte?
Then it would always take the same amount of time to return `true/false`, even if you knew this value earlier in the loop.
- sjducb 3y agoWhat’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.
- continuational 3y agoQuick take, assuming equal length of a and b: For each byte index i: x[i] = a[i] XOR b[i] return sum(x) == 0
- sjducb 3y agoI 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-processing-a-sorted-array-faster-than-processing-an-unsorted-array https://stackoverflow.com/questions/11227809/why-is-processi...
- Ar-Curunir 3y agoThere is no branch here, so nothing for the CPU to speculate on.
- bluGill 3y agoThere 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.
- faceplanted 3y agoIn 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.
- another-dave 3y agoAs 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.
- madacol 3y ago> 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) } ...
- another-dave 3y agoBut 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.
- ramchip 3y agoBranch 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.
- another-dave 3y agoah cool I understand what you mean now. Thanks for the explanation!