From: nobu@...
Date: 2016-12-04T02:45:38+00:00
Subject: [ruby-core:78482] [Ruby trunk Bug#13002] Hash calculations no longer using universal hashing
Issue #13002 has been updated by Nobuyoshi Nakada.
Vladimir Makarov wrote:
> Instead of using siphash (a secure hash function) all the time, the new hash tables use faster hash functions and when they recognize an ongoing denial attack, they are **rebuilt and switches to secure hash function** (the same siphash). One table can use a secure hash when another one can still use faster hash functions.
That means the hash function must be stronger when `strong_p`, doesn't it?
`Integer#hash` calls `rb_any_hash`, not `rb_any_hash_weak`, so its result should be strong but it isn't now.
```diff
diff --git c/hash.c w/hash.c
index b4c74ed..a5f660e 100644
--- c/hash.c
+++ w/hash.c
@@ -147,24 +147,19 @@ long rb_objid_hash(st_index_t index);
long
-rb_dbl_long_hash(double d)
+rb_dbl_long_hash(double d, int strong_p)
{
+ union {double d; st_index_t i;} u;
+ st_index_t hnum;
/* normalize -0.0 to 0.0 */
if (d == 0.0) d = 0.0;
-#if SIZEOF_INT == SIZEOF_VOIDP
- return rb_memhash(&d, sizeof(d));
-#else
- {
- union {double d; uint64_t i;} u;
-
- u.d = d;
- return rb_objid_hash(u.i);
- }
-#endif
+ u.d = d;
+ hnum = strong_p ? rb_hash_start(u.i) : u.i;
+ return rb_objid_hash(hnum);
}
#if SIZEOF_INT == SIZEOF_VOIDP
-static const st_index_t str_seed = 0xfa835867;
+# define str_seed rb_hash_start(0xfa835867)
#else
-static const st_index_t str_seed = 0xc42b5e2e6480b23bULL;
+# define str_seed rb_hash_start(0xc42b5e2e6480b23bULL)
#endif
@@ -184,4 +180,5 @@ any_hash_general(VALUE a, int strong_p, st_index_t (*other_func)(VALUE))
goto flt;
}
+ if (strong_p) a = rb_hash_start(a);
hnum = rb_objid_hash((st_index_t)a);
}
@@ -200,5 +197,5 @@ any_hash_general(VALUE a, int strong_p, st_index_t (*other_func)(VALUE))
else if (BUILTIN_TYPE(a) == T_FLOAT) {
flt:
- hnum = rb_dbl_long_hash(rb_float_value(a));
+ hnum = rb_dbl_long_hash(rb_float_value(a), strong_p);
}
else {
diff --git c/internal.h w/internal.h
index 3a4fbd5..8f04165 100644
--- c/internal.h
+++ w/internal.h
@@ -1086,5 +1086,5 @@ VALUE rb_hash_default_value(VALUE hash, VALUE key);
VALUE rb_hash_set_default_proc(VALUE hash, VALUE proc);
long rb_objid_hash(st_index_t index);
-long rb_dbl_long_hash(double d);
+long rb_dbl_long_hash(double d, int strong_p);
st_table *rb_init_identtable(void);
st_table *rb_init_identtable_with_size(st_index_t size);
diff --git c/numeric.c w/numeric.c
index d2c9cf7..c4af7f1 100644
--- c/numeric.c
+++ w/numeric.c
@@ -1454,5 +1454,5 @@ VALUE
rb_dbl_hash(double d)
{
- return LONG2FIX(rb_dbl_long_hash (d));
+ return LONG2FIX(rb_dbl_long_hash(d, TRUE));
}
diff --git c/test/ruby/test_rand.rb w/test/ruby/test_rand.rb
index 46d10f8..4d2805b 100644
--- c/test/ruby/test_rand.rb
+++ w/test/ruby/test_rand.rb
@@ -570,3 +570,35 @@
assert_operator(size.fdiv(n), :>, 15)
end
+
+ def assert_hash_random(obj, dump = obj.inspect)
+ a = [obj.hash.to_s]
+ 3.times {
+ assert_in_out_err(["-e", "print #{dump}.hash"], "") do |r, e|
+ a += r
+ assert_equal([], e)
+ end
+ }
+ assert_not_equal([obj.hash.to_s], a.uniq)
+ assert_operator(a.uniq.size, :>, 2, proc {a.inspect})
+ end
+
+ def test_str_hash
+ assert_hash_random('abc')
+ end
+
+ def test_int_hash
+ assert_hash_random(0)
+ assert_hash_random(+1)
+ assert_hash_random(-1)
+ assert_hash_random(+(1<<100))
+ assert_hash_random(-(1<<100))
+ end
+
+ def test_float_hash
+ assert_hash_random(0.0)
+ assert_hash_random(+1.0)
+ assert_hash_random(-1.0)
+ assert_hash_random(1.72723e-77)
+ assert_hash_random(Float::INFINITY, "Float::INFINITY")
+ end
end
diff --git c/test/ruby/test_string.rb w/test/ruby/test_string.rb
index 7ee7fa7..2bd35b1 100644
--- c/test/ruby/test_string.rb
+++ w/test/ruby/test_string.rb
@@ -980,16 +980,4 @@
end
- def test_hash_random
- str = 'abc'
- a = [str.hash.to_s]
- 3.times {
- assert_in_out_err(["-e", "print #{str.dump}.hash"], "") do |r, e|
- a += r
- assert_equal([], e)
- end
- }
- assert_not_equal([str.hash.to_s], a.uniq)
- end
-
def test_hex
assert_equal(255, S("0xff").hex)
```
----------------------------------------
Bug #13002: Hash calculations no longer using universal hashing
https://bugs.ruby-lang.org/issues/13002#change-61860
* Author: Martin D��rst
* Status: Open
* Priority: Normal
* Assignee:
* ruby -v:
* Backport: 2.1: DONTNEED, 2.2: DONTNEED, 2.3: DONTNEED
----------------------------------------
When preparing for my lecture on hash tables last week, I found that Ruby trunk doesn't do universal hashing anymore. See http://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf for background.
I contacted security@ruby-lang.org, but was told by Shugo that because trunk is not a published version, we can talk about it publicly.
Shugo also said that the change was introduced in r56650.
Following is some output from two different versions of Ruby that show the problem:
On Ruby 2.2.3, different hash value for the same number every time Ruby is restarted:
C:\Users\duerst>ruby -v
ruby 2.2.3p173 (2015-08-18 revision 51636) [i386-mingw32]
C:\Users\duerst>ruby -e 'puts 12345678.hash'
611647260
C:\Users\duerst>ruby -e 'puts 12345678.hash'
-844752827
C:\Users\duerst>ruby -e 'puts 12345678.hash'
387106497
On Ruby trunk, always the same value:
duerst@Arnisee /cygdrive/c/Data/ruby
$ ruby -v
ruby 2.4.0dev (2016-12-02 trunk 56965) [x86_64-cygwin]
duerst@Arnisee /cygdrive/c/Data/ruby
$ ruby -e 'puts 12345678.hash'
1846311797112760547
duerst@Arnisee /cygdrive/c/Data/ruby
$ ruby -e 'puts 12345678.hash'
1846311797112760547
duerst@Arnisee /cygdrive/c/Data/ruby
$ ruby -e 'puts 12345678.hash'
1846311797112760547
--
https://bugs.ruby-lang.org/
Unsubscribe: <mailto:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>