Is your comparison secure?
Preface
Let's assume we need to compare two byte arrays
In psuedo-code we could write function like below.
bool compare(byte* src, byte* dst) {
assert(src.len == dst.len);
for (int i = 0 ; i < src.len; i++) {
if (src[i] != dst[i]) {
return false;
}
}
return true;
}
It works fine, but is this really safe?
The answer is no, that function isn't safe at all.
Why? Let's explorer why that function is unsafe by simulating a attack scenario.
Attack Scenario
Before scenario, let's assume each byte comparison that takes 1ms and for convenience there are no time cost in if statement execution.
First guess
server's secret src = { 0, 1, 2, 3, 4, 5, 6, 7 }
malicious user's guess = { 0, 0, 0, 0, 0, 0, 0, 0 }
It takes 2ms, because server compare first byte that matches, and second byte that does not match.
Second guess
server's secret src = { 0, 1, 2, 3, 4, 5, 6, 7 }
malicious user's guess = { 1, 0, 0, 0, 0, 0, 0, 0 }
It takes 1ms, because server compare first byte that does not match. by reducing time 2ms -> 1ms, malicious user can infer that first byte is correct.
Third guess
server's secret src = { 0, 1, 2, 3, 4, 5, 6, 7 }
malicious user's guess = { 0, 1, 0, 0, 0, 0, 0, 0 }
It takes 3ms, the first two bytes are correct, and third byte is incorrect. the malicious user can infer second byte is also correct by comparing response time's difference.
... and by trying more and more. malicious user can determine all bytes.
Solution
hmm that's really big problem.. then how we can write it secure? The answer is very simple, even thought src and dst does not matched make server respond at similar time.
bool compare(byte* src, byte* dst) {
assert(src.len == dst.len);
bool result = true;
for (int i = 0 ; i < src.len; i++) {
result &= !(src[i] ^ dst[i]);
}
return result;
}
In the above scenario, there was no consideration about if statement's cost, but if statement also takes time cost. because they generate compare & jump routine in assembly. so in the above fixed code use any if statement not at all.
Luckyily, those timing attack is not as simple as illustrated in real world. there are much more variants that might effect on response time. and almost attacker isn't smart enough to considering those variants. but by considering those misc details, we could write much more safe code.