Re: [VOTE] Timing attack safe string comparison function

Hi Stas, On Tue, Feb 4, 2014 at 7:09 AM, Stas Malyshev <smalyshev@sugarcrm.com>wrote: > > * You are using MAX, i.e. an if-then-else branch. I'm pretty sure that > the > > if and else branches will have different instruction counts in that case. > > Simple alternative would be something fixed like mod_len = known_len+1 or > > known_len&1. > > * You leak information on mod_len / known_len, because you will have > > If it's meant to compare hashes and other such things, we can presume > the attacker already knows what your code does, and thus knows what the > expected hash length is. What he doesn't know is what that hash is. The > timing attack is based on the fact that regular comparison drops after > first mismatch, so the attacker by trying different first symbols and > using time as oracle between match and mismatch, can guess the hash. The > length of the hash however is not useful for him - for most standard > crypto protocols all lengths are already known and even if you are using > some modifications basic crypto principles tell us to assume your > algorithm is known to the attacker and thus most probably your known > hash length is too. I agree partially. Length leak would not be serious issue when length is long enough. I've already posted possible improvement that would not be affected by supplied string length. + /** + * If known_string has a length of 0 we set the length to 1, + * this will cause us to compare all bytes of userString with the null byte which fails + */ + mod_len = MAX(known_len, 1); len = MAX(known_len, 256); + + /* This is security sensitive code. Do not optimize this for speed. */ + result = known_len - user_len; + for (j = 0; j < user_len; j++) { for (j = 0; j < len; j++) { + result |= known_str[j % mod_len] ^ user_str[j]; result |= known_str[j % known_len] ^ user_str[j % user_len]; + } It's enough for hash functions up to 1024 bits. For SHA-3, we may set larger minimum. Comments, corrections, improvements are appreciated. Regards, -- Yasuo Ohgaki yohgaki@ohgaki.net