Real-World Impact of Hash DoS in Lua

classic Classic list List threaded Threaded
49 messages Options
123
Reply | Threaded
Open this post in threaded view
|

Re: Real-World Impact of Hash DoS in Lua

William Ahern
On Thu, Jan 26, 2012 at 05:56:34PM -0200, Roberto Ierusalimschy wrote:
> > What are Bob Jenkin's "mixing functions"? Hash functions?
>
> Never mind. I found them.
>

You might want to try asking over on sci.crypt (usenet). The quality of
discussion has gone down over the years, but there are still several posters
with strong cryptographic credentials answering questions.

Reply | Threaded
Open this post in threaded view
|

Re: Real-World Impact of Hash DoS in Lua

Mike Pall-35
In reply to this post by Roberto Ierusalimschy
Roberto Ierusalimschy wrote:
> I still think this whole problem is somewhat overstated. As Jay Carlson
> put it (Jan 20), there are many other forms of DoS attacks that most
> sites are not resistant to.

Seconded.

In fact, nobody should _ever_ write their own HTTP handler! This
is absolutely not a trivial task, if you want it to be DoS-proof.
Even most of the 'batteries included' HTTP handlers of other
languages are just toys. There's only handful of web servers
packages that have seen the necessary scrutiny and that stand a
chance to survive an attack from a single client. But even those
will go down from a concerted DoS attack, unless you throw tons of
hardware at it or fight it at the network-level.

So, yes ... some expert with the right skills _could_ write a
targeted program that exploits some weakness in the hash
implementation three layers down an application -- given
sufficient effort. But it's orders of magnitude cheaper to rent a
bot net with exactly the same effect. Your site goes down and they
have a much lower chance of getting caught. Now, guess what the
bad guys will do?

> The main reasons we are changing Lua
> are that we like this idea of long non-internalized strings

That, I'm not so sure about. I'll freely admit: it does have a
certain appeal. But I'd want to see convincing, quantitative proof
that the resulting increase in complexity does not adversely
affect the performance of the common case. The simplicity of the
current solution and the resulting stability is a very convincing
argument against such a big change, too.

> and for propaganda.

Ok, that's tough. There's always someone with a vested interest,
who'd want to give this story a certain spin ('developer refuses
to fix gaping security hole'). And the topic is way too complex,
to defend your position in layman terms.

--Mike

Reply | Threaded
Open this post in threaded view
|

Re: Real-World Impact of Hash DoS in Lua

Roberto Ierusalimschy
> > The main reasons we are changing Lua
> > are that we like this idea of long non-internalized strings
>
> That, I'm not so sure about. I'll freely admit: it does have a
> certain appeal. But I'd want to see convincing, quantitative proof
> that the resulting increase in complexity does not adversely
> affect the performance of the common case. The simplicity of the
> current solution and the resulting stability is a very convincing
> argument against such a big change, too.

Certainly it is. The real interesting thing is that non-internalized
strings open the door for "external" buffers, that is, buffers decopled
form the TString struture. That would allow things like luaL_Buffer
and even lua_concat to use the intermediate buffer as the resulting
string. It would allow large literal strings to point directly to its
fixed version. But simplicity is always a compelling argument.

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: Real-World Impact of Hash DoS in Lua

Rob Kendrick-2
In reply to this post by Sean Conner
On Thu, Jan 26, 2012 at 11:58:51AM -0500, Sean Conner wrote:

