Вот никогда не любил хеш-таблицы.

[thesz]

Вот тут рассказывают, что для торчащих наружу API можно организовать DOS с помощью провоцирования вычисления одинаковых криптосумм.

Утащено с этой странички, где есть статья про короткий хэш и ещё слайды.

Comments

[worm_ii]

Как, оказывается, много слайдов нужно, чтобы сообщить, что от атак защищают алгоритмы, работающие оптимально в худшем случае.

[metaclass]

Уже починили везде, добавив рандомную соль к вычислению хэша.
В смысле при старте инстанса системы однократно считается случайное число и используется для расчета хэшей, делая их непредсказуемыми (между разными запусками)

[helvegr]

Уже есть атаки, которые позволяют сгенерировать большое число коллизий даже без знания соли.

http://www.serpentine.com/blog/2012/12/13/a-major-new-release-of-the-haskell-hashable-library/

Собственно, SipHash (про который в слайдах) как раз и разработан в ответ на такие атаки.

[wizzard0]

А я не люблю бинарные деревья, их балансировать надо. Особенно весело, когда это в потрохах какой-то либы происходит, как в описанном по ссылке случае.

Квиксорт так вообще умеет вырождаться в О(n^2).

А то, что по ссылке - уже везде запатчили.

Короче, наброс не удался имхо ;)

[thesz]

>А я не люблю бинарные деревья, их балансировать надо

Patricia tree, как в IntMap/IntSet, балансировать не надо.

>А то, что по ссылке - уже везде запатчили.

Я попал на ту ссылку из обсуждения уязвимости brtfs, в которой возникал бесконечный цикл.

Я не набрасывал, а делился обнаруженным.

[wizzard0]

> Patricia tree

Я тоже люблю сабж. Но увы не раз натыкался на бинарные деревья глубоко в потрохах, втч в closed-source вещах. В которые вставляешь записи с таймстампом, а оно оп - и вырождается в список :/

> Я не набрасывал, а делился обнаруженным.

Ок, сорри тогда.