Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] How to secure an OCaml server
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-02-28 (20:24)
From: Thomas Fischbacher <Thomas.Fischbacher@P...>
Subject: Re: [Caml-list] How to secure an OCaml server

> 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 - - [20/Feb/2004:00:30:11 +0100] "GET /~tf/tf.html HTTP/1.0" 200 7142 - - [20/Feb/2004:00:30:11 +0100] "GET /~tf/tutorials.html HTTP/1.0" 200 4767 - - [20/Feb/2004:00:30:11 +0100] "GET /~tf/interests.html HTTP/1.0" 200 1282 - - [20/Feb/2004:00:30:11 +0100] "GET /~tf/misc.html HTTP/1.0" 200 14094 - - [20/Feb/2004:00:30:11 +0100] "GET /~tf/fun.html HTTP/1.0" 200 714 - - [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,                   (o_
 Thomas Fischbacher -  //\
(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 Archives:
Bug reports: FAQ:
Beginner's list: