Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:72438 Return-Path: Mailing-List: contact internals-help@lists.php.net; run by ezmlm Delivered-To: mailing list internals@lists.php.net Received: (qmail 43092 invoked from network); 10 Feb 2014 12:39:30 -0000 Received: from unknown (HELO lists.php.net) (127.0.0.1) by localhost with SMTP; 10 Feb 2014 12:39:30 -0000 Authentication-Results: pb1.pair.com smtp.mail=padraic.brady@gmail.com; spf=pass; sender-id=pass Authentication-Results: pb1.pair.com header.from=padraic.brady@gmail.com; sender-id=pass Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.160.170 as permitted sender) X-PHP-List-Original-Sender: padraic.brady@gmail.com X-Host-Fingerprint: 209.85.160.170 mail-yk0-f170.google.com Received: from [209.85.160.170] ([209.85.160.170:55028] helo=mail-yk0-f170.google.com) by pb1.pair.com (ecelerity 2.1.1.9-wez r(12769M)) with ESMTP id 0C/F3-18799-188C8F25 for ; Mon, 10 Feb 2014 07:39:29 -0500 Received: by mail-yk0-f170.google.com with SMTP id 9so6884600ykp.1 for ; Mon, 10 Feb 2014 04:39:26 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=VU0TyGwRTlA3HfjB0+tTTPr9N6bIuQAnf8L5FhexM9U=; b=xANbIHfBY75hW6HmYq27xcA/kg0LoyycNhnKyQ1/kunwbRByRl2tUFBvrFtEU/rfR4 xVaXx4eJm/nanQ7lVpF3zexJnpZTnnLzSzlMpRSUafW5DgqSnsBWpj3jp10kzT+2qnLl 48B9vGMVrCT0c5jXGPn7KqnTj8E9r5I3CuyIrbaXoWEI8xfZ2eWD9Q1U16YWJJZfgqS4 jUkfM1YrwVRqjqSuHu+mP9KFwdDkqRNHcutFYV0YjNPA9QFY5hA/ee/qb3baenZLaRbI O5CtDAHSN5RpCbsu6zlgbEUsTouRb/MGKKz6COg8e52yrsyOnAViGI3pGPfNagmVk5JS tvxw== MIME-Version: 1.0 X-Received: by 10.236.83.194 with SMTP id q42mr8314754yhe.56.1392035966464; Mon, 10 Feb 2014 04:39:26 -0800 (PST) Received: by 10.170.84.138 with HTTP; Mon, 10 Feb 2014 04:39:26 -0800 (PST) In-Reply-To: References: <9E3AA302-1EC1-4497-996F-716555CAAB64@rouvenwessling.de> Date: Mon, 10 Feb 2014 12:39:26 +0000 Message-ID: To: Tjerk Meesters Cc: Yasuo Ohgaki , =?UTF-8?Q?Rouven_We=C3=9Fling?= , PHP internals Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Subject: Re: [PHP-DEV] [VOTE] Timing attack safe string comparison function From: padraic.brady@gmail.com (=?UTF-8?Q?P=C3=A1draic_Brady?=) Hi, On 10 February 2014 09:29, Tjerk Meesters wrote: >> 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= per > 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)` instea= d > of `b2_len` alone; imo you've just made it harder to prove that it actual= ly > prevents timing attacks. Which is a significant risk. This is extremely easy to get wrong which is why adopting an established solution that has actually withstood examination is better than going with something that perhaps hasn=E2=80=99t= . There=E2=80=99s also Keep It Simple, Stupid ;). > 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 confiden= ce > for the most common scenarios. We do not need to protect length information because we=E2=80=99re not protecting strings of arbitrary length. We=E2=80=99re protecting hashes whi= ch have fixed lengths across a small range of commonly used types, i.e. a hacker should already have a good idea of what the length is. So what is length hiding? It=E2=80=99s security through obscurity. The function docs should just state that it only accepts strings of equal length or will throw an error. Users can then make merry, bikeshedding workarounds on their own time, like hashing both strings to an equal length and then comparing the hashes. That sort of thing. We may even find that we already do that=E2=80=A6 Paddy -- P=C3=A1draic Brady http://blog.astrumfutura.com http://www.survivethedeepend.com Zend Framework Community Review Team Zend Framework PHP-FIG Representative On 10 February 2014 09:29, Tjerk Meesters wrote: > Hi, > > On Mon, Feb 10, 2014 at 9:15 AM, Yasuo Ohgaki wrote: > >> Hi all, >> >> On Mon, Feb 10, 2014 at 9:24 AM, Yasuo Ohgaki wrote= : >> >> > On Fri, Feb 7, 2014 at 10:39 AM, Yasuo Ohgaki >> wrote: >> > >> >> On Fri, Feb 7, 2014 at 8:05 AM, Yasuo Ohgaki >> 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: 1= 28 >> str_xxhash32_compare Elapsed: 1.560131 Iterations: 1000000 DataSize: 1= 28 >> str_md5_compare Elapsed: 6.055007 Iterations: 1000000 DataSize: 1= 28 >> str_byte_compare Elapsed: 1.799050 Iterations: 1000000 DataSize: 1= 28 >> str_byte_compare2 Elapsed: 2.163229 Iterations: 1000000 DataSize: 1= 28 >> str_word_compare Elapsed: 1.337508 Iterations: 1000000 DataSize: 1= 28 >> str_compare Elapsed: 1.194582 Iterations: 1000000 DataSize: 1= 28 >> >> 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= per > 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)` instea= d > of `b2_len` alone; imo you've just made it harder to prove that it actual= ly > 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 confiden= ce > for the most common scenarios. > > >> >> Regards, >> >> -- >> Yasuo Ohgaki >> yohgaki@ohgaki.net >> > > > > -- > -- > Tjerk --=20 -- P=C3=A1draic Brady http://blog.astrumfutura.com http://www.survivethedeepend.com Zend Framework Community Review Team Zend Framework PHP-FIG Representative