T1ha = fast positive hash

Идеальная криптографическая хеш-функция

Идеальной криптографической хеш-функцияей является такая криптографическая хеш-функция, к которой можно отнести пять основных свойств:

  1. Детерминированность. При одинаковых входных данных результат выполнения хеш-функции будет одинаковым (одно и то же сообщение всегда приводит к одному и тому же хешу);
  2. Высокая скорость вычисления значения хеш-функции для любого заданного сообщения;
  3. Невозможность сгенерировать сообщение из его хеш-значения, за исключением попыток создания всех возможных сообщений;
  4. Наличие лавинного эффекта. Небольшое изменение в сообщениях должно изменить хэш-значения, так широко, что новые хэш-значения не совпадают со старыми хэш-значениями;
  5. Невозможность найти два разных сообщения с одинаковыми хеш-значениями.

Таким образом, идеальная криптографическая хеш-функция, у которой длина n (то есть на выходе n бит), для вычисления прообраза должна требовать как минимум 2n{\displaystyle 2^{n}} операций.

Злоумышленник будет искать прообраз для идеальной хеш-функции следующим образом: у него есть число h, и ему надо найти такое m, что H(m) = h. Если это идеальная хеш-функция, то злоумышленнику остается лишь перебирать все возможные M и проверять, чему равна хеш-функция от этого сообщения. Результат вычисления, если m перебирается полностью, есть фактически случайное число. Если число h лежит в диапазоне от 0 до 2n{\displaystyle 2^{n}} , то тогда в среднем на поиски нужного h злоумышленник будет тратить 2n−1{\displaystyle 2^{n-1}} итераций. Таким образом, вычисление прообраза займёт в два раза меньше итераций, чем в идеальном случае.

Вычисление второго прообраза останется 2n{\displaystyle 2^{n}}. В поиске коллизий оценка даст 2n{\displaystyle 2^{n}} , причём это не совсем точный результат. Данная оценка идет из оценки так называемого «Парадокса дней рождения».

Если злоумышленник хочет написать программу по поиску коллизий, ему будет оптимально вначале завести себе словарь коллизий. Соответственно, дальше он вычисляет хеш-функцию от очередного сообщения и проверяет, принадлежит эта хеш-функция очередному сообщению или нет. Если принадлежит, то коллизия найдена, и тогда можно найти по словарю исходное сообщение с данным хеш-кодом. Если нет, то он пополняет словарь. На практике такой способ не реализуется, потому что не хватило бы памяти для подобного словаря.

Безопасность хеш-функций

Хеш-функция является безопасной в случае, когда криптоаналитику требуется очень много информации, для того чтобы взломать данную хеш-функцию (что делает взлом маловероятным) и если хеш-функция не взломана к данному времени.

Для того, чтобы хеш-функция была безопасной, необходимо, чтобы выполнялись условия:

При изменениях в тексте сообщения M{\displaystyle M} (вставки, перестановки и т. д.) должен меняться и хеш-код сообщения;


Иначе человек, который вводит свои логин и пароль для входа в Википедию, мог бы попасть на страницу другого участника.

Невозможность нахождения сообщения M{\displaystyle M} по известному хеш-коду h{\displaystyle h} из h=H(M){\displaystyle h=H(M)};

Если данное условие не выполняется, то это делает возможным нахождение паролей пользователей Википедии.

Задача нахождения сообщений M1{\displaystyle M_{1}} и M2{\displaystyle M_{2}}, таких что их хеш-коды равны h1=h2{\displaystyle h_{1}=h_{2}} должна быть очень трудоёмкой.

Иначе, можно было бы найти два пароля с одинаковыми хеш-кодами.

N-Hash не является безопасной функцией, так как для неё не выполнено последнее условие.

Криптоанализ N-Hash

В настоящее время N-Hash считается небезопасной функцией. На данном рисунке указаны все безопасные однонаправленные функции на данный момент согласно стандарту ISO/IEC 10118:

Из алгоритмов, построенных как и N-Hash на основе блочных шифров, безопасными считаются только MDC-2 и MDC-4.

Для N-Hash характерна следующая проблема:


