Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:72167
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.217.176 as permitted sender)
MIME-Version: 1.0
Sender: yohgaki@gmail.com
In-Reply-To: <52F0139C.2060102@sugarcrm.com>
References: <9E3AA302-1EC1-4497-996F-716555CAAB64@rouvenwessling.de>
 <CAF+90c-32u=vVy4L4pB_OWGu2VmeUckxq8UW_AVJNC8iDtiWMQ@mail.gmail.com> <52F0139C.2060102@sugarcrm.com>
Date: Tue, 4 Feb 2014 13:06:30 +0900
Message-ID: <CAGa2bXZhT_8-BEjLuA4EPkZmxtpO1onz7AGTjCE-w85XC5pwdQ@mail.gmail.com>
To: Stas Malyshev <smalyshev@sugarcrm.com>
Cc: Nikita Popov <nikita.ppv@gmail.com>, =?UTF-8?Q?Rouven_We=C3=9Fling?= <me@rouvenwessling.de>, 
	PHP internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary=001a1136c74246e1fa04f18cc689
Subject: Re: [PHP-DEV] [VOTE] Timing attack safe string comparison function
From: yohgaki@ohgaki.net (Yasuo Ohgaki)

--001a1136c74246e1fa04f18cc689
Content-Type: text/plain; charset=UTF-8

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

--001a1136c74246e1fa04f18cc689--