[perl #117257] Re: Bleadperl v5.17.9-200-g0e0ab62 breaks MLEHMANN/JSON-XS-2.33.tar.gz

# New Ticket Created by  yves orton 
# Please include the string:  [perl #117257]
# in the subject line of all future correspondence about this issue. 
# <URL: https://rt.perl.org:443/rt3/Ticket/Display.html?id=117257 >


On 21 March 2013 11:02, Marc Lehmann <schmorp@schmorp.de> wrote:
> On Thu, Mar 21, 2013 at 10:04:24AM +0100, demerphq <demerphq@gmail.com> wrote:
>> Your opinion is noted. However given you appear to be uninformed as to
>> the details it is not worth much.
>
> Then please state where I was wrong, I am always open to learn the facts.
>
>> > - Unless I am mistaken, this is to avoid a DOS attack. DOS attacks are easy
>> >   to protect against, and this won't protect me against basically any form
>> >   of attack, so it's useless. Far better methods exist that prevent every
>> >   form of memory resource and/or cpu time starvation.
>>
>> You are mistaken.
>
> You are really claiming that this is one of the best methods to prevent
> memory resource and/or cpu time starvation? Because that's what the satteemnt
> you quoted says.

I am sorry, I seem to be missing some context here. What statement did
I quote? I just checked this thread I did not quote anything.

The purpose of hash iterator randomization is make it harder, and
hopefully outright impossible to discover the hash seed a given
process is using.

Once an attacker can determine the hash seed they can launch
algorithmic complexity attacks on our hash implementation. However the
iterator randomization does not in any way prevent a DOS, it prevents
obtaining the information that makes a DOS possible.

> Or maybe you meant I am mistaken in something else? Without telling me
> what it is you are refering to it is hard to tell.

>> > - I'd say this simply breaks perl, as perl documented the order is fixed,
>> >   at least between runs (I would argue even the earlier fix to randomise
>> >   between runs is a bug). Sure, the wording is ambiguous, but that doesn't
>> >   make it any better.
>>
>> I am unaware of any such documentation. Please state your sources.
>
> The perlfunc 5.16 documentation on "keys". Older versions are even more
> explicit.
>
> all them are ambiguous, but I already mentioned that.

Well, I beg to differ. I think you are conflating "does not say
anything on the subject" and "says something ambiguous".

The documentation for keys(), and as far as I know all other
documentation relating to hashes says nothing about consistency,
either cross process or in between hashes. It says that the keys are
returned in an apparently random order, that the random order is
subject to change in future versions of perl, and the only guarantee
of any form provided is that the keys() function will return items in
the same order that each() and values would return them assuming the
hash has not been modified (a secondary clause in the documentation
for "each" specifies it is safe to delete the key that was just
returned by each()).

Furthermore I cannot find any evidence that the wording for this has
changed in terms of specificity in the lifetime of perlfunc.pod:

In bleadperl it says:

aeedbbed (Nicholas Clark                         2007-12-21 17:58:03
+0000 3109) The keys of a hash are returned in an apparently random
order.  The actual
3b10bc60 (brian d foy                            2010-01-13 16:19:33
+0100 3110) random order is subject to change in future versions of
Perl, but it
504f80c1 (Jarkko Hietaniemi                      2003-06-26 05:32:02
+0000 3111) is guaranteed to be the same order as either the C<values>
or C<each>
4546b9e6 (Jarkko Hietaniemi                      2003-07-27 20:21:40
+0000 3112) function produces (given that the hash has not been
modified).  Since
c5f61d2f (Peter J. Holzer                        2010-12-04 11:40:23
-0800 3113) Perl 5.8.1 the ordering can be different even between
different runs of
4546b9e6 (Jarkko Hietaniemi                      2003-07-27 20:21:40
+0000 3114) Perl for security reasons (see L<perlsec/"Algorithmic
Complexity
d6df3700 (Ronald J. Kimball                      2003-07-02 07:43:05
-0400 3115) Attacks">).

In Perl 5.14.2 it says this:

               The keys of a hash are returned in an apparently random
order.  The actual random order is subject to change in future
versions of Perl, but it is guaranteed to be the same order as either
               the "values" or "each" function produces (given that
the hash has not been modified).  Since Perl 5.8.1 the ordering is
different even between different runs of Perl for security reasons
               (see "Algorithmic Complexity Attacks" in perlsec).

In perl 5.8.5 it says this:

               The keys are returned in an apparently random order.
The actual random order is subject to change in future versions of
perl, but it is guaranteed to be the same order as either the "val-
               ues" or "each" function produces (given that the hash
has not been modified).  Since Perl 5.8.1 the ordering is different
even between different runs of Perl for security reasons (see "Algo-
               rithmic Complexity Attacks" in perlsec).

Here is what it said in 1998/99:

19799a22 (Gurusamy Sarathy                       1999-05-24 07:24:11
+0000 2314) Returns a list consisting of all the keys of the named
hash.  (In
1d2dff63 (Gurusamy Sarathy                       1998-05-29 02:31:44
+0000 2315) scalar context, returns the number of keys.)  The keys are
returned in
ab192400 (Gurusamy Sarathy                       1998-11-28 09:36:40
+0000 2316) an apparently random order.  The actual random order is
subject to
ab192400 (Gurusamy Sarathy                       1998-11-28 09:36:40
+0000 2317) change in future versions of perl, but it is guaranteed to
be the same
19799a22 (Gurusamy Sarathy                       1999-05-24 07:24:11
+0000 2318) order as either the C<values> or C<each> function produces
(given
ab192400 (Gurusamy Sarathy                       1998-11-28 09:36:40
+0000 2319) that the hash has not been modified).  As a side effect,
it resets
ab192400 (Gurusamy Sarathy                       1998-11-28 09:36:40
+0000 2320) HASH's iterator.

And in 97:

aa689395 (Perl 5 Porters                         1997-02-22 04:41:00
+1200 1710) Returns a normal array consisting of all the keys of the
named hash.  (In
aa689395 (Perl 5 Porters                         1997-02-22 04:41:00
+1200 1711) a scalar context, returns the number of keys.)  The keys
are returned in
aa689395 (Perl 5 Porters                         1997-02-22 04:41:00
+1200 1712) an apparently random order, but it is the same order as
either the
aa689395 (Perl 5 Porters                         1997-02-22 04:41:00
+1200 1713) values() or each() function produces (given that the hash
has not been
aa689395 (Perl 5 Porters                         1997-02-22 04:41:00
+1200 1714) modified).  As a side effect, it resets HASH's iterator.

And in 94 (5.000)

a0d0e21e (Larry Wall         1994-10-17 23:00:00 +0000 1578) Returns a
normal array consisting of all the keys of the named
a0d0e21e (Larry Wall         1994-10-17 23:00:00 +0000 1579)
associative array.  (In a scalar context, returns the number of keys.)
a0d0e21e (Larry Wall         1994-10-17 23:00:00 +0000 1580) The keys
are returned in an apparently random order, but it is the same
a0d0e21e (Larry Wall         1994-10-17 23:00:00 +0000 1581) order as
either the values() or each() function produces (given that
a0d0e21e (Larry Wall         1994-10-17 23:00:00 +0000 1582) the
associative array has not been modified).  Here is yet another way
a0d0e21e (Larry Wall         1994-10-17 23:00:00 +0000 1583) to print
your environment:

perlfunc.pod didnt exist prior to that commit.

I see nothing ambiguous in the documentation, nor do I see it becoming
more or less specific over time.

>
>> > - Perl hash already are very slow (just write yourself some XS functions to
>> >   interface to gcc's unordered_hash and watch the speed - despite the
>> >   overhead of XS).
>>
>> Yes, and this is a very tiny drop in a large bucket. If you think that
>> the changes I made are going to affect hash performance in any kind of
>> significant way then please provide evidence.
>
> I don't think that, and haven't made that claim. I think you can make
> faster hashes with better properties without the drawbacks.

So then why did you bring it up in this thread? If you have issues
with hash performance and think you can do better then please start a
new thread, preferably by posting patches.

>> > - Taking out the inability to write a proper hash on all the perl developers
>> >   out there is just wrong - Perl is the runtime, and should get it right,
>> >   if possible.
>>
>> This doesn't make grammatical sense,
>
> I think it's a perfectly fine english sentence. Maybe a bit complicated for
> you to understand though.

I guess you meant "your" when you said "the".

If so then I will just say that I find this comment rude and
uniformed. I am not responsible for our current hash implementation,
nor do I think you could do any better. I am pretty sure that the only
way one can improve perls hash performance is to make it do less, and
that by doing so you would upset far more people than you would make
happy by making it a nanosecond faster.

But please, go ahead and prove me wrong. Post some patches.

>
>> so I don't know what you are trying to say.
>
> I am trying to say that the solution for bad hash tables is better hash
> tables, or a sense of proportion, not breaking perfectly fine existing
> code.

I find it really hard to take you seriously given how often you make
silly statements like "not breaking perfectly fine existing code". If
your code broke because of this change it is because you were making
unwarranted assumptions about how perl's hash function operated, and
as such your code wasn't perfectly fine. In fact if your code is
breaking due to this change then I could trivially contrive code in an
older version of perl that would also break your assumptions.

>> > So please reconsider your choice of making perl worse again.
>>
>> I don't think I have made Perl worse, so currently I have nothing to reconsider.
>
> To me, breaking existing code for questionable or no reason is making it
> worse. It is obvious that you disagree and think you didn't make it worse,
> but at best, you have to disagree with my perfectly valid opinion on this
> topic-

I have to disagree? What? Did you mean "agree"?

Anyway, it doesnt matter. I don't break existing code for no reason.
A) I have reasons, B) any code broken was already broken but the
author did not know it C) there is a reason the docs say "The actual
random order is subject to change in future versions of perl" and make
no other guarantees that the limited ones I enumerated above. The
reason of course is to allow the hash function to be changed or
improved over time.