Так как длина хеш-кода равна длине блока алгоритма шифрования, то алгоритм нестоек перед атакой методом «дней рождения».

Атаки на хеш-функции

На данном рисунке приведена классификация атак на все алгоритмы хеширования в целом.

Атаки, зависящие от алгоритма, являются атаками, основанными на свойствах конкретного алгоритма.

Например, N-Hash успешно атакуют с помощью дифференциального метода, атакой с фиксированной точкой и встречей посередине.

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

Действенные атаки на N-Hash

  • Полный перебор
  • Метод встречи в середине атаки
  • Парадокс дня рождения
  • Дифференциальный криптоанализ
  • Атака с фиксированной точкой
Атаки, базирующиеся на уязвимости алгоритма
Дифференциальный метод

Ден Бур предложил способ построения коллизии для однораундовой схемы N-Hash.

Бихам и Шамир успешно применили метод дифференциального криптоанализа для компрометации 6-раундовой схемы N-Hash. Предложенный ими способ построения коллизии срабатывает для любого значения N кратного трём и при этом для N ≤ 12 он оказывается эффективнее подхода, основанного на парадоксе дней рождения.

Для 12-раундовой схемы сложность построения коллизий предложенным методом оценивается величиной 256 операций (трудоёмкость метода, основанного на парадоксе дней рождения — 264 операций).

Атаки, не зависящие от алгоритма

Увеличение длины хеш-кода и секретного ключа усложнит работу криптоаналитика. Можно попытаться сделать вычисления слишком трудоёмкими для персонального компьютера и требующими больших ресурсов. Тогда криптоаналитику надо будет или искать суперкомпьютер, или написать вирус, который на основе распараллеливания процесса взлома хеш-функции будет использовать сразу несколько персональных компьютеров для решения проблемы.

Также действенны такие методы защиты хеш-функции:

  • использование контрольных сумм на разных этапах хеширования;
  • проверка на достоверность информации;
  • внедрение в сообщение информации типа salt.

Специфика криптографических хэш-функций

Рассмотрим более подробно, каким образом исследуемые нами типы алгоритмов могут задействоваться в сфере криптографии. Ключевое требование к соответствующим функциям — стойкость к коллизиям, о которых мы сказали выше. То есть не должны формироваться повторяющиеся значения хеш-функции, если значения эти уже присутствуют в структуре соседствующего алгоритма. Прочим отмеченным выше критериям криптографические функции также должны соответствовать. Понятно, что всегда есть некая теоретическая возможность восстановления исходного файла на основе хэша, особенно если в доступе есть мощный вычислительный инструмент. Однако подобный сценарий предполагается свести к минимуму, благодаря надежным алгоритмам шифрования. Так, вычислить хэш-функцию будет очень сложно, если ее вычислительная стойкость соответствует формуле 2^{n/2}.

Другой важнейший критерий криптографического алгоритма — изменение хэша в случае корректировки изначального массива данных. Выше мы отметили, что стандарты шифрования должны обладать чувствительностью на уровне 1 бита. Так, данное свойство — ключевой фактор обеспечения надежной парольной защиты доступа к файлам.

Итеративные схемы


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

Разумеется, сжимающая функция обязана соответствовать необходимым критериям криптостойкости. При интеративной схеме первая операция по обработке потока входных данных делится на блоки, размер которых исчисляется в битах. Соответствующий алгоритм также задействует временные переменные величиной в заданном количестве бит. В качестве первого значения задействуется общеизвестное число, в то время как последующие блоки данных объединяются со значением рассматриваемой функции на выходе. Значением хэша становятся выходные показатели бит для последней итерации, в которых учитывается весь входной поток, включая первое значение. Обеспечивается так называемый «лавинный эффект» хеширования.

Основная сложность, характеризующая реализуемое в виде итерационной схемы хеширование, — хэш-функции иногда сложно построить в том случае, если входной поток не является идентичным размеру блока, на который делится изначальный массив данных. Но в этом случае в стандарте хеширования могут быть прописаны алгоритмы, посредством которых исходный поток может быть расширен тем или иным образом.

