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

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Хеш-функция облегчённой криптографии — криптостойкая хеш-функция, используемая в «легковесной» криптографии[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]

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

  1. Атака «дней рождения» — используется для поиска коллизии второго рода, эксплуатирует парадокс дней рождения. Для успешной атаки число обращений к хеш-функции должно составлять примерно <math>2^{\frac n 2}</math>, а квантовым компьютерам <math>2^{\frac n 3}</math>[12]
  2. Шаблон:Не переведено 2 — эффективна для атак на хеш-функций и шифров, которые используют LFSR[13]
  3. Шаблон:Не переведено 2 — разработана для хеш-функций, использующих блочные и потоковые шифры[14]
  4. Шаблон:Не переведено 2 — действенны для хеш-функций с блочными шифрами[15]
  5. Атака методом бумеранга — усовершенствованная дифференциальная атака, которая успешно применяется к хеш-функциям[16]. Так, например, для нахождения коллизий SHA-0 с помощью этой атаки потребовался всего лишь один час на обычном ПК[17]
  6. Атака удлинением сообщения — применяется для хеш-функций, основанных на структуре Меркла — Дамгора[18]. Суть атаки заключается в добавлении новых битов в конец сообщения. Среди уязвимых функций: MD5 и SHA-1[19][20]
  7. Мультиколлизионная атака Жу[21] — направлена на хеш-функции, использующие в качестве своей основы функцию губки, которая распространена среди функций облегчённой криптографии
  8. Rebound атака — предназначена для AES-подобных алгоритмов[22]
  9. Шаблон:Не переведено 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> стадии:

  1. Абсорбция
    • Первые <math>r</math> бит внутреннего состояния заменяются результатом операции XOR этих бит и очередного блока исходного сообщения
    • Внутреннее состояние обрабатывается функцией перестановки
  1. Выжимание
    • Считываются первые <math>r</math> бит внутреннего состояния губки
    • Внутреннее состояние обрабатывается функцией перестановки[24][25]

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

П(ерестановочная)-губка и Т(рансформационная)-губка — губки, использующие соответственно случайную перестановку и ГПСЧ для обновления своего внутреннего состояния. В статье, в которой были введены функции губки, было показано, что губки с мощностью <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.

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

  1. Первые <math>r</math> бит внутреннего состояния заменяются результатом операции XOR этих бит и очередного блока исходного сообщения
  2. Внутреннее состояние обрабатывается функцией перестановки
  3. Последние <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 этапов:

  1. Дополнительные константы (AddConstants) — дополнительные константы выбираются так, чтобы быть разными на каждой итерации, и чтобы отсутствовала симметрия между столбцами, как в AES подобных архитектурах (без этого слоя входное сообщение с равными столбцами будет сохранять это качество спустя любое количество итераций). Дополнительные константы могут быть сгенерированы регистром сдвига с линейной обратной связью. Для высокой производительности задействован только первый столбец внутреннего состояния. После того, как константы были сгенерированы, они складываются по модулю 2 с каждой ячейкой.
  2. Замена ячеек (SubCells) — S-блок применяется на каждой ячейке. Если ячейка имеет длину 4 бита, то используется PRESENT Sbox SBOXPRE, если 8 бит — AES Sbox SBOXAES.
  3. Сдвиг строк (ShiftRows) — идентичен AES.
  4. 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. Каждая итерация состоит из:

  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].

См. также

Литература

Шаблон:Примечания

Шаблон:Криптография

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Книга
  2. ↑ 2,0 2,1 Шаблон:Статья
  3. ↑ Шаблон:Статья
  4. ↑ 4,0 4,1 Шаблон:Статья
  5. ↑ Шаблон:Статья
  6. ↑ Шаблон:Статья
  7. ↑ Шаблон:Статья
  8. ↑ Шаблон:Статья
  9. ↑ Шаблон:Статья
  10. ↑ Шаблон:Статья
  11. ↑ Шаблон:Книга
  12. ↑ Шаблон:Статья
  13. ↑ Шаблон:Книга
  14. ↑ Шаблон:Книга
  15. ↑ Шаблон:Статья
  16. ↑ Шаблон:Статья
  17. ↑ Шаблон:Статья
  18. ↑ 18,0 18,1 18,2 Шаблон:Статья
  19. ↑ Шаблон:Статья
  20. ↑ Шаблон:Статья
  21. ↑ Шаблон:Статья
  22. ↑ Шаблон:Статья
  23. ↑ Шаблон:Статья
  24. ↑ 24,0 24,1 Шаблон:Статья
  25. ↑ 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
  26. ↑ Шаблон:Статья
  27. ↑ Шаблон:Статья
  28. ↑ Шаблон:Статья
  29. ↑ Шаблон:Статья
  30. ↑ 30,0 30,1 Шаблон:Статья
  31. ↑ Шаблон:Статья
  32. ↑ 32,0 32,1 Шаблон:Статья
  33. ↑ Шаблон:Статья
  34. ↑ 34,0 34,1 Шаблон:Статья
  35. ↑ Шаблон:Статья
  36. ↑ Шаблон:Статья
  37. ↑ Шаблон:Статья
  38. ↑ Шаблон:Статья
  39. ↑ Шаблон:Статья
  40. ↑ Шаблон:Статья
  41. ↑ Шаблон:Статья
  42. ↑ Шаблон:Статья
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Хеш-функция_облегчённой_криптографии&oldid=11244395