Как рассчитываются шифры SHACAL-2?

Jan 12 2021

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

Один из методов хеширования - это использование конструкции Меркель-Дамгарда с функцией Дэвида Мейерса и блочными шифрами SHACAL-2.

Насколько я понимаю, MD - это сообщение, разделенное на цепочку из 64-битных блоков, содержащих значение предыдущего блока или IV (начальный вектор, определенный хеш-функцией или настраиваемым солевым ключом). Значение блока или IV вместе с текущим значением блока и некоторым x-битовым ключом после прохождения функции SHACAL-2, а затем нового шифра.

Это правильно понято? Если это так: что происходит внутри функции SHACAL? Что такое математика?

Я нашел это, но на самом деле это не отвечает на мой вопрос: SHACAL в SHA-256

Ответы

2 kelalaka Jan 12 2021 at 18:13

Конструкция MD использует функцию сжатия $C$ ($F$ на рисунках), так что у него есть два входа.

$$h_i = C(h_{i-1},m_i)$$

и первый $h_{-1} = IV$ и последнее $H = h_{2^k-1}$ это хеш-значение.

Функция сжатия может использовать блочный шифр, где сообщение для блочного шифра - это предыдущее значение хеш-функции, а ключ - это сообщение. $h_i = E_{m}(h_{i-1})$

Первое описание использования блочного шифра для функции сжатия существует в диссертации Меркла на странице 11 . Эта конструкция совершенно небезопасна, поскольку существующий блочный шифр напрямую связан цепочкой, и можно показать, что он имеет$\mathcal{O}(2^{n/2})$ сопротивление второму прообразу вместо $\mathcal{O}(2^{n})$.

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

Нам нужны большие входные данные из-за атак на столкновение с функциями сжатия [1] и, следовательно, больше раундов для обработки. Поэтому дизайнеры создают новый блочный шифр для конструкций МД вместо использования существующих. Для SHA-1 он называется SHACAL, а для SHA-2 - SHACAL-2.

Значение деления зависит от функции сжатия, MD5, SHA-1 и SHA256 используют 512-битные блоки сообщений, SHA512 использует 1024-битные блоки сообщений. Сообщения дополняются так, чтобы быть кратными размеру блока, при этом размер сообщения кодируется в конце.

Например, заполнение SHA-512 в NIST FIPS 180-4

Предположим, что длина сообщения, $M$, является $\ell$биты. Добавьте бит 1в конец сообщения, а затем$k$ нулевые биты, где $k$ - наименьшее неотрицательное решение уравнения $$\ell + 1 + k \equiv 896 \bmod 1024$$ Затем добавьте 128-битный блок, равный числу $\ell$ выражается с использованием двоичного представления

Формализовать под произвольный размер блока $b$ и $d$размер сообщения, закодированного в битах (64 для SHA-1 и SHA256, 128 для SHA512.

$$\ell + 1 + k \equiv b-d \bmod b$$

Таким образом, критерии разработки включают блочный шифр с множеством раундов, SHACAL - 80, SHA-256 - 64, а SHA512 - 80 раундов, сохраняя при этом простую функцию раунда.

А блочный шифр используется Дэвисом-Мейером для создания функции одностороннего сжатия.

Например, математика для SHA256:

  • $\operatorname{Ch}(E,F,G) = (E \land F) \oplus (\neg E \land G)$
  • $\operatorname{Ma}(A,B,C) = (A \land B) \oplus (A \land C) \oplus (B \land C)$
  • $\Sigma_0(A) = (A\!\ggg\!2) \oplus (A\!\ggg\!13) \oplus (A\!\ggg\!22)$
  • $\Sigma_1(E) = (E\!\ggg\!6) \oplus (E\!\ggg\!11) \oplus (E\!\ggg\!25)$

Побитовое вращение использует разные константы для SHA-512. Приведены числа для SHA-256.
Красный$\boxplus$ значить $ c = a + b \mod 2^{32}$, т.е. сложение по модулю.

Как мы видим, простые операции, с которыми могут справиться процессоры, легкая круглая функция с немного ухудшенной несбалансированной структурой Фейстеля.

И мы узнали из алгоритма Tiny Encryption, что даже простые раунды могут быть безопасными после 32 раундов.