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

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

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

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

Хеш-функции

Применение

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

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

Требования

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

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

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

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

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

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

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

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

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

Допустим, нам дан вектор инициализации ${\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 и нулями^[18]. Например: если

${\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}}$

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

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

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

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

${\displaystyle 12345678\quad 91000009}$

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

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

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

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

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

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

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

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

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

Губка	Первый прообраз	Второй прообраз	Коллизия	Нахождение цикла
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 этих бит и очередного блока исходного сообщения^[27]

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

GLUON

GLUON — это хеш-функция, использующая T-губку, основанную на программно-ориентированных потоковых шифрах X-FCSR-v2 и F-FCSR-H-v3^[28]: внутреннее состояние губки дополняется и загружается в 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 .}$ используется в качестве обозначения логического И)^[29].

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

QUARK

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

Функция обновления отображает вектор ${\displaystyle \{0,1\}^{b}}$ в ${\displaystyle \{0,1\}^{b}}$, загружая каждую половину в отдельный NFSR (англ. Nonlinear-feedback shift register) длины ${\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 с сообщением^[32].

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

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

Коллизии	Первого прообраза	Второго прообраза
${\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, не является уязвимой для ротационной атаки^[33].

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

PHOTON

PHOTON представляет собой P-губку, основанную на AES-подобной^[34] перестановке. Для наименьшего параметра безопасности (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})}$ для наибольшего параметра безопасности), и каждый столбец умножается на матрицу MDS, специально созданной для эффективной реализации в аппаратном обеспечении^[35].

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

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

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

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

SPONGENT

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

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

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

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

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

SPN-Hash

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

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

DM-PRESENT

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

ARMADILLO

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

См. также

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