2011年12月28日

[ruby-list:48584] [ANN] CVE-2011-4815: Denial of service attack was found for Ruby'sHash algorithm

Subject:

Denial of service attack was found for Ruby's Hash algorithm

Impact:

This is something related to computational complexity. Specially
crafted series of strings that intentionally collide their hash values

each other was found. With such sequences an attacker can issue a
denial of service attack by, for instance, giving them as POST
parameters of HTTP requests for your Rails application.

Detailed description:

The situation is similar to the one found for Perl in 2003. In 1.8
series of Ruby, we use a deterministic hash function to hash a string.
Here the "deterministic" means no other bits of information than the
input string itself is involved to generate a hash value. So you can
precalculate a string's hash value beforehand. By collecting a series
of strings that have the identical hash value, an attacker can let
ruby process collide bins of hash tables (including `Hash` class
instances). Hash tables' amortized O(1) attribute depends on
uniformity of distribution of hash values. By giving such crafted
input, an attacker can let hash tables work much slower than expected
(namely O(n2) to construct a n-elements table this case).

Affected versions:

- Ruby 1.8.7-p352 and all prior versions.

All Ruby 1.9 series are not affected by this kind of attack. They do
not share hash implementations with Ruby 1.8 series.

Solution:

Our solution is to scramble the string hash function by some
PRNG-generated random bits. By doing so a string's hashed value is no
longer deterministic. That is, a `String#hash` result is consistent
only for current process lifetime and will generate a different number
for the next boot. To break this situation an attacker must create a
set of strings which are robust to this kind of scrambling. This is
believed to be quite difficult.

Please upgrade to the latest version of ruby via my previous post.

http://mla.n-z.jp/?ruby-talk=391606

Notes:

* Bear in mind that the solution _does_ _not_ _mean_ our hash
algorithm is cryptographically secure. To put it simple, we fixed
the hash table but we didn't fix `String#hash` weakness. An
attacker could still exploit it once he / she got a pair of a string
and its hash value returned from `String#hash`. You _must_ _not_
disclose `String#hash` outputs. If you need to do such things,
consider using secure hash algorithms instead. Some of them (such
as SHA256) are provided in Ruby's standard library.

* For those who knows alternative hash algorithms inside our code
base: we do not support them (they are disabled by default). By
choosing them we consider you can read C, and you can understand
what was wrong with the default one. Make sure that your choice is
safe at your own risk.

Credit:

Credit to Alexander Klink <alexander.klink@xxxxx> and Julian
Waelde <jwaelde@xxxxx> for reporting this
issue.


投稿者 xml-rpc : 2011年12月28日 22:33
役に立ちました?:
過去のフィードバック 平均:(0) 総合:(0) 投票回数:(0)
本記事へのTrackback: http://hoop.euqset.org/blog/mt-tb2006.cgi/107751
トラックバック
コメント
コメントする




画像の中に見える文字を入力してください。