Hello
Here is the latest Caml Weekly News, for the week of December 27, 2011 to January 03, 2012.
Archive: https://sympa-roc.inria.fr/wws/arc/caml-list/2011-12/msg00442.html
Continuing the thread from last week, Gabriel Scherer asked and Fabrice Le Fessant replied:
> I played with the toplevel a bit, but was frustrated by the limitation
> of one-liner input.
> Even in an interactive toplevel it is nice, I think, to be able to
> write multiline programs.
I uploaded a new version a few minutes ago. Now, you can use "multiline
true" to tell the toplevel that you will use ;; as an end of input
instead of the newline (and "multiline false;;" to switch back). My
patch is inspired from yours, but with minimal changes to the current code.
It works for me, but I would be happy to get feed back from "multi-line
users".
Archive: https://sympa-roc.inria.fr/wws/arc/caml-list/2011-12/msg00450.html
Gerd Stolpmann said and Xavier Leroy replied:
> there was recently a security alert for web services that use hash
> tables to store web form parameters sent via POST (so that millions of
> such parameters can be sent in a single request). It is possible to keep
> the web service busy for hours with such a DoS (denial of service)
> attack. The type of attack boils down to a problem in most hash table
> implementations, namely that the hash functions are invertible, and it
> is possible for a malicious user to construct lots of keys that all map
> to the same bucket of the hash table, creating a mass collision.
>
> The text of the alert:
> http://www.nruns.com/_downloads/advisory28122011.pdf
>
> I'd like to discuss this issue, because it is not restricted to the
> processing of web requests, but may also occur for all other data coming
> from untrusted sources. The web is only the most exposed area where this
> issue exists.
>
> So how is Ocaml affected? The hash functions used in recent Ocaml
> releases are also insecure in the above mentioned sense (currently
> MurmurHash3, and even a simpler hash function in previous releases). A
> quick survey of the Internet revealed at least one site that tries to
> break it. Probably a good cryptographer could do it in minutes.
>
> A pure Hashtbl.add of the constructed keys does not yet lead to the
> performance degradation, but a Hashtbl.replace, and of course
> Hashtbl.find after the table is built up will. So it depends very much
> of the details of the programs whether they are affected or not.
>
> I've just checked that Ocamlnet uses only Hashtbl.add to collect POST
> parameters, so it is not directly vulnerable. But if the crafted request
> is actually served by a handler, the handler would get a degraded table,
> and could show in turn bad performance (again leading to DoS).
>
> What are possible fixes?
>
> 1) Avoid hash tables in contexts where security is relevant. The
> alternative is Set (actually a balanced binary tree), which does not
> show this problem.
Highly recommended. Nothing beats guaranteed O(log n) operations.
> 2) Use cryptographically secure hash functions.
Hopeless: with a hash size of 30 bits, as in Caml, or even 64 bits,
there are no cryptographically secure hash functions.
> 3) Use "randomized" hash tables. The trick here is that there is not a
> single hash function h anymore, but a family h(1)...h(n). When the hash
> table is created, one of the functions is picked randomly. This makes it
> impossible to craft an attack request, because you cannot predict the
> function.
Indeed. The optional "seed" parameter to Hashtbl.create does exactly
this in the new implementation of Hashtbl (the one based on Murmur3).
> So, the question is how to do 3). I see two problems here:
>
> a) how to define the family of hash functions. Is it e.g. sufficient to
> introduce an initialization vector for the Murmurhash algorithm, and
> fill it randomly?
IIRC, the Web pages for the Murmur family of hashes gives some
statistical evidence that this approach works.
> How to get a random number that is good enough?
Hmm. /dev/random is your friend on the platforms that support it.
Otherwise, there's always the Random module, but Random.self_init
isn't very strong.
Gerd Stolpmann then replied:
> Indeed. The optional "seed" parameter to Hashtbl.create does exactly
> this in the new implementation of Hashtbl (the one based on Murmur3).
I see. It will be available in 3.13:
val create : ?seed:int -> int -> ('a, 'b) t
There is also an additional functorized interface where this seed
argument exists (Hashtbl.MakeSeeded), and the hash functions seeded_hash
and seeded_hash_param. Well done!
Nevertheless, as we all don't know when 3.13 is ready, I'll have to find
a temporary fix for Ocamlnet. Maybe just a limit for the number of POST
parameters.
> > How to get a random number that is good enough?
>
> Hmm. /dev/random is your friend on the platforms that support it.
> Otherwise, there's always the Random module, but Random.self_init
> isn't very strong.
Well, /dev/(u)random covers most Unix platforms nowadays. If you are
interested, I have a wrapper for Win32:
https://godirepo.camlcity.org/svn/lib-ocamlnet2/trunk/code/src/netsys/netsys_c_win32.c
Scroll down until netsys_fill_random.
Richard Jones also replied and Xavier Leroy said:
> It may be worth noting that Perl solved this problem (back in 2003) by
> unconditionally using a seed which is a global set to a random number
> during interpreter initialization.
That's how my initial reimplementation of Hashtbl worked, using the
Random module to produce seeds, but I was told (correctly) that in
security-sensitive applications it's better to leave the generation of
random numbers under control of the programmer. For some applications
Random.self_init might be good enough and for others stronger
randomness is needed.
Of course, you can trivially emulate Perl's behavior using the new
Hashtbl implementation + the Random module.
Thanks to Alp Mestan, we now include in the Caml Weekly News the links to the
recent posts from the ocamlcore planet blog at http://planet.ocamlcore.org/.
(One by) Four by Nine:
http://alaska-kamtchatka.blogspot.com/2011/12/one-by-four-by-nine.html
Two-way bindings:
http://www.nicollet.net/2011/12/two-way-bindings/
Vose's Alias Method:
http://alaska-kamtchatka.blogspot.com/2011/12/voses-alias-method.html
opdf:
https://forge.ocamlcore.org/projects/opdf/
Packing circles into a rectangle:
https://forge.ocamlcore.org/forum/forum.php?forum_id=820
Beta-release of Coq 8.4:
http://coq.inria.fr/beta-release-of-coq-84
If you happen to miss a CWN, you can send me a message and I'll mail it to you, or go take a look at the archive or the RSS feed of the archives.
If you also wish to receive it every week by mail, you may subscribe online.