Re: [VOTE] Timing attack safe string comparison function

From: Date: Thu, 06 Feb 2014 04:20:55 +0000
Subject: Re: [VOTE] Timing attack safe string comparison function
References: 1 2 3 4 5 6 7 8  Groups: php.internals 
Request: Send a blank email to [email protected] to get a copy of this message
Hi all,

On Thu, Feb 6, 2014 at 12:56 PM, Yasuo Ohgaki <[email protected]> wrote:

> Padraic gave me an another idea of additional mitigation for this.
> Although we cannot rely on it, randomized delay can be used
> as mitigation. It would be good for length leak.
>
> On Thu, Feb 6, 2014 at 10:28 AM, Yasuo Ohgaki <[email protected]> wrote:
>
>> Perhaps, something like this would be good enough.
>>
>>  + /**
>>  +  * 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(user_len, 64); // Do not care much
>> len = MAX(known_len, len); // Do not care much
>>
>> // These kind of operations have done somewhere anyway
>> // Just don't care.
>> k = (unsinged char *)emalloc(len+1)
>> u = (unsinged char *)emalloc(len+1);
>> memset(k, 0, len+1);
>> memset(u, 0, len+1);
>> strncpy(k, known_str, known_len);
>> strncpy(u, user_str, user_len);
>>
>
> // Determination of delay is tricky. Too short or too long delay does not
> work.
> // It depends on execution path/data. e.g. How many times
> strlen/strncpy/etc is called, length of string.
> // I'm not sure if this is sufficient/valid as mitigation for average
> usage. Experiments are needed.
> // Improvement/suggestion is appreciated.
>     r1 = (unsigned char)get_random_byte();
>     r1 *= 2; // doubles range
>     for (; r1 > 0; r1--) {
>       r2 = (unsigned char)get_random_byte();
>       for (; r2 > 0; r2--) {
>         if (r1 < r2) {
>            buf[r2] = r2 % r1;
>         } else {
>            buf[r2] = r1 % r2;
>         }
>       }
>     }
>
>   +
>>  + /* This is security sensitive code. Do not optimize this for speed. */
>>  + result = known_len - user_len;
>>
>>
>> +	for (j = 0; j < user_len; j++) {
>>
>>
>> +		result |= known_str[j % mod_len] ^ user_str[j];
>>
>> for (; len > 0; len--) {
>>
>>                                  result |= *k++ ^ *u++; // This must be constant. Use
>> simpler operation and keep constant operation here is enough.
>>
>>
>>
>>
>>  + }
>>
>
Since comparison of short and/or not hashed data (e.g. user supplied raw
password) should
not be done as the function name imply, we may better to document so that
users always
compare hashed values even when they store raw password/etc.
So randomized delay may be overkill.

Regards,

--
Yasuo Ohgaki
[email protected]


Thread (54 messages)

« previous php.internals (#72314) next »