В некоторых случаях в процессе обработки данных в рамках итерационной схемы могут быть задействованы так называемые многопроходные алгоритмы. Они предполагают формирование еще более интенсивного «лавинного эффекта». Подобный сценарий предполагает формирование повторных массивов данных, и только во вторую очередь идет расширение.

Методы борьбы с коллизиями


Основная статья: Коллизия хеш-функции

Коллизией (иногда конфликтом или столкновением) называется случай, при котором одна хеш-функция для разных входных блоков возвращает одинаковые хеш-коды.

Методы борьбы с коллизиями в хеш-таблицах

Основная статья: Хеш-таблица

Большинство первых работ, описывающих хеширование, посвящено методам борьбы с коллизиями в хеш-таблицах. Тогда хеш-функции применялись при поиске текста в файлах большого размера. Существует два основных метода борьбы с коллизиями в хеш-таблицах:

  1. метод цепочек (метод прямого связывания);
  2. метод открытой адресации.

При использовании метода цепочек в хеш-таблице хранятся пары «связный список ключей» — «хеш-код». Для каждого ключа хеш-функцией вычисляется хеш-код; если хеш-код был получен ранее (для другого ключа), ключ добавляется в существующий список ключей, парный хеш-коду; иначе создаётся новая пара «список ключей» — «хеш-код», и ключ добавляется в созданный список. В общем случае, если имеется N{\displaystyle N} ключей и M{\displaystyle M} списков, средний размер хеш-таблицы составит NM{\displaystyle {\frac {N}{M}}}. В этом случае при поиске по таблице по сравнению со случаем, в котором поиск выполняется последовательно, средний объём работ уменьшится примерно в M{\displaystyle M} раз.

При использовании метода открытой адресации в хеш-таблице хранятся пары «ключ» — «хеш-код». Для каждого ключа хеш-функцией вычисляется хеш-код; пара «ключ» — «хеш-код» сохраняется в таблице. В этом случае при поиске по таблице по сравнению со случаем, в котором используются связные списки, ссылки не используются, выполняется последовательный перебор пар «ключ» — «хеш-код», перебор прекращается после обнаружения нужного ключа. Последовательность, в которой просматриваются ячейки таблицы, называется последовательностью проб.

Криптографическая соль

Основная статья: Соль (криптография)

Для защиты паролей и цифровых подписей от подделки создано несколько методов, работающих даже в том случае, если криптоаналитику известны способы построения коллизий для используемой хеш-функции. Одним из таких методов является добавление к входным данным так называемой криптографической «соли» — строки случайных данных; иногда «соль» добавляется и к хеш-коду. Добавление случайных данных значительно затрудняет анализ итоговых хеш-таблиц. Данный метод, к примеру, используется при сохранении паролей в UNIX-подобных операционных системах.

Теоретическое обоснование[править]

Теорема:
Если ключей сохраняются в хеш-таблице размером c использованием хеш-функции , случайно выбранной из универсального множества хеш-функций, то математическое ожидание числа коллизий не превышает .
Доказательство:

Всего имеется пар ключей, которые могут вызвать коллизию. Если хеш-функция выбрана случайным образом из универсального семейства хеш-функций , то для каждой пары вероятность возникновения коллизии равна . Пусть — случайная величина, которая подсчитывает количество коллизий. Если , то математическое ожидание числа коллизий равно

Это является очень хорошим результатом, если хотя бы вспомнить на примере о том, что вероятность коллизий растет крайне быстро по сравнению с размером хеш-таблицы.

Теорема:
Если мы сохраняем ключей в хеш-таблице размеров c использованием хеш-функции , выбираемой случайным образом из универсального множества хеш-функций, то , где — количество ключей, хешированных в ячейку .
Доказательство:

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

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

А так как , то

, ч.т.д.

Теперь выведем 2 следствия из этой теоремы.

Теорема:
Если мы сохраняем ключей в хеш-таблице размером с использованием хеш-функции , выбираемой случайным образом из универсального множества хеш-функций, и устанавливаем размер каждой вторичной хеш-таблицы равным , то математическое ожидание количества необходимой для вторичных хеш-таблиц в схеме идеального хеширования памяти не превышает .
Доказательство:

Поскольку для , согласно предыдущей теореме:

