Хеш-функция облегчённой криптографии — криптостойкая хеш-функция , используемая в «легковесной» криптографии . В настоящее время актуальность таких хеш-функций резко возросла благодаря возможности использовать их во многих сферах деятельности (от RFID до Интернета вещей ) и на стыке дисциплин ( Блокчейн и IoT ) . В виду специфики использования данных хеш-функций, на них накладываются дополнительные требования . Большинство современных хеш-функций в качестве своей основы используют структуру Меркла — Дамгора и функцию губки .

Концепция облегчённой криптографии

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

Хеш-функции

Применение

Для того, чтобы адресату убедиться в том, что ему было прислано сообщение от настоящего адресанта, оно отправляется вместе с электронной подписью. На практике подписывают не сообщение, а его хеш-сумму, это позволяет значительно уменьшить вычислительные ресурсы на создание подписи (так как обычно хеш-сумма на порядки меньше ключа) и повысить криптостойкость (злоумышленник не сможет узнать исходные данные только из хеша) . Хеш-функции используются в технологии блокчейн для того, чтобы определить блок, который добавится в общую цепь. Например: для добавления нового блока в платформу Bitcoin требуется найти хеш-сумму SHA-256 меньше, чем определённое целевое число. В следующий созданный блок будет записан хеш предыдущего . Более того, хеш-функции, в частности хеш-функции облегчённой криптографии могут применяться на стыке дисциплин. Например: они применяются в блокчейне LSB, который предназначен для использования в интернете вещей .

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

Требования

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

• Стойкость к восстановлению первого прообраза — при наличии хеш-суммы ${\displaystyle H(m)}$ невозможность вычислить ${\displaystyle m}$
• Стойкость к восстановлению вторых прообразов — при наличии ${\displaystyle m}$ невозможность найти ${\displaystyle n}$ , такое что ${\displaystyle H(n)=H(m)}$
• Стойкость к коллизиям — невозможность найти ${\displaystyle m}$ и ${\displaystyle n}$ , такие что ${\displaystyle H(n)=H(m)}$

Принимая в расчёт возможности вычислительных устройств, на которых будут производиться алгоритмы, а также задачи, которые требуется выполнить, к основным требованиям добавляются специальные:

• Малое потребление энергии
• Небольшой размер внутреннего состояния

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

1. Атака «дней рождения» — используется для поиска коллизии второго рода , эксплуатирует парадокс дней рождения . Для успешной атаки число обращений к хеш-функции должно составлять примерно ${\displaystyle 2^{\frac {n}{2}}}$ , а квантовым компьютерам ${\displaystyle 2^{\frac {n}{3}}}$
2. ( англ. ) — эффективна для атак на хеш-функций и шифров, которые используют LFSR
3. ( англ. ) — разработана для хеш-функций, использующих блочные и потоковые шифры
4. ( англ. ) — действенны для хеш-функций с блочными шифрами
5. Атака методом бумеранга — усовершенствованная дифференциальная атака, которая успешно применяется к хеш-функциям . Так, например, для нахождения коллизий SHA-0 с помощью этой атаки потребовался всего лишь один час на обычном ПК
6. Атака удлинением сообщения — применяется для хеш-функций, основанных на структуре Меркла — Дамгора . Суть атаки заключается в добавлении новых битов в конец сообщения. Среди уязвимых функций: MD5 и SHA-1
7. Мультиколлизионная атака Жу — направлена на хеш-функции, использующие в качестве своей основы функцию губки , которая распространена среди функций облегчённой криптографии
8. Rebound атака — предназначена для AES-подобных алгоритмов
9. ( англ. ) — создана для взлома хеш-функций, основанных на ARX ( сравнение по модулю - битовый сдвиг - XOR )

Виды хеширований

Меркл — Дамгор

Основная идея

Допустим, нам дан вектор инициализации ${\displaystyle IV}$ : ${\displaystyle \{0,1\}^{n}}$ (фиксированный и открытый), функция сжатия ${\displaystyle h}$ отображающая ${\displaystyle \{0,1\}^{n}\times \{0,1\}^{k}}$ в ${\displaystyle \{0,1\}^{n}}$ и сообщение ${\displaystyle m=(m_{0},m_{1},...,m_{L-1})}$ , где ${\displaystyle m_{i}}$ блок из ${\displaystyle k}$ битов, если ${\displaystyle m}$ не кратно ${\displaystyle k}$ , то последний блок мы дополняем 1 и нулями . Например: если

