- PVSM.RU - https://www.pvsm.ru -
Некриптографические хеш-функции применяются там, где важна скорость и не так важна возможность атаки на характеристики функции. Последнее время активно обсуждается атака на алгоритмическую сложность хеш-таблиц, которая может привести к DoS. Мы рассмотрим современные некриптографические хеш-функции, их свойства, и возможные методы защиты от атаки на хеш-таблицы.
Если криптографические хеш-функции у всех на слуху, то про некриптографические (хеш-функции общего назначения) известно мало. Некриптографические функции применяются там, где на данные не воздействуют третьи лица (злоумышленник). Например, такие функции могут использоваться для построения хеш-таблиц.
Критерии, которые важны для некриптографических хеш-функций:
Поскольку обычно пространство входных значений больше пространства выходных значений, то коллизии неизбежны. У идеальной функции выходные значения имеют равномерное распределение, поэтому вероятность коллизий минимальная. Это можно проверить хи-квадрат тестом (χ²).
2003 год. Скорость: 4.5 циклов на байт.
Очень простая функция [1] (RFC [5]).
1. Равномерное распределение: плохое, может использоваться до 14 бит для хеш-таблицы (до 214 слотов хеш-таблицы). Чуть-чуть лучше в вариации FNV-1a, которая рекомендуется по умолчанию.
2. Лавинный критерий: плохо. Также плохо и в FNV-1a.
Оба критерия значительно улучшены в модифицированном FNV-1a [2], где к FNV-1a добавлены перемешивания в конце.
2006 год, длина 32 и 64 бита, 32-битные инструкции, скорость: 2.62 цикла на байт (для сообщений длиной 16 байт).
1. Равномерное распределение: отличное для всех бит.
2. Лавинный критерий: хорошо. Есть небольшая проблема с верхними битами.
Первый вариант функции назывался One-at-a-Time.
1975 год, длина: 32, 64 и 128 бит, скорость: 1.2–0.13 цикла на байт (для сообщений короче 64 бит, в зависимости от CPU).
1. Равномерное распределение: плохое распределение нижних бит. Используйте верхние биты для хеш-таблицы, тогда можно использовать все протестированные биты — до 16 верхних бит (до 216 слотов хеш-таблицы).
2. Лавинный критерий: очень плохо. Лавинный эффект отсутствует. Сказывается назначение хеша: его выходные биты спроектированы так, чтобы обнаруживать ошибки в канале передачи данных. Также, у CRC есть важное свойство: можно разбить сообщение на части, посчитать хеш для каждой части, потом объединить сообщение, и посчитать хеш всего сообщения из хешей его частей.
2008 год, длина 32 и 64 бита, 32 и 64-битные инструкции.
Есть проблема с равномерностью распределения некоторых ключей [3].
2011 год, длина 32 и 128 бит, 32 и 64-битные инструкции, скорость: 1.87 циклов на байт (для сообщений длиной 16 байт).
1. Равномерное распределение: хорошее (в одном случае из трёх «почти подозрительное»).
2. Лавинный критерий: отлично.
2011 год, длина 32, 64, 128 и 256 бит, 64-битные инструкции. Достаточно сложная функция.
Для самого быстрого варианта нужны CRC32 инструкции процессора (SSE 4.2 — Intel Nehalem).
1. Равномерное распределение: хорошее (в одном случае из трёх «почти подозрительное»).
2. Лавинный критерий: хорошо. Есть небольшая проблема с нижними битами.
2011 год, длина 32, 64 и 128 бит, скорость: 0.33 цикла на байт. Автор Bob Jenkins.
1. Равномерное распределение: среднее (в одном случае из трёх «подозрительное»).
2. Лавинный критерий: отлично.
Статистический анализ хеш-функций можно сделать при помощи инструментов [17], использовались результаты анализа [2], [4], [18].
CityHash более сложный и имеет большую пропускную способность, чем MurmurHash. MurmurHash более простой, имеет низкую задержку для коротких ключей (< 20 байт).
CityHash использует инструкции CRC у новых процессоров, обеспечивая до 0.17 циклов на байт, что быстрее всех остальных хешей; для сравнения, SHA-1 — 4.6 циклов на байт (Ivy Bridge). Без поддержки этих инструкций CityHash в два раза медленнее SpookyHash (по мнению автора последнего).
Для 32-битной платформы MurmurHash 3 может быть быстрее, чем SpookyHash и CityHash.
Если массив сообщений заранее известен, то можно использовать идеальную хеш-функцию: без коллизий и с поиском в одну операцию сравнения. Пример: gperf.
Если хеш-функция имеет нормальное распределение, то вероятность коллизии будет следующей:
На сколько реальны коллизии? Для 32-битных хешей они встречаются регулярно. Например, CRC32 совпадает у «codding» и «gnu», «exhibiters» и «schlager», «завиток» и «естествен» и т.д. Это не вина статистических особенностей хеш-функции, а следствие ограниченного размера хеша — всего 4 байта.
Все перечисленные функции, кроме CRC32 и FNV-1, имеют хорошие статистические показатели. Для 32-битной системы, возможно, быстрее всех будет работать MurmurHash. Если система не может делать невыровненное чтение (unaligned memory read), например, ARM или SPARC, то MurmurHash, возможно, также будет работать быстрее всех. Скорость CityHash сильно зависит от компилятора, поскольку используется много сложного кода, она может быть как больше, так и меньше остальных.
В качестве хеш-функции общего назначения можно применять MurmurHash 3, CityHash, SpookyHash V2, gperf.
Можно представить DoS атаку, когда атакующий скармливает в хеш-таблицу данные так, что они попадают все в один слот, и получается худшая скорость поиска одного элемента — O(n), вставки каждой новой коллизии — O(n²), растёт объём памяти (hash-flooding). Для осуществления атаки нужно иметь возможность помещать произвольные данные в хеш-таблицу, и найти коллизии хеш-функции.
Атака ещё называется hash DoS или, более обще, атака на алгоритмическую сложность (algorithmic complexity attack).
Коллизии можно создать несколькими способами:
Перечислим свойства криптографических хеш-функций (неприменимо к хеш-функциям общего назначения):
Иногда последние два критерия называют стойкостью к коллизиям первого и второго рода соответственно. Мы будем называть коллизией только случай, когда ни сообщение, ни хеш изначально не заданы.
Обычно самая «лёгкая» атака — это поиск коллизий. Из-за парадокса «дней рождений» сложность этой атаки как минимум в два раза меньше, чем длина хеша. Именно эта атака существует для SHA-1: при теоретической сложности коллизии O(280), атака уменьшает сложность до O(261). Атаки восстановления первого или второго прообраза для SHA-1 нет.
Чтобы увеличить стойкость к коллизиям, можно:
MAC, построенный на базе криптографической функции, имеет следующие свойства:
Если мы решим применять криптографическую хеш-функцию (например, SHA-3) или MAC на её основе, то мы столкнёмся со следующими недостатками:
Универсальная хеш-функция помимо сообщения также получает ключ, используя который выбирает хеш-функцию из конечного семейства функций. При ключе, известном атакующему, функция должна быть стойка к восстановлению второго прообраза, но нет требования стойкости к коллизиям. Если же ключ неизвестен атакующему, то функция будет стойка к коллизиям. Учитывая наши требования к скорости, желательно обойтись без криптографических функций.
Чтобы усложнить поиск коллизий, иногда пытаются построить MAC на базе хеш-функций общего назначения, используя seed в качестве ключа. Но полученный «MAC» не будет обладать требуемыми свойствами, поскольку построен не на базе криптографической функции. Возможны следующие атаки:
Поэтому, хотя этот подход может усложнить жизнь случайному атакующему, часто он не выдерживает простейшего криптоанализа (oCERT [8]). Было показано, что большинство хеш-функций общего назначения не стойки к криптографическим атакам:
До 2008-2010 года большинство языков и фреймворков использовало достаточно простые хеш-функции:
Исключение: Perl 4, использовал One-at-a-Time со случайным seed с 2003 года (в этом году обсуждали на конференции эту атаку), позже (5.17.6) использовал MurmurHash 3.
Чтобы уменьшить число коллизий и усложнить DoS атаку, многие языки за последний год перешли на современные хеш-функции со случайным seed. А когда выяснилось, что это не решает проблему с атакой, то многие сменили хеш и во второй раз.
Пример MAC, стойких к коллизиям:
2012 год, длина 64 бита, ключ 128 бит.
Скорость: 15.50 циклов на байт для 8 байт сообщения, 3.66 циклов на байт для 64 байт сообщения, до 1.96 циклов на байт для длинных сообщений. Для сравнения наиболее быстрый финалист SHA-3 BLAKE-512: 134 цикла на байт для 8 байт, 20 циклов на байт для 64 байт.
Можно использовать любое число раундов compression и finalization. Например, SipHash-2-4 — 2 и 4 раунда соответственно.
Был разработан как не стойкая к коллизиям хеш-функция на основе криптографической псевдослучайной функции (PRF), быстрая для коротких сообщений. Поскольку предполагается использование со случайным ключом, то нет требования стойкости к коллизиям. Отличается от некриптографических хеш-функций тем, что корректно и безопасно работает с ключом, обеспечивая как свойства MAC, так и свойства универсальной хеш-функции.
Ситуация по языкам на текущий момент выглядит так:
Открытые задачи:
Есть мнение, что борьба с этой атакой — не та задача, которую должна выполнять хеш-функция. Можно вместо этого:
Для структур данных, в которых используются недоверенные данные, применять алгоритмы со сложностью O(log n), например, сбалансированное дерево. Если нет возможности, то использовать хеш-функцию, случайно выбираемую из семейства функций (MAC), например, VMAC или SipHash.
Автор: Vanav
Источник [19]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/33750
Ссылки в тексте:
[1] www.isthe.com/chongo/tech/comp/fnv/index.html: http://www.isthe.com/chongo/tech/comp/fnv/index.html
[2] Pluto Scarab — Hash Functions: http://home.comcast.net/~bretm/hash/
[3] code.google.com/p/smhasher/wiki/MurmurHash2Flaw: http://code.google.com/p/smhasher/wiki/MurmurHash2Flaw
[4] blog.aggregateknowledge.com/2012/02/02/choosing-a-good-hash-function-part-3/: http://blog.aggregateknowledge.com/2012/02/02/choosing-a-good-hash-function-part-3/
[5] tools.ietf.org/html/draft-eastlake-fnv-05: http://tools.ietf.org/html/draft-eastlake-fnv-05
[6] www.ocert.org/advisories/ocert-2011-003.html: http://www.ocert.org/advisories/ocert-2011-003.html
[7] www.nruns.com/_downloads/advisory28122011.pdf: http://www.nruns.com/_downloads/advisory28122011.pdf
[8] www.ocert.org/advisories/ocert-2012-001.html: http://www.ocert.org/advisories/ocert-2012-001.html
[9] github.com/floodyberry/Marvin32/blob/master/Marvin32.c: https://github.com/floodyberry/Marvin32/blob/master/Marvin32.c
[10] arxiv.org/abs/1202.4961: http://arxiv.org/abs/1202.4961
[11] bugs.python.org/issue13703: http://bugs.python.org/issue13703
[12] crypto.stackexchange.com/questions/6408/from-hash-to-cryptographic-hash: http://crypto.stackexchange.com/questions/6408/from-hash-to-cryptographic-hash
[13] 131002.net/siphash/#at: https://131002.net/siphash/#at
[14] bugs.python.org/issue14621: http://bugs.python.org/issue14621
[15] code.google.com/p/go/issues/detail?id=4604: http://code.google.com/p/go/issues/detail?id=4604
[16] bugzilla.redhat.com/show_bug.cgi?id=880705: https://bugzilla.redhat.com/show_bug.cgi?id=880705
[17] code.google.com/p/smhasher/wiki/SMHasher: http://code.google.com/p/smhasher/wiki/SMHasher
[18] floodyberry.com/noncryptohashzoo/: http://floodyberry.com/noncryptohashzoo/
[19] Источник: http://habrahabr.ru/post/178955/
Нажмите здесь для печати.