> It was thus said that the Great Paul Hudson once stated:
> > On 26 January 2012 16:10, Sean Conner <[hidden email]> wrote:
> >
> > >  -spc (So it's not exactly *Linux only*)
> >
> > But it is a small subset of the things Lua does or could run on.  And since
> > we're talking about a core feature of Lua,  platform/OS dependencies are to
> > be avoided (IMO) if a portable solution can be found.
>
>   And I was replying to Roberto, who asked:
>
> > We can have better implementations for particular system. For instance, we
> > can use arc4random if present, but how to detect it? Are there any other
> > suggestions?
>
>   C89 is pretty restrictive in this (seeding a random number generator)
> regard.  You really can't even rely upon time() since a C89 implementation
> has to only give "its best approximation of the time" which could be 0 (I
> don't my references handy at the moment, but once I get home I can cite the
> appropriate documenation).  

Is anybody actually concerned about a system lacking a decent
implementation of time() being DoSed?  In any case, combining it with
pointers of symbols, stacks, the state pointer, etc, should get you a
long way towards something that changes enough to make it more of a
challenge to exploit, as well as being portable.

Unless you're running on a microcontroller or some similar constrained
system, where there are much much easier ways of DoSing them due to low
performance and RAM.

B.

Reply | Threaded
Open this post in threaded view
|

Re: Real-World Impact of Hash DoS in Lua

Mike Pall-35
In reply to this post by Roberto Ierusalimschy
Roberto Ierusalimschy wrote:

> > > The main reasons we are changing Lua
> > > are that we like this idea of long non-internalized strings
> >
> > That, I'm not so sure about. I'll freely admit: it does have a
> > certain appeal. But I'd want to see convincing, quantitative proof
> > that the resulting increase in complexity does not adversely
> > affect the performance of the common case. The simplicity of the
> > current solution and the resulting stability is a very convincing
> > argument against such a big change, too.
>
> Certainly it is. The real interesting thing is that non-internalized
> strings open the door for "external" buffers, that is, buffers decopled
> form the TString struture. That would allow things like luaL_Buffer
> and even lua_concat to use the intermediate buffer as the resulting
> string. It would allow large literal strings to point directly to its
> fixed version. But simplicity is always a compelling argument.

Well, string data co-location is actually one of the strengths of
the current approach. Java strings originally have been designed
around segregated, shared string data. The following paper shows
that moving to unshared, co-located string data (i.e. what Lua
does) is faster for the JVM, too:

http://ssw.jku.at/Research/Papers/Haeubl08Master/

[It also makes a compelling case _against_ ropes. That's on of my
old pet peeves: IMHO ropes look nice on paper, but they increase
complexity and rarely pay off outside of targeted benchmarks.]

One would have to evaluate whether the trade-offs are better, if
only longer strings have segregated string data. Not sure. We need
to measure, not guess.

My ancient 'fast string' patch (look in the archives) did sort of
the opposite: store small string values entirely in the tagged
value slot. This reduced overhead for string interning, but that
turned out not to be the real bottleneck (at least for small
strings). The increase in complexity for handling two different
string types everywhere was noticeable, though.

--Mike

Reply | Threaded
Open this post in threaded view
|

Re: Real-World Impact of Hash DoS in Lua

Petite Abeille
In reply to this post by Mike Pall-35

On Jan 26, 2012, at 11:56 PM, Mike Pall wrote:

> In fact, nobody should _ever_ write their own HTTP handler!

Bah... nonsense... experts are not born, they are made... made by learning from all their mistakes... today's fiddling hobbyists are tomorrow's "experts"...


Reply | Threaded
Open this post in threaded view
|

Re: Real-World Impact of Hash DoS in Lua

Miles Bader-2
Petite Abeille <[hidden email]> writes:
> On Jan 26, 2012, at 11:56 PM, Mike Pall wrote:
>> In fact, nobody should _ever_ write their own HTTP handler!
>
> Bah... nonsense... experts are not born, they are made... made by
> learning from all their mistakes... today's fiddling hobbyists are
> tomorrow's "experts"...

Maybe it should be stated as "Everybody should write their own HTTP
handler, but nobody should ever use them!"  :]

-miles

--
Vote, v. The instrument and symbol of a freeman's power to make a fool of
himself and a wreck of his country.

Reply | Threaded
Open this post in threaded view
|

Re: Real-World Impact of Hash DoS in Lua

Florian Weimer
In reply to this post by Mike Pall-35
* Mike Pall:

> In fact, nobody should _ever_ write their own HTTP handler! This
> is absolutely not a trivial task, if you want it to be DoS-proof.

With connection keepalive, it's also imperative to get the request and
response boundaries correct, or you risk data leakage between
sessions.  This might even happen without a deliberate attack.

> Even most of the 'batteries included' HTTP handlers of other
> languages are just toys. There's only handful of web servers
> packages that have seen the necessary scrutiny and that stand a
> chance to survive an attack from a single client. But even those
> will go down from a concerted DoS attack, unless you throw tons of
> hardware at it or fight it at the network-level.

On the other hand, at one point, the request has to hit the
application code.  Then, most of the badness should have been dealt
with, but you have to cope with the remaining data.  The hash
collision issue is a bit annoying in this regard because it will go
through filters (just like the Java float parser issue).

However, there is one aspect that's conveniently ignored.  In order to
trigger collisions that really hurt, you need to send large requests
with lots of data.  Really lots of data: the proof-of-concept exploits
I've seen send 2 megabytes per request and more.  Internal memory
usage will be much higher due to per-string and per-key overhead.
Even without hash collisions, such levels of per-request memory usage
is very problematic.  Most systems have trouble recovering from memory
allocation failures, or just from swapping.  Therefore, you really
want strict limits on HTTP request size (or more generally, per-user
memory allocation), which also indirectly limits the length of hash
chains.

String interning complicates matters a bit, but it seems to me that
the Lua implementation is fairly robust if the data retained per
request is limited and the per-state heap size isn't large.

Reply | Threaded
Open this post in threaded view
|

Re: Real-World Impact of Hash DoS in Lua

Natanael Copa
In reply to this post by Roberto Ierusalimschy
sorry late reply....

On Wed, Jan 25, 2012 at 11:26 PM, Roberto Ierusalimschy
<[hidden email]> wrote:

>> OK.  Cool.  This is a showstopper for the company I am working with for
>> rolling out embedded Lua with nginx.  Is there anything I can do to help?
>
> what it is still missing now is how to create the initial per-state
> random seed. Suggestions included some address and arc4random. I am
> afraid that, for the backup ANSI implementation, we cannot do much
> better than something like this:
>
>  seed = (unsigned int)time() + (unsigned int)L;
>
> We can have better implementations for particular system. For instance,
> we can use arc4random if present, but how to detect it? Are there any
> other suggestions?

Other projects normally use configure scripts and options to
detect/configure things like that.

How about something like:

make configure

will generate a config.mk file which holds the different variables:

HAVE_ARC4RANDOM=1

And then in Makefile you have:

-include config.mk

That way you can:
* configure the build by editing config.mk
* build it without config.mk, use defaults but still override. for example:
   make HAVE_ARC4RANDOM=1
* run make configure to autodetect stuff

I think GNU make is needed for the "-include config.mk"

Other option is to write a configure shell script that can be run
optionally. (similar to what qemu does)

--
Natanael Copa

123