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/27 12:48:55 UTC
svn commit: r1236642 - in /apr/apr/trunk: tables/apr_hash.c test/testhash.c
Author: bojan
Date: Fri Jan 27 11:48:54 2012
New Revision: 1236642
URL: http://svn.apache.org/viewvc?rev=1236642&view=rev
Log:
Randomise hashes by providing a seed.
Modified:
apr/apr/trunk/tables/apr_hash.c
apr/apr/trunk/test/testhash.c
Modified: apr/apr/trunk/tables/apr_hash.c
URL: http://svn.apache.org/viewvc/apr/apr/trunk/tables/apr_hash.c?rev=1236642&r1=1236641&r2=1236642&view=diff
==============================================================================
--- apr/apr/trunk/tables/apr_hash.c (original)
+++ apr/apr/trunk/tables/apr_hash.c Fri Jan 27 11:48:54 2012
@@ -18,6 +18,7 @@
#include "apr_general.h"
#include "apr_pools.h"
+#include "apr_time.h"
#include "apr_hash.h"
@@ -75,7 +76,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 +96,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;
+ ht->seed = (unsigned int)((now >> 32) ^ now ^ (apr_uintptr_t)pool ^
+ (apr_uintptr_t)ht ^ (apr_uintptr_t)&now) - 1;
ht->array = alloc_array(ht, ht->max);
ht->hash_func = apr_hashfunc_default;
+
return ht;
}
@@ -280,7 +286,7 @@ static apr_hash_entry_t **find_entry(apr
apr_hash_entry_t **hep, *he;
unsigned int hash;
- hash = ht->hash_func(key, &klen);
+ hash = ht->seed ^ ht->hash_func(key, &klen);
/* scan linked list */
for (hep = &ht->array[hash & ht->max], he = *hep;
@@ -322,6 +328,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));
@@ -419,7 +426,7 @@ APR_DECLARE(apr_hash_t *) apr_hash_merge
apr_hash_entry_t *new_vals = NULL;
apr_hash_entry_t *iter;
apr_hash_entry_t *ent;
- unsigned int i,j,k;
+ unsigned int i, j, k, hash;
#if APR_POOL_DEBUG
/* we don't copy keys and values, so it's necessary that
@@ -447,6 +454,7 @@ APR_DECLARE(apr_hash_t *) apr_hash_merge
if (base->count + overlay->count > res->max) {
res->max = res->max * 2 + 1;
}
+ res->seed = base->seed;
res->array = alloc_array(res, res->max);
if (base->count + overlay->count) {
new_vals = apr_palloc(p, sizeof(apr_hash_entry_t) *
@@ -468,7 +476,12 @@ APR_DECLARE(apr_hash_t *) apr_hash_merge
for (k = 0; k <= overlay->max; k++) {
for (iter = overlay->array[k]; iter; iter = iter->next) {
- i = iter->hash & res->max;
+ if (res->hash_func == overlay->hash_func)
+ hash = iter->hash ^ overlay->seed;
+ else
+ hash = res->hash_func(iter->key, &iter->klen);
+ hash = res->seed ^ hash;
+ i = hash & res->max;
for (ent = res->array[i]; ent; ent = ent->next) {
if ((ent->klen == iter->klen) &&
(memcmp(ent->key, iter->key, iter->klen) == 0)) {
@@ -486,7 +499,7 @@ APR_DECLARE(apr_hash_t *) apr_hash_merge
new_vals[j].klen = iter->klen;
new_vals[j].key = iter->key;
new_vals[j].val = iter->val;
- new_vals[j].hash = iter->hash;
+ new_vals[j].hash = hash;
new_vals[j].next = res->array[i];
res->array[i] = &new_vals[j];
res->count++;
Modified: apr/apr/trunk/test/testhash.c
URL: http://svn.apache.org/viewvc/apr/apr/trunk/test/testhash.c?rev=1236642&r1=1236641&r2=1236642&view=diff
==============================================================================
--- apr/apr/trunk/test/testhash.c (original)
+++ apr/apr/trunk/test/testhash.c Fri Jan 27 11:48:54 2012
@@ -438,6 +438,79 @@ static void overlay_same(abts_case *tc,
ABTS_STR_EQUAL(tc, "#entries 5\n", StrArray[5]);
}
+static void overlay_fetch(abts_case *tc, void *data)
+{
+ apr_hash_t *base = NULL;
+ apr_hash_t *overlay = NULL;
+ apr_hash_t *result = NULL;
+ int count;
+
+ base = apr_hash_make(p);
+ overlay = apr_hash_make(p);
+ ABTS_PTR_NOTNULL(tc, base);
+ ABTS_PTR_NOTNULL(tc, overlay);
+
+ apr_hash_set(base, "base1", APR_HASH_KEY_STRING, "value1");
+ apr_hash_set(base, "base2", APR_HASH_KEY_STRING, "value2");
+ apr_hash_set(base, "base3", APR_HASH_KEY_STRING, "value3");
+ apr_hash_set(base, "base4", APR_HASH_KEY_STRING, "value4");
+ apr_hash_set(base, "base5", APR_HASH_KEY_STRING, "value5");
+
+ apr_hash_set(overlay, "overlay1", APR_HASH_KEY_STRING, "value1");
+ apr_hash_set(overlay, "overlay2", APR_HASH_KEY_STRING, "value2");
+ apr_hash_set(overlay, "overlay3", APR_HASH_KEY_STRING, "value3");
+ apr_hash_set(overlay, "overlay4", APR_HASH_KEY_STRING, "value4");
+ apr_hash_set(overlay, "overlay5", APR_HASH_KEY_STRING, "value5");
+
+ result = apr_hash_overlay(p, overlay, base);
+
+ count = apr_hash_count(result);
+ ABTS_INT_EQUAL(tc, 10, count);
+
+ ABTS_STR_EQUAL(tc, "value1",
+ apr_hash_get(result, "base1", APR_HASH_KEY_STRING));
+ ABTS_STR_EQUAL(tc, "value2",
+ apr_hash_get(result, "base2", APR_HASH_KEY_STRING));
+ ABTS_STR_EQUAL(tc, "value3",
+ apr_hash_get(result, "base3", APR_HASH_KEY_STRING));
+ ABTS_STR_EQUAL(tc, "value4",
+ apr_hash_get(result, "base4", APR_HASH_KEY_STRING));
+ ABTS_STR_EQUAL(tc, "value5",
+ apr_hash_get(result, "base5", APR_HASH_KEY_STRING));
+ ABTS_STR_EQUAL(tc, "value1",
+ apr_hash_get(result, "overlay1", APR_HASH_KEY_STRING));
+ ABTS_STR_EQUAL(tc, "value2",
+ apr_hash_get(result, "overlay2", APR_HASH_KEY_STRING));
+ ABTS_STR_EQUAL(tc, "value3",
+ apr_hash_get(result, "overlay3", APR_HASH_KEY_STRING));
+ ABTS_STR_EQUAL(tc, "value4",
+ apr_hash_get(result, "overlay4", APR_HASH_KEY_STRING));
+ ABTS_STR_EQUAL(tc, "value5",
+ apr_hash_get(result, "overlay5", APR_HASH_KEY_STRING));
+
+ ABTS_STR_EQUAL(tc, "value1",
+ apr_hash_get(base, "base1", APR_HASH_KEY_STRING));
+ ABTS_STR_EQUAL(tc, "value2",
+ apr_hash_get(base, "base2", APR_HASH_KEY_STRING));
+ ABTS_STR_EQUAL(tc, "value3",
+ apr_hash_get(base, "base3", APR_HASH_KEY_STRING));
+ ABTS_STR_EQUAL(tc, "value4",
+ apr_hash_get(base, "base4", APR_HASH_KEY_STRING));
+ ABTS_STR_EQUAL(tc, "value5",
+ apr_hash_get(base, "base5", APR_HASH_KEY_STRING));
+
+ ABTS_STR_EQUAL(tc, "value1",
+ apr_hash_get(overlay, "overlay1", APR_HASH_KEY_STRING));
+ ABTS_STR_EQUAL(tc, "value2",
+ apr_hash_get(overlay, "overlay2", APR_HASH_KEY_STRING));
+ ABTS_STR_EQUAL(tc, "value3",
+ apr_hash_get(overlay, "overlay3", APR_HASH_KEY_STRING));
+ ABTS_STR_EQUAL(tc, "value4",
+ apr_hash_get(overlay, "overlay4", APR_HASH_KEY_STRING));
+ ABTS_STR_EQUAL(tc, "value5",
+ apr_hash_get(overlay, "overlay5", APR_HASH_KEY_STRING));
+}
+
abts_suite *testhash(abts_suite *suite)
{
suite = ADD_SUITE(suite)
@@ -461,6 +534,7 @@ abts_suite *testhash(abts_suite *suite)
abts_run_test(suite, overlay_empty, NULL);
abts_run_test(suite, overlay_2unique, NULL);
abts_run_test(suite, overlay_same, NULL);
+ abts_run_test(suite, overlay_fetch, NULL);
return suite;
}
Re: svn commit: r1236642 - in /apr/apr/trunk: tables/apr_hash.c test/testhash.c
Posted by Bojan Smojver <bo...@rexursive.com>.
------- Original message -------
> From: Bojan Smojver
> If you can think of a nice function that does that,
Actually, I can think of one - the internal hash function I introduced in
the latest commit. We can simply pass the hash done by the regular hash
function into it and treat it as a string that has to be hashed, starting
with the random seed.
--
Bojan
Re: svn commit: r1236642 - in /apr/apr/trunk: tables/apr_hash.c
test/testhash.c
Posted by Bojan Smojver <bo...@rexursive.com>.
On Sat, 2012-01-28 at 11:37 +0100, Branko Čibej wrote:
> Seeding the hash function is effectively the same as using the hash
> function's output to seed the randomizer, right?
Yeah, randomiser function would have to be something other than simple
xor or similar. The modulo that is used for indexing would have to
change for sure (which xor does not do), otherwise it would be useless.
If you can think of a nice function that does that, feel free to
implement (maybe byte reshuffling could work). I just didn't want to
keep an implementation in SVN that I know was broken.
--
Bojan
Re: svn commit: r1236642 - in /apr/apr/trunk: tables/apr_hash.c
test/testhash.c
Posted by Bojan Smojver <bo...@rexursive.com>.
On Sat, 2012-01-28 at 11:37 +0100, Branko Čibej wrote:
> rerun the result + seed through the built-in hash function
Hopefully r1237078 should do something like that now. I completely
missed this part of your reply, to be honest, so I had to do a bit of
NIH of my own. Reading things on a tiny phone screen has
disadvantages. :-)
PS. Sorry folks for so many commits on this. I will try to refrain from
more. I promise. Maybe. ;-)
--
Bojan
Re: svn commit: r1236642 - in /apr/apr/trunk: tables/apr_hash.c test/testhash.c
Posted by Branko Čibej <br...@xbc.nu>.
On 28.01.2012 00:54, Bojan Smojver wrote:
> ------- Original message -------
>> + hash = ht->seed ^ ht->hash_func(key, &klen);
>
> Actually, when I think about this, it will probably be inefective. If
> two keys produce the same hash, the xor-ed value against the seed will
> most certainly be the same as well. So, this won't actually do
> anything to stop the attack, except change which bucket attack picks.
>
> So, we probably do need to seed the hash function instead.
Seeding the hash function is essentially the same as not using a simple
XOR to do the randomization. Which is why my original suggestion said
randomize_hash(), not XOR.
Seeding the hash function is effectively the same as using the hash
function's output to seed the randomizer, right? So what remains is to
pick a good randomizer, which XOR is not. There's still no no need to
change the hash_func_t signature.
What randomizer you pick really depends on how secure you want to be.
You can use XOR (which you note is useless), or rerun the result + seed
through the built-in hash function (which is probably a bit better), or
run both through a secure hash algorithm (which sounds like overkill).
-- Brane
Re: svn commit: r1236642 - in /apr/apr/trunk: tables/apr_hash.c test/testhash.c
Posted by Bojan Smojver <bo...@rexursive.com>.
------- Original message -------
> + hash = ht->seed ^ ht->hash_func(key, &klen);
Actually, when I think about this, it will probably be inefective. If two
keys produce the same hash, the xor-ed value against the seed will most
certainly be the same as well. So, this won't actually do anything to stop
the attack, except change which bucket attack picks.
So, we probably do need to seed the hash function instead.
--
Bojan