Виявлено атаку відмови в обслуговуванні для алгоритму Hash Ruby (CVE-2011-4815)

Опублікував Urabe Shyouhei 28-12-2011
Переклав: Andrii Furmanets

Вплив

Це щось пов’язане з обчислювальною складністю. Виявлено спеціально сконструйовану серію рядків, які навмисно зіштовхують їхні значення хешу один з одним. З такими послідовностями зловмисник може здійснити атаку відмови в обслуговуванні, наприклад, надаючи їх як POST параметри HTTP запитів для вашого додатка Rails.

Детальний опис

Ситуація схожа на ту, що знайдено для Perl в 2003 році. У серії 1.8 Ruby ми використовуємо детерміновану хеш-функцію для хешування рядка. Тут “детермінована” означає, що жодні інші біти інформації, крім самого вхідного рядка, не залучені для генерації значення хешу. Тому ви можете заздалегідь обчислити значення хешу рядка. Збираючи серію рядків, які мають ідентичне значення хешу, зловмисник може змусити ruby обробляти зіткнення бінів хеш-таблиць (включаючи екземпляри класу Hash). Амортизована властивість O(1) хеш-таблиць залежить від рівномірності розподілу значень хешу. Надаючи такий сконструйований вхід, зловмисник може змусити хеш-таблиці працювати набагато повільніше, ніж очікується (а саме O(n²) для побудови таблиці з n елементами в цьому випадку).

Зачеплені версії

• Ruby 1.8.7-p352 та всі попередні версії.

Всі серії Ruby 1.9 не зачеплені цим видом атаки. Вони не поділяють реалізації хешу з серією Ruby 1.8.

Рішення

Наше рішення - перемішати хеш-функцію рядка деякими бітами, згенерованими PRNG. Роблячи це, значення хешу рядка більше не детерміноване. Тобто, результат String#hash узгоджений лише для поточного життєвого циклу процесу та згенерує інше число для наступного завантаження. Щоб зламати цю ситуацію, зловмисник повинен створити набір рядків, які стійкі до цього виду перемішування. Вважається, що це досить важко.

Будь ласка, оновіться до ruby 1.8.7-p357.

Примітки

• Майте на увазі, що рішення не означає, що наш алгоритм хешування криптографічно безпечний. Простіше кажучи, ми виправили хеш-таблицю, але ми не виправили слабкість String#hash. Зловмисник все ще міг би експлуатувати її, як тільки він/вона отримав пару рядка та його значення хешу, повернутого з String#hash. Ви не повинні розкривати виходи String#hash. Якщо вам потрібно робити такі речі, розгляньте використання безпечних алгоритмів хешування замість цього. Деякі з них (такі як SHA256) надаються в стандартній бібліотеці Ruby.

• Для тих, хто знає альтернативні алгоритми хешування всередині нашої кодової бази: ми не підтримуємо їх (вони вимкнені за замовчуванням). Вибираючи їх, ми вважаємо, що ви можете читати C, і ви можете зрозуміти, що було не так з тим, що за замовчуванням. Переконайтеся, що ваш вибір безпечний на ваш власний ризик.

Подяка

Подяка Alexander Klink alexander.klink@nruns.com та Julian Waelde jwaelde@cdc.informatik.tu-darmstadt.de за повідомлення про цю проблему.

РЕДАГУВАННЯ деякі пов’язані посилання:

• CVE-2011-4815 призначено для цієї проблеми.
• oCERT.org опублікував консультацію про це.
• JRuby випустив версію 1.6.5.1 для виправлення ідентичної проблеми. Інші альтернативи ruby також можуть страждати.
• Обліковий запис Twitter @hashDoS збирає інформацію про атаки зіткнення хешу.