${\displaystyle m=123456789}$ ,

то на вход мы подаём ${\displaystyle 2}$ блока:

${\displaystyle 12345678\quad 91000000}$ ,

где единица добавляется для избежания коллизий. Теперь можно определить хеш-функцию ${\displaystyle H}$ :

• ${\displaystyle c_{0}=IV}$
• ${\displaystyle c_{i+1}=h(c_{i},m_{i})}$
• ${\displaystyle H(m)=d=c_{L}}$

Усовершенствованный алгоритм

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

${\displaystyle 12345678\quad 91000000\quad 00000009}$

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

${\displaystyle 12345678\quad 91000009}$

Функция губки

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

Основная идея

Губку размера ${\displaystyle b}$ можно разделить на 2 части: битовую скорость ${\displaystyle r}$ и мощность ${\displaystyle c}$ . При инициализации внутреннее состояние губки обнуляется; сообщение ${\displaystyle m}$ дополняется нулями, чтобы его размер был кратен ${\displaystyle r}$ .

Далее следуют ${\displaystyle 2}$ стадии:

1. Абсорбция
   • Первые ${\displaystyle r}$ бит внутреннего состояния заменяются результатом операции XOR этих бит и очередного блока исходного сообщения
   • Внутреннее состояние обрабатывается функцией перестановки

1. Выжимание
   • Считываются первые ${\displaystyle r}$ бит внутреннего состояния губки
   • Внутреннее состояние обрабатывается функцией перестановки

П-губка и Т-губка

П(ерестановочная)-губка и Т(рансформационная)-губка — губки, использующие соответственно случайную перестановку и ГПСЧ для обновления своего внутреннего состояния. В статье, в которой были введены функции губки, было показано, что губки с мощностью ${\displaystyle c}$ , битовой скоростью ${\displaystyle r}$ и вектором размера ${\displaystyle n}$ , принимающие на вход сообщения длиной ${\displaystyle m<2^{\frac {c}{2}}}$ , таковы, что для различных атак в среднем требуется следующее количество обращений к функциям обновлении(приведены степени двойки) :

Губка	Первый прообраз	Второй прообраз	Коллизия	Нахождение цикла
T-губка	${\displaystyle \min(n,c+r)}$	${\displaystyle \min(n,c-\log _{2}(m))}$	${\displaystyle \min(n,c)/2}$	${\displaystyle (c+r)/2}$
П-губка	${\displaystyle c-1}$	${\displaystyle \min(n,c/2)}$	${\displaystyle \min(n,c)/2}$	${\displaystyle c+r}$

JH-губка

JH-губку называют так, потому что она похожа на структуру хеш-функции JH .

У неё стадия абсорбции состоит из трёх частей:

1. Первые ${\displaystyle r}$ бит внутреннего состояния заменяются результатом операции XOR этих бит и очередного блока исходного сообщения
2. Внутреннее состояние обрабатывается функцией перестановки
3. Последние ${\displaystyle r}$ бит внутреннего состояния заменяются результатом операции XOR этих бит и очередного блока исходного сообщения

Примеры хеш-функций в облегчённой криптографии

GLUON

GLUON — это хеш-функция, использующая T-губку, основанную на программно-ориентированных потоковых шифрах X-FCSR-v2 и F-FCSR-H-v3 : внутреннее состояние губки дополняется и загружается в FCSR , который синхронизируется за фиксированное количество времени. Затем некоторые ячейки FCSR складываются по модулю 2 для формирования первого слова следующего внутреннего состояния, FCSR синхронизируется, эти же слова складываются по модулю 2 для формирования второго слова следующего внутреннего состояния и т. д.

Функция обладает высокой криптографической стойкостью. Например: атака нахождения прообраза в общем случае имеет сложность ${\displaystyle 2^{\frac {3\omega r}{2}}}$ , где ${\displaystyle \omega \times \omega }$ — размер матрицы ${\displaystyle T}$ (которая определяет FCSR ), а ${\displaystyle r}$ - размер слова, подаваемого на FCSR.

