Хеш-функция облегчённой криптографии

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

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

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

Хеш-функции

Применение

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

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

Требования

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

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

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

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

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

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

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

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

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

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

$m=123456789$,

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

$12345678\quad 91000000$,

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

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

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

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

$12345678\quad 91000000\quad 00000009$

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

$12345678\quad 91000009$

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

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

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

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

Далее следуют $2$ стадии:

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

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

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

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

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

JH-губка

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

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

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

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

GLUON

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

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

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

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

QUARK

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

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

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

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

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

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

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

SipHash-2-4

SipHash имеет структуру ARX, которая была создана под влиянием BLAKE и Skein. Он собой предоставляет семейство отображений $\{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 итераций (для каждого параметра безопасности) ниже описанной последовательности преобразований, выполненных на квадрате $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 GF(2^{4})}$ (или $GF(2^{8})$ для наибольшего параметра безопасности), и каждый столбец умножается на матрицу MDS, специально созданной для эффективной реализации в аппаратном обеспечении.

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

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

Коллизии	Первого прообраза	Второго прообраза
$2^{\frac {n}{2}}$	$2^{n-r}$	$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). Он был взломан Найей-Пласенсией и Пейрином. Они нашли способ быстро обнаруживать коллизии, когда он используется в качестве хеш-функции (несколько секунд на обычном ПК).

См. также

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