Attachment 661196 Details for Bug 880671 – patch to the issue

[patch] patch to the issue

0009-CVE-2012-5370.patch (text/plain), 11.08 KB, created by Martin Quinson on 2012-12-10 23:50:35 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Martin Quinson

Created: 2012-12-10 23:50:35 UTC

Size: 11.08 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 SipHash instead, as it was done in the C implementation of Ruby.
>
>Index: jruby-1.5.6/src/org/jruby/util/MurmurHash.java
>===================================================================
>--- jruby-1.5.6.orig/src/org/jruby/util/MurmurHash.java	2012-12-10 23:38:21.827577622 +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-1.5.6/src/org/jruby/RubyString.java
>===================================================================
>--- jruby-1.5.6.orig/src/org/jruby/RubyString.java	2012-12-10 23:38:21.827577622 +0100
>+++ jruby-1.5.6/src/org/jruby/RubyString.java	2012-12-10 23:43:27.737909143 +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.SipHash;
> 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 = SipHash.hash32(value.getUnsafeBytes(), value.getBegin(), value.getRealSize(), runtime.getHashSeed());
>         if (runtime.is1_9()) {
>             hash ^= (value.getEncoding().isAsciiCompatible() && scanForCodeRange() == CR_7BIT ? 0 : value.getEncoding().getIndex());
>         }
>Index: jruby-1.5.6/src/org/jruby/util/SipHash.java
>===================================================================
>--- /dev/null	1970-01-01 00:00:00.000000000 +0000
>+++ jruby-1.5.6/src/org/jruby/util/SipHash.java	2012-12-10 23:51:14.867456445 +0100
>@@ -0,0 +1,190 @@
>+package org.jruby.util;
>+
>+/**
>+ * Original author: <a href="mailto:Martin.Bosslet@googlemail.com">Martin Bosslet</a>
>+ * Original license: 
>+ *   Copyright (c) 2012 Martin BoÃlet
>+ *   
>+ *   Permission is hereby granted, free of charge, to any person obtaining
>+ *   a copy of this software and associated documentation files (the
>+ *   "Software"), to deal in the Software without restriction, including
>+ *   without limitation the rights to use, copy, modify, merge, publish,
>+ *   distribute, sublicense, and/or sell copies of the Software, and to
>+ *   permit persons to whom the Software is furnished to do so, subject to
>+ *   the following conditions:
>+ *   
>+ *   The above copyright notice and this permission notice shall be
>+ *   included in all copies or substantial portions of the Software.
>+ *   
>+ *   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
>+ *   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
>+ *   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
>+ *   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
>+ *   LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
>+ *   OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
>+ *   WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
>+ *   
>+ * Adapted by Martin Quinson (mquinson@debian.org) to accept the hash32 prototype that is used in jruby.
>+ *   (same license applies)
>+ * 
>+ */
>+public class SipHash {
>+    public static int hash32(byte[] src, int offset, int length, byte[] seed) {
>+        long m;
>+        State s = new State(new SipKey(seed));
>+        int iter = length / 8;
>+        
>+        for(int i=0; i < iter; i++) {
>+            m = UnsignedInt64.binToIntOffset(src, (i * 8) + offset);
>+            s.processBlock(m);
>+        }
>+        
>+        m = lastBlock(src, offset, length, iter);
>+        s.processBlock(m);
>+        s.finish();
>+        return s.digest32();
>+        
>+    }
>+    
>+    private static long lastBlock(byte[] data, int offset, int length, int iter) {
>+        long last = ((long) length) << 56;
>+        int off = iter * 8+offset;
>+
>+        switch (length % 8) {
>+            case 7: 
>+                last |= ((long) data[off + 6]) << 48;
>+            case 6:
>+                last |= ((long) data[off + 5]) << 40;
>+            case 5:
>+                last |= ((long) data[off + 4]) << 32;
>+            case 4:
>+                last |= ((long) data[off + 3]) << 24;
>+            case 3:
>+                last |= ((long) data[off + 2]) << 16;
>+            case 2:
>+                last |= ((long) data[off + 1]) << 8;
>+            case 1:
>+                last |= (long) data[off];
>+                break;
>+            case 0:
>+                break;
>+        }
>+        return last;
>+    }
>+    
>+    private static class State {
>+        private long v0;
>+        private long v1;
>+        private long v2;
>+        private long v3;
>+        
>+        public State(SipKey key) {
>+            v0 = 0x736f6d6570736575L;
>+            v1 = 0x646f72616e646f6dL;
>+            v2 = 0x6c7967656e657261L;
>+            v3 = 0x7465646279746573L;
>+            
>+            long k0 = key.getLeftHalf();
>+            long k1 = key.getRightHalf();
>+            
>+            v0 ^= k0;
>+            v1 ^= k1;
>+            v2 ^= k0;
>+            v3 ^= k1;
>+        }
>+
>+        private void compress() {
>+            v0 += v1;
>+            v2 += v3;
>+            v1 = UnsignedInt64.rotateLeft(v1, 13);
>+            v3 = UnsignedInt64.rotateLeft(v3, 16);
>+            v1 ^= v0;
>+            v3 ^= v2;
>+            v0 = UnsignedInt64.rotateLeft(v0, 32);
>+            v2 += v1;
>+            v0 += v3;
>+            v1 = UnsignedInt64.rotateLeft(v1, 17);
>+            v3 = UnsignedInt64.rotateLeft(v3, 21);
>+            v1 ^= v2;
>+            v3 ^= v0;
>+            v2 = UnsignedInt64.rotateLeft(v2, 32);
>+        }
>+        
>+        private void compressTimes(int times) {
>+            for (int i=0; i < times; i++) {
>+                compress();
>+            }
>+        }
>+        
>+        public void processBlock(long m) {
>+            v3 ^= m;
>+            compressTimes(2);
>+            v0 ^= m;
>+        }
>+        
>+        public void finish() {
>+            v2 ^= 0xff;
>+            compressTimes(4);
>+        }
>+        
>+        public long digest() {
>+            return v0 ^ v1 ^ v2 ^ v3;
>+        }
>+        public int digest32() {
>+            long res = digest();
>+            return ((int) (res & 0xFFFFFFFF)) ^ ((int) (res >>> 32));
>+        }
>+    }   
>+}
>+
>+class SipKey {
>+    private final byte[] key;
>+    
>+    public SipKey(byte[] key) {
>+        if (key == null || key.length != 16)
>+            throw new RuntimeException("SipHash key must be 16 bytes");
>+        this.key = key;
>+    }
>+    
>+    long getLeftHalf() {
>+       return UnsignedInt64.binToIntOffset(key, 0); 
>+    }
>+    
>+    long getRightHalf() {
>+        return UnsignedInt64.binToIntOffset(key, 8); 
>+    }
>+}
>+
>+class UnsignedInt64 {
>+    private UnsignedInt64() {}
>+    
>+    public static long binToInt(byte[] b) {
>+        return  binToIntOffset(b, 0);
>+    }
>+    
>+    public static long binToIntOffset(byte[] b, int off) {
>+        return ((long) b[off    ])       |
>+               ((long) b[off + 1]) << 8  |
>+               ((long) b[off + 2]) << 16 |
>+               ((long) b[off + 3]) << 24 |
>+               ((long) b[off + 4]) << 32 |
>+               ((long) b[off + 5]) << 40 |
>+               ((long) b[off + 6]) << 48 |
>+               ((long) b[off + 7]) << 56;
>+    }
>+    
>+    public static void intToBin(long l, byte[] b) {
>+        b[0] = (byte) ( l         & 0xff);
>+        b[1] = (byte) ((l >>> 8 ) & 0xff);
>+        b[2] = (byte) ((l >>> 16) & 0xff);
>+        b[3] = (byte) ((l >>> 24) & 0xff);
>+        b[4] = (byte) ((l >>> 32) & 0xff);
>+        b[5] = (byte) ((l >>> 40) & 0xff);
>+        b[6] = (byte) ((l >>> 48) & 0xff);
>+        b[7] = (byte) ((l >>> 56) & 0xff);
>+    }
>+    
>+    public static long rotateLeft(long l, int shift) {
>+        return (l << shift) | l >>> (64 - shift);
>+    }
>+}
>Index: jruby-1.5.6/src/org/jruby/Ruby.java
>===================================================================
>--- jruby-1.5.6.orig/src/org/jruby/Ruby.java	2012-12-10 23:38:21.827577622 +0100
>+++ jruby-1.5.6/src/org/jruby/Ruby.java	2012-12-10 23:43:28.377922386 +0100
>@@ -270,7 +270,8 @@
>         this.jitCompiler        = new JITCompiler(this);
>         this.parserStats        = new ParserStats(this);
> 
>-	this.hashSeed = this.random.nextInt();
>+	this.hashSeed = new byte[16];
>+	this.random.nextBytes(hashSeed);
>         
>         this.beanManager.register(new Config(this));
>         this.beanManager.register(parserStats);
>@@ -3707,7 +3708,7 @@
>         return jittedMethods;
>     }
> 
>-    public int getHashSeed() {
>+    public byte[] getHashSeed() {
>         return hashSeed;
>     }
>     
>@@ -3815,7 +3816,7 @@
>     private long randomSeedSequence = 0;
>     private Random random = new Random();
>     /** The runtime-local seed for hash randomization */
>-    private int hashSeed = 0;
>+    private byte[] hashSeed;
> 
>     private final List<EventHook> eventHooks = new Vector<EventHook>();
>     private boolean hasEventHooks;

Actions: View | Diff

Attachments on bug 880671: 661196 | 661686