Исходное сообщение
"DoS атака против файловой системы Btrfs" Отправлено Аноним, 13-Дек-12 23:46
> По ссылке не ходил статью не читал? Не только читал, но и в курсе как хэш таблицы делают. Понимаете ли, для хэш-таблиц сроду не использовали криптографически стойкие функции. Потому что они медленные. Коллизии для хэш-таблиц - нормальное явление. Это как правило не просто допустимо, но и явно обрабатывается. Так что путем того или иного костылинга таблица в результате помнит обе конфликтующие записи и может достать и ту и другую. В общем случае это не создает никаких проблем. Главное чтобы процент коллизий был небольшой. Большой процент коллизий говорит о том что разрядность хэша мала относительно числа элементов и таблица работает неэффективно (приходится смотреть по нескольку записей с одним и тем же хэшом чтобы понять какая из них нужна). Но это не является чем-то совершенно недопустимым. Но как оказалось, при должной изобретательности можно глушить коллизиями прицельно. Спровоцировав очень много коллизий. В этом случае хэш-таблица завалится в дуpной режим, когда она вместо быстрого лукапа по индексу начинает разгрeбать немеряную цепочку коллизий. Большинство алгоритмов хэш-таблиц вообще никогда не дизайнилось с прицелом на учет такой подставы. И на практике такие атаки появились лишь сравнительно недавно.