Как происходит хеширование в памяти уровни

Хеширование (иногда «хэширование», англ. hashing ) — преобразование по детерминированному алгоритму входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или сводкой сообщения( англ. message digest ).

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

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

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

История

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

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

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

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

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

Виды хеш-функций

Хорошая хеш-функция должна удовлетворять двум свойствам:

Быстро вычисляться;
Минимизировать количество коллизий

Предположим, для определённости, что количество ключей $K$ , а хеш-функция $h(K)$ имеет не более $M$ различных значений:

$0<h(k)<M$

В качестве примера «плохой» хеш-функции можно привести функцию с $M=1000$ , которая десятизначному натуральном числу $K$ сопоставляет три цифры выбранные из середины двадцатизначного квадрата числа $K$ . Казалось бы значения хеш-кодов должны равномерно распределиться между «000» и «999», но для реальных данных такой метод подходит лишь в том случае, если ключи не имеют большого количества нулей слева или справа. [3]

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

Хеш-функции, основанные на делении

Первый метод заключается в том, что мы используем в качестве хеша остаток от деления на alt=»M» />, где alt=»M» />- это количество всех возможных хешей:

$h(K)= K \mod M$

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

Ещё следует сказать о методе хеширования, основанном на делении на полином по модулю два. В данном методе $M$ также должна являться степенью двойки, а бинарные ключи ( $K=k_<n-1>k_<n-2>. k_<0>» />) представляются в виде полиномов. В этом случае в качестве хеш-кода берутся значения коэффциентов полинома, полученного как остаток от деления <img decoding=$ на заранее выбранный полином $P$ степени $m$ :

При правильном выборе $P(x)$ такой способ гарантирует отсутствие коллизий между почти одинаковыми ключами. [3]

Мультипликативная схема хеширования

Второй метод состоит в выборе некоторой целой константы $A$ , взаимно простой с $w$ , где $w$ — количество представимых машинным словом значений (в компьютерах IBM PC $2^<32>» />). Тогда можем взять хеш-функцию вида:</p> <p>В этом случае, на компьютере с двоичной системой счисления, <img decoding=$ является степенью двойки и $h(K)$ будет состоять из старших битов правой половины произведения $A*K$ .

Среди преимуществ этих двух методов стоит отметь, что они выгодно используют то, что реальные ключи неслучайны, например в том случае если ключи представляют собой арифметическую прогрессию (допустим последовательность имён «ИМЯ1», «ИМЯ2», «ИМЯ3»). Мультипликативный метод отобразит арифметическую прогрессию в приближенно арифметическую прогрессию различных хеш-значений, что уменьшает количество коллизий по сравнению со случайной ситуацией. [3]

Одной из вариаций данного метода является хеширование Фибоначчи, основанное на свойствах золотого сечения. В качестве $A$ здесь выбирается ближайшее к $\varphi^<-1>*w» /> целое число, взаимно простое с <img decoding=$

Хеширование строк переменной длины

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

Хеширование Пирсона (англ. Pearson hashing ) — алгоритм, предложенный Питером Пирсоном (англ. Peter Pearson ) для процессоров с 8-битными регистрами, задачей которого является быстрое вычисление хеш-кода для строки произвольной длины. На вход функция получает слово $W$ , состоящее из $n$ символов, каждый размером 1 байт, и возвращает значение в диапазоне от 0 до 255. Причем значение хеш-кода зависит от каждого символа входного слова.

Алгоритм можно описать следующим псевдокодом, который получает на вход строку $W$ и использует таблицу перестановок $T$

Среди преимуществ алгоритма следует отметить:

Простоту вычисления;
Не существует таких входных данных, для которых вероятность коллизии наибольшая;
Возможность модификации в идеальную хеш-функцию.

В качестве альтернативного способа хеширования ключей, $K$ состоящих из $l$ символов ( $K=x_<1>x_<2>. x_<l>» />), можно предложить вычисление</p> <h4>Идеальное хеширование</h4> <p>Идеальной хеш-функцией (англ. <i>Perfect hash function</i> ) называется такая функция, которая отображает каждый ключ из набора <img decoding=$ в множество целых чисел без коллизий. В математических терминах это инъективное отображение.

Описание

