[Caml-list] Re: [oss-security] CVE request: Hash DoS vulnerability (ocert-2011-003)

[Caml-list] Re: [oss-security] CVE request: Hash DoS vulnerability (ocert-2011-003)

[Kurt Seifried]

On 02/06/2012 06:05 PM, Kurt Seifried wrote:
> So going through various things looks like Ocaml is vulnerable and has
> not had a CVE # assigned for this issue yet.
> 
> Discussion of the issue takes place on the mailing list, here is a link
> for the originating thread:
> 
>cc
> 
> There doesn't appear to be a fix yet.
> 
> 

Please use CVE-2012-0839 for this issue.

-- 
Kurt Seifried Red Hat Security Response Team (SRT)

Re: [Caml-list] Re: [oss-security] CVE request: Hash DoS vulnerability (ocert-2011-003)

[Richard W.M. Jones]

On Mon, Feb 06, 2012 at 06:10:15PM -0700, Kurt Seifried wrote:
> On 02/06/2012 06:05 PM, Kurt Seifried wrote:
> > So going through various things looks like Ocaml is vulnerable and has
> > not had a CVE # assigned for this issue yet.
> > 
> > Discussion of the issue takes place on the mailing list, here is a link
> > for the originating thread:
> > 
> >cc
> > 
> > There doesn't appear to be a fix yet.
> > 
> > 
> 
> Please use CVE-2012-0839 for this issue.

Red Hat BZ:

https://bugzilla.redhat.com/show_bug.cgi?id=787888

Rather than changing every app that uses Hashtbl, I'd prefer to fix
this upstream by choosing a random seed for hash tables unless the
caller explicitly sets one or sets an environment variable to disable
this.

In Perl, the seed is a random number chosen when the Perl interpreter
starts up.  This is low overhead, but still leaves a (much more
theoretical) attack where someone can determine the seed from a
long-running process using some other method and still attack the hash
table.

In Python there is an environment variable you can set to disable
randomized hash tables.  Further Python discussion here:
http://bugs.python.org/issue13703
http://mail.python.org/pipermail/python-dev/2012-January/thread.html#115465

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] Re: [oss-security] CVE request: Hash DoS vulnerability (ocert-2011-003)

[Richard W.M. Jones]

On Tue, Feb 07, 2012 at 08:34:12AM +0000, Richard W.M. Jones wrote:
> On Mon, Feb 06, 2012 at 06:10:15PM -0700, Kurt Seifried wrote:
> > On 02/06/2012 06:05 PM, Kurt Seifried wrote:
> > > So going through various things looks like Ocaml is vulnerable and has
> > > not had a CVE # assigned for this issue yet.
> > > 
> > > Discussion of the issue takes place on the mailing list, here is a link
> > > for the originating thread:
> > > 
> > >cc
> > > 
> > > There doesn't appear to be a fix yet.
> > > 
> > > 
> > 
> > Please use CVE-2012-0839 for this issue.
> 
> Red Hat BZ:
> 
> https://bugzilla.redhat.com/show_bug.cgi?id=787888
> 
> Rather than changing every app that uses Hashtbl, I'd prefer to fix
> this upstream by choosing a random seed for hash tables unless the
> caller explicitly sets one or sets an environment variable to disable
> this.
> 
> In Perl, the seed is a random number chosen when the Perl interpreter
> starts up.  This is low overhead, but still leaves a (much more
> theoretical) attack where someone can determine the seed from a
> long-running process using some other method and still attack the hash
> table.
> 
> In Python there is an environment variable you can set to disable
> randomized hash tables.  Further Python discussion here:
> http://bugs.python.org/issue13703
> http://mail.python.org/pipermail/python-dev/2012-January/thread.html#115465

No comment at all?  This is an exploitable CVE ...

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] Re: [oss-security] CVE request: Hash DoS vulnerability (ocert-2011-003)

[Gerd Stolpmann]

