-----Messaggio originale-----
Inviato: mercoledì 28 dicembre 2011 14:33
Hash 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@nruns.com> and Julian
Waelde <jwaelde@cdc.informatik.tu-darmstadt.de> for reporting this
issue.
···
Da: Urabe Shyouhei [mailto:shyouhei@ruby-lang.org]
A: ruby-talk ML; ruby-list@ruby-lang.org
Oggetto: [ANN] CVE-2011-4815: Denial of service attack was found for Ruby's
--
Caselle da 1GB, trasmetti allegati fino a 3GB e in piu' IMAP, POP3 e SMTP autenticato? GRATIS solo con Email.it http://www.email.it/f
Sponsor:
Riccione Hotel 3 stelle in centro: Pacchetto Capodanno mezza pensione, animazione bimbi, zona relax, parcheggio. Scopri l'offerta solo per oggi...
Clicca qui: http://adv.email.it/cgi-bin/foclick.cgi?mid983&d)-12