> Hello Thomas,
> 
> Thomas Fischbacher <Thomas.Fischbacher@Physik.Uni-Muenchen.DE> writes:
> 
> > Yes. Another interesting issue that frequently comes up in such situations 
> > is provoking hash collisions.
> 
> Could you elaborate more on this? I don't understand about which hash
> your are talking.

This is a quite general situation that comes up when you store data on 
your server in a hash in such a way that an external source can control at 
least part of the hash keys.

A very simple and quite harmless example would be creating access 
statistics from webserver logs similar to:

perl -e 'while(<>){s/^(\S+)/$h{$1}++/e;}; printf "%-50s => %6d\n", $_, $h{$_} for sort keys %h;' access_log


with access_log entries of the format

glockner.cip.physik.uni-muenchen.de - - [20/Feb/2004:00:30:11 +0100] "GET /~tf/tf.html HTTP/1.0" 200 7142
glockner.cip.physik.uni-muenchen.de - - [20/Feb/2004:00:30:11 +0100] "GET /~tf/tutorials.html HTTP/1.0" 200 4767
glockner.cip.physik.uni-muenchen.de - - [20/Feb/2004:00:30:11 +0100] "GET /~tf/interests.html HTTP/1.0" 200 1282
glockner.cip.physik.uni-muenchen.de - - [20/Feb/2004:00:30:11 +0100] "GET /~tf/misc.html HTTP/1.0" 200 14094
glockner.cip.physik.uni-muenchen.de - - [20/Feb/2004:00:30:11 +0100] "GET /~tf/fun.html HTTP/1.0" 200 714
glockner.cip.physik.uni-muenchen.de - - [20/Feb/2004:00:30:11 +0100] "GET /~tf/links.html HTTP/1.0" 200 497


Suppose we have a bad guy that controls his own DNS. If we sends me 
thousands of queries which were crafted in such a way that all are mapped 
to the same hash key by my hashing function, he can degrade an O(N log N) 
algorithm to an O(N^2) algorithm with very little effort, effectively 
bringing the program to a standstill.


-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners