From: eregontp@gmail.com
To: ruby-core@ruby-lang.org
Subject: [ruby-core:82089] [Ruby trunk Bug#13660] rb_str_hash_m discards bits from the hash
Date: Mon, 17 Jul 2017 16:11:58 +0000 (UTC) [thread overview]
Message-ID: <redmine.journal-65820.20170717161146.6dd617752fad24df@ruby-lang.org> (raw)
In-Reply-To: redmine.issue-13660.20170614215607@ruby-lang.org
Issue #13660 has been updated by Eregon (Benoit Daloze).
I think the case where half the bits are lost could become a potential security issue.
Essentially all strings which have the same first half will collide in a Hash, and that's likely trivial to generate
(the same prefix/suffix of the right length is likely to generate the same half).
In that case (sizeof(long) < sizeof(void*)), I think at least the two parts should be combined with something like (long)(value ^ (value >> 32)).
But I am not a security expert.
----------------------------------------
Bug #13660: rb_str_hash_m discards bits from the hash
https://bugs.ruby-lang.org/issues/13660#change-65820
* Author: Eregon (Benoit Daloze)
* Status: Open
* Priority: Normal
* Assignee:
* Target version:
* ruby -v: ruby 2.3.3p222 (2016-11-21 revision 56859) [x64-mingw32]
* Backport: 2.2: UNKNOWN, 2.3: UNKNOWN, 2.4: UNKNOWN
----------------------------------------
I believe rb_str_hash_m might discard some bits from the hash value in some situations.
It computes the hash as a st_index_t, which is either a unsigned long or a unsigned long long.
But the st_index_t value is converted to a VALUE with:
#define ST2FIX(h) LONG2FIX((long)(h))
Note that for instance on x64-mingw32, SIZEOF_LONG is 4, but SIZEOF_LONG_LONG and SIZEOF_VOIDP are 8 bytes.
So that truncates half the bits of the hash on such a platform if my understanding is correct.
Even is SIZEOF_LONG is 8, LONG2FIX loses the MSB I think, given that not all long can fit the Fixnum range on MRI (should it be LONG2NUM?).
Also, I am not sure if it is intended to cast from a unsigned value to a signed value.
I tried many things while debugging the rb_str_hash spec on ruby/spec and eventually gave up.
This computation looks wrong to me in MRI.
For info, here is my debug code:
https://github.com/eregon/rubyspec/blob/d62189450c0a56bfcd379e5e505ad097892d2bc7/optional/capi/string_spec.rb#L501-L518
https://github.com/eregon/rubyspec/blob/d62189450c0a56bfcd379e5e505ad097892d2bc7/optional/capi/ext/string_spec.c#L361-L381
and the build result on AppVeyor:
https://ci.appveyor.com/project/eregon/spec-x948i/build/629
--
https://bugs.ruby-lang.org/
prev parent reply other threads:[~2017-07-17 16:12 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <redmine.issue-13660.20170614215607@ruby-lang.org>
2017-06-14 21:56 ` [ruby-core:81681] [Ruby trunk Bug#13660] rb_str_hash_m discards bits from the hash eregontp
2017-06-14 21:58 ` [ruby-core:81682] " eregontp
2017-06-15 5:13 ` [ruby-core:81688] " duerst
2017-07-15 2:22 ` [ruby-core:82071] " shyouhei
2017-07-17 16:11 ` eregontp [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-list from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.ruby-lang.org/en/community/mailing-lists/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=redmine.journal-65820.20170717161146.6dd617752fad24df@ruby-lang.org \
--to=ruby-core@ruby-lang.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).