using Hash functions for denial of service attacks on web services

On Thu, Dec 29, 2011 at 12:07 PM, Henry Story <henry.story@gmail.com> wrote:

It is worth being aware of this talk that took place at the 28c3 recently

 http://www.youtube.com/watch?v=R2Cq3CLI6H8

Perhaps there are some things that can be done language level to improve things here.

Ah. Thanks for posting. I just came across the paper the other day

http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf

I find it stunning that they don't know the Big-O complexity of a hash table.

On Thu, Dec 29, 2011 at 11:10 AM, Doug Tangren <d.tangren@gmail.com> wrote:

On Thu, Dec 29, 2011 at 12:07 PM, Henry Story <henry.story@gmail.com> wrote:

It is worth being aware of this talk that took place at the 28c3 recently

 http://www.youtube.com/watch?v=R2Cq3CLI6H8

Perhaps there are some things that can be done language level to improve things here.

Ah. Thanks for posting. I just came across the paper the other day

http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf

Scala uses the MurmurHash3 algorithm for most everything, so it would be hard for an attacker to predict how to change the input values to cause a collision.  Java String is kind of a problem, since it uses an embarrassingly simple algorithm (e.g. "CB" collides with "Ba").  scala.util.MurmurHash.stringHash(s) will compute a higher-quality hash, if you need it.

So I think Scala is on reasonably good ground here.  Of course, using a cryptographic hash would make things harder yet, but at least compared to Java, I think things are (now) done sensibly.

Having a RobustHashMap backed by AVL trees or somesuch (for collisions) on items with an Ordering would be a good idea too, for applications where people expect the map to be attacked.  Or one could just use immutable.TreeMap.

  --Rex


On Thu, Dec 29, 2011 at 12:07 PM, Henry Story <henry.story@gmail.com> wrote:

It is worth being aware of this talk that took place at the 28c3 recently

 http://www.youtube.com/watch?v=R2Cq3CLI6H8

Perhaps there are some things that can be done language level to improve things here.

Henry

Social Web Architect
http://bblfish.net/

On Thu, Dec 29, 2011 at 1:49 PM, Rex Kerr <ichoran@gmail.com> wrote:

Scala uses the MurmurHash3 algorithm for most everything, so it would be hard for an attacker to predict how to change the input values to cause a collision.  Java String is kind of a problem, since it uses an embarrassingly simple algorithm (e.g. "CB" collides with "Ba").  scala.util.MurmurHash.stringHash(s) will compute a higher-quality hash, if you need it.

Hot dang. I was just going to look into writing a murmur2 hasher the other day. What luck!

I might be wrong, but if the servlet container (written in Java) uses
any hashes on String, it doesn't matter what Scala, or Lift uses,
correct?

Thanks,
Eric

On Thu, Dec 29, 2011 at 12:49 PM, Rex Kerr wrote:
> Scala uses the MurmurHash3 algorithm for most everything, so it would be
> hard for an attacker to predict how to change the input values to cause a
> collision.  Java String is kind of a problem, since it uses an
> embarrassingly simple algorithm (e.g. "CB" collides with "Ba").
> scala.util.MurmurHash.stringHash(s) will compute a higher-quality hash, if
> you need it.
>
> So I think Scala is on reasonably good ground here.  Of course, using a
> cryptographic hash would make things harder yet, but at least compared to
> Java, I think things are (now) done sensibly.
>
> Having a RobustHashMap backed by AVL trees or somesuch (for collisions) on
> items with an Ordering would be a good idea too, for applications where
> people expect the map to be attacked.  Or one could just use
> immutable.TreeMap.
>
>   --Rex
>
>
> On Thu, Dec 29, 2011 at 12:07 PM, Henry Story wrote:
>>
>> It is worth being aware of this talk that took place at the 28c3 recently
>>
>>  http://www.youtube.com/watch?v=R2Cq3CLI6H8
>>
>> Perhaps there are some things that can be done language level to improve
>> things here.
>>
>> Henry
>>
>> Social Web Architect
>> http://bblfish.net/
>>
>

