Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:72118
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.217.182 as permitted sender)
MIME-Version: 1.0
Sender: yohgaki@gmail.com
In-Reply-To: <CAF+90c-32u=vVy4L4pB_OWGu2VmeUckxq8UW_AVJNC8iDtiWMQ@mail.gmail.com>
References: <9E3AA302-1EC1-4497-996F-716555CAAB64@rouvenwessling.de> <CAF+90c-32u=vVy4L4pB_OWGu2VmeUckxq8UW_AVJNC8iDtiWMQ@mail.gmail.com>
Date: Tue, 4 Feb 2014 05:57:13 +0900
Message-ID: <CAGa2bXYc2iRsW6fmSpyqr-N-g-Mrj9PEyVoc0ckBwRoLdtepXQ@mail.gmail.com>
To: Nikita Popov <nikita.ppv@gmail.com>
Cc: =?UTF-8?Q?Rouven_We=C3=9Fling?= <me@rouvenwessling.de>, 
	PHP internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary=001a1137f67c109ed204f186c70c
Subject: Re: [PHP-DEV] [VOTE] Timing attack safe string comparison function
From: yohgaki@ohgaki.net (Yasuo Ohgaki)

--001a1137f67c109ed204f186c70c
Content-Type: text/plain; charset=UTF-8

Hi Nikita,

On Tue, Feb 4, 2014 at 2:10 AM, Nikita Popov <nikita.ppv@gmail.com> wrote:

> > Hi internals,
> >
> > as I've received no further feedback I've opened the voting on "Timing
> > attack safe string comparison function":
> >
> > - https://wiki.php.net/rfc/timing_attack
> >
> > Voting ends on 2014/02/09 11:00PM UTC
> >
> > Best regards
> > Rouven
> >
>
> Did your code already get reviewed by someone with understanding of the
> issue? From a quick glance, two potential issues:
>  * 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
> different cache access patterns for comparing always the same 10 memory
> positions and 10000 different ones, at least I'd assume so.
> I don't know how you can prevent the latter issue, and if it is possible at
> all. Personally I'd just drop the length magic and explicitly document it
> to be safe for equal-length strings only. In any case you should have this
> reviewed by someone with more than just a cursory understanding of the
> matter.


Length leak is known issue and we may improve these. There was discussion
for this.
For the sake of completeness, we may address issues now or later.

To be honest, I think length leak must be avoided especially for shorter
strings.
It would be better to iterate at least 100 times regardless of input.

Perhaps, something like

+ /**
 + * 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, 127);
 +
 + /* 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];
 + }

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

--001a1137f67c109ed204f186c70c--