Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:72783
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.215.53 as permitted sender)
MIME-Version: 1.0
Sender: yohgaki@gmail.com
In-Reply-To: <530AFE9A.30502@lsces.co.uk>
References: <9E3AA302-1EC1-4497-996F-716555CAAB64@rouvenwessling.de>
 <3EAEC401-F0FF-42E6-8B93-41D2E8658A80@rouvenwessling.de> <47C11B57-84E9-4805-9952-1E78A9F112C5@rouvenwessling.de>
 <CAGa2bXYz0o=swhqt=OrwdxFScA=LuxZQ=8vpvMxEJj7_FTZUeQ@mail.gmail.com>
 <8092191F-9B60-43C3-91A8-095FB74C02A5@rouvenwessling.de> <CAGa2bXYE8YFvpMsfksi1QLcULa-7_PKh__=z8AsrKjjYdqxy4w@mail.gmail.com>
 <530AFE9A.30502@lsces.co.uk>
Date: Mon, 24 Feb 2014 18:00:24 +0900
Message-ID: <CAGa2bXayaxQNDo5EP3mYTN3jebLgcVgpdcvCS27jo8BnHwXi8A@mail.gmail.com>
To: Lester Caine <lester@lsces.co.uk>
Cc: PHP internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary=001a11c3353020574904f323360a
Subject: Re: [PHP-DEV] [VOTE] Timing attack safe string comparison function
From: yohgaki@ohgaki.net (Yasuo Ohgaki)

--001a11c3353020574904f323360a
Content-Type: text/plain; charset=UTF-8

Hi Lester,

On Mon, Feb 24, 2014 at 5:11 PM, Lester Caine <lester@lsces.co.uk> wrote:

> Yasuo Ohgaki wrote:
>
>> I did some experiments. It seems it's good to implement timing safe
>>>>
>>> comparison in engine. i.e. We can make ==/=== secure by default like
>>> Python. It would be much safer get rid of all timing from PHP.
>>>
>>>>
>>>> We need new RFC to include the change in engine.
>>>>
>>>
>>> That's not how I read that discussion (though I might have missed a
>>> mail).
>>> Also personally I don't like it. I don't see that the supposed gain in
>>> security is worth the performance implication. Also if it turns out
>>> there's
>>> a bug, and we'd have to make it 100 times slower for some reason, than
>>> that's not a big deal for a function like hash_equals. It is however if
>>> it
>>> affects all comparisons.
>>>
>>> Since I don't believe in that change, I'm not interested in proposing
>>> that
>>> RFC.
>>>
>>
>> Understood. This is OK.
>>
>>  From the experiment, performance implication is not much.
>>>
>> Automatic protection in any place would worth the trade off. IMHO.
>> Python even uses less efficient hash for comparison. I heard they
>> use optimized version of SipHash, we may better try it before deciding
>> algorithm, though.
>>
>> Any other comments regarding ==/=== timing safety?
>>
>
> Surely there are two elements to this?
>
> Simply comparing two strings in a time stable manner is relatively easy.
> You just modify the compare to store the result and always complete a full
> scan. Only the lengths of the string come into that. How physically that is
> handled in the processor will actually determine if the time taken is 'byte
> sensitive' anyway! Simply stopping the core process from the unnecessary <>
> comparison where the answer is not used is going to be a performance gain,
> all be it minuscule, but the timing differences that are trying to be
> hidden are even smaller than that? Tidying the core use of string compare
> is generally more useful than simply adding yet another method of calling
> it.
>
> The other element here is actually calculating the hash value to compare
> with? That will also depend on just how the processor is processing
> multiple bytes, so simply fixing the final comparison may be somewhat
> irrelevant if the hash generation also has a leak? Yes it should be another
> constant, but what is being fed in is the variable being changed during the
> attack?


Good hash function will produce unpredictable values with constant size.
Computation is too complex to get the usable difference, I suppose.
Therefore, hash value comparison should be safe.

I don't know why Python uses optimized version of SipHash. Are they using
shared strings like Java? If so, it's understandable.

From my experiment, simple byte by byte comparison seems the way to go.
There is only negligible difference between strncmp() and simple byte by
byte comparison. If we care for performance, word by word comparison may be
used. It was the fastest. Detailed benchmark should be taken, though.

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

--001a11c3353020574904f323360a--