Re: [Caml-list] Hashtbl and security

[oliver <oliver@first.in-berlin.de>]

On Sun, Jan 01, 2012 at 10:04:03PM +0100, Gerd Stolpmann wrote:
> Am Sonntag, den 01.01.2012, 18:29 +0100 schrieb Xavier Leroy:
> > On 01/01/2012 01:52 PM, Richard W.M. Jones wrote:
> > > On Fri, Dec 30, 2011 at 06:06:26PM +0100, Xavier Leroy wrote:
> > >> Indeed.  The optional "seed" parameter to Hashtbl.create does exactly
> > >> this in the new implementation of Hashtbl (the one based on Murmur3).
> > > 
> > > 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.
> 
> I understand it very well that adding support for cryptographically
> secure random numbers to core Ocaml is a challenge. There is no POSIX
> API, and /dev/random is, although widely available, still non-standard.
[...]

And also might not be good enough for some certain areas.

val Hashtbl.HashedType.hash: t -> int

allows at least providing your own hashing.function,
but that function then must be sophisticated enough
to provide some dynamic re-seeding.
Not sure if this does not rather conflict with referential transparency?!
Under the hood such a function of course good do some reading from
a random source... but that looks dirty to me.

So such a function with optional seed-parameters (as mentioned by Xavier leroy) might
make sense; when using the imperative features from my understanding it seems
to be much easier to address that hash-collision problem.


> And it is certainly true that there are various levels of security, and
> for some purposes the programmer should be free to install even better
> generators. Nevertheless, Ocaml is now widely used in environments where
> a certain minimum of security is demanded, and I think Ocaml should
> provide this minimum at least, and use it for things like an
> automatically chosen seed for hash tables.

That's already planned and even implemented, as was mentioned in this thread.
So urging for a new official release would make sense.

> 
> My argument is: Even providing a half solution is in this area better
> than leaving the unwary programmer completely alone. Because in the
> latter case, nothing will be done to address the problems, and apps
> would be easier to attack.

Maybe a "half solution" is, what already is done.
I doubt that hash collisions are a new topic,
so I wonder why such things were not already implemented.
Only that this might be used in attacks seems to be "new".


> 
> What I could imagine is a module Sys.Security where all security
> features are accessible and configurable, e.g.

I doubt that this makes sense.
Nearly anything that can be programmed can become a security
issue, if done wrong; especially things done on the
operating system level (like Unix module) could become
a security issue, if things are handled without care.

A mandatory (not optional) hash-function-parameter
that must be passed (plus some default hash functions
with elaborated documentation on the properties of those)
would make more sense to me.

Putting things that need tp be part of the Hash-module
aside into a Sys.security-module makes these things less
apparent to the programmer who just wants to use hashes,
and don't thinks about using hashes might be a security problem.

So, this solution IMHO would be counterproductive
and non-intuitive.


Ciao,
   Oliver