Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:72434
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.128.172 as permitted sender)
MIME-Version: 1.0
In-Reply-To: <CAGa2bXYriMBx_d38VwQCtUoCj_+DCNdBjMwRxAYOguiuvbH1Qw@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>
	<CAGa2bXYriMBx_d38VwQCtUoCj_+DCNdBjMwRxAYOguiuvbH1Qw@mail.gmail.com>
Date: Mon, 10 Feb 2014 17:29:31 +0800
Message-ID: <CAHMUw2FRGihSmhuC=1TKz=XM-f0PRc8dFw0T+w2qpm9cHFcbHQ@mail.gmail.com>
To: Yasuo Ohgaki <yohgaki@ohgaki.net>
Cc: =?ISO-8859-1?Q?Rouven_We=DFling?= <me@rouvenwessling.de>, 
	PHP internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary=20cf307d010416159a04f209faee
Subject: Re: [PHP-DEV] [VOTE] Timing attack safe string comparison function
From: tjerk.meesters@gmail.com (Tjerk Meesters)

--20cf307d010416159a04f209faee
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

Hi,

On Mon, Feb 10, 2014 at 9:15 AM, Yasuo Ohgaki <yohgaki@ohgaki.net> wrote:

> 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: 12=
8
> str_xxhash32_compare Elapsed: 1.560131   Iterations: 1000000 DataSize: 12=
8
> str_md5_compare      Elapsed: 6.055007   Iterations: 1000000 DataSize: 12=
8
> str_byte_compare     Elapsed: 1.799050   Iterations: 1000000 DataSize: 12=
8
> str_byte_compare2    Elapsed: 2.163229   Iterations: 1000000 DataSize: 12=
8
> str_word_compare     Elapsed: 1.337508   Iterations: 1000000 DataSize: 12=
8
> str_compare          Elapsed: 1.194582   Iterations: 1000000 DataSize: 12=
8
>
> str_word_compare() is the winner for relatively large data.
>
> It seems str_word_compare() is the way to go.
>

Quite honestly, I don't think that an absolute difference of 0.46 =CE=BCs p=
er
function call should be used to pick the "winner" from the line-up you're
made.

That said, the implementation of `str_word_compare` introduces a `MIN()`
branch and the second loop should loop until `MAX(b1_len, b2_len)` instead
of `b2_len` alone; imo you've just made it harder to prove that it actually
prevents timing attacks.

From what has been discussed so far, to me, the question that needs an
answer is:

"Should we have a function that attempts to provide a constant comparison
for strings of different lengths?"

If not, reduce the function to just a length mismatch branch and a loop;
length information is leaked as long as both strings are of difference
lengths only.

If so, then we need to create and run a simulation program to prove that a
particular algorithm is indeed suitable with a certain amount of confidence
for the most common scenarios.


>
> Regards,
>
> --
> Yasuo Ohgaki
> yohgaki@ohgaki.net
>



--=20
--
Tjerk

--20cf307d010416159a04f209faee--