>> I am sure the perl5porters who are regular contributors will give your
>> opinions on how they use their time the full attention and consideration
>> that they deserve.
>
> I am fully aware of them being volunteers, but so am I (and I am a regular
> contributor as well), please keep that in mind.

Perhaps you are, I never advanced an opinion on the subject.

>
> The perl5porters are not "better" than me as a major contributor to perl
> in any way, and have no higher moral ground. Acting uppity because you are
> part of a mailinglist and contribute more often than me is proving nothing
> really.

I never made any comments about anyones individuals merits. Nor do I
know what I did that was "uppity".

> I can't "the people who maintainer perl5" (as opposed to perl5porters) to
> do what I want, and neither do I try, but sarcaasm and ignorance on your
> part is wrong too. My concerns are valid, and while you have all the right
> in the world to ignore them, or even ridicule them, that doesn't make them
> invalid.

Well I have responded to the only cogent concern that I have seen you
express, which is that you think that these changes contradict the
documentation. The documentation does not support you in this regard.

Is there some other matter I should respond to?

Oh, I suppose I forgot. Afaik, you don't even have to fix this, just
take the patches I did to the JSON::PP tests and apply them.

See: https://rt.cpan.org/Public/Bug/Display.html?id=83421

Thanks for your feedback.

Yves

-- 
perl -Mre=debug -e "/just|another|perl|hacker/"

• [perl #117257] Re: Bleadperl v5.17.9-200-g0e0ab62 breaks MLEHMANN/JSON-XS-2.33.tar.gz by yves orton