Ломаем хэши CityHash64, MurmurHash2/3, wyhash и не только…

[titbit]

Вроде CityHash64, MurmurHash2/3, wyhash не являются криптографическими хэшами, а значит имеют меньшую стойкость к атакам на коллизии. Поэтому в принципе неудивительно, что такие атаки стали возможны. Но ведь и смысл этих хэшей в их быстроте и простоте реализации, если коллизии могут стать проблемой надо использовать криптографические типа sha256/512, sha3, и других.

[Serge3leo]

Собственно, статья об этом. Что если используете данные из канала для хэширования таблиц и БД, то случайная соль или, типа того - полезный ингредиент.

Как бы, с примерами, что это не Бог весть как сложно, а как два байта переслать.

[webhamster]

Так я не понял, в чем проблема слабых хешей в libstdc++ и в прочих языках? То что можно создать набор данных, которые будут вызывать постоянное перехеширование, и тем самым замедлить работу некоего сервиса?

[Sulerad]

Да. Привычный hashmap внезапно превращается из замечательной коллекции с O(1) доступом в O(N). Это запросто приводит к O(N^2) от входных данных (контроллируемых злоумышленником) и резко усиливает эффективность атаки. Например, представьте что вам приходит массив некоторых сущностей и вы всегда проверяете, что у них всех различный ID.

Более того, в случае хэшмапы нельзя использовать криптографические функции, иначе ваш сервис ляжет и без зловредной нагрузки =)