Forwarded for Kurt, as he's not subscribed.
Original Message
Subject: Re: Hash collision vectors in APR?
Date: Thu, 23 Feb 2012 18:32:30 -0700
From: Kurt Seifried kseifr...@redhat.com
To: William A. Rowe Jr. wr...@rowe-clan.net
CC: APR Developer List dev@apr.apache.org, Stefan
And responding;
On 2/23/2012 8:27 PM, William A. Rowe Jr. wrote:
Forwarded for Kurt, as he's not subscribed.
Original Message
Subject: Re: Hash collision vectors in APR?
Date: Thu, 23 Feb 2012 18:32:30 -0700
From: Kurt Seifried kseifr...@redhat.com
To: William A. Rowe Jr
On 1/5/2012 11:45 AM, William A. Rowe Jr. wrote:
http://www.nruns.com/_downloads/advisory28122011.pdf
Should we add some randomization to prevent abuse?
It's hard to anticipate how folks might leverage apr, and how malicious
folks might then seek to exploit computational workload vectors.
Funny how things escalate. Looks like someone turned this:
Should we add some randomization to prevent abuse?
Into this:
http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2012-0840
http://secunia.com/advisories/47862
The vulnerability is caused due to an error within a hash generation function
On 26.01.2012 22:59, Bojan Smojver wrote:
On Fri, 2012-01-27 at 00:36 +1100, Bojan Smojver wrote:
Thanks, will implement.
Attached. If nobody comes up with regressions or other problems with
this approach, I'll commit it to trunk.
Thanks everyone for their input.
The only thing that pops
--- Original message ---
From: Branko Čibej
But the original code is already wrong in assuming that res-hash_func
and overlay-hash_func are the same, so in fact you're silently fixing a
bug with the current change. :)
Surprisingly enough, I actually thought about this bit. Surely
On 06.01.2012 00:05, Bojan Smojver wrote:
On Fri, 2012-01-06 at 09:48 +1100, Bojan Smojver wrote:
The apr_hashfunc_t function prototype would then most likely have to
change. We'd probably need to pass the hash itself into it, which
would then hold the per-hash seed. Right?
Actually, that
--- Original message ---
From: Branko Čibej
- hash = ht-hash_func(key, klen);
+ hash = randomize_hash(ht, ht-hash_func(key, klen);
Completely private change that leaves hash_func_t unchanged.
Interesting approach. So, randomize_hash() would then perturb (xor or
something) what the
On 26.01.2012 12:15, Bojan Smojver wrote:
--- Original message ---
From: Branko Čibej
- hash = ht-hash_func(key, klen);
+ hash = randomize_hash(ht, ht-hash_func(key, klen);
Completely private change that leaves hash_func_t unchanged.
Interesting approach. So, randomize_hash()
--- Original message ---
From: Branko Čibej
Correct. I intentionally left out the implementation, since i don't
really have an opinion about how it should be done. I just wanted to
point out that there's a simple way to add per-table randomization
without changing any of the existing
On Fri, 2012-01-27 at 00:36 +1100, Bojan Smojver wrote:
Thanks, will implement.
Attached. If nobody comes up with regressions or other problems with
this approach, I'll commit it to trunk.
Thanks everyone for their input.
--
Bojan
Index: tables/apr_hash.c
--- Original message ---
From: Joe Orton
(hash(key) * ht-pure_random_number) % ht-max
where ht-max is 15 by default. So you merely have to increase the
size of the input by 15 to produce at least the same overhead; the
attacker must generate 15n keys to ensure they hit all the
On Thu, Jan 05, 2012 at 01:35:50PM -0500, Jeff Trawick wrote:
We don't want to say go fish to APR applications if our hash plus
their vector results in an exploit.
I'll bite.
1) Chained hash tables have quadratic worst case insertion time,
O(n**2). The APR hash table (apr_hash_*)
On Sat, 2012-01-14 at 14:50 +1100, Bojan Smojver wrote:
Yeah, that's probably what we'll have to do.
Gone bold and committed that in r1231605. Feel free to improve,
criticise, rip out etc.
--
Bojan
On Thu, 2012-01-12 at 19:58 -0800, Chris Darroch wrote:
+if (strcmp(DEV_RANDOM, /dev/random) != 0
+apr_generate_random_bytes((unsigned char *)ht-seed,
+ sizeof(ht-seed)) != APR_SUCCESS)
This probably wouldn't work as expected. If you had
On Fri, 2012-01-13 at 19:57 +1100, Bojan Smojver wrote:
This probably wouldn't work as expected. If you had /dev/random
selected for DEV_RANDOM, the if would fail and srand()/rand() bit
would never get called. No?
Like attached maybe?
--
Bojan
Index: tables/apr_hash.c
Chris Darroch chr...@pearsoncmg.com writes:
The other question, I suppose, is whether there's a hit to performance
from apr_generate_random_bytes() call. Without having tested explicitly,
it looks like the default case for modern Linux is APR_HAS_RANDOM=1 and
DEV_RANDOM=/dev/random, with
Bojan Smojver wrote:
On Fri, 2012-01-13 at 19:57 +1100, Bojan Smojver wrote:
This probably wouldn't work as expected. If you had /dev/random
selected for DEV_RANDOM, the if would fail and srand()/rand() bit
would never get called. No?
Like attached maybe?
Yes, that looks better than
Philip Martin wrote:
I'm not sure how Linux distributors configure things, but APR itself
defaults to /dev/urandom.
Yup, Bojan corrected me on that too!
I don't think apr_hash_make should be trying to second guess
apr_generate_random_bytes.
I suppose my strong hesitation about handing
--- Original message ---
From: Chris Darroch
I'd personally rather see the use of it dropped entirely in all cases
and the code Bojan worked on as the fallback case always used, since
it adds no significant complexity and appears in line with other
solutions,
such as the one in
Bojan Smojver wrote:
Given we use CTR, maybe I can just commit something like this to trunk
and others can then commit improvements over the top, if desired?
I'm an httpd guy but not a APR one, so it's really up to you!
Here's a slight variant which, I believe, bypasses
--- Original message ---
From: Chris Darroch
Please test and improve!
Thanks Chris!
--
Bojan
Bojan Smojver wrote:
On Fri, 2012-01-06 at 10:52 +1100, Bojan Smojver wrote:
+if (apr_generate_random_bytes(
+(unsigned char *)ht-seed, sizeof(ht-seed)) != APR_SUCCESS)
+return NULL;
Chris,
What I mean is, instead of return NULL, we could have ht-seed =
(unsigned
On Tue, 2012-01-10 at 15:29 -0800, Chris Darroch wrote:
Without having tested explicitly, it looks like the default case for
modern Linux is APR_HAS_RANDOM=1 and DEV_RANDOM=/dev/random,
with /dev/random blocking when there's no entropy.
Don't think so (run on my F-16 machine, without passing
On Tue, 2012-01-10 at 15:29 -0800, Chris Darroch wrote:
The patch might also need to account for the !APR_HAS_RANDOM case,
now that I look again.
Yes, true.
So I'm less than certain what to suggest here ...
We can always use ANSI C rand()/srand() (racy) or even other APR random
Bojan:
On Tue, 2012-01-10 at 15:29 -0800, Chris Darroch wrote:
Without having tested explicitly, it looks like the default case for
modern Linux is APR_HAS_RANDOM=1 and DEV_RANDOM=/dev/random,
with /dev/random blocking when there's no entropy.
Don't think so (run on my F-16 machine, without
On Tue, 2012-01-10 at 16:04 -0800, Chris Darroch wrote:
I guess the question is what happens if /dev/random
is chosen, though, either automagically or through an explicit choice
with --with-devrandom=/dev/random.
I can tell you from experience - your program stalls a lot. And I mean,
A LOT.
On Tue, 2012-01-10 at 15:29 -0800, Chris Darroch wrote:
I don't know if any of that is useful for APR, but there it is.
There is a function a bit like this in APR: get_random_info() in
crypto/getuuid.c. Essentially, if there is no
apr_generate_random_bytes(), then do the magic.
--
Bojan
On Wed, 2012-01-11 at 11:01 +1100, Bojan Smojver wrote:
We can always use ANSI C rand()/srand() (racy)
This is what I meant. Some code stolen from crypto/getuuid.c.
--
Bojan
Index: tables/apr_hash.c
===
--- tables/apr_hash.c
On 1/10/2012 5:29 PM, Chris Darroch wrote:
Bojan Smojver wrote:
On Fri, 2012-01-06 at 10:52 +1100, Bojan Smojver wrote:
+if (apr_generate_random_bytes(
+(unsigned char *)ht-seed, sizeof(ht-seed)) != APR_SUCCESS)
+return NULL;
Chris,
What I mean is, instead of
On 1/11/2012 12:50 AM, Bojan Smojver wrote:
--- Original message ---
From: William A. Rowe Jr.
Or, rather, ht-seed = (unsigned int)ht - 1 to avoid the obviousness
of folding on even values.
We could also whack ht into the xor with time and use it as seed to srand().
So many
Bojan Smojver wrote:
On Fri, 2012-01-06 at 10:05 +1100, Bojan Smojver wrote:
Any other ideas?
Maybe like this?
Something like that would be appreciated, by me, at least.
One caution, though -- if apr_hash_make() can now return NULL,
a lot of things might suddenly break, like httpd.
On Fri, 2012-01-06 at 10:52 +1100, Bojan Smojver wrote:
+if (apr_generate_random_bytes(
+(unsigned char *)ht-seed, sizeof(ht-seed)) != APR_SUCCESS)
+return NULL;
Chris,
What I mean is, instead of return NULL, we could have ht-seed =
(unsigned int) ht. Not as random as
http://www.nruns.com/_downloads/advisory28122011.pdf
Should we add some randomization to prevent abuse?
It's hard to anticipate how folks might leverage apr, and how malicious
folks might then seek to exploit computational workload vectors.
Thoughts?
On Thu, Jan 5, 2012 at 12:45 PM, William A. Rowe Jr.
wr...@rowe-clan.net wrote:
http://www.nruns.com/_downloads/advisory28122011.pdf
Should we add some randomization to prevent abuse?
It's hard to anticipate how folks might leverage apr, and how malicious
folks might then seek to exploit
On 1/5/2012 12:37 PM, Ben Laurie wrote:
On Thu, Jan 5, 2012 at 5:45 PM, William A. Rowe Jr. wr...@rowe-clan.net
wrote:
http://www.nruns.com/_downloads/advisory28122011.pdf
Should we add some randomization to prevent abuse?
Yes.
So my question comes down to, if we want to preserve using
On Thu, 2012-01-05 at 11:45 -0600, William A. Rowe Jr. wrote:
Should we add some randomization to prevent abuse?
There are Ruby patches in RH bug database that may help as an example:
https://bugzilla.redhat.com/show_bug.cgi?id=CVE-2011-4815
--
Bojan
On Thu, 2012-01-05 at 11:45 -0600, William A. Rowe Jr. wrote:
Should we add some randomization to prevent abuse?
No idea whether this is something that may be useful, but here it is
nevertheless. At least it can be used as an example of what not to
do. :-)
--
Bojan
Index: tables/apr_hash.c
On 1/5/2012 4:13 PM, Bojan Smojver wrote:
On Thu, 2012-01-05 at 11:45 -0600, William A. Rowe Jr. wrote:
Should we add some randomization to prevent abuse?
No idea whether this is something that may be useful, but here it is
nevertheless. At least it can be used as an example of what not to
On Thu, 2012-01-05 at 16:39 -0600, William A. Rowe Jr. wrote:
Question; do we want each hash to have a unique randomization factor?
That would probably be more secure. As is, seed would be initialised
just once per process.
The apr_hashfunc_t function prototype would then most likely have to
On Fri, 2012-01-06 at 09:48 +1100, Bojan Smojver wrote:
The apr_hashfunc_t function prototype would then most likely have to
change. We'd probably need to pass the hash itself into it, which
would then hold the per-hash seed. Right?
Actually, that would not be a good plan. A custom hash
On Fri, 2012-01-06 at 10:05 +1100, Bojan Smojver wrote:
Any other ideas?
Maybe like this?
--
Bojan
Index: tables/apr_hash.c
===
--- tables/apr_hash.c (revision 1227896)
+++ tables/apr_hash.c (working copy)
@@ -75,7 +75,7 @@
42 matches
Mail list logo
