Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:72314
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.215.49 as permitted sender)
MIME-Version: 1.0
Sender: yohgaki@gmail.com
In-Reply-To: <CAGa2bXZpcjichYTB1kXDJ5dp4dcB2rdR1jAQo=TKtSK2cNqZFQ@mail.gmail.com>
References: <9E3AA302-1EC1-4497-996F-716555CAAB64@rouvenwessling.de>
 <CAF+90c-32u=vVy4L4pB_OWGu2VmeUckxq8UW_AVJNC8iDtiWMQ@mail.gmail.com>
 <52F0139C.2060102@sugarcrm.com> <CAGa2bXZhT_8-BEjLuA4EPkZmxtpO1onz7AGTjCE-w85XC5pwdQ@mail.gmail.com>
 <CAGa2bXYab=2DeJu+ESWP_9Vte2FY37L2+kJFnuN4JwUj9Num1w@mail.gmail.com>
 <AC16ADC6-801E-4D0D-9FD4-0BEE2D017E16@rouvenwessling.de> <CAGa2bXa0i6LBykCNChcCXS+zgp+3KfMEi+H=umFAwL1mC0s__Q@mail.gmail.com>
 <CAGa2bXZpcjichYTB1kXDJ5dp4dcB2rdR1jAQo=TKtSK2cNqZFQ@mail.gmail.com>
Date: Thu, 6 Feb 2014 13:20:55 +0900
Message-ID: <CAGa2bXaJWRMFHgqZSFUyAmhAM5Zf1Cf7F4koPdkdBpwZg3cgsw@mail.gmail.com>
To: =?UTF-8?Q?Rouven_We=C3=9Fling?= <me@rouvenwessling.de>
Cc: Stas Malyshev <smalyshev@sugarcrm.com>, Nikita Popov <nikita.ppv@gmail.com>, 
	PHP internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary=001a1136dfc67fa66304f1b535df
Subject: Re: [PHP-DEV] [VOTE] Timing attack safe string comparison function
From: yohgaki@ohgaki.net (Yasuo Ohgaki)

--001a1136dfc67fa66304f1b535df
Content-Type: text/plain; charset=UTF-8

Hi all,

On Thu, Feb 6, 2014 at 12:56 PM, Yasuo Ohgaki <yohgaki@ohgaki.net> 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 <yohgaki@ohgaki.net> 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
yohgaki@ohgaki.net

--001a1136dfc67fa66304f1b535df--