Хеш-функция облегчённой криптографии (}yo-srutenx kQlyic~uukw tjnhmkijgsnn)

Хеш-функция облегчённой криптографии — криптостойкая хеш-функция, используемая в «легковесной» криптографии. В настоящее время актуальность таких хеш-функций резко возросла благодаря возможности использовать их во многих сферах деятельности (от 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). Он был взломан Найей-Пласенсией и Пейрином. Они нашли способ быстро обнаруживать коллизии, когда он используется в качестве хеш-функции (несколько секунд на обычном ПК).

См. также

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