Русская Википедия:Хеш-функция облегчённой криптографии
Хеш-функция облегчённой криптографии — криптостойкая хеш-функция, используемая в «легковесной» криптографии[1]Шаблон:Переход. В настоящее время актуальность таких хеш-функций резко возросла благодаря возможности использовать их во многих сферах деятельности (от RFID до Интернета вещей) и на стыке дисциплин (Блокчейн и IoT)Шаблон:Переход. В виду специфики использования данных хеш-функций, на них накладываются дополнительные требованияШаблон:Переход. Большинство современных хеш-функций в качестве своей основы используют структуру Меркла — ДамгораШаблон:Переход и функцию губкиШаблон:Переход.
Концепция облегчённой криптографии
Облегчённая криптография — раздел криптографии, в котором рассматриваются алгоритмы для устройств, не обладающих достаточными ресурсами для реализации существующих шифров, хеш-функций, электронных подписей и т. д.[2] «Легковесная» криптография приобрела исключительную актуальность в настоящее время в связи распространением парадигмы умного дома, где множество приборов небольшого размера, с ограниченной вычислительной мощностью, лимитированным объёмом памяти и малым энергопотреблением коммуницируют между собой, обмениваясь конфиденциальной информацией жильца, для выполнения своих задач[3][4]. Также особый интерес представляют алгоритмы для RFID меток[5]. Для того, чтобы злоумышленики не воспользовались приватной информацией пользователя, требуется специальная разработка и оптимизация алгоритмов способных работать при ограниченных ресурсах и обеспечивать должный уровень безопасности[4].
Хеш-функции
Применение
Для того, чтобы адресату убедиться в том, что ему было прислано сообщение от настоящего адресанта, оно отправляется вместе с электронной подписью. На практике подписывают не сообщение, а его хеш-сумму, это позволяет значительно уменьшить вычислительные ресурсы на создание подписи (так как обычно хеш-сумма на порядки меньше ключа) и повысить криптостойкость (злоумышленник не сможет узнать исходные данные только из хеша)[6]. Хеш-функции используются в технологии блокчейн для того, чтобы определить блок, который добавится в общую цепь. Например: для добавления нового блока в платформу Bitcoin требуется найти хеш-сумму SHA-256 меньше, чем определённое целевое число. В следующий созданный блок будет записан хеш предыдущего[7]. Более того, хеш-функции, в частности хеш-функции облегчённой криптографии могут применяться на стыке дисциплин. Например: они применяются в блокчейне LSB, который предназначен для использования в интернете вещей[8].
Также хеш-суммы используются при проверке паролей. Если бы операционные системы хранили пароли в файлах, то взломщики с помощью несанкционированного доступа смогли бы получить к ним доступ, извлечение хеша, в свою очередь, им ничего не даст[9].
Требования
Основные требования к хеш-функциям облегчённой криптографии такие же, как и к обычным криптографическим хеш-функциям[10]:
- Стойкость к восстановлению первого прообраза — при наличии хеш-суммы <math>H(m)</math> невозможность вычислить <math>m</math>
- Стойкость к восстановлению вторых прообразов — при наличии <math>m</math> невозможность найти <math>n</math>, такое что <math>H(n) = H(m)</math>
- Стойкость к коллизиям — невозможность найти <math>m</math> и <math>n</math>, такие что <math>H(n) = H(m)</math>[11]
Принимая в расчёт возможности вычислительных устройств, на которых будут производиться алгоритмы, а также задачи, которые требуется выполнить, к основным требованиям добавляются специальные:
- Малое потребление энергии
- Небольшой размер внутреннего состояния[2]
Атаки на хеш-функции
- Атака «дней рождения» — используется для поиска коллизии второго рода, эксплуатирует парадокс дней рождения. Для успешной атаки число обращений к хеш-функции должно составлять примерно <math>2^{\frac n 2}</math>, а квантовым компьютерам <math>2^{\frac n 3}</math>[12]
- Шаблон:Не переведено 2 — эффективна для атак на хеш-функций и шифров, которые используют LFSR[13]
- Шаблон:Не переведено 2 — разработана для хеш-функций, использующих блочные и потоковые шифры[14]
- Шаблон:Не переведено 2 — действенны для хеш-функций с блочными шифрами[15]
- Атака методом бумеранга — усовершенствованная дифференциальная атака, которая успешно применяется к хеш-функциям[16]. Так, например, для нахождения коллизий SHA-0 с помощью этой атаки потребовался всего лишь один час на обычном ПК[17]
- Атака удлинением сообщения — применяется для хеш-функций, основанных на структуре Меркла — Дамгора[18]. Суть атаки заключается в добавлении новых битов в конец сообщения. Среди уязвимых функций: MD5 и SHA-1[19][20]
- Мультиколлизионная атака Жу[21] — направлена на хеш-функции, использующие в качестве своей основы функцию губки, которая распространена среди функций облегчённой криптографии
- Rebound атака — предназначена для AES-подобных алгоритмов[22]
- Шаблон:Не переведено 2 — создана для взлома хеш-функций, основанных на ARX (сравнение по модулю-битовый сдвиг-XOR)[23]
Виды хеширований
Меркл — Дамгор
Основная идея
Допустим, нам дан вектор инициализации <math>IV</math>: <math> \{0, 1\}^n</math>(фиксированный и открытый), функция сжатия <math>h</math> отображающая <math>\{0,1\}^n\times\{0,1\}^k</math> в <math>\{0,1\}^n</math> и сообщение <math>m = (m_0, m_1, ..., m_{L-1})</math>, где <math>m_i</math> блок из <math>k</math> битов, если <math>m</math> не кратно <math>k</math>, то последний блок мы дополняем 1 и нулями[18]. Например: если
<math>m = 123456789</math>,
то на вход мы подаём <math>2</math> блока:
<math>12345678\quad 91000000</math>,
где единица добавляется для избежания коллизий. Теперь можно определить хеш-функцию <math>H</math>:
- <math>c_0 = IV</math>
- <math>c_{i+1} = h(c_i, m_i)</math>
- <math>H(m) = d = c_L</math>
Усовершенствованный алгоритм
Для усиления защиты от атак, основанных на расширении входного сообщения, можно добавить новый блок, в котором будет записана длина сообщения[18]. В данном случае это будет:
<math>12345678\quad 91000000\quad 00000009</math>
Также есть оптимизация, которая позволяет экономить ресурсы памяти (что важно для задач облегчённой криптографии): если в последнем блоке достаточно места для записи длины сообщения, то она будет там и записана:
<math>12345678\quad 91000009</math>
Функция губки
Функция губки широко используется в криптографии, с помощью неё создаются алгоритмы ГПСЧ[24], потоковых и блочных шифров, а также хеш-функций[25].
Основная идея
Губку размера <math>b</math> можно разделить на 2 части: битовую скорость <math>r</math> и мощность <math>c</math>. При инициализации внутреннее состояние губки обнуляется; сообщение <math>m</math> дополняется нулями, чтобы его размер был кратен <math>r</math>.
Далее следуют <math>2</math> стадии:
- Абсорбция
- Первые <math>r</math> бит внутреннего состояния заменяются результатом операции XOR этих бит и очередного блока исходного сообщения
- Внутреннее состояние обрабатывается функцией перестановки
- Выжимание
П-губка и Т-губка
П(ерестановочная)-губка и Т(рансформационная)-губка — губки, использующие соответственно случайную перестановку и ГПСЧ для обновления своего внутреннего состояния. В статье, в которой были введены функции губки, было показано, что губки с мощностью <math>c</math>, битовой скоростью <math>r</math> и вектором размера <math>n</math>, принимающие на вход сообщения длиной <math>m < 2^\frac c 2</math>, таковы, что для различных атак в среднем требуется следующее количество обращений к функциям обновлении(приведены степени двойки)[26]:
Губка | Первый прообраз | Второй прообраз | Коллизия | Нахождение цикла |
---|---|---|---|---|
T-губка | <math>\min(n, c+r)</math> | <math>\min(n, c-\log_2(m))</math> | <math>\min(n, c)/2</math> | <math>(c+r)/2</math> |
П-губка | <math>c-1</math> | <math>\min(n, c/2)</math> | <math>\min(n, c)/2</math> | <math>c+r</math> |
JH-губка
JH-губку называют так, потому что она похожа на структуру хеш-функции JH.
У неё стадия абсорбции состоит из трёх частей:
- Первые <math>r</math> бит внутреннего состояния заменяются результатом операции XOR этих бит и очередного блока исходного сообщения
- Внутреннее состояние обрабатывается функцией перестановки
- Последние <math>r</math> бит внутреннего состояния заменяются результатом операции XOR этих бит и очередного блока исходного сообщения[27]
Примеры хеш-функций в облегчённой криптографии
GLUON
GLUON — это хеш-функция, использующая T-губку, основанную на программно-ориентированных потоковых шифрах X-FCSR-v2 и F-FCSR-H-v3[28]: внутреннее состояние губки дополняется и загружается в FCSR, который синхронизируется за фиксированное количество времени. Затем некоторые ячейки FCSR складываются по модулю 2 для формирования первого слова следующего внутреннего состояния, FCSR синхронизируется, эти же слова складываются по модулю 2 для формирования второго слова следующего внутреннего состояния и т. д.
Функция обладает высокой криптографической стойкостью. Например: атака нахождения прообраза в общем случае имеет сложность <math>2^\frac {3\omega r} {2}</math> , где <math>\omega \times \omega </math> — размер матрицы <math>T</math> (которая определяет FCSR), а <math>r</math> - размер слова, подаваемого на FCSR.
Особенность реализации GLUON состоит в том, что данные в FCSR записываются не последовательно, а параллельно, что значительно повышает скорость исполнения. Также был оптимизирован adder (элемент, осуществляющий сложение), который используется в FCSR, следующим образом: <math>s = (a \oplus b) \oplus c</math>, где <math>c = (a.b) \oplus (a \oplus b ).c</math> (здесь <math>.</math> используется в качестве обозначения логического И)[29].
Функция обновления GLUON-64 является многозначной, и её поведение сильно отличается от поведения ГПСЧ.
QUARK
QUARK — это хеш-функция, использующая П-губку с аппаратно-ориентированной перестановкой. Была реализована под влиянием облегчённых блочных шифров KTANTAN[30] и KATAN[30] и аппаратно-ориентированного потокового шифра Grain[31]. Наименьшая версия (хеш-сумма длиной 136 бит) называется U-QUARK, средняя (176 бит) D-QUARK и самая длинная (256 бит) S-QUARK.
Функция обновления отображает вектор <math>\{0,1\}^b</math> в <math>\{0,1\}^b</math>, загружая каждую половину в отдельный Шаблон:Не переведено 2 длины <math>\frac b 2</math>, а затем повторяет это <math>4b</math> раза. NFSR связаны друг с другом и с небольшим LFSR длины <math>\log(4b)</math>. Функции <math>f</math>, <math>g</math> и <math>h</math> являются булевыми функциями, выбранными из-за их нелинейности и алгебраической сложности. <math>f</math> и <math>g</math> одинаковы для всех версий и заимствованы из Grain-v1, а <math>h</math> определяется отдельным случаем.
Специфика реализации QUARK состоит в том, что в ней отсутствуют промежуточные значения функции губки, которые требуют дополнительных элементов для их запоминания. Другими словами, после перестановки значений состояния значения не записываются в следующее состояние, а сразу подаются на функцию перестановки, причём первые <math>r</math> бит делают XOR с сообщением[32].
Обладает высокой криптостойкостью. Данные по резистентности к различным атакам приведены ниже[32]:
Коллизии | Первого прообраза | Второго прообраза |
---|---|---|
<math>2^\frac c 2</math> | <math>2^c</math> | <math>2^\frac c 2</math> |
У данной хеш-функции есть реализация в открытом доступе, написанная на языке C.
SipHash-2-4
SipHash имеет структуру ARX, которая была создана под влиянием BLAKE и Skein. Он собой предоставляет семейство отображений <math>\{0,1\}^*\rightarrow\{0,1\}^{64}</math>, и предназначен для использования в качестве 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 итераций (для каждого параметра безопасности) ниже описанной последовательности преобразований, выполненных на квадрате <math>d \times d</math> ячеек из 4 бит (8 бит для самой большой версии). Конвейер PHOTON состоит из 4 этапов:
- Дополнительные константы (AddConstants) — дополнительные константы выбираются так, чтобы быть разными на каждой итерации, и чтобы отсутствовала симметрия между столбцами, как в AES подобных архитектурах (без этого слоя входное сообщение с равными столбцами будет сохранять это качество спустя любое количество итераций). Дополнительные константы могут быть сгенерированы регистром сдвига с линейной обратной связью. Для высокой производительности задействован только первый столбец внутреннего состояния. После того, как константы были сгенерированы, они складываются по модулю 2 с каждой ячейкой.
- Замена ячеек (SubCells) — S-блок применяется на каждой ячейке. Если ячейка имеет длину 4 бита, то используется PRESENT Sbox SBOXPRE, если 8 бит — AES Sbox SBOXAES.
- Сдвиг строк (ShiftRows) — идентичен AES.
- MixColumnsSerial — ячейки рассматриваются как элементы поля Галуа <math>{\displaystyle GF(2^{4})}
</math> (или <math>GF(2^8)</math> для наибольшего параметра безопасности), и каждый столбец умножается на матрицу MDS, специально созданной для эффективной реализации в аппаратном обеспечении[35].
Данные по криптостойкости:
Коллизии | Первого прообраза | Второго прообраза |
---|---|---|
<math>2^\frac n 2</math> | <math>2^ {n-r}</math> | <math>2^\frac n 2</math> |
Способ перестановки, используемый для обновления губки, близок к LED[36] шифру, который был разработан позже создателями PHOTON.
SPONGENT
SPONGENT можно рассматривать как П-губку, где перестановка является модифицированной версией блочного шифра PRESENT.
Число итераций PRESENT-подобной перестановки варьируется от 45 для SPONGENT-88 до 140 для SPONGENT-256. Каждая итерация состоит из:
- Складывания по модулю 2 содержимого LFSR, синхронизированного на каждой итерации (может рассматриваться, как константа на итерации)
- Применение к слою S-блока S-блок 4×4, удовлетворяющий тем же критериям, что и PRESENT S-блок
- Переставляя биты способом, подобным в 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].
См. также
Литература
- ↑ Шаблон:Книга
- ↑ 2,0 2,1 Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ 4,0 4,1 Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Книга
- ↑ Шаблон:Статья
- ↑ Шаблон:Книга
- ↑ Шаблон:Книга
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ 18,0 18,1 18,2 Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ 24,0 24,1 Шаблон:Статья
- ↑ 25,0 25,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
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ 30,0 30,1 Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ 32,0 32,1 Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ 34,0 34,1 Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья