Attachment 661686 Details for Bug 880671 – Updated version of the patch, picking the main change from upstream

[patch] Updated version of the patch, picking the main change from upstream

0009-CVE-2012-5370.patch (text/plain), 4.78 KB, created by Martin Quinson on 2012-12-11 21:07:01 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Martin Quinson

Created: 2012-12-11 21:07:01 UTC

Size: 4.78 KB

patch

obsolete

>Drop the MurmurHash to compute hashes, as it is vulnerable to a DoS:
>A specially-crafted set of keys could trigger Murmur hash function
>collisions, which degrade hash table items insert performance by
>changing hash table operations complexity from an expected/average
>O(n) to the worst case O(n^2). Reporters were able to find colliding
>strings efficiently using equivalent substrings.
>
>Use PerlHash instead, as it was done upstream (see commit
>5e4aab28b26fd127112b76fabfac9a33b64caf77 of git://jruby.org/jruby.git)
>instead of the SipHash that is used in the C implementation of Ruby,
>for performance reasons.
>
>Index: jruby/src/org/jruby/util/MurmurHash.java
>===================================================================
>--- jruby.orig/src/org/jruby/util/MurmurHash.java	2012-12-11 20:29:23.666433052 +0100
>+++ /dev/null	1970-01-01 00:00:00.000000000 +0000
>@@ -1,62 +0,0 @@
>-package org.jruby.util;
>-
>-public class MurmurHash {
>-    // Based on Murmurhash 2.0 Java port at http://dmy999.com/article/50/murmurhash-2-java-port
>-    // 2011-12-05: Modified by Hiroshi Nakamura <nahi@ruby-lang.org>
>-    // - signature change to use offset
>-    //   hash(byte[] data, int seed) to hash(byte[] src, int offset, int length, int seed)
>-    // - extract 'm' and 'r' as murmurhash2.0 constants
>-
>-    // Ported by Derek Young from the C version (specifically the endian-neutral
>-    // version) from:
>-    //   http://murmurhash.googlepages.com/
>-    //
>-    // released to the public domain - dmy999@gmail.com
>-
>-    // 'm' and 'r' are mixing constants generated offline.
>-    // They're not really 'magic', they just happen to work well.
>-    private static final int MURMUR2_MAGIC = 0x5bd1e995;
>-    // CRuby 1.9 uses 16 but original C++ implementation uses 24 with above Magic.
>-    private static final int MURMUR2_R = 24;
>-
>-    @SuppressWarnings("fallthrough")
>-    public static int hash32(byte[] src, int offset, int length, int seed) {
>-        // Initialize the hash to a 'random' value
>-        int h = seed ^ length;
>-
>-        int i = offset;
>-        int len = length;
>-        while (len >= 4) {
>-            int k = src[i + 0] & 0xFF;
>-            k |= (src[i + 1] & 0xFF) << 8;
>-            k |= (src[i + 2] & 0xFF) << 16;
>-            k |= (src[i + 3] & 0xFF) << 24;
>-
>-            k *= MURMUR2_MAGIC;
>-            k ^= k >>> MURMUR2_R;
>-            k *= MURMUR2_MAGIC;
>-
>-            h *= MURMUR2_MAGIC;
>-            h ^= k;
>-
>-            i += 4;
>-            len -= 4;
>-        }
>-
>-        switch (len) {
>-        case 3:
>-            h ^= (src[i + 2] & 0xFF) << 16;
>-        case 2:
>-            h ^= (src[i + 1] & 0xFF) << 8;
>-        case 1:
>-            h ^= (src[i + 0] & 0xFF);
>-            h *= MURMUR2_MAGIC;
>-        }
>-
>-        h ^= h >>> 13;
>-        h *= MURMUR2_MAGIC;
>-        h ^= h >>> 15;
>-
>-        return h;
>-    }
>-}
>Index: jruby/src/org/jruby/RubyString.java
>===================================================================
>--- jruby.orig/src/org/jruby/RubyString.java	2012-12-11 20:29:23.650433034 +0100
>+++ jruby/src/org/jruby/RubyString.java	2012-12-11 20:49:48.895686092 +0100
>@@ -91,7 +91,7 @@
> import org.jruby.runtime.marshal.UnmarshalStream;
> import org.jruby.util.ByteList;
> import org.jruby.util.ConvertBytes;
>-import org.jruby.util.MurmurHash;
>+import org.jruby.util.PerlHash;
> import org.jruby.util.Numeric;
> import org.jruby.util.Pack;
> import org.jruby.util.Sprintf;
>@@ -1025,7 +1025,7 @@
>     }
> 
>     private int strHashCode(Ruby runtime) {
>-        int hash = MurmurHash.hash32(value.getUnsafeBytes(), value.getBegin(), value.getRealSize(), runtime.getHashSeed());
>+        int hash = PerlHash.hash32(runtime.getHashSeed(), value.getUnsafeBytes(), value.getBegin(), value.getRealSize());
>         if (runtime.is1_9()) {
>             hash ^= (value.getEncoding().isAsciiCompatible() && scanForCodeRange() == CR_7BIT ? 0 : value.getEncoding().getIndex());
>         }
>Index: jruby/src/org/jruby/util/PerlHash.java
>===================================================================
>--- /dev/null	1970-01-01 00:00:00.000000000 +0000
>+++ jruby/src/org/jruby/util/PerlHash.java	2012-12-11 20:42:32.429215037 +0100
>@@ -0,0 +1,24 @@
>+package org.jruby.util;
>+
>+/**
>+ * Perl's Hash implementation.
>+ *
>+ * @author nahi@ruby-lang.org
>+ */
>+public class PerlHash {
>+    public static long hash64(long key, byte[] src, int offset, int length) {
>+        for (int idx = 0; idx < length; ++idx) {
>+            key += (src[offset + idx] & 0xFF);
>+            key += (key << 10);
>+            key ^= (key >>> 6);
>+        }
>+        key += (key << 3);
>+        key ^= (key >>> 11);
>+        key += (key << 15);
>+        return key;
>+    }
>+    public static int hash32(long key, byte[] src, int offset, int length) {
>+        long res = hash64(key,src,offset,length);
>+        return ((int) (res & 0xFFFFFFFF)) ^ ((int) (res >>> 32));
>+    }
>+}

Actions: View | Diff

Attachments on bug 880671: 661196 | 661686