Хеш-функция облегчённой криптографии — криптостойкая хеш-функция, используемая в «легковесной» криптографии. В настоящее время актуальность таких хеш-функций резко возросла благодаря возможности использовать их во многих сферах деятельности (от RFID до Интернета вещей) и на стыке дисциплин (Блокчейн и IoT). Ввиду специфики использования данных хеш-функций на них накладываются дополнительные требования. Большинство современных хеш-функций в качестве своей основы использует структуру Меркла — Дамгора и функцию губки.
Концепция облегчённой криптографии Облегчённая криптография — раздел криптографии, в котором рассматриваются алгоритмы для устройств, не обладающих достаточными ресурсами для реализации существующих шифров, хеш-функций, электронных подписей и т. д. «Легковесная» криптография приобрела исключительную актуальность в настоящее время в связи распространением парадигмы умного дома, где множество приборов небольшого размера, с ограниченной вычислительной мощностью, лимитированным объёмом памяти и малым энергопотреблением коммуницируют между собой, обмениваясь конфиденциальной информацией жильца, для выполнения своих задач. Также особый интерес представляют алгоритмы для RFID-меток. Для того, чтобы злоумышленики не воспользовались приватной информацией пользователя, требуется специальная разработка и оптимизация алгоритмов, способных работать при ограниченных ресурсах и обеспечивать должный уровень безопасности.
Хеш-функции
Применение Для того, чтобы адресату убедиться в том, что ему было прислано сообщение от настоящего адресанта, оно отправляется вместе с электронной подписью. На практике подписывают не сообщение, а его хеш-сумму, это позволяет значительно уменьшить вычислительные ресурсы на создание подписи (так как обычно хеш-сумма на порядки меньше ключа) и повысить криптостойкость (злоумышленник не сможет узнать исходные данные только из хеша). Хеш-функции используются в технологии блокчейн для того, чтобы определить блок, который добавится в общую цепь. Например: для добавления нового блока в платформу Bitcoin требуется найти хеш-сумму SHA-256 меньше, чем определённое целевое число. В следующий созданный блок будет записан хеш предыдущего. Более того, хеш-функции, в частности хеш-функции облегчённой криптографии могут применяться на стыке дисциплин. Например: они применяются в блокчейне LSB, который предназначен для использования в интернете вещей.
Также хеш-суммы используются при проверке паролей. Если бы операционные системы хранили пароли в файлах, то взломщики с помощью несанкционированного доступа смогли бы получить к ним доступ, извлечение хеша, в свою очередь, им ничего не даст.
Требования Основные требования к хеш-функциям облегчённой криптографии такие же, как и к обычным криптографическим хеш-функциям:
Стойкость к восстановлению первого прообраза — при наличии хеш-суммы невозможность вычислить Стойкость к восстановлению вторых прообразов — при наличии невозможность найти , такое что Стойкость к коллизиям — невозможность найти и , такие что
Принимая в расчёт возможности вычислительных устройств, на которых будут производиться алгоритмы, а также задачи, которые требуется выполнить, к основным требованиям добавляются специальные:
Малое потребление энергии Небольшой размер внутреннего состояния
Атаки на хеш-функции Атака «дней рождения» — используется для поиска коллизии второго рода, эксплуатирует парадокс дней рождения. Для успешной атаки число обращений к хеш-функции должно составлять примерно , а квантовым компьютерам — эффективна для атак на хеш-функций и шифров, которые используют LFSR Линейная атака — разработана для хеш-функций, использующих блочные и потоковые шифры Дифференциальные атаки — действенны для хеш-функций с блочными шифрами Атака методом бумеранга — усовершенствованная дифференциальная атака, которая успешно применяется к хеш-функциям. Так, например, для нахождения коллизий SHA-0 с помощью этой атаки потребовался всего лишь один час на обычном ПК Атака удлинением сообщения — применяется для хеш-функций, основанных на структуре Меркла — Дамгора. Суть атаки заключается в добавлении новых битов в конец сообщения. Среди уязвимых функций: MD5 и SHA-1 Мультиколлизионная атака Жу — направлена на хеш-функции, использующие в качестве своей основы функцию губки, которая распространена среди функций облегчённой криптографии Rebound атака — предназначена для AES-подобных алгоритмов — создана для взлома хеш-функций, основанных на ARX (сравнение по модулю-битовый сдвиг-XOR)
Виды хеширований
Меркл — Дамгор
Основная идея Допустим, нам дан вектор инициализации : (фиксированный и открытый), функция сжатия отображающая в и сообщение , где блок из битов, если не кратно , то последний блок мы дополняем 1 и нулями. Например: если
,
то на вход мы подаём блока:
,
где единица добавляется для избежания коллизий. Теперь можно определить хеш-функцию :
Усовершенствованный алгоритм Для усиления защиты от атак, основанных на расширении входного сообщения, можно добавить новый блок, в котором будет записана длина сообщения. В данном случае это будет:
Также есть оптимизация, которая позволяет экономить ресурсы памяти (что важно для задач облегчённой криптографии): если в последнем блоке достаточно места для записи длины сообщения, то она будет там и записана:
Функция губки Функция губки широко используется в криптографии, с помощью неё создаются алгоритмы ГПСЧ, потоковых и блочных шифров, а также хеш-функцийBertoni, Guido, Joan Daemen, Michaël Peeters and Gilles Van Assche. «Sponge Functions.» (2007). http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.8103&rep=rep1&type=pdf .
Основная идея Губку размера можно разделить на 2 части: битовую скорость и мощность . При инициализации внутреннее состояние губки обнуляется; сообщение дополняется нулями, чтобы его размер был кратен .
Далее следуют стадии:
Абсорбция Первые бит внутреннего состояния заменяются результатом операции XOR этих бит и очередного блока исходного сообщения Внутреннее состояние обрабатывается функцией перестановки
Выжимание Считываются первые бит внутреннего состояния губки Внутреннее состояние обрабатывается функцией перестановки
П-губка и Т-губка П(ерестановочная)-губка и Т(рансформационная)-губка — губки, использующие соответственно случайную перестановку и ГПСЧ для обновления своего внутреннего состояния. В статье, в которой были введены функции губки, было показано, что губки с мощностью , битовой скоростью и вектором размера , принимающие на вход сообщения длиной , таковы, что для различных атак в среднем требуется следующее количество обращений к функциям обновлении(приведены степени двойки): +ГубкаПервый прообразВторой прообразКоллизияНахождение циклаT-губкаП-губка
JH-губка JH-губку называют так, потому что она похожа на структуру хеш-функции JH.
У неё стадия абсорбции состоит из трёх частей:
Первые бит внутреннего состояния заменяются результатом операции XOR этих бит и очередного блока исходного сообщения Внутреннее состояние обрабатывается функцией перестановки Последние бит внутреннего состояния заменяются результатом операции XOR этих бит и очередного блока исходного сообщения
Примеры хеш-функций в облегчённой криптографии
GLUON GLUON — это хеш-функция, использующая T-губку, основанную на программно-ориентированных потоковых шифрах X-FCSR-v2 и F-FCSR-H-v3: внутреннее состояние губки дополняется и загружается в FCSR, который синхронизируется за фиксированное количество времени. Затем некоторые ячейки FCSR складываются по модулю 2 для формирования первого слова следующего внутреннего состояния, FCSR синхронизируется, эти же слова складываются по модулю 2 для формирования второго слова следующего внутреннего состояния и т. д.
Функция обладает высокой криптографической стойкостью. Например: атака нахождения прообраза в общем случае имеет сложность , где — размер матрицы (которая определяет FCSR), а - размер слова, подаваемого на FCSR.
Особенность реализации GLUON состоит в том, что данные в FCSR записываются не последовательно, а параллельно, что значительно повышает скорость исполнения. Также был оптимизирован adder (элемент, осуществляющий сложение), который используется в FCSR, следующим образом: , где (здесь используется в качестве обозначения логического И).
Функция обновления GLUON-64 является многозначной, и её поведение сильно отличается от поведения ГПСЧ.
QUARK QUARK — это хеш-функция, использующая П-губку с аппаратно-ориентированной перестановкой. Была реализована под влиянием облегчённых блочных шифров KTANTAN и KATAN и аппаратно-ориентированного потокового шифра Grain. Наименьшая версия (хеш-сумма длиной 136 бит) называется U-QUARK, средняя (176 бит) D-QUARK и самая длинная (256 бит) S-QUARK.
Функция обновления отображает вектор в , загружая каждую половину в отдельный длины , а затем повторяет это раза. NFSR связаны друг с другом и с небольшим LFSR длины . Функции , и являются булевыми функциями, выбранными из-за их нелинейности и алгебраической сложности. и одинаковы для всех версий и заимствованы из Grain-v1, а определяется отдельным случаем.
Специфика реализации QUARK состоит в том, что в ней отсутствуют промежуточные значения функции губки, которые требуют дополнительных элементов для их запоминания. Другими словами, после перестановки значений состояния значения не записываются в следующее состояние, а сразу подаются на функцию перестановки, причём первые бит делают XOR с сообщением.
Обладает высокой криптостойкостью. Данные по резистентности к различным атакам приведены ниже: +Сложность успешной атаки для нахождения:КоллизииПервого прообразаВторого прообраза У данной хеш-функции есть реализация в открытом доступе, написанная на языке C.
SipHash-2-4 SipHash имеет структуру ARX, которая была создана под влиянием BLAKE и Skein. Он собой предоставляет семейство отображений , и предназначен для использования в качестве MAC или в хеш-таблицах. Он имеет структуру, аналогичную JH, как SPN-Hash, и использует заполнение, учитывающее также длину сообщения. Однако, оно заключается просто в добавлении байта с длиной сообщения по модулю 256. SipHash не претендует на устойчивость к коллизиям и, очевидно, не из-за небольшого размера хеш-суммы.
Отличительная черта SipHash состоит в том, что сообщения «ксорятся», не как в обычной функции губки, а по особому алгоритму:
Первое сообщение ксорится с последней четвертью губки Губка обрабатывается двумя функциями перестановки Первое сообщение снова ксорится, но уже с первой четвертью губки, в то время, как второе сообщение с последней Губка обрабатывается двумя функциями перестановки Второе сообщение ксорится с первой четвертью губки, а третья четверть ксорится с 0xFF
Несмотря на то, что в основе SipHash лежит ARX, не является уязвимой для ротационной атаки.
Существуют материалы по применению SipHash на github в открытом доступе.
PHOTON PHOTON представляет собой P-губку, основанную на AES-подобной перестановке. Для наименьшего параметра безопасности (PHOTON-80/20/16) битовая скорость во время абсорбции равна 20 и равна 16 во время выжимания. Перестановка состоит из 12 итераций (для каждого параметра безопасности) ниже описанной последовательности преобразований, выполненных на квадрате ячеек из 4 бит (8 бит для самой большой версии). Конвейер PHOTON состоит из 4 этапов:
Дополнительные константы (AddConstants) — дополнительные константы выбираются так, чтобы быть разными на каждой итерации, и чтобы отсутствовала симметрия между столбцами, как в AES подобных архитектурах (без этого слоя входное сообщение с равными столбцами будет сохранять это качество спустя любое количество итераций). Дополнительные константы могут быть сгенерированы регистром сдвига с линейной обратной связью. Для высокой производительности задействован только первый столбец внутреннего состояния. После того, как константы были сгенерированы, они складываются по модулю 2 с каждой ячейкой.