, ч.т.д.
Теорема:
Если мы сохраняем ключей в хеш-таблице размером с использованием хеш-функции , выбираемой случайным образом из универсального множества хеш-функций, и устанавливаем размер каждой вторичной хеш-таблицы равным , то вероятность того, что общее количество необходимой для вторичных хеш-таблиц памяти не менее , меньше чем .
Доказательство:

Применим неравенство Маркова

Пусть и .

Тогда , ч.т.д.

История

Шифровка сообщений без возможности однозначной расшифровки, а только с целью подтверждения авторского приоритета, применялась издавна.

Галилео Галилей наблюдал кольца Сатурна, которые принял за «ушки». Не будучи уверен, но желая утвердить свой приоритет, он опубликовал сообщение с перестановленными буквами: smaismrmilmepoetaleumibunenugttauiras. В 1610 году он раскрыл исходную фразу: Altissimum planetam tergeminum obseruaui, что в переводе с латинского языка означает «высочайшую планету тройною наблюдал». Таким образом, на момент публикации первого сообщения исходная фраза не была раскрыта, но была создана возможность подтвердить её позже.

В середине 1650-х Христиан Гюйгенс разглядел кольца и опубликовал сообщение с буквами, расставленными по алфавиту: ааааааа, ссссс, d, еееее, g, h, iiiiiii, lllll, mm, nnnnnnnnn, oooo, pp, q, rr, s, ttttt, uuuuu. Через некоторое время была опубликована и исходная фраза: Annulo cingitur, tenui plano, nusquam cohaerente, ad eclipticam inclinato — «Окружен кольцом тонким, плоским, нигде не подвешенным, наклоненным к эклиптике». От применения хеш-функции, включая и цель позднее подтвердить некоторое нераскрытое сообщение, данный случай отличается только тем, что выходное сообщение не имеет фиксированной длины, а определяется длиной входного. Фактически, расстановка букв исходного сообщения по алфавиту является некоторой хеш-функцией, но только с результатом нефиксированной длины.

В январе 1953 года Ханс Петер Лун (нем. Hans Peter Luhn) (сотрудник фирмы IBM) предложил «хеш-кодирование». Дональд Кнут считает, что Ханс первым выдвинул систематическую идею «хеширования».

В 1956 году Арнольд Думи (англ. Arnold Dumey) в своей работе «Computers and automation» первым описал идею «хеширования» такой, какой её знает большинство программистов сейчас. Думи рассматривал «хеширование» как решение «проблемы словаря», предложил использовать в качестве «хеш-адреса» остаток от деления на простое число.

В 1957 году в журнале «IBM Journal of Research and Development» была опубликована статья Уэсли Питерсона (англ. W. Wesley Peterson) о поиске текста в больших файлах. Эта работа считается первой «серьёзной» работой по «хешированию». В статье Уэсли определил «открытую адресацию», указал на уменьшение производительности при удалении. Спустя шесть лет была опубликована работа Вернера Бухгольца (нем. Werner Buchholz), в которой было проведено обширное исследование «хеш-функций». В течение нескольких последующих лет «хеширование» широко использовалось, однако никаких значимых работ не публиковалось.

В 1967 году «хеширование» в современном значении упомянуто в книге Херберта Хеллермана «Принципы цифровых вычислительных систем». В 1968 году Роберт Моррис (англ. Robert Morris) опубликовал в журнале «Communications of the ACM» большой обзор по «хешированию». Эта работа считается «ключевой» публикацией, вводящей понятие о «хешировании» в научный оборот, и закрепившей термин «хеш», ранее применявшийся только специалистами (жаргон).

До начала 1990-х годов в русскоязычной литературе в качестве эквивалента термину «хеширование» благодаря работам Андрея Петровича Ершова использовалось слово «расстановка», а для «коллизий» использовался термин «конфликт» (А. П. Ершов использовал «расстановку» с 1956 года). В русскоязычном издании книги Никлауса Вирта «Алгоритмы и структуры данных» 1989 года также используется термин «расстановка». Предлагалось также назвать метод другим русским словом: «окрошка». Однако ни один из этих вариантов не прижился, и в русской литературе используется преимущественно термин «хеширование».


С этим читают