package jruby
tags 694694 patch
thanks
Hello,
I just commited the attached patch to the package's git. I intend to
upload the package with that correction (and maybe some other minor
ones) within the next few days unless someone objects.
I was about uploading it right away but I'm not a jruby user myself,
and I a no way of checking it beside of the included test suite (which
works exactly as well with or without this patch).
Thanks for any feedback,
Mt.
--
Comme le taupin, qui n'a cure des progrès de la technique, s'imagine
que les théories représentent la réalité, que c'est arrivé, il croit
la science boulversée par une théorie nouvelle, c'est-à-dire par un
changement de langage. -- Henri Bouasse, l'esprit Taupin, 1928.
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 <n...@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 - dmy...@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.boss...@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 (mquin...@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;