Функция $h(k)\colon U\to [m]$ называется идеальной хеш-функцией для $S\subseteq U$ , если она инъективна на $S$ ;
Функция $h(k)\colon U\to [m]$ называется минимальной идеальной хеш-функцией для $S\subseteq U$ , если она является ИХФ и $m = n = |S|$ ;
Для целого , функция называется -идеальной хеш-функцией (k-PHF) для если для каждого имеем в числа . На входе алгоритм получает некоторый набор данных и размерностью , причем неизвестный заранее. Как правило целью хеширования является получение наименьшего числа коллизий, чего трудно добиться используя какую-то определенную хеш-функцию.

В качестве решения такой проблемы можно выбирать функцию случайным образом из определенного набора, называемого универсальным семейством $H = \< h : U \to [m] \>» />.</p> <h2>Хеш-функция, что это такое?</h2> <p><img decoding=$

Сегодня я хотел бы рассказать о том, что из себя представляет хеш-функция, коснуться её основных свойств, привести примеры использования и в общих чертах разобрать современный алгоритм хеширования SHA-3, который был опубликован в качестве Федерального Стандарта Обработки Информации США в 2015 году.

Общие сведения

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

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

Для идеальной хеш-функции выполняются следующие условия:

а) хеш-функция является детерминированной, то есть одно и то же сообщение приводит к одному и тому же хеш-значению
b) значение хеш-функции быстро вычисляется для любого сообщения
c) невозможно найти сообщение, которое дает заданное хеш-значение
d) невозможно найти два разных сообщения с одинаковым хеш-значением
e) небольшое изменение в сообщении изменяет хеш настолько сильно, что новое и старое значения кажутся некоррелирующими

Давайте сразу рассмотрим пример воздействия хеш-функции SHA3-256.

Число 256 в названии алгоритма означает, что на выходе мы получим строку фиксированной длины 256 бит независимо от того, какие данные поступят на вход.

На рисунке ниже видно, что на выходе функции мы имеем 64 цифры шестнадцатеричной системы счисления. Переводя это в двоичную систему, получаем желанные 256 бит.

Любой заинтересованный читатель задаст себе вопрос: «А что будет, если на вход подать данные, бинарный код которых во много раз превосходит 256 бит?»

Ответ таков: на выходе получим все те же 256 бит!
Дело в том, что 256 бит — это соответствий, то есть различных входов имеют свой уникальный хеш.
Чтобы прикинуть, насколько велико это значение, запишем его следующим образом:

Надеюсь, теперь нет сомнений в том, что это очень внушительное число!

Поэтому ничего не мешает нам сопоставлять длинному входному массиву данных массив фиксированной длины.

Свойства

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

Pre-image resistance

Имея заданное значение h, должно быть сложно найти любое сообщение m такое, что

Second pre-image resistance

Имея заданное входное значение , должно быть сложно найти другое входное значение такое, что

Collision resistance

Должно быть сложно найти два различных сообщения и таких, что

Такая пара сообщений и называется коллизией хеш-функции

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

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

Несмотря на то, что хеш-функций без коллизий не существует, некоторые из них достаточно надежны и считаются устойчивыми к коллизиям.

Pre-image resistance. Это свойство называют сопротивлением прообразу. Хеш-функция считается защищенной от нахождения прообраза, если существует очень низкая вероятность того, что злоумышленник найдет сообщение, которое сгенерировало заданный хеш. Это свойство является важным для защиты данных, поскольку хеш сообщения может доказать его подлинность без необходимости раскрытия информации. Далее будет приведён простой пример и вы поймете смысл предыдущего предложения.

Second pre-image resistance. Это свойство называют сопротивлением второму прообразу. Для упрощения можно сказать, что это свойство находится где-то посередине между двумя предыдущими. Атака по нахождению второго прообраза происходит, когда злоумышленник находит определенный вход, который генерирует тот же хеш, что и другой вход, который ему уже известен. Другими словами, злоумышленник, зная, что пытается найти такое, что

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

Неформально все эти свойства означают, что злоумышленник не сможет заменить или изменить входные данные, не меняя их хеша.

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

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

Применение хеш-функций

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

• Проверка целостности сообщений и файлов
Сравнивая хеш-значения сообщений, вычисленные до и после передачи, можно определить, были ли внесены какие-либо изменения в сообщение или файл.

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

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

Предлагаю также рассмотреть следующий бытовой пример:

