Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:72423
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.215.47 as permitted sender)
MIME-Version: 1.0
Sender: yohgaki@gmail.com
In-Reply-To: <CAGa2bXbuH7cDpr6_F==wse-s7doExxqB-BJzP1Vm_127aJ1O2A@mail.gmail.com>
References: <9E3AA302-1EC1-4497-996F-716555CAAB64@rouvenwessling.de>
 <CAGa2bXYBbPw8RYZmwHPGe8BPFvicjNs1bD85QvRjMJ6i9aoPuQ@mail.gmail.com>
 <CAGa2bXa35rkmqNLvMw-9hkPJ6F2oPgpzkk4aMXe_9Vbfuoxc2g@mail.gmail.com> <CAGa2bXbuH7cDpr6_F==wse-s7doExxqB-BJzP1Vm_127aJ1O2A@mail.gmail.com>
Date: Mon, 10 Feb 2014 10:15:25 +0900
Message-ID: <CAGa2bXYriMBx_d38VwQCtUoCj_+DCNdBjMwRxAYOguiuvbH1Qw@mail.gmail.com>
To: =?UTF-8?Q?Rouven_We=C3=9Fling?= <me@rouvenwessling.de>
Cc: PHP internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary=001a11c239be77956104f2031508
Subject: Re: [PHP-DEV] [VOTE] Timing attack safe string comparison function
From: yohgaki@ohgaki.net (Yasuo Ohgaki)

--001a11c239be77956104f2031508
Content-Type: text/plain; charset=UTF-8

Hi all,

On Mon, Feb 10, 2014 at 9:24 AM, Yasuo Ohgaki <yohgaki@ohgaki.net> wrote:

> On Fri, Feb 7, 2014 at 10:39 AM, Yasuo Ohgaki <yohgaki@ohgaki.net> wrote:
>
>> On Fri, Feb 7, 2014 at 8:05 AM, Yasuo Ohgaki <yohgaki@ohgaki.net> wrote:
>>
>>> I made SipHash version of str_compare() as a sample.
>>> There is timing safe php_compare(), which is stolen from BSD.
>>>
>>> https://github.com/yohgaki/php-src/compare/PHP-5.6-rfc-hash-compare
>>>
>>> [yohgaki@dev github-php-src]$ ./php-bin -r 'var_dump(str_compare("abc",
>>> "abc"));'
>>> bool(true)
>>> [yohgaki@dev github-php-src]$ ./php-bin -r
>>> 'var_dump(str_compare("asfasdf", "slkjojoeiwrj"));'
>>> bool(false)
>>>
>>> It's quick patch made less than 30 min.
>>> So it can be improved, I suppose.
>>>
>>
>> I thought it would be better to compare performance difference.
>> Added more functions to play with.
>> There are
>>
>>  bool str_siphash_compare(str, str) - siphash. timing safe. (64bit)
>>   bool str_xxhash32_compare(str, str) - xxhash. timing safe. (32bit)
>>  bool str_md5_compare(str, str) - md5. Timing safe (128bit)
>>   bool str_byte_compare(str, str) - Byte compare. Timing safe. No
>> division.
>>  bool str_byte_compare2(str, str) - Byte compare. Timing safe. With
>> division. (Modulo as this RFC)
>>  bool str_compare(str, str) - plain strncmp(). Not timing safe.
>>
>> I didn't took bench mark and did minimum tests.
>> I appreciate if anyone take benchmark.
>>
>
> Added yet another function to compare suggested by Lester.
>
> bool str_word_compare(str, str)
>
> This function compares data word by word rather than byte by byte.
> It supposed to be faster for large data.
>

I took a benchmark. str_compare() is not timing safe. It's there for
reference.

str_siphash_compare  Elapsed: 1.389824   Iterations: 1000000 DataSize: 8
str_xxhash32_compare Elapsed: 1.241737   Iterations: 1000000 DataSize: 8
str_md5_compare      Elapsed: 3.029127   Iterations: 1000000 DataSize: 8
str_byte_compare     Elapsed: 1.236183   Iterations: 1000000 DataSize: 8
str_byte_compare2    Elapsed: 1.269901   Iterations: 1000000 DataSize: 8
str_word_compare     Elapsed: 1.273266   Iterations: 1000000 DataSize: 8
str_compare          Elapsed: 1.181425   Iterations: 1000000 DataSize: 8

str_byte_compare() is the winner for small data.
I'm a little surprised that str_xxhash32_compare() is the second.
str_word_compare() is marginally slower.

str_siphash_compare  Elapsed: 2.341025   Iterations: 1000000 DataSize: 128
str_xxhash32_compare Elapsed: 1.560131   Iterations: 1000000 DataSize: 128
str_md5_compare      Elapsed: 6.055007   Iterations: 1000000 DataSize: 128
str_byte_compare     Elapsed: 1.799050   Iterations: 1000000 DataSize: 128
str_byte_compare2    Elapsed: 2.163229   Iterations: 1000000 DataSize: 128
str_word_compare     Elapsed: 1.337508   Iterations: 1000000 DataSize: 128
str_compare          Elapsed: 1.194582   Iterations: 1000000 DataSize: 128

str_word_compare() is the winner for relatively large data.

It seems str_word_compare() is the way to go.

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

--001a11c239be77956104f2031508--