On Thursday, 29 December 2011 20:26:18 UTC+1, Eric J. Christeson wrote:

I might be wrong, but if the servlet container (written in Java) uses
any hashes on String, it doesn't matter what Scala, or Lift uses,
correct?

That makes sense to me. The good news might be for people using minimalisticframeworks such as unfiltered with netty, as there the hashes generated would with I imagine (need to check) be using the Scala collections.
The other thing that is important to take from this is just how easy denial of service attacks can be. As much as possible web services should use Streams instead of putting things into memory, for POSTs and PUTs for example... 
It also looks like there may be very good reason to use the Scala for parsers as this speaker of this talk "The Science of Insecurity" mentioned a couple of times, as I suppose the scala parsers use the less problematic hash maps...   http://www.youtube.com/watch?v=3kEfedtQVOY 

Thanks,
Eric

 

Am 29.12.2011 19:49, schrieb Rex Kerr:
> Java String is kind of a problem, since it uses an
> embarrassingly simple algorithm (e.g. "CB" collides with "Ba").

And if you need more colliding keys, just concatenate some
copies of "CB" and "Ba":

scala> :paste
// Entering paste mode (ctrl-D to finish)

val a = List("CB", "Ba");
(for (i <- a; j <- a; k <- a; l <- a; m <- a; n <-a)
yield (i+j+k+l+m+n).hashCode) toSet

// Exiting paste mode, now interpreting.

a: List[java.lang.String] = List(CB, Ba)
res14: scala.collection.immutable.Set[Int] = Set(-659435014)

On 30 Dec 2011, at 12:39, Florian Hars wrote:

> Am 29.12.2011 19:49, schrieb Rex Kerr:
>> Java String is kind of a problem, since it uses an
>> embarrassingly simple algorithm (e.g. "CB" collides with "Ba").
>
> And if you need more colliding keys, just concatenate some
> copies of "CB" and "Ba":
>
> scala> :paste
> // Entering paste mode (ctrl-D to finish)
>
> val a = List("CB", "Ba");
> (for (i <- a; j <- a; k <- a; l <- a; m <- a; n <-a)
> yield (i+j+k+l+m+n).hashCode) toSet
>
> // Exiting paste mode, now interpreting.
>
> a: List[java.lang.String] = List(CB, Ba)
> res14: scala.collection.immutable.Set[Int] = Set(-659435014)

with MurmurHash

-----------------------------------
scala> :paste
// Entering paste mode (ctrl-D to finish)

import scala.util.MurmurHash.stringHash

val a = List("CB", "Ba");

(for (i <- a; j <- a; k <- a; l <- a; m <- a; n <-a)
yield stringHash(i+j+k+l+m+n)) toSet

// Exiting paste mode, now interpreting.