Особенность реализации GLUON состоит в том, что данные в FCSR записываются не последовательно, а параллельно, что значительно повышает скорость исполнения. Также был оптимизирован adder (элемент, осуществляющий сложение), который используется в FCSR, следующим образом: ${\displaystyle s=(a\oplus b)\oplus c}$ , где ${\displaystyle c=(a.b)\oplus (a\oplus b).c}$ (здесь ${\displaystyle .}$ используется в качестве обозначения логического И ) .

Функция обновления GLUON-64 является многозначной, и её поведение сильно отличается от поведения ГПСЧ .

QUARK

QUARK — это хеш-функция, использующая П-губку с аппаратно-ориентированной перестановкой. Была реализована под влиянием облегчённых блочных шифров KTANTAN и KATAN и аппаратно-ориентированного потокового шифра Grain . Наименьшая версия (хеш-сумма длиной 136 бит) называется U-QUARK, средняя (176 бит) D-QUARK и самая длинная (256 бит) S-QUARK.

Функция обновления отображает вектор ${\displaystyle \{0,1\}^{b}}$ в ${\displaystyle \{0,1\}^{b}}$ , загружая каждую половину в отдельный ( англ. ) длины ${\displaystyle {\frac {b}{2}}}$ , а затем повторяет это ${\displaystyle 4b}$ раза. NFSR связаны друг с другом и с небольшим LFSR длины ${\displaystyle \log(4b)}$ . Функции ${\displaystyle f}$ , ${\displaystyle g}$ и ${\displaystyle h}$ являются булевыми функциями, выбранными из-за их нелинейности и алгебраической сложности. ${\displaystyle f}$ и ${\displaystyle g}$ одинаковы для всех версий и заимствованы из Grain-v1, а ${\displaystyle h}$ определяется отдельным случаем.

Специфика реализации QUARK состоит в том, что в ней отсутствуют промежуточные значения функции губки, которые требуют дополнительных элементов для их запоминания. Другими словами, после перестановки значений состояния значения не записываются в следующее состояние, а сразу подаются на функцию перестановки, причём первые ${\displaystyle r}$ бит делают XOR с сообщением .

Обладает высокой криптостойкостью. Данные по резистентности к различным атакам приведены ниже :

Сложность успешной атаки для нахождения:

Коллизии	Первого прообраза	Второго прообраза
${\displaystyle 2^{\frac {c}{2}}}$	${\displaystyle 2^{c}}$	${\displaystyle 2^{\frac {c}{2}}}$

У данной хеш-функции есть реализация в открытом , написанная на языке C .

SipHash-2-4

SipHash имеет структуру ARX, которая была создана под влиянием BLAKE и Skein . Он собой предоставляет семейство отображений ${\displaystyle \{0,1\}^{*}\rightarrow \{0,1\}^{64}}$ , и предназначен для использования в качестве MAC или в хеш-таблицах. Он имеет структуру, аналогичную JH, как SPN-Hash, и использует заполнение, учитывающее также длину сообщения. Однако, оно заключается просто в добавлении байта с длиной сообщения по модулю 256. SipHash не претендует на устойчивость к коллизиям и, очевидно, не из-за небольшого размера хеш-суммы.

Отличительная черта SipHash состоит в том, что сообщения « ксорятся », не как в обычной функции губки, а по особому алгоритму:

• Первое сообщение ксорится с последней четвертью губки
• Губка обрабатывается двумя функциями перестановки
• Первое сообщение снова ксорится, но уже с первой четвертью губки, в то время, как второе сообщение с последней
• Губка обрабатывается двумя функциями перестановки
• Второе сообщение ксорится с первой четвертью губки, а третья четверть ксорится с 0xFF

Несмотря на то, что в основе SipHash лежит ARX, не является уязвимой для .

Существуют SipHash на github в открытом доступе.

PHOTON

PHOTON представляет собой P-губку, основанную на AES-подобной перестановке. Для наименьшего параметра безопасности (PHOTON-80/20/16) битовая скорость во время абсорбции равна 20 и равна 16 во время выжимания. Перестановка состоит из 12 итераций (для каждого параметра безопасности) ниже описанной последовательности преобразований, выполненных на квадрате ${\displaystyle d\times d}$ ячеек из 4 бит (8 бит для самой большой версии). Конвейер PHOTON состоит из 4 этапов:

