Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:72313
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: <CAGa2bXa0i6LBykCNChcCXS+zgp+3KfMEi+H=umFAwL1mC0s__Q@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>
Date: Thu, 6 Feb 2014 12:56:11 +0900
Message-ID: <CAGa2bXZpcjichYTB1kXDJ5dp4dcB2rdR1jAQo=TKtSK2cNqZFQ@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=001a11c3324205094d04f1b4ddbf
Subject: Re: [PHP-DEV] [VOTE] Timing attack safe string comparison function
From: yohgaki@ohgaki.net (Yasuo Ohgaki)

--001a11c3324205094d04f1b4ddbf
Content-Type: text/plain; charset=UTF-8

Hi all,

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.
>
>
>  + }
>



--
Yasuo Ohgaki
yohgaki@ohgaki.net

--001a11c3324205094d04f1b4ddbf--