[Перевод] Ломаем хэши CityHash64, MurmurHash2/3, wyhash и не только…

info@vsetut.pro

О проекте

Вернуться

22.11.2024 07:18:39 | Хабр

Хабы: Информационная безопасность, Алгоритмы, Математика, Программирование

Хэш-функции — невероятно красивые математические объекты. Они могут отображать произвольные данные на небольшую область выходных данных фиксированного размера таким образом, что отображение оказывается детерминированным, хоть и кажется случайным. Такая «детерминированная случайность» невероятно полезна для широкого спектра применений, например, для хэш-таблиц, контрольных сумм, алгоритмов Монте-Карло, распределённых алгоритмов без коммуникаций и так далее.

В этой статье мы взглянем на тёмную сторону хэш-функций: ситуации, когда всё идёт не так. К счастью, такое, по сути, в реальной жизни никогда не происходит из-за неудачных входных данных (по крайней мере, в случае хороших хэш-функций). Однако кроме программ существуют и люди, и не все из них настроены миролюбиво, поэтому нам следует обратиться за ответами к сфере компьютерной безопасности. Я вкратце объясню основы безопасности хэш-функций, а затем покажу, насколько легко поломать эту безопасность для некоторых популярных некриптографических хэш-фукнкций.

Для затравки скажу, что в этой статье объясняется, как генерировать за секунду тысячи подобных строк:

cityhash64("orlp-cityhash64-D-:K5yx*zkgaaaaa") == 1337 murmurhash2("orlp-murmurhash64-bkiaaa&JInaNcZ") == 1337 murmurhash3("orlp-murmurhash3_x86_32-haaaPa*+") == 1337 farmhash64("orlp-farmhash64-/v^CqdPvziuheaaa") == 1337

Также я покажу, как можно создавать очень специфичные пары строк, которые можно произвольно конкатенировать таким образом, что при конкатенации k строк любая из 2k комбинаций будет иметь одинаковый хэш вне зависимости от использованного для хэш-функции порождающего значения (seed):

a = "xx0rlpx!xxsXъВ" b = "xxsXъВxx0rlpx!" murmurhash2(a + a, seed) == murmurhash2(a + b, seed) murmurhash2(a + a, seed) == murmurhash2(b + a, seed) murmurhash2(a + a, seed) == murmurhash2(b + b, seed) a = "!&orlpՓ" b = "yǏglp$X" murmurhash3(a + a, seed) == murmurhash3(a + b, seed) murmurhash3(a + a, seed) == murmurhash3(b + a, seed) murmurhash3(a + a, seed) == murmurhash3(b + b, seed)

Подробнее