Re: Real-World Impact of Hash DoS in Lua

[Sean Conner <sean@...>]

It was thus said that the Great Paul Hudson once stated:
> On 26 January 2012 16:10, Sean Conner <sean@conman.org> 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).  

  Even using the address of a function or variable can fail to provide a
seed, given an implementation that does not randomize addresses.  

  I just tested Linux 2.6.9 and 2.6.35, and yes, both will randomize the
base stack address, but not necessarily library function addresses:

#include <stdio.h>
#include <stdlib.h>

#include <openssl/evp.h>

int main(int argc,char *argv[])
{
  int x;
  
  printf(
        "x:                    %p\n"
        "srand:                %p\n"
        "EVP_get_digestbyname: %p\n",
        (void *)&x,
        (void *)srand,
        (void *)EVP_get_digestbyname
  );
  return EXIT_SUCCESS;
}

2.6.9 (32 bit system):
[spc]lucy:/tmp>./a.out 
x:                    0xbff14df4
srand:                0x8048404
EVP_get_digestbyname: 0x8048414
[spc]lucy:/tmp>./a.out 
x:                    0xbfe95f14
srand:                0x8048404
EVP_get_digestbyname: 0x8048414
[spc]lucy:/tmp>./a.out 
x:                    0xbff4d0f4
srand:                0x8048404
EVP_get_digestbyname: 0x8048414
[spc]lucy:/tmp>./a.out 
x:                    0xbffbcfc4
srand:                0x8048404
EVP_get_digestbyname: 0x8048414
[spc]lucy:/tmp>./a.out 
x:                    0xbffa9194
srand:                0x8048404
EVP_get_digestbyname: 0x8048414

2.6.35 (64 bit system):
[spc]saltmine:/tmp>./a.out 
x:                    0x7fff0e3e0c1c
srand:                0x4005d8
EVP_get_digestbyname: 0x4005c8
[spc]saltmine:/tmp>./a.out 
x:                    0x7fff4638091c
srand:                0x4005d8
EVP_get_digestbyname: 0x4005c8
[spc]saltmine:/tmp>./a.out 
x:                    0x7fff79e3a16c
srand:                0x4005d8
EVP_get_digestbyname: 0x4005c8
[spc]saltmine:/tmp>./a.out 
x:                    0x7fffb2e2b3ac
srand:                0x4005d8
EVP_get_digestbyname: 0x4005c8
[spc]saltmine:/tmp>./a.out 
x:                    0x7fff2676dd1c
srand:                0x4005d8
EVP_get_digestbyname: 0x4005c8

I find it interesting though, that even with the random stack addresses, the
lowest four bits on both systems are identical, and the upper N bits (8 bits
for the 32b system, 32 bits for the 64b system) are also identical, which
still isn't ideal for seeding a random number generator (although it's
better than just 0).  

Solaris (v5.10, 64 bit SPARC) is amusing---while the address of x changes
per invocation, it's not exactly random either:

[spc]sol:/tmp>./a.out 
x:                    ffffffff7ffff8e8
srand:                100100ae0
EVP_get_digestbyname: 100100b00
[spc]sol:/tmp>./a.out 
x:                    ffffffff7ffff8d8
srand:                100100ae0
EVP_get_digestbyname: 100100b00
[spc]sol:/tmp>./a.out 
x:                    ffffffff7ffff8c8
srand:                100100ae0
EVP_get_digestbyname: 100100b00
[spc]sol:/tmp>./a.out 
x:                    ffffffff7ffff8b8
srand:                100100ae0
EVP_get_digestbyname: 100100b00
[spc]sol:/tmp>./a.out 
x:                    ffffffff7ffff8a8
srand:                100100ae0
EVP_get_digestbyname: 100100b00
[spc]sol:/tmp>./a.out 
x:                    ffffffff7ffff898
srand:                100100ae0
EVP_get_digestbyname: 100100b00
[spc]sol:/tmp>./a.out 
x:                    ffffffff7ffff888
srand:                100100ae0
EVP_get_digestbyname: 100100b00
[spc]sol:/tmp>./a.out 
x:                    ffffffff7ffff878
srand:                100100ae0
EVP_get_digestbyname: 100100b00
[spc]sol:/tmp>./a.out 
x:                    ffffffff7ffff868
srand:                100100ae0
EVP_get_digestbyname: 100100b00

(the 32b version of this code under Solaris behaves similarly, only with a
32-bit address).

  Even using the address of the lua_State might not work, even if allocated
via malloc(), since the program state up to that point could very well be
deterministic and thus, the same address could be returned each time
(malloc() returned random addresses for the the two Linux systems I tested
on, Solaris returned the same address each time).

  -spc (So, portably seeding the random number generator in C89?  Not so
	easy ...)