import scala.util.MurmurHash.stringHash
a: List[java.lang.String] = List(CB, Ba)
res0: scala.collection.immutable.Set[Int] = Set(1258942331, -2077668356, 1489034968, -423024682, -997514797, 316420206, -2017853295, 1262230940, 2101210924, -1545283093, -1933605740, -347611784, -373791822, 1960052462, 307713112, 1952948212, 1159902624, 865320068, 1766915109, 1693875134, 1979016885, 249570340, 1615072379, 946244333, -115044496, 615686764, 374747868, -408010445, -1600448894, 904377899, 2023208484, -1257554771, -1129770341, 1782454564, 1919681108, 169874909, 1356792094, -593012089, 1547271063, -1062440636, 48304905, 729867060, -1103430469, -511066595, -1063610861, 191256646, 999062302, -1138404309, -652333510, 1140025380, 188991042, 1381439889, 872107563, 1592531872, -1613173278, -1423073787,...
scala> res0.size
res1: Int = 64
--------------------------------------

Now of course murmur hash may be attackable differently, but at least here it makes a difference....

Henry

Social Web Architect
http://bblfish.net/

More to the point,

scala> stringHash("dmogo") == stringHash("oevmw")  // Found a collision!
res155: Boolean = true

scala> stringHash("uqjeg") == stringHash("akqiy")  // Found another!
res157: Boolean = true

scala> stringHash("dmogouqjeg") == stringHash("oevmwakqiy")
res158: Boolean = false

If you have collisions, you can't use them to create more (not easily, anyway).

  --Rex

On Fri, Dec 30, 2011 at 7:27 AM, Henry Story <henry.story@gmail.com> wrote:

On 30 Dec 2011, at 12:39, Florian Hars wrote:

> Am 29.12.2011 19:49, schrieb Rex Kerr:
>> Java String is kind of a problem, since it uses an
>> embarrassingly simple algorithm (e.g. "CB" collides with "Ba").
>
> And if you need more colliding keys, just concatenate some
> copies of "CB" and "Ba":
>
> scala> :paste
> // Entering paste mode (ctrl-D to finish)
>
> val a = List("CB", "Ba");
> (for (i <- a; j <- a; k <- a; l <- a; m <- a; n <-a)
>    yield (i+j+k+l+m+n).hashCode) toSet
>
> // Exiting paste mode, now interpreting.
>
> a: List[java.lang.String] = List(CB, Ba)
> res14: scala.collection.immutable.Set[Int] = Set(-659435014)

with MurmurHash

-----------------------------------
scala> :paste
// Entering paste mode (ctrl-D to finish)

import scala.util.MurmurHash.stringHash

val a = List("CB", "Ba");

(for (i <- a; j <- a; k <- a; l <- a; m <- a; n <-a)
  yield stringHash(i+j+k+l+m+n)) toSet

// Exiting paste mode, now interpreting.

import scala.util.MurmurHash.stringHash
a: List[java.lang.String] = List(CB, Ba)
res0: scala.collection.immutable.Set[Int] = Set(1258942331, -2077668356, 1489034968, -423024682, -997514797, 316420206, -2017853295, 1262230940, 2101210924, -1545283093, -1933605740, -347611784, -373791822, 1960052462, 307713112, 1952948212, 1159902624, 865320068, 1766915109, 1693875134, 1979016885, 249570340, 1615072379, 946244333, -115044496, 615686764, 374747868, -408010445, -1600448894, 904377899, 2023208484, -1257554771, -1129770341, 1782454564, 1919681108, 169874909, 1356792094, -593012089, 1547271063, -1062440636, 48304905, 729867060, -1103430469, -511066595, -1063610861, 191256646, 999062302, -1138404309, -652333510, 1140025380, 188991042, 1381439889, 872107563, 1592531872, -1613173278, -1423073787,...
scala> res0.size
res1: Int = 64
--------------------------------------

Now of course murmur hash may be attackable differently, but at least here it makes a difference....

Henry

Social Web Architect
http://bblfish.net/

Let me apologize for this idiotic statement. I misread one of their slides.

On Thu, Dec 29, 2011 at 12:06 PM, Nils Kilden-Pedersen <nilskp@gmail.com> wrote:

I find it stunning that they don't know the Big-O complexity of a hash table.

On Thu, Dec 29, 2011 at 2:26 PM, ejc <eric.j.christeson@gmail.com> wrote:

I might be wrong, but if the servlet container (written in Java) uses
any hashes on String, it doesn't matter what Scala, or Lift uses,
correct?

I think this is the important point. 
Fortunately, jetty is on top of it [1] and netty, out of the box, leaves post param parsing up to the user [2] which, if you're parsing post params using scala [3], should should be good to go.
As far as tomcat and other servlet containers go, *shugs*. I don't really use em.
[1]: https://github.com/eclipse/jetty.project/commit/085c79d7d6cfbccc02821ffdb64968593df3e0bf (using the same lame limitation of params) [2]: https://github.com/netty/netty/blob/master/src/main/java/io/netty/handler/codec/http/DefaultHttpMessage.java#L136-139 [3]: https://github.com/unfiltered/unfiltered/blob/master/netty/src/main/scala/bindings.scala#L33-37

This thread seems to suggest that by using Scala HashMap one is using MurmurHash3.  But in immutable/HashMap.scala I see
    protected def elemHashCode(key: A) = key.##
and in mutable/HashTable.scala which mutable.HashMap builds upon, I see
    protected def elemHashCode(key: KeyType) = key.##
So I think that in both cases, the Scala HashMap would use the Java hashing function for String keys like POST params.  It does look like one can use mutable.OpenHashMap to supply the hash function, and then hook in MurmurHash that way.  Moreover,  one could seed MurmurHash differently foreach instance of an OpenHashMap, and that's what alech and zeri were arguing for.
However, OpenHashMap is in the mutable package.  Is there a way to override the hashing mechanism for an immutable hash table?
On Fri, Dec 30, 2011 at 8:14 PM, Doug Tangren <d.tangren@gmail.com> wrote:

On Thu, Dec 29, 2011 at 2:26 PM, ejc <eric.j.christeson@gmail.com> wrote:

I might be wrong, but if the servlet container (written in Java) uses
any hashes on String, it doesn't matter what Scala, or Lift uses,
correct?

I think this is the important point. 
Fortunately, jetty is on top of it [1] and netty, out of the box, leaves post param parsing up to the user [2] which, if you're parsing post params using scala [3], should should be good to go.
As far as tomcat and other servlet containers go, *shugs*. I don't really use em.
[1]: https://github.com/eclipse/jetty.project/commit/085c79d7d6cfbccc02821ffdb64968593df3e0bf (using the same lame limitation of params) [2]: https://github.com/netty/netty/blob/master/src/main/java/io/netty/handler/codec/http/DefaultHttpMessage.java#L136-139 [3]: https://github.com/unfiltered/unfiltered/blob/master/netty/src/main/scala/bindings.scala#L33-37

On Sunday, 1 January 2012 16:23:56 UTC+1, Topher wrote:

This thread seems to suggest that by using Scala HashMap one is using MurmurHash3.  But in immutable/HashMap.scala I see
    protected def elemHashCode(key: A) = key.##
and in mutable/HashTable.scala which mutable.HashMap builds upon, I see
    protected def elemHashCode(key: KeyType) = key.##
So I think that in both cases, the Scala HashMap would use the Java hashing function for String keys like POST params.  It does look like one can use mutable.OpenHashMap to supply the hash function, and then hook in MurmurHash that way.  Moreover,  one could seed MurmurHash differently foreach instance of an OpenHashMap, and that's what alech and zeri were arguing for.

Well the opposite could also be the case. If it were using the Java Hash then it could also have just called the java hashMap method.
I am not sure where ## is defined. It is defined on Any, but that is not a class I can find from IntelliJ and according to this it is not one that is available
http://stackoverflow.com/questions/2335319/what-are-the-relationships-be...

In Martin Odersky's book "Programming in Scala" 2nd edition, it says 
"Because every class inherits from Any, every object in a Scala program can be compared using ==, !=, or equals; hashed using ## or hashCode; and formatted using toString." and "Likewise, the ## method provides a Scala version of hashing that is the same as Java’s hashCode, except for boxed numeric types, where it works consistently with ==. For in- stance new Integer(1) and new Long(1) hash the same with ## even though their Java hashCodes are different."
So it does not say anything about the hashing strings, I would guess that this is available somwhere. Perhaps if you step through some really simple code? If you do please let us know. 

Henry 

However, OpenHashMap is in the mutable package.  Is there a way to override the hashing mechanism for an immutable hash table?
On Fri, Dec 30, 2011 at 8:14 PM, Doug Tangren <d.ta...@gmail.com> wrote:

On Thu, Dec 29, 2011 at 2:26 PM, ejc <eric.j.c...@gmail.com> wrote:

I might be wrong, but if the servlet container (written in Java) uses
any hashes on String, it doesn't matter what Scala, or Lift uses,
correct?

I think this is the important point. 
Fortunately, jetty is on top of it [1] and netty, out of the box, leaves post param parsing up to the user [2] which, if you're parsing post params using scala [3], should should be good to go.
As far as tomcat and other servlet containers go, *shugs*. I don't really use em.
[1]: https://github.com/eclipse/jetty.project/commit/085c79d7d6cfbccc02821ffdb64968593df3e0bf (using the same lame limitation of params) [2]: https://github.com/netty/netty/blob/master/src/main/java/io/netty/handler/codec/http/DefaultHttpMessage.java#L136-139 [3]: https://github.com/unfiltered/unfiltered/blob/master/netty/src/main/scala/bindings.scala#L33-37

## is a special method inlined (I believe) by the compiler and used to unify hashing of boxed primitives with primitive values.

On Jan 3, 2012 5:32 AM, "bblfish" <henry.story@gmail.com> wrote:

On Sunday, 1 January 2012 16:23:56 UTC+1, Topher wrote:

This thread seems to suggest that by using Scala HashMap one is using MurmurHash3.  But in immutable/HashMap.scala I see
    protected def elemHashCode(key: A) = key.##
and in mutable/HashTable.scala which mutable.HashMap builds upon, I see
    protected def elemHashCode(key: KeyType) = key.##
So I think that in both cases, the Scala HashMap would use the Java hashing function for String keys like POST params.  It does look like one can use mutable.OpenHashMap to supply the hash function, and then hook in MurmurHash that way.  Moreover,  one could seed MurmurHash differently foreach instance of an OpenHashMap, and that's what alech and zeri were arguing for.

Well the opposite could also be the case. If it were using the Java Hash then it could also have just called the java hashMap method.
I am not sure where ## is defined. It is defined on Any, but that is not a class I can find from IntelliJ and according to this it is not one that is available
http://stackoverflow.com/questions/2335319/what-are-the-relationships-between-any-anyval-anyref-object-and-how-do-they-m

In Martin Odersky's book "Programming in Scala" 2nd edition, it says 
"Because every class inherits from Any, every object in a Scala program can be compared using ==, !=, or equals; hashed using ## or hashCode; and formatted using toString." and "Likewise, the ## method provides a Scala version of hashing that is the same as Java’s hashCode, except for boxed numeric types, where it works consistently with ==. For in- stance new Integer(1) and new Long(1) hash the same with ## even though their Java hashCodes are different."
So it does not say anything about the hashing strings, I would guess that this is available somwhere. Perhaps if you step through some really simple code? If you do please let us know. 

Henry 

However, OpenHashMap is in the mutable package.  Is there a way to override the hashing mechanism for an immutable hash table?
On Fri, Dec 30, 2011 at 8:14 PM, Doug Tangren <d.ta...@gmail.com> wrote:

On Thu, Dec 29, 2011 at 2:26 PM, ejc <eric.j.c...@gmail.com> wrote:

I might be wrong, but if the servlet container (written in Java) uses
any hashes on String, it doesn't matter what Scala, or Lift uses,
correct?

I think this is the important point. 
Fortunately, jetty is on top of it [1] and netty, out of the box, leaves post param parsing up to the user [2] which, if you're parsing post params using scala [3], should should be good to go.
As far as tomcat and other servlet containers go, *shugs*. I don't really use em.
[1]: https://github.com/eclipse/jetty.project/commit/085c79d7d6cfbccc02821ffdb64968593df3e0bf (using the same lame limitation of params) [2]: https://github.com/netty/netty/blob/master/src/main/java/io/netty/handler/codec/http/DefaultHttpMessage.java#L136-139 [3]: https://github.com/unfiltered/unfiltered/blob/master/netty/src/main/scala/bindings.scala#L33-37