Алиса ставит перед Бобом сложную математическую задачу и утверждает, что она ее решила. Боб хотел бы попробовать решить задачу сам, но все же хотел бы быть уверенным, что Алиса не блефует. Поэтому Алиса записывает свое решение, вычисляет его хеш и сообщает Бобу (сохраняя решение в секрете). Затем, когда Боб сам придумает решение, Алиса может доказать, что она получила решение раньше Боба. Для этого ей нужно попросить Боба хешировать его решение и проверить, соответствует ли оно хеш-значению, которое она предоставила ему раньше.

Теперь давайте поговорим о SHA-3.

Национальный институт стандартов и технологий (NIST) в течение 2007—2012 провёл конкурс на новую криптографическую хеш-функцию, предназначенную для замены SHA-1 и SHA-2.

Организаторами были опубликованы некоторые критерии, на которых основывался выбор финалистов:

Способность противостоять атакам злоумышленников

• Производительность и стоимость

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

• Гибкость и простота дизайна

Гибкость в эффективной работе на самых разных платформах, гибкость в использовании параллелизма или расширений ISA для достижения более высокой производительности

В финальный тур попали всего 5 алгоритмов:

Победителем и новым SHA-3 стал алгоритм Keccak.

Давайте рассмотрим Keccak более подробно.

Keccak

Хеш-функции семейства Keccak построены на основе конструкции криптографической губки, в которой данные сначала «впитываются» в губку, а затем результат Z «отжимается» из губки.

Любая губчатая функция Keccak использует одну из семи перестановок которая обозначается , где

перестановки представляют собой итерационные конструкции, состоящие из последовательности почти одинаковых раундов. Число раундов зависит от ширины перестановки и задаётся как где

В качестве стандарта SHA-3 была выбрана перестановка Keccak-f[1600], для неё количество раундов

Далее будем рассматривать

Давайте сразу введем понятие строки состояния, которая играет важную роль в алгоритме.

Строка состояния представляет собой строку длины 1600 бит, которая делится на и части, которые называются скоростью и ёмкостью состояния соотвественно.

Соотношение деления зависит от конкретного алгоритма семейства, например, для SHA3-256

В SHA-3 строка состояния S представлена в виде массива слов длины бит, всего бит. В Keccak также могут использоваться слова длины , равные меньшим степеням 2.

Алгоритм получения хеш-функции можно разделить на несколько этапов:

• С помощью функции дополнения исходное сообщение M дополняется до строки P длины кратной r

• Строка P делится на n блоков длины

• «Впитывание»: каждый блок дополняется нулями до строки длиной бит (b = r+c) и суммируется по модулю 2 со строкой состояния , далее результат суммирования подаётся в функцию перестановки и получается новая строка состояния , которая опять суммируется по модулю 2 с блоком и дальше опять подаётся в функцию перестановки . Перед началом работы криптографической губки все элементыравны 0.

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

Все сразу станет понятно, когда вы посмотрите на картинку ниже:

Функция дополнения

В SHA-3 используется следующий шаблон дополнения 10. 1: к сообщению добавляется 1, после него от 0 до r — 1 нулевых бит и в конце добавляется 1.

r — 1 нулевых бит может быть добавлено, когда последний блок сообщения имеет длину r — 1 бит. В этом случае последний блок дополняется единицей и к нему добавляется блок, состоящий из r — 1 нулевых бит и единицы в конце.

Если длина исходного сообщения M делится на r, то в этом случае к сообщению добавляется блок, начинающийся и оканчивающийся единицами, между которыми находятся r — 2 нулевых бит. Это делается для того, чтобы для сообщения, оканчивающегося последовательностью бит как в функции дополнения, и для сообщения без этих бит значения хеш-функции были различны.

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

Функция перестановок

Базовая функция перестановки состоит из раундов по пять шагов:

Тета, Ро, Пи, Хи, Йота

Далее будем использовать следующие обозначения:

Так как состояние имеет форму массива , то мы можем обозначить каждый бит состояния как

Обозначим результат преобразования состояния функцией перестановки

Также обозначим функцию, которая выполняет следующее соответствие:

— обычная функция трансляции, которая сопоставляет биту бит ,

где — длина слова (64 бит в нашем случае)

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

Шаг

Эффект отображения можно описать следующим образом: оно добавляет к каждому биту побитовую сумму двух столбцов и

Схематическое представление функции:

Шаг

Отображение направлено на трансляции внутри слов (вдоль оси z).

Проще всего его описать псевдокодом и схематическим рисунком:

Шаг

Шаг представляется псевдокодом и схематическим рисунком:

Шаг

Шаг является единственный нелинейным преобразованием в

Псевдокод и схематическое представление:

