From: "Stefan Reich" <[email protected]>
> You should always add a random value in the doubling phase; otherwise, the
> indices will be as easy to spam as they are now - just fill slots 1, 2, 4,
> 8, 16, ... with your bogus values.
The devil certainly puts your mind to good service ;-)
You stopped an exploit before the vulnerability was even coded.
Perhaps instead of doubling, I could add a random number between 3n/2 and
5n/2, where n is the current guess.
In fact, the simulation reveals that the random factor makes the search
slightly faster on average.
(code below).
Now, Stefan or anyone, any thoughts on the n-threads version?
Cheers
David
------------
#include <stdio.h>
#include <time.h>
long findnextfreekey(long actual, char userandom);
int keyexists(long guess, long actual);
long max_keyfound_hits = 0;
long max_keynotfound_hits = 0;
long max_keyfound_hits_r = 0;
long max_keynotfound_hits_r = 0;
main(int argc, char *argv[])
{
long max;
long curkey;
char buf[80];
srand(time(NULL));
printf("Max free index num: ");
fflush(stdout);
gets(buf);
sscanf(buf, "%ld", &max);
for (curkey = 1; curkey <= max; curkey *= 2)
{
findnextfreekey(curkey, 0);
findnextfreekey(curkey, 1);
}
printf("Linear: Max successful hits = %ld, max failed hits = %ld\n",
max_keyfound_hits, max_keynotfound_hits);
printf("Random: Max successful hits = %ld, max failed hits = %ld\n",
max_keyfound_hits_r, max_keynotfound_hits_r);
printf("Press <enter> to quit");
fflush(stdout);
getchar();
}
long findnextfreekey(long actual, char userandom)
{
long guess;
long prev_yes = 0;
long prev_no = -1;
long prev_guess = 0;
long num_keyfound_hits = 0;
long num_keynotfound_hits = 0;
guess = 1;
while (1)
{
if (prev_guess == guess)
{
printf("actual=%ld, guess=%ld, keyfoundhits=%ld, keynotfoundhits=%ld,
totalhits=%ld\n",
actual, guess + 1, num_keyfound_hits, num_keynotfound_hits,
num_keyfound_hits + num_keynotfound_hits);
if (userandom)
{
if (num_keyfound_hits > max_keyfound_hits)
max_keyfound_hits = num_keyfound_hits;
if (num_keynotfound_hits > max_keynotfound_hits)
max_keynotfound_hits = num_keynotfound_hits;
return guess + 1;
}
else
{
if (num_keyfound_hits > max_keyfound_hits_r)
max_keyfound_hits_r = num_keyfound_hits;
if (num_keynotfound_hits > max_keynotfound_hits_r)
max_keynotfound_hits_r = num_keynotfound_hits;
return guess + 1;
}
}
prev_guess = guess;
if (keyexists(guess, actual))
{
num_keyfound_hits++;
prev_yes = guess;
if (prev_no == -1)
guess += guess + (rand() % guess) - (guess / 2);
else
guess = (guess + prev_no) / 2;
}
else
{
num_keynotfound_hits++;
prev_no = guess;
guess = (prev_yes + guess) / 2;
}
}
}
int keyexists(long guess, long actual)
{
return (guess < actual);
}
-----------------
----- Original Message -----
From: "Stefan Reich" <[email protected]>
To: <devl at freenetproject.org>
Sent: Wednesday, June 06, 2001 00:32
Subject: Re: [freenet-devl] Exponential Key Index Insertion
> ----- Original Message -----
> From: "David McNab" <david at rebirthing.co.nz>
> > Perhaps this is way ancient, but in case it's not, here goes.
>
> Exponential insertion is dearly needed, so definitely not ancient. I don't
> really see what you need to simulate here though =;-)
>
> > Algorithm is to start at a guess of 1, and keep doubling the guess till
> the
> > key request fails, then binary search till the next empty key slot is
> found.
>
> You should always add a random value in the doubling phase; otherwise, the
> indices will be as easy to spam as they are now - just fill slots 1, 2, 4,
> 8, 16, ... with your bogus values.
>
> -Stefan
>
>
>
> _______________________________________________
> Devl mailing list
> Devl at freenetproject.org
> http://lists.freenetproject.org/mailman/listinfo/devl
>
_______________________________________________
Devl mailing list
Devl at freenetproject.org
http://lists.freenetproject.org/mailman/listinfo/devl