1. Дополнительные константы (AddConstants) — дополнительные константы выбираются так, чтобы быть разными на каждой итерации, и чтобы отсутствовала симметрия между столбцами, как в AES подобных архитектурах (без этого слоя входное сообщение с равными столбцами будет сохранять это качество спустя любое количество итераций). Дополнительные константы могут быть сгенерированы регистром сдвига с линейной обратной связью. Для высокой производительности задействован только первый столбец внутреннего состояния. После того, как константы были сгенерированы, они складываются по модулю 2 с каждой ячейкой.
2. Замена ячеек (SubCells) — S-блок применяется на каждой ячейке. Если ячейка имеет длину 4 бита, то используется PRESENT Sbox SBOXPRE, если 8 бит — AES Sbox SBOXAES.
3. Сдвиг строк (ShiftRows) — идентичен AES.
4. MixColumnsSerial — ячейки рассматриваются как элементы поля Галуа ${\displaystyle {\displaystyle GF(2^{4})}}$ (или ${\displaystyle GF(2^{8})}$ для наибольшего параметра безопасности), и каждый столбец умножается на матрицу , специально созданной для эффективной реализации в аппаратном обеспечении .

Данные по криптостойкости:

Сложность успешной атаки для нахождения:

Коллизии	Первого прообраза	Второго прообраза
${\displaystyle 2^{\frac {n}{2}}}$	${\displaystyle 2^{n-r}}$	${\displaystyle 2^{\frac {n}{2}}}$

Способ перестановки, используемый для обновления губки, близок к LED шифру, который был разработан позже создателями PHOTON.

SPONGENT

SPONGENT можно рассматривать как П-губку, где перестановка является модифицированной версией блочного шифра PRESENT.

Число итераций PRESENT-подобной перестановки варьируется от 45 для SPONGENT-88 до 140 для SPONGENT-256. Каждая итерация состоит из:

1. Складывания по модулю 2 содержимого LFSR, синхронизированного на каждой итерации (может рассматриваться, как константа на итерации)
2. Применение к слою S-блока S-блок 4×4, удовлетворяющий тем же критериям, что и PRESENT S-блок
3. Переставляя биты способом, подобным в PRESENT

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

SPONGENT на ассемблере и Си есть в открытом доступе.

SPN-Hash

Основной интерес SPN-Hash заключается в её доказуемой защите от дифференциальных коллизионных атак. Это JH-губка, использующая, как следует из её названия, перестановку, основанную на SPN . Структура SPN основана на структуре AES : сначала S-блоки 8×8 применяются к каждому байту внутреннего состояния. Используемый S-блок в точности совпадает с использующимся в AES. Затем применяется более сложный перемешивающий слой; Сильной стороной этого хеширования являются хорошая диффузия и легковесность. Наконец, константы на каждой итерации записываются во внутренне состояние (строгой дизъюнкцией), аналогичной LED и PHOTON. Эти операции повторяются 10 раз для всех параметров безопасности.

Используемый отступ такой же, как в усиленном Меркле-Дамгоре: длина сообщения добавляется к последнему блоку .

DM-PRESENT

DM-PRESENT — это просто схема Меркла-Дамгора, где функцией сжатия является блочный шифр PRESENT в режиме Дэвиса-Мейера. DM-PRESENT-80 основан на PRESENT-80, а DM-PRESENT-128 — на PRESENT-128. Данная хеш-функция уязвима для коллизий и не является стойкой к восстановлению вторых прообразов, такие хеш-функции будут полезны только в приложениях, которым требуется стойкость к восстановлению первого прообраза и 64-битная защита .

ARMADILLO

ARMADILLO — это многоцелевой примитив, предназначенный для использования в качестве FIL-MAC (приложение I), для хеширования и цифровых подписей (приложение II), а также для PRNG и PRF (приложение III). Он был взломан Найей-Пласенсией и Пейрином . Они нашли способ быстро обнаруживать коллизии, когда он используется в качестве хеш-функции (несколько секунд на обычном ПК) .

См. также

• Хеш-функция
• Хеш-сумма
• Функция губки
• Структура Меркла — Дамгора

Литература