Шаг

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

Ниже приведена таблица раундовых констант для бит

Все шаги можно объединить вместе и тогда мы получим следующее:

Где константы являются циклическими сдвигами и задаются таблицей:

Итоги

В данной статье я постарался объяснить, что такое хеш-функция и зачем она нужна
Также в общих чертах мной был разобран принцип работы алгоритма SHA-3 Keccak, который является последним стандартизированным алгоритмом семейства Secure Hash Algorithm

Алгоритм хеширования данных: просто о сложном

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

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

Что такое хеш (хэш, hash)?

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

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

Убедиться в этом можно на любом онлайн-генераторе. Набрав слово «Otus» и воспользовавшись алгоритмом sha1 (Secure Hashing Algorithm), мы получим хеш 7576750f9d76fab50762b5987739c18d99d2aff7. При изменении любой буквы изменится и результат, причем изменится полностью. Мало того, если просто поменять регистр хотя бы одной буквы, итог тоже будет совершенно иным: если написать «otus», алгоритм хэш-функции отработает со следующим результатом: 1bbd70dc1b6fc84e5617ca8703c72c744b3b4fc1. Хотя общие моменты все же есть: строка всегда состоит из сорока символов.

В предыдущем примере речь шла о применении хэш-алгоритма для слова из 4 букв. Но с тем же успехом можно вставить слово из 1000 букв — все равно после обработки данных на выходе получится значение из 40 символов. Аналогичная ситуация будет и при обработке полного собрания сочинений Льва Толстого.

Криптостойкость функций хеширования

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

Проблемы хэшей

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

Цель хороших криптографических функций — максимально усложнить вероятность нахождения способов генерации входных данных, хешируемых с одинаковым значением. Как уже было сказано ранее, вычисление хэша не должно быть простым, а сам алгоритм должен быть устойчив к «атакам нахождения прообраза». Необходимо, чтобы на практике было чрезвычайно сложно (а лучше — невозможно) вычислить обратные детерминированные шаги, которые предприняты для воспроизведения созданного хешем значения.

Если S = hash (x), то, в идеале, нахождение x должно быть практически невозможным.

Алгоритм MD5 и его подверженность взлому

MD5 hash — один из первых стандартов алгоритма, который применялся в целях проверки целостности файлов (контрольных сумм). Также с его помощью хранили пароли в базах данных web-приложений. Функциональность относительно проста — алгоритм выводит для каждого ввода данных фиксированную 128-битную строку, задействуя для вычисления детерминированного результата однонаправленные тривиальные операции в нескольких раундах. Особенность — простота операций и короткая выходная длина, в результате чего MD5 является относительно легким для взлома. А еще он обладает низкой степенью защиты к атаке типа «дня рождения».

Атака дня рождения

Если поместить 23 человека в одну комнату, можно дать 50%-ную вероятность того, что у двух человек день рождения будет в один и тот же день. Если же количество людей довести до 70-ти, вероятность совпадения по дню рождения приблизится к 99,9 %. Есть и другая интерпретация: если голубям дать возможность сесть в коробки, при условии, что число коробок меньше числа голубей, окажется, что хотя бы в одной из коробок находится более одного голубя.

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

Когда разговор идет о сопротивлении коллизиям, то алгоритм MD5 действительно очень слаб. Настолько слаб, что даже бытовой Pentium 2,4 ГГц сможет вычислить искусственные хеш-коллизии, затратив на это чуть более нескольких секунд. Всё это в ранние годы стало причиной утечки большого количества предварительных MD5-прообразов.

SHA1, SHA2, SHA3

Secure Hashing Algorithm (SHA1) — алгоритм, созданный Агентством национальной безопасности (NSA). Он создает 160-битные выходные данные фиксированной длины. На деле SHA1 лишь улучшил MD5 и увеличил длину вывода, а также увеличил число однонаправленных операций и их сложность. Однако каких-нибудь фундаментальных улучшений не произошло, особенно когда разговор шел о противодействии более мощным вычислительным машинам. Со временем появилась альтернатива — SHA2, а потом и SHA3. Последний алгоритм уже принципиально отличается по архитектуре и является частью большой схемы алгоритмов хеширования (известен как KECCAK — «Кетч-Ак»). Несмотря на схожесть названия, SHA3 имеет другой внутренний механизм, в котором используются случайные перестановки при обработке данных — «Впитывание» и «Выжимание» (конструкция «губки»).

Что в будущем?

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

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