From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id VAA10984; Sat, 28 Feb 2004 21:24:26 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id VAA10972 for ; Sat, 28 Feb 2004 21:24:25 +0100 (MET) Received: from mail.physik.uni-muenchen.de (mail.physik.uni-muenchen.de [192.54.42.129]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i1SKOUIq023416 for ; Sat, 28 Feb 2004 21:24:30 +0100 Received: from localhost (unknown [127.0.0.1]) by mail.physik.uni-muenchen.de (Postfix) with ESMTP id 4204D20230; Sat, 28 Feb 2004 20:24:24 +0000 (UTC) Received: from mail.physik.uni-muenchen.de ([127.0.0.1]) by localhost (mail.physik.uni-muenchen.de [127.0.0.1]) (amavisd-new, port 10024) with LMTP id 03128-02-66; Sat, 28 Feb 2004 21:24:13 +0100 (CET) Received: from mailhost.cip.physik.uni-muenchen.de (kaiser.cip.physik.uni-muenchen.de [141.84.136.1]) by mail.physik.uni-muenchen.de (Postfix) with ESMTP id 4655E2027B; Sat, 28 Feb 2004 21:24:13 +0100 (CET) Received: from seekar.cip.physik.uni-muenchen.de (seekar.cip.physik.uni-muenchen.de [141.84.136.52]) by mailhost.cip.physik.uni-muenchen.de (Postfix) with ESMTP id 22D4B8514F; Sat, 28 Feb 2004 21:24:13 +0100 (CET) Received: by seekar.cip.physik.uni-muenchen.de (Postfix, from userid 3092) id 1AD7279FD; Sat, 28 Feb 2004 21:24:13 +0100 (CET) Received: from localhost (localhost [127.0.0.1]) by seekar.cip.physik.uni-muenchen.de (Postfix) with ESMTP id 1865A79FC; Sat, 28 Feb 2004 21:24:13 +0100 (CET) Date: Sat, 28 Feb 2004 21:24:13 +0100 (CET) From: Thomas Fischbacher To: David MENTRE Cc: Richard Jones , caml-list@inria.fr Subject: Re: [Caml-list] How to secure an OCaml server In-Reply-To: <877jy7kn52.fsf@linux-france.org> Message-ID: References: <87llmnme9b.fsf@linux-france.org> <20040228165400.GA24495@redhat.com> <877jy7kn52.fsf@linux-france.org> X-BOFH: Daemons did it MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Virus-Scanned: by amavisd-new at physik.uni-muenchen.de X-Miltered: at nez-perce by Joe's j-chkmail ("http://j-chkmail.ensmp.fr")! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; physik:01 caml-list:01 physik:01 hash:01 hash:01 printf:01 cip:99 2004:99 cip:99 2004:99 714:99 hashing:01 ocaml:01 writes:01 external:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > Hello Thomas, > > Thomas Fischbacher 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