> On Tue, Feb 07, 2012 at 08:34:12AM +0000, Richard W.M. Jones wrote:
>> On Mon, Feb 06, 2012 at 06:10:15PM -0700, Kurt Seifried wrote:
>> > On 02/06/2012 06:05 PM, Kurt Seifried wrote:
>> > > So going through various things looks like Ocaml is vulnerable and
>> has
>> > > not had a CVE # assigned for this issue yet.
>> > >
>> > > Discussion of the issue takes place on the mailing list, here is a
>> link
>> > > for the originating thread:
>> > >
>> > >cc
>> > >
>> > > There doesn't appear to be a fix yet.
>> > >
>> > >
>> >
>> > Please use CVE-2012-0839 for this issue.
>>
>> Red Hat BZ:
>>
>> https://bugzilla.redhat.com/show_bug.cgi?id=787888
>>
>> Rather than changing every app that uses Hashtbl, I'd prefer to fix
>> this upstream by choosing a random seed for hash tables unless the
>> caller explicitly sets one or sets an environment variable to disable
>> this.
>>
>> In Perl, the seed is a random number chosen when the Perl interpreter
>> starts up.  This is low overhead, but still leaves a (much more
>> theoretical) attack where someone can determine the seed from a
>> long-running process using some other method and still attack the hash
>> table.
>>
>> In Python there is an environment variable you can set to disable
>> randomized hash tables.  Further Python discussion here:
>> http://bugs.python.org/issue13703
>> http://mail.python.org/pipermail/python-dev/2012-January/thread.html#115465
>
> No comment at all?  This is an exploitable CVE ...

Well, we discussed it already (
http://groups.google.com/group/fa.caml/browse_frm/thread/83d76b4869606c86/3c7eb9abe7d6aa50?tvc=1&q=hashtbl#3c7eb9abe7d6aa50
), and there was no consensus that the "Perl way" is the preferrable one.
OCaml 3.13 will provide options for Hashtbl allowing it pass a seed, but
only in a case by case way. What will not be included in OCaml 3.13 is
access to RNGs with entropy injection (i.e. it is left to the programmer
to solve this difficulty).

IMHO, the situation with 3.13 is not yet satisfying from a security
standpoint, because Ocaml does not guide the developer to a safe solution.

Currently, the only way for library developers to fix their product for
3.12 is to restrict the size of the hashtables coming from untrusted
sources. For example, Ocamlnet-3.5.1 contains a fix for the HTTP and CGI
protocol interpreters in this style. I don't know if there are fixes in
other libraries.

Gerd

>
> Rich.
>
> --
> Richard Jones
> Red Hat
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>
>


-- 
Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
Creator of GODI and camlcity.org.
Contact details:        http://www.camlcity.org/contact.html
Company homepage:       http://www.gerd-stolpmann.de
*** Searching for new projects! Need consulting for system
*** programming in Ocaml? Gerd Stolpmann can help you.

Re: [Caml-list] Re: [oss-security] CVE request: Hash DoS vulnerability (ocert-2011-003)

[Xavier Leroy]

On 03/10/2012 08:31 AM, Richard W.M. Jones wrote:

>> Rather than changing every app that uses Hashtbl, I'd prefer to fix
>> this upstream by choosing a random seed for hash tables unless the
>> caller explicitly sets one or sets an environment variable to disable
>> this.
>>
>> In Perl, the seed is a random number chosen when the Perl interpreter
>> starts up.  This is low overhead, but still leaves a (much more
>> theoretical) attack where someone can determine the seed from a
>> long-running process using some other method and still attack the hash
>> table.
>>
>> In Python there is an environment variable you can set to disable
>> randomized hash tables.  Further Python discussion here:
>> http://bugs.python.org/issue13703
>> http://mail.python.org/pipermail/python-dev/2012-January/thread.html#115465
> 
> No comment at all?  This is an exploitable CVE ...

As you and Gerd said, the new Hashtbl implementation in the upcoming
major release has everything needed to randomize hash tables by
seeding.  The question at this point is whether randomization should
be the default or not: some of our big users who don't do Web stuff
value reproducibility highly...  We (OCaml core developers) will take
a decision soon.

Musing: there is something strange about saying that a data structure
has a DOS vulnerability.  It's a bit like saying that a steak knife
has homicidal intent.  Web-facing applications that use the wrong data
structure have vulnerabilities; the data structure does not.  And,
even randomized, a hashtable still has O(n) worst-case behavior...

Gerd Stolpmann adds:

> Currently, the only way for library developers to fix their product for
> 3.12 is to restrict the size of the hashtables coming from untrusted
> sources.

A much better fix is to replace your hash tables with references to
AVL maps.  Guaranteed O(log n) is the way to go for Web app developers
to sleep soundly at night.

Resignedly awaiting a CVE about association lists,

- Xavier Leroy

Re: [Caml-list] Re: [oss-security] CVE request: Hash DoS vulnerability (ocert-2011-003)

[Romain Bardou]

Hi,

> As you and Gerd said, the new Hashtbl implementation in the upcoming
> major release has everything needed to randomize hash tables by
> seeding.  The question at this point is whether randomization should
> be the default or not: some of our big users who don't do Web stuff
> value reproducibility highly...  We (OCaml core developers) will take
> a decision soon.

FWIW, as a developer I do not expect reproducibility from Hash tables 
(nor from the Random module actually) but I do expect some way to 
control reproducibility (i.e. read the current seed, give my own seed). 
Maybe it's better to assume that the programmer will not be aware of 
attacks, and provide him with a safer environment.

On the other hand, when you find a bug and need reproducibility, it's 
too late if you have used a random seed without recording it. And could 
it break some existing applications?

I guess you('re) already had(having) this discussion though.

Cheers,

-- 
Romain

Re: [Caml-list] Re: [oss-security] CVE request: Hash DoS vulnerability (ocert-2011-003)

[Paolo Donadeo]

In my humble opinion, here we have two different vision of what
computer programming is, or should be. Your statement "maybe it's
better to assume that the programmer will not be aware of attacks" may
be true for the average Java programmer (please, no flame, no insult
intended to Java programmers reading this list!) but not for an OCaml
programmer. I want to be perfectly aware of attacks, and I want to be
in control of the data structure I use, and not "be unaware"...

In Python, the other language I use every day, dictionaries are
implemented as hash tables and not having reproducibility is a PITA.


-- 
Paolo


On Tue, Mar 13, 2012 at 10:54, Romain Bardou <bardou@lsv.ens-cachan.fr> wrote:
> Hi,
>
>
>> As you and Gerd said, the new Hashtbl implementation in the upcoming
>> major release has everything needed to randomize hash tables by
>> seeding.  The question at this point is whether randomization should
>> be the default or not: some of our big users who don't do Web stuff
>> value reproducibility highly...  We (OCaml core developers) will take
>> a decision soon.
>
>
> FWIW, as a developer I do not expect reproducibility from Hash tables (nor
> from the Random module actually) but I do expect some way to control
> reproducibility (i.e. read the current seed, give my own seed). Maybe it's
> better to assume that the programmer will not be aware of attacks, and
> provide him with a safer environment.
>
> On the other hand, when you find a bug and need reproducibility, it's too
> late if you have used a random seed without recording it. And could it break
> some existing applications?
>
> I guess you('re) already had(having) this discussion though.
>
> Cheers,
>
> --
> Romain

Re: [Caml-list] Re: [oss-security] CVE request: Hash DoS vulnerability (ocert-2011-003)

[Philippe Veber]

[-- Attachment #1: Type: text/plain, Size: 3350 bytes --]

The best compromise to me is to leave the default for Hashtbl, but properly
document this aspect in the manual (with succint explanation and one
relevant pointer). That way:
- you don't break compatibility
- you keep default reproducibility (which is a real feature)
- you teach beginners like myself on tough aspects related to the use of a
datastructure in some frequent use cases.

Having a default randomisation seems much too intrusive to me
(notwithstanding the importance of web programming for ocaml's future ;o))
and for those changes that modify the semantic of a program, you have to be
in control. So I second Paolo's opinion.

However, assuming ocaml users will be "aware of attacks", at least more
than users of other languages, is not only controversial but also non
relevant: there are beginners in ocaml too (who may also be beginners in
programming), and these should be taken care of. A small note in the doc on
the DOS vulnerability that may arise from the use of Hashtbl in a web
application context is enough to protect the users I think, and is of
interest for the casual Hashtbl reader. This note could appear in a
different font/color than the main description of [Hashtbl.create], to
preserve the readability of the docs.

my 2 cent
ph.

2012/3/13 Paolo Donadeo <p.donadeo@gmail.com>

> In my humble opinion, here we have two different vision of what
> computer programming is, or should be. Your statement "maybe it's
> better to assume that the programmer will not be aware of attacks" may
> be true for the average Java programmer (please, no flame, no insult
> intended to Java programmers reading this list!) but not for an OCaml
> programmer. I want to be perfectly aware of attacks, and I want to be
> in control of the data structure I use, and not "be unaware"...
>
> In Python, the other language I use every day, dictionaries are
> implemented as hash tables and not having reproducibility is a PITA.
>
>
> --
> Paolo
>
>
> On Tue, Mar 13, 2012 at 10:54, Romain Bardou <bardou@lsv.ens-cachan.fr>
> wrote:
> > Hi,
> >
> >
> >> As you and Gerd said, the new Hashtbl implementation in the upcoming
> >> major release has everything needed to randomize hash tables by
> >> seeding.  The question at this point is whether randomization should
> >> be the default or not: some of our big users who don't do Web stuff
> >> value reproducibility highly...  We (OCaml core developers) will take
> >> a decision soon.
> >
> >
> > FWIW, as a developer I do not expect reproducibility from Hash tables
> (nor
> > from the Random module actually) but I do expect some way to control
> > reproducibility (i.e. read the current seed, give my own seed). Maybe
> it's
> > better to assume that the programmer will not be aware of attacks, and
> > provide him with a safer environment.
> >
> > On the other hand, when you find a bug and need reproducibility, it's too
> > late if you have used a random seed without recording it. And could it
> break
> > some existing applications?
> >
> > I guess you('re) already had(having) this discussion though.
> >
> > Cheers,
> >
> > --
> > Romain
>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>

[-- Attachment #2: Type: text/html, Size: 4323 bytes --]

Re: [Caml-list] Re: [oss-security] CVE request: Hash DoS vulnerability (ocert-2011-003)

[Gerd Stolpmann]

> The best compromise to me is to leave the default for Hashtbl, but
> properly
> document this aspect in the manual (with succint explanation and one
> relevant pointer). That way:
> - you don't break compatibility
> - you keep default reproducibility (which is a real feature)
> - you teach beginners like myself on tough aspects related to the use of a
> datastructure in some frequent use cases.

Basically I like the idea of "teaching" users this way. The typical user
will understand the impact, and act accordingly. Nevertheless, I would
like it if it would be made as easy as possible to provide good seeds if
required. The Random module is definitely not good enough (e.g. if you
know when the program was started like for a cgi, and the cgi reveals
information it should better not like the pid, the Random seed is made
from less than 10 unpredictable bits, and on some systems even 0 bits).

The ideal would be to guide the user to the decision whether protection is
necessary, and if the answer is yes, to give the instructions how to do it
(and provide all means for it, of course).

> Having a default randomisation seems much too intrusive to me
> (notwithstanding the importance of web programming for ocaml's future ;o))

Btw, it's not just web programming. This is only the original example, and
it works because there is a message type for web protocols with unlimited
length. Most other network protocols don't have this, and are immune. The
other big class of attackable programs are offline processors of untrusted
data. It's of course harder to do, and you would probably need some other
information leak to conduct it, but these programs are not outside the
danger zone just because they are not directly accessible.

> and for those changes that modify the semantic of a program, you have to
> be
> in control. So I second Paolo's opinion.

Reproducibility is definitely an important feature.

Gerd

> However, assuming ocaml users will be "aware of attacks", at least more
> than users of other languages, is not only controversial but also non
> relevant: there are beginners in ocaml too (who may also be beginners in
> programming), and these should be taken care of. A small note in the doc
> on
> the DOS vulnerability that may arise from the use of Hashtbl in a web
> application context is enough to protect the users I think, and is of
> interest for the casual Hashtbl reader. This note could appear in a
> different font/color than the main description of [Hashtbl.create], to
> preserve the readability of the docs.
>
> my 2 cent
> ph.
>
> 2012/3/13 Paolo Donadeo <p.donadeo@gmail.com>
>
>> In my humble opinion, here we have two different vision of what
>> computer programming is, or should be. Your statement "maybe it's
>> better to assume that the programmer will not be aware of attacks" may
>> be true for the average Java programmer (please, no flame, no insult
>> intended to Java programmers reading this list!) but not for an OCaml
>> programmer. I want to be perfectly aware of attacks, and I want to be
>> in control of the data structure I use, and not "be unaware"...
>>
>> In Python, the other language I use every day, dictionaries are
>> implemented as hash tables and not having reproducibility is a PITA.
>>
>>
>> --
>> Paolo
>>
>>
>> On Tue, Mar 13, 2012 at 10:54, Romain Bardou <bardou@lsv.ens-cachan.fr>
>> wrote:
>> > Hi,
>> >
>> >
>> >> As you and Gerd said, the new Hashtbl implementation in the upcoming
>> >> major release has everything needed to randomize hash tables by
>> >> seeding.  The question at this point is whether randomization should
>> >> be the default or not: some of our big users who don't do Web stuff
>> >> value reproducibility highly...  We (OCaml core developers) will take
>> >> a decision soon.
>> >
>> >
>> > FWIW, as a developer I do not expect reproducibility from Hash tables
>> (nor
>> > from the Random module actually) but I do expect some way to control
>> > reproducibility (i.e. read the current seed, give my own seed). Maybe
>> it's
>> > better to assume that the programmer will not be aware of attacks, and
>> > provide him with a safer environment.
>> >
>> > On the other hand, when you find a bug and need reproducibility, it's
>> too
>> > late if you have used a random seed without recording it. And could it
>> break
>> > some existing applications?
>> >
>> > I guess you('re) already had(having) this discussion though.
>> >
>> > Cheers,
>> >
>> > --
>> > Romain
>>
>>
>> --
>> Caml-list mailing list.  Subscription management and archives:
>> https://sympa-roc.inria.fr/wws/info/caml-list
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs
>>
>>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>


-- 
Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
Creator of GODI and camlcity.org.
Contact details:        http://www.camlcity.org/contact.html
Company homepage:       http://www.gerd-stolpmann.de
*** Searching for new projects! Need consulting for system
*** programming in Ocaml? Gerd Stolpmann can help you.

Re: [Caml-list] Re: [oss-security] CVE request: Hash DoS vulnerability (ocert-2011-003)

[Romain Bardou]

Le 13/03/2012 14:23, Gerd Stolpmann a écrit :
>
>> The best compromise to me is to leave the default for Hashtbl, but
>> properly
>> document this aspect in the manual (with succint explanation and one
>> relevant pointer). That way:
>> - you don't break compatibility
>> - you keep default reproducibility (which is a real feature)
>> - you teach beginners like myself on tough aspects related to the use of a
>> datastructure in some frequent use cases.
>
> Basically I like the idea of "teaching" users this way. The typical user
> will understand the impact, and act accordingly. Nevertheless, I would
> like it if it would be made as easy as possible to provide good seeds if
> required. The Random module is definitely not good enough (e.g. if you
> know when the program was started like for a cgi, and the cgi reveals
> information it should better not like the pid, the Random seed is made
> from less than 10 unpredictable bits, and on some systems even 0 bits).
>
> The ideal would be to guide the user to the decision whether protection is
> necessary, and if the answer is yes, to give the instructions how to do it
> (and provide all means for it, of course).

This teaching idea sounds great indeed, but on the other hand, where do 
we draw the line? If we push this reasoning too far, we could remove 
typing altogether and just tell the programmer to be careful. What is 
the difference here? Is a potential DoS attack "less bad" than a seg fault?

So although the idea of teaching the programmer through the 
documentation makes sense, I would put it the other way around: make the 
safer behavior the default, and give debugging tools with proper 
warnings. Here the tool is a "set_seed" function and the warning is in 
its documentation: "using the same seed everytime can lead to DoS attacks".

That being said I don't really care that much, I'm just thinking out 
loud here :p

Cheers,

-- 
Romain Bardou

Re: [Caml-list] Re: [oss-security] CVE request: Hash DoS vulnerability (ocert-2011-003)

[Richard W.M. Jones]

On Tue, Mar 13, 2012 at 12:58:13PM +0100, Paolo Donadeo wrote:
> In my humble opinion, here we have two different vision of what
> computer programming is, or should be. Your statement "maybe it's
> better to assume that the programmer will not be aware of attacks" may
> be true for the average Java programmer (please, no flame, no insult
> intended to Java programmers reading this list!) but not for an OCaml
> programmer.

Actually the thing I enjoy about OCaml is the respite from having to
worry about so many things (in contrast to C).

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] Re: [oss-security] CVE request: Hash DoS vulnerability (ocert-2011-003)

[Dario Teixeira]

Hi,

> Basically I like the idea of "teaching" users this way. The typical user

> will understand the impact, and act accordingly. Nevertheless, I would
> like it if it would be made as easy as possible to provide good seeds if
> required. The Random module is definitely not good enough (e.g. if you
> know when the program was started like for a cgi, and the cgi reveals
> information it should better not like the pid, the Random seed is made
> from less than 10 unpredictable bits, and on some systems even 0 bits).
> 
> The ideal would be to guide the user to the decision whether protection is
> necessary, and if the answer is yes, to give the instructions how to do it
> (and provide all means for it, of course).

I think the problem may be in finding a good source of randomness that is
common across all OSes.  In Unixland this problem has largely been solved:
pretty much everyone supports /dev/random and /dev/urandom.  Windows
does things differently, however.

Cheers,
Dario Teixeira

RE: [Caml-list] Re: [oss-security] CVE request: Hash DoS vulnerability (ocert-2011-003)

[David Allsopp]

Romain Bardou wrote:
> Le 13/03/2012 14:23, Gerd Stolpmann a écrit :
> >
> >> The best compromise to me is to leave the default for Hashtbl, but
> >> properly document this aspect in the manual (with succint explanation
> >> and one relevant pointer). That way:
> >> - you don't break compatibility
> >> - you keep default reproducibility (which is a real feature)
> >> - you teach beginners like myself on tough aspects related to the use
> >> of a datastructure in some frequent use cases.
> >
> > Basically I like the idea of "teaching" users this way. The typical
> > user will understand the impact, and act accordingly. Nevertheless, I
> > would like it if it would be made as easy as possible to provide good
> > seeds if required. The Random module is definitely not good enough
> > (e.g. if you know when the program was started like for a cgi, and the
> > cgi reveals information it should better not like the pid, the Random
> > seed is made from less than 10 unpredictable bits, and on some systems
> even 0 bits).
> >
> > The ideal would be to guide the user to the decision whether
> > protection is necessary, and if the answer is yes, to give the
> > instructions how to do it (and provide all means for it, of course).
> 
> This teaching idea sounds great indeed, but on the other hand, where do
> we draw the line? If we push this reasoning too far, we could remove
> typing altogether and just tell the programmer to be careful. What is the
> difference here? Is a potential DoS attack "less bad" than a seg fault?
> 
> So although the idea of teaching the programmer through the documentation
> makes sense, I would put it the other way around: make the safer behavior
> the default, and give debugging tools with proper warnings. Here the tool
> is a "set_seed" function and the warning is in its documentation: "using
> the same seed everytime can lead to DoS attacks".

+1. Surely in projects where repeatability is important, the change in behaviour to randomly seeded tables would be quickly noticed (and can be quickly solved, if the appropriate "set_seed" or whatever is there) through failing unit tests and so on, surely? Repeatability seems the more niche use of a hash table, IMHO, even if it's by some of OCaml's bigger players! One could even imagine having things so that programs linked normally use a randomly seed hashtable and programs *linked* with -g use a fixed seed, for debugging (i.e. the current behaviour) - again, with suitable documentation explaining why you don't put debug builds of software on live web servers...


David 

RE: [Caml-list] Re: [oss-security] CVE request: Hash DoS vulnerability (ocert-2011-003)

[David Allsopp]

Dario Teixeira wrote:
> Hi,
> 
> > Basically I like the idea of "teaching" users this way. The typical
> > user
> 
> > will understand the impact, and act accordingly. Nevertheless, I would
> > like it if it would be made as easy as possible to provide good seeds
> > if required. The Random module is definitely not good enough (e.g. if
> > you know when the program was started like for a cgi, and the cgi
> > reveals information it should better not like the pid, the Random seed
> > is made from less than 10 unpredictable bits, and on some systems even
> 0 bits).
> >
> > The ideal would be to guide the user to the decision whether
> > protection is necessary, and if the answer is yes, to give the
> > instructions how to do it (and provide all means for it, of course).
> 
> I think the problem may be in finding a good source of randomness that is
> common across all OSes.  In Unixland this problem has largely been
> solved:
> pretty much everyone supports /dev/random and /dev/urandom.  Windows does
> things differently, however.

Does the source of randomness have to be common? The decision to use a random seed doesn't need to be limited by a problem getting a good cryptographically secure generator on a given OS - you'd simply document that the implementation on that particular OS doesn't seed with a good PRNG and await a patch from someone who may care in the future, but at least the philosophy behind the decision is correct!

On Windows, as it happens, the situation is relatively easy (and it's not as even the Windows ports don't already have 1001 other workarounds and alternate methods in the runtime and standard library!): CryptGenRandom in the Crypto API or a neat little trick described in http://blogs.msdn.com/b/michael_howard/archive/2005/01/14/353379.aspx.


David

Re: [Caml-list] Re: [oss-security] CVE request: Hash DoS vulnerability (ocert-2011-003)

[Alain Frisch]

On 03/13/2012 07:27 PM, David Allsopp wrote:
> +1. Surely in projects where repeatability is important, the change in behaviour to randomly seeded tables would be quickly noticed

The problem is that the randomization might go unnoticed if the 
high-level outputs of the program does not depend on the ordering when 
enumerating the hash table (because the "interesting" algorithms built 
above the hash table is supposed to be invariant w.r.t. the ordering of 
their input).  So the programmer doesn't turn randomization off, but one 
day, the end-user discovers a bug (caused by a very subtle bug in the 
algorithm, which in fact, depends on the ordering), and one cannot 
reproduce it.

Ocsigen and other web libraries can decide to turn randomization on by 
default to protect their users, but for a general purpose programming 
system like OCaml's stdlib, increasing reproducibility seems more 
important than protecting programmers from high-level defects 
(possibility of DoS) caused by a poor choice or use of low-level data 
structure.


Alain

Re: [Caml-list] Re: [oss-security] CVE request: Hash DoS vulnerability (ocert-2011-003)

[Xavier Leroy]

Gerd Stolpmann writes:
> The Random module is definitely not good enough (e.g. if you
> know when the program was started like for a cgi, and the cgi reveals
> information it should better not like the pid, the Random seed is made
> from less than 10 unpredictable bits, and on some systems even 0 bits).

Dario Teixeira adds:
> I think the problem may be in finding a good source of randomness
> that is common across all OSes.  In Unixland this problem has
> largely been solved: pretty much everyone supports /dev/random and
> /dev/urandom.  Windows does things differently, however.

David Allsopp adds:
> Does the source of randomness have to be common? The decision to use
> a random seed doesn't need to be limited by a problem getting a good
> cryptographically secure generator on a given OS - you'd simply
> document that the implementation on that particular OS doesn't seed
> with a good PRNG and await a patch from someone who may care in the
> future, but at least the philosophy behind the decision is correct!

We are also thinking of strengthening Random.self_init, for instance
by using /dev/urandom when available.  This said, for randomizing
hashtables or other data structures, we do *not* need a
cryptographically-strong PRNG: we're not generating an RSA key pair or
some other situation where cryptographic quality is required; we're
just making a mild DOS attack impractical.

(Obligatory advertisement: if you're in need of
cryptographically-strong random data,
http://forge.ocamlcore.org/projects/cryptokit/
is what you need.)

- Xavier Leroy