You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@apr.apache.org by bo...@apache.org on 2012/01/15 01:37:14 UTC
svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c
Author: bojan
Date: Sun Jan 15 00:37:14 2012
New Revision: 1231605
URL: http://svn.apache.org/viewvc?rev=1231605&view=rev
Log:
Randomise hashes by providing a seed.
This is supposed to be a "good enough" approach. Using a crypto quality
function like apr_generate_random_bytes() may be stronger, but this function
may block, so it will be avoided for now.
Modified:
apr/apr/trunk/tables/apr_hash.c
Modified: apr/apr/trunk/tables/apr_hash.c
URL: http://svn.apache.org/viewvc/apr/apr/trunk/tables/apr_hash.c?rev=1231605&r1=1231604&r2=1231605&view=diff
==============================================================================
--- apr/apr/trunk/tables/apr_hash.c (original)
+++ apr/apr/trunk/tables/apr_hash.c Sun Jan 15 00:37:14 2012
@@ -18,6 +18,10 @@
#include "apr_general.h"
#include "apr_pools.h"
+#include "apr_time.h"
+#if APR_HAVE_STDLIB_H
+#include <stdlib.h> /* for rand, srand */
+#endif
#include "apr_hash.h"
@@ -75,7 +79,7 @@ struct apr_hash_t {
apr_pool_t *pool;
apr_hash_entry_t **array;
apr_hash_index_t iterator; /* For apr_hash_first(NULL, ...) */
- unsigned int count, max;
+ unsigned int count, max, seed;
apr_hashfunc_t hash_func;
apr_hash_entry_t *free; /* List of recycled entries */
};
@@ -95,13 +99,18 @@ static apr_hash_entry_t **alloc_array(ap
APR_DECLARE(apr_hash_t *) apr_hash_make(apr_pool_t *pool)
{
apr_hash_t *ht;
+ apr_time_t now = apr_time_now();
+
ht = apr_palloc(pool, sizeof(apr_hash_t));
ht->pool = pool;
ht->free = NULL;
ht->count = 0;
ht->max = INITIAL_MAX;
+ srand((unsigned int)((now >> 32) ^ now ^ (apr_uintptr_t)ht));
+ ht->seed = (unsigned int)(rand());
ht->array = alloc_array(ht, ht->max);
- ht->hash_func = apr_hashfunc_default;
+ ht->hash_func = NULL;
+
return ht;
}
@@ -201,10 +210,10 @@ static void expand_array(apr_hash_t *ht)
ht->max = new_max;
}
-APR_DECLARE_NONSTD(unsigned int) apr_hashfunc_default(const char *char_key,
- apr_ssize_t *klen)
+static unsigned int apr_hashfunc_default_internal(const char *char_key,
+ apr_ssize_t *klen,
+ unsigned int hash)
{
- unsigned int hash = 0;
const unsigned char *key = (const unsigned char *)char_key;
const unsigned char *p;
apr_ssize_t i;
@@ -246,7 +255,7 @@ APR_DECLARE_NONSTD(unsigned int) apr_has
*
* -- Ralf S. Engelschall <rs...@engelschall.com>
*/
-
+
if (*klen == APR_HASH_KEY_STRING) {
for (p = key; *p; p++) {
hash = hash * 33 + *p;
@@ -262,6 +271,11 @@ APR_DECLARE_NONSTD(unsigned int) apr_has
return hash;
}
+APR_DECLARE_NONSTD(unsigned int) apr_hashfunc_default(const char *char_key,
+ apr_ssize_t *klen)
+{
+ return apr_hashfunc_default_internal(char_key, klen, 0);
+}
/*
* This is where we keep the details of the hash function and control
@@ -280,7 +294,10 @@ static apr_hash_entry_t **find_entry(apr
apr_hash_entry_t **hep, *he;
unsigned int hash;
- hash = ht->hash_func(key, &klen);
+ if (ht->hash_func)
+ hash = ht->hash_func(key, &klen);
+ else
+ hash = apr_hashfunc_default_internal(key, &klen, ht->seed);
/* scan linked list */
for (hep = &ht->array[hash & ht->max], he = *hep;
@@ -322,6 +339,7 @@ APR_DECLARE(apr_hash_t *) apr_hash_copy(
ht->free = NULL;
ht->count = orig->count;
ht->max = orig->max;
+ ht->seed = orig->seed;
ht->hash_func = orig->hash_func;
ht->array = (apr_hash_entry_t **)((char *)ht + sizeof(apr_hash_t));
Re: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c
Posted by Bojan Smojver <bo...@rexursive.com>.
------- Original message -------
> From: Bojan Smojver
> Sent: 17.1.'12, 5:18
>
> ------- Original message -------
>> From: Ruediger Pluem
>
>> r1231605 and r1231858 cause massive regressions and test case failures
>> in httpd.
>
> I won't be able to commit for a while. Please feel free to revert both.
> Sorry about the breakage. :-(
I had a look at the apr_hash.c and I see that I completely missed patching
the merge function. So, if the tests in question are using it, they will
fail for sure.
--
Bojan
Re: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c
Posted by Bojan Smojver <bo...@rexursive.com>.
------- Original message -------
> From: Bojan Smojver
> Just reverted both.
I'll work on that merge functionality that I missed and will actually test
more before comitting anything. Not near a decent computer now, so it may
be a while.
--
Bojan
Re: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c
Posted by Bojan Smojver <bo...@rexursive.com>.
------- Original message -------
> From: Bojan Smojver
> Sent: 17.1.'12, 5:18
>
> ------- Original message -------
>> From: Ruediger Pluem
>
>> r1231605 and r1231858 cause massive regressions and test case failures
>> in httpd.
>
> I won't be able to commit for a while. Please feel free to revert both.
> Sorry about the breakage. :-(
Just reverted both.
--
Bojan
Re: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c
Posted by Bojan Smojver <bo...@rexursive.com>.
------- Original message -------
> From: Ruediger Pluem
> r1231605 and r1231858 cause massive regressions and test case failures in
> httpd.
I won't be able to commit for a while. Please feel free to revert both.
Sorry about the breakage. :-(
--
Bojan
Re: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c
Posted by Ruediger Pluem <rp...@apache.org>.
Bojan Smojver wrote:
> On Thu, 2012-01-26 at 09:05 +1100, Bojan Smojver wrote:
>> Will fix.
>
> Better?
>
Yes. No more regression in httpd and APR tests pass as well.
Regards
Rüdiger
Re: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c
Posted by Bojan Smojver <bo...@rexursive.com>.
On Thu, 2012-01-26 at 09:05 +1100, Bojan Smojver wrote:
> Will fix.
Better?
--
Bojan
Re: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c
Posted by Bojan Smojver <bo...@rexursive.com>.
------- Original message -------
> From: Ruediger Pluem
> Shouldn't you store the result of res->hash_func /
> apr_hashfunc_default_internal in a local temporary
> variable and use it later on? Otherwise you change the overlay hash and
> may make it unusable by setting a new hash
> value. IMHO all operations by this code are currently readonly on the
> base and overlay hash.
Yeah, good point. I was working under the assumption that overlay gets
thrown away, which may not be true. Will fix.
--
Bojan
Re: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c
Posted by Ruediger Pluem <rp...@apache.org>.
Bojan Smojver wrote:
> On Mon, 2012-01-16 at 14:11 +0100, Ruediger Pluem wrote:
>> r1231605 and r1231858 cause massive regressions and test case failures
>> in httpd. Not sure why right now.
>
> Could you please run your tests with this patch. Let me know how it
> goes. Thanks.
>
I think there is still a problem with your patch:
@@ -468,6 +484,12 @@
for (k = 0; k <= overlay->max; k++) {
for (iter = overlay->array[k]; iter; iter = iter->next) {
+ if (res->hash_func)
+ iter->hash = res->hash_func(iter->key, &iter->klen);
+ else
+ iter->hash = apr_hashfunc_default_internal(iter->key,
+ &iter->klen,
+ res->seed);
Shouldn't you store the result of res->hash_func / apr_hashfunc_default_internal in a local temporary
variable and use it later on? Otherwise you change the overlay hash and may make it unusable by setting a new hash
value. IMHO all operations by this code are currently readonly on the base and overlay hash.
i = iter->hash & res->max;
for (ent = res->array[i]; ent; ent = ent->next) {
if ((ent->klen == iter->klen) &&
Regards
Rüdiger
Re: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c
Posted by Bojan Smojver <bo...@rexursive.com>.
On Mon, 2012-01-16 at 14:11 +0100, Ruediger Pluem wrote:
> r1231605 and r1231858 cause massive regressions and test case failures
> in httpd. Not sure why right now.
Could you please run your tests with this patch. Let me know how it
goes. Thanks.
--
Bojan
Re: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c
Posted by Ruediger Pluem <rp...@apache.org>.
Bojan Smojver wrote:
> On Sun, 2012-01-15 at 18:06 +0100, Bert Huijben wrote:
>> If the timer has enough detail we could just use the time, ptr
>> combination as the seed here.
>
> See whether you like r1231858.
>
r1231605 and r1231858 cause massive regressions and test case failures in httpd.
Not sure why right now.
est Summary Report
-------------------
t/apache/acceptpathinfo.t (Wstat: 0 Tests: 36 Failed: 10)
Failed tests: 2, 6, 8, 12, 14, 18, 26, 30, 35-36
t/apache/cfg_getline.t (Wstat: 0 Tests: 116 Failed: 58)
Failed tests: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22
24, 26, 28, 30, 32, 34, 36, 38, 40, 42
44, 46, 48, 50, 52, 54, 56, 58, 60, 62
64, 66, 68, 70, 72, 74, 76, 78, 80, 82
84, 86, 88, 90, 92, 94, 96, 98, 100, 102
104, 106, 108, 110, 112, 114, 116
t/apache/pr17629.t (Wstat: 0 Tests: 4 Failed: 2)
Failed tests: 1, 3
t/apache/pr43939.t (Wstat: 0 Tests: 4 Failed: 2)
Failed tests: 1, 3
t/apache/pr49328.t (Wstat: 0 Tests: 1 Failed: 1)
Failed test: 1
t/modules/asis.t (Wstat: 0 Tests: 3 Failed: 3)
Failed tests: 1-3
t/modules/filter.t (Wstat: 0 Tests: 1 Failed: 1)
Failed test: 1
t/modules/lua.t (Wstat: 0 Tests: 36 Failed: 8)
Failed tests: 7-8, 13-14, 16-17, 22-23
t/modules/negotiation.t (Wstat: 0 Tests: 99 Failed: 1)
Failed test: 99
t/modules/proxy.t (Wstat: 0 Tests: 15 Failed: 2)
Failed tests: 9-10
Files=104, Tests=4551, 112 wallclock secs ( 1.37 usr 0.53 sys + 37.48 cusr 14.01 csys = 53.39 CPU)
Regards
Rüdiger
Re: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c
Posted by Ruediger Pluem <rp...@apache.org>.
Bojan Smojver wrote:
> On Sun, 2012-01-15 at 18:06 +0100, Bert Huijben wrote:
>> If the timer has enough detail we could just use the time, ptr
>> combination as the seed here.
>
> See whether you like r1231858.
>
r1231605 and r1231858 cause massive regressions and test case failures in httpd.
Not sure why right now.
est Summary Report
-------------------
t/apache/acceptpathinfo.t (Wstat: 0 Tests: 36 Failed: 10)
Failed tests: 2, 6, 8, 12, 14, 18, 26, 30, 35-36
t/apache/cfg_getline.t (Wstat: 0 Tests: 116 Failed: 58)
Failed tests: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22
24, 26, 28, 30, 32, 34, 36, 38, 40, 42
44, 46, 48, 50, 52, 54, 56, 58, 60, 62
64, 66, 68, 70, 72, 74, 76, 78, 80, 82
84, 86, 88, 90, 92, 94, 96, 98, 100, 102
104, 106, 108, 110, 112, 114, 116
t/apache/pr17629.t (Wstat: 0 Tests: 4 Failed: 2)
Failed tests: 1, 3
t/apache/pr43939.t (Wstat: 0 Tests: 4 Failed: 2)
Failed tests: 1, 3
t/apache/pr49328.t (Wstat: 0 Tests: 1 Failed: 1)
Failed test: 1
t/modules/asis.t (Wstat: 0 Tests: 3 Failed: 3)
Failed tests: 1-3
t/modules/filter.t (Wstat: 0 Tests: 1 Failed: 1)
Failed test: 1
t/modules/lua.t (Wstat: 0 Tests: 36 Failed: 8)
Failed tests: 7-8, 13-14, 16-17, 22-23
t/modules/negotiation.t (Wstat: 0 Tests: 99 Failed: 1)
Failed test: 99
t/modules/proxy.t (Wstat: 0 Tests: 15 Failed: 2)
Failed tests: 9-10
Files=104, Tests=4551, 112 wallclock secs ( 1.37 usr 0.53 sys + 37.48 cusr 14.01 csys = 53.39 CPU)
Regards
Rüdiger
RE: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c
Posted by Bojan Smojver <bo...@rexursive.com>.
On Sun, 2012-01-15 at 18:06 +0100, Bert Huijben wrote:
> If the timer has enough detail we could just use the time, ptr
> combination as the seed here.
See whether you like r1231858.
--
Bojan
RE: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c
Posted by Bojan Smojver <bo...@rexursive.com>.
On Mon, 2012-01-16 at 08:38 +1100, Bojan Smojver wrote:
> That is true. In fact, my first code to the list just used ht. We
> could use ht and time to get "random" values. Same attack vectors as
> noted by you above apply, of course.
Maybe like this?
--
Bojan
RE: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c
Posted by Bojan Smojver <bo...@rexursive.com>.
On Sun, 2012-01-15 at 18:06 +0100, Bert Huijben wrote:
> If you call srand() before every call to rand() the result is no longer random.
Yes, I'm aware of that.
> And in this case we do this inside a shared library, so this might introduce other attack vectors in applications that use apr.
Also aware of that.
> If we really want to call srand() from apr we should do that from a one-time initialization (apr_initialize? Or some initialize flag), to avoid breaking applications that assume rand() produces random values for them. Calling srand() from apr_hash_make might even break scientific applications that want the same set of random values multiple times (srand(CONSTANT)).
We can call srand() once as you suggest, but that doesn't mean something
else isn't going to call it from some other thread at any point. Relying
on rand() returning predictable values in a multi-threaded app would be
naive anyway.
> If the timer has enough detail we could just use the time, ptr combination as the seed here. This is essentially what the code does by calling srand() every time anyway.
That is true. In fact, my first code to the list just used ht. We could
use ht and time to get "random" values. Same attack vectors as noted by
you above apply, of course.
--
Bojan
RE: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c
Posted by Bert Huijben <be...@qqmail.nl>.
> -----Original Message-----
> From: bojan@apache.org [mailto:bojan@apache.org]
> Sent: zondag 15 januari 2012 1:37
> To: commits@apr.apache.org
> Subject: svn commit: r1231605 - /apr/apr/trunk/tables/apr_hash.c
>
> Author: bojan
> Date: Sun Jan 15 00:37:14 2012
> New Revision: 1231605
>
> URL: http://svn.apache.org/viewvc?rev=1231605&view=rev
> Log:
> Randomise hashes by providing a seed.
> This is supposed to be a "good enough" approach. Using a crypto quality
> function like apr_generate_random_bytes() may be stronger, but this
> function
> may block, so it will be avoided for now.
>
> Modified:
> apr/apr/trunk/tables/apr_hash.c
>
> Modified: apr/apr/trunk/tables/apr_hash.c
> URL:
> http://svn.apache.org/viewvc/apr/apr/trunk/tables/apr_hash.c?rev=123160
> 5&r1=1231604&r2=1231605&view=diff
> ==========================================================
> ====================
> --- apr/apr/trunk/tables/apr_hash.c (original)
> +++ apr/apr/trunk/tables/apr_hash.c Sun Jan 15 00:37:14 2012
> @@ -18,6 +18,10 @@
>
> #include "apr_general.h"
> #include "apr_pools.h"
> +#include "apr_time.h"
> +#if APR_HAVE_STDLIB_H
> +#include <stdlib.h> /* for rand, srand */
> +#endif
>
> #include "apr_hash.h"
>
> @@ -75,7 +79,7 @@ struct apr_hash_t {
> apr_pool_t *pool;
> apr_hash_entry_t **array;
> apr_hash_index_t iterator; /* For apr_hash_first(NULL, ...) */
> - unsigned int count, max;
> + unsigned int count, max, seed;
> apr_hashfunc_t hash_func;
> apr_hash_entry_t *free; /* List of recycled entries */
> };
> @@ -95,13 +99,18 @@ static apr_hash_entry_t **alloc_array(ap
> APR_DECLARE(apr_hash_t *) apr_hash_make(apr_pool_t *pool)
> {
> apr_hash_t *ht;
> + apr_time_t now = apr_time_now();
> +
> ht = apr_palloc(pool, sizeof(apr_hash_t));
> ht->pool = pool;
> ht->free = NULL;
> ht->count = 0;
> ht->max = INITIAL_MAX;
> + srand((unsigned int)((now >> 32) ^ now ^ (apr_uintptr_t)ht));
> + ht->seed = (unsigned int)(rand());
If you call srand() before every call to rand() the result is no longer random.
And in this case we do this inside a shared library, so this might introduce other attack vectors in applications that use apr.
If we really want to call srand() from apr we should do that from a one-time initialization (apr_initialize? Or some initialize flag), to avoid breaking applications that assume rand() produces random values for them. Calling srand() from apr_hash_make might even break scientific applications that want the same set of random values multiple times (srand(CONSTANT)).
If the timer has enough detail we could just use the time, ptr combination as the seed here. This is essentially what the code does by calling srand() every time anyway.
Bert