Хеш-функция на основе быстрого синдрома

В криптографии быстрые синдромные хеш-функции (FSB) являются семейство криптографических хэш-функций, представленных в 2003 году Даниэлем Ауго, Матье Финиасом и Николя Сендриером. В отличие от большинства других криптографических хеш-функций, используемых сегодня, FSB в определенной степени может быть доказана как безопасная. Точнее, можно доказать, что взлом FSB не менее сложен, чем решение определенной NP-полной проблемы, известной как обычное синдромное декодирование, поэтому FSB доказуемо безопасна. Хотя неизвестно, разрешимы ли NP-полные задачи за полиномиальное время, часто предполагается, что это не так.

Было предложено несколько версий FSB, последняя из которых была представлена ​​на конкурс SHA-3 криптографии, но была отклонена в первом раунде. Хотя все версии ФСБ заявляют о доказуемой безопасности, некоторые предварительные версии в конечном итоге были сломаны. Однако конструкция последней версии FSB учла эту атаку и остается защищенной от всех известных в настоящее время атак.

Как обычно, доказуемая безопасность имеет свою цену. FSB работает медленнее, чем традиционные хеш-функции, и использует довольно много памяти, что делает ее непрактичной в средах с ограниченным объемом памяти. Кроме того, функция сжатия, используемая в FSB, требует большого размера вывода, чтобы гарантировать безопасность. Эта последняя проблема была решена в последних версиях путем простого сжатия вывода с помощью другой функции сжатия, называемой Whirlpool. Однако, хотя авторы утверждают, что добавление этого последнего сжатия не снижает безопасность, оно делает невозможным формальное доказательство безопасности.

• 1 Описание хеш-функции
  • 1.1 Определения
  • 1.2 Функция сжатия
  • 1.3 Пример сжатия
• 2 Доказательство безопасности FSB
  • 2.1 Сопротивление прорисовке и декодирование обычного синдрома (RSD)
  • 2.2 Устойчивость к коллизиям и декодирование 2-регулярного нулевого синдрома (2-RNSD)
  • 2.3 Примеры
  • 2.4 Линейный криптоанализ
  • 2.5 Практические результаты безопасности
• 3 Genesis
• 4 Другие свойства
• 5 Варианты
• 6 Ссылки
• 7 Внешние ссылки

Начнем с функции сжатия $\varphi \; \{\backslash \; displaystyle\; \backslash \; phi\}$с параметрами $n,\; r,\; w\; \{\backslash \; displaystyle\; \{n,\; r,\; w\}\}$такими, что $n>w\; \{\backslash \; displaystyle\; n>w\}$и <18 журнал ⁡ (п / ш)>r {\ displaystyle w \ log (n / w)>r}. Эта функция будет работать только с сообщениями длиной $s\; =\; w\; log\; \; (n\; /\; w)\; \{\backslash \; displaystyle\; s\; =\; w\; \backslash \; log\; (n\; /\; w)\}$; $r\; \{\backslash \; displaystyle\; r\}$будет размер вывода. Кроме того, нам нужны $n,\; r,\; w,\; s\; \{\backslash \; displaystyle\; n,\; r,\; w,\; s\}$и $log\; \; (n\; /\; w)\; \{\backslash \; displaystyle\; \backslash \; log\; (n\; /\; w)\}$как натуральные числа, где $log\; \{\backslash \; displaystyle\; \backslash \; log\}$обозначает двоичный логарифм. Причина $w\; \cdot \; log\; \; (n\; /\; w)>r\; \{\backslash \; displaystyle\; w\; \backslash \; cdot\; \backslash \; log\; (n\; /\; w)>r\}$- это то, что нам нужно $\varphi \; \{\backslash \; displaystyle\; \backslash \; phi\}$быть функцией сжатия, поэтому входные данные должны быть больше, чем выходные. Позже мы будем использовать конструкцию Меркла – Дамгарда, чтобы расширить область до входов произвольной длины.

Базис этой функции состоит из (случайно выбранной) двоичной $r\; \times \; n\; \{\backslash \; displaystyle\; r\; \backslash \; times\; n\}$матрицы $H\; \{\backslash \; displaystyle\; H\}$, которая действует на сообщение из $n\; \{\backslash \; displaystyle\; n\}$бит на матричное умножение. Здесь мы кодируем $w\; log\; \; (n\; /\; w)\; \{\backslash \; displaystyle\; w\; \backslash \; log\; (n\; /\; w)\}$-битовое сообщение как вектор в $(F\; 2)\; n\; \{\backslash \; displaystyle\; (\backslash \; mathbf\; \{F\}\; \_\; \{2\})\; ^\; \{n\}\}$, $n\; \{\backslash \; displaystyle\; n\}$-мерное векторное пространство над fi eld из двух элементов, поэтому на выходе будет сообщение из $r\; \{\backslash \; displaystyle\; r\}$бит.

В целях безопасности, а также для увеличения скорости хеширования мы хотим использовать только «обычные слова с весом $w\; \{\backslash \; displaystyle\; w\}$» в качестве входных данных для нашей матрицы.

Определения

• Сообщение называется словом веса $w\; \{\backslash \; displaystyle\; w\}$и длины $n\; \{\backslash \; displaystyle\; n\}$если он состоит из $n\; \{\backslash \; displaystyle\; n\}$битов, и ровно $w\; \{\backslash \; displaystyle\; w\}$из этих битов равны единице.
• A слово веса $w\; \{\backslash \; displaystyle\; w\}$и длины $n\; \{\backslash \; displaystyle\; n\}$называется обычным, если в каждом интервале $[(я\; -\; 1)\; (п\; /\; ш),\; я\; (п\; /\; ш))\; \{\backslash \; displaystyle\; [(я-1)\; (п\; /\; ш),\; я\; (п\; /\; ш))\}$это содержит ровно одну ненулевую запись для всех . Более интуитивно это означает, что если мы разделим сообщение на w равных частей, то каждая часть будет содержать ровно одну ненулевую запись.

Функция сжатия

Ровно $(n\; /\; w)\; w\; \{\backslash \; displaystyle\; (n\; /\; w)\; ^\; \{w\}\}$различные регулярные слова веса $w\; \{\backslash \; displaystyle\; w\}$и длины $n\; \{\backslash \; displaystyle\; n\}$, поэтому нам нужно ровно $журнал\; \; ((n\; /\; w)\; w)\; =\; w\; log\; \; (n\; /\; w)\; =\; s\; \{\backslash \; displaystyle\; \backslash \; log\; ((n\; /\; w)\; ^\; \{w\})\; =\; w\; \backslash \; log\; (n\; /\; w)\; =\; s\}$битов данных для кодирования этих обычных слов. Мы фиксируем биекцию из набора битовых строк длины $s\; \{\backslash \; displaystyle\; s\}$на набор регулярных слов веса $w\; \{\backslash \; displaystyle\; w\}$и длина $n\; \{\backslash \; displaystyle\; n\}$, а затем функция сжатия FSB определяется следующим образом:

1. input: сообщение размера $s\; \{\backslash \; displaystyle\; s\}$
2. convert на обычное слово длины $n\; \{\backslash \; displaystyle\; n\}$и веса $w\; \{\backslash \; displaystyle\; w\}$
3. умножить на матрицу $H\; \{\backslash \; displaystyle\; H\}$
4. вывод: хэш размера $r\; \{\backslash \; displaystyle\; r\}$

Эта версия обычно называется синдромным сжатием . Это очень медленно и на практике выполняется другим, более быстрым способом, что приводит к быстрому синдромному сжатию . Мы разбиваем $H\; \{\backslash \; displaystyle\; H\}$на субматрицы $H\; i\; \{\backslash \; displaystyle\; H\_\; \{i\}\}$размером $r\; \times \; n\; /\; w.\; \{\backslash \; displaystyle\; r\; \backslash \; times\; n\; /\; w\}$, и мы исправляем взаимное соответствие из битовых строк длины $w\; log\; \; (n\; /\; w)\; \{\backslash \; displaystyle\; w\; \backslash \; log\; (n\; /\; w)\}$к набору последовательностей $w\; \{\backslash \; displaystyle\; w\}$чисел от 1 до $n\; /\; w\; \{\backslash \; displaystyle\; n\; /\; w\}$. Это эквивалентно взаимно однозначному отображению набора обычных слов длины $n\; \{\backslash \; displaystyle\; n\}$и веса $w\; \{\backslash \; displaystyle\; w\}$, поскольку мы можем рассматривайте такое слово как последовательность чисел от 1 до $n\; /\; w\; \{\backslash \; displaystyle\; n\; /\; w\}$. Функция сжатия выглядит следующим образом:

1. Вход: сообщение размера $s\; \{\backslash \; displaystyle\; s\}$
2. Преобразование $s\; \{\backslash \; displaystyle\; s\}$в последовательность $w\; \{\backslash \; displaystyle\; w\}$числа $s\; 1,\dots ,\; sw\; \{\backslash \; displaystyle\; s\_\; \{1\},\; \backslash \; dots,\; s\_\; \{w\}\}$между 1 и $n\; /\; w\; \{\backslash \; displaystyle\; n\; /\; w\}$
3. Добавьте соответствующие столбцы матриц $H\; i\; \{\backslash \; displaystyle\; H\_\; \{i\}\}$, чтобы получить двоичную строку длиной $r\; \{\backslash \; displaystyle\; r\}$
4. Вывод: хэш размера $r\; \{\backslash \; displaystyle\; r\}$

Теперь мы можем использовать конструкцию Меркла – Дамгарда, чтобы обобщить функцию сжатия для приема входных данных произвольной длины.

Пример сжатия

Ситуация и инициализация : Хеширование сообщения $s\; =\; 010011\; \{\backslash \; displaystyle\; s\; =\; 010011\}$с использованием $4\; \times \; 12\; \{\; \backslash \; displaystyle\; 4\; \backslash \; times\; 12\}$матрица H. $H\; =\; (1\; 0\; 1\; 1\; 0\; 1\; 0\; 0\; 1\; 0\; 1\; 1\; 0\; 1\; 0\; 0\; 0\; 1\; 1\; 1\; 0\; 1\; 0\; 0\; 0\; 1\; 1\; 1\; 0\; 1\; 0\; 0\; 1\; 0\; 1\; 0\; 1\; 1\; 0\; 0\; 1\; 0\; 1\; 1\; 0\; 0\; 0\; 1)\; \{\backslash \; displaystyle\; H\; =\; \backslash \; left\; (\{\backslash \; begin\; \{array\}\; \{llllcllllcllll\}\; 1\; 0\; 1\; 1\; ~\; 0\; 1\; 0\; 0\; ~\; 1\; 0\; 1\; 1\; \backslash \backslash \; 0\; 1\; 0\; 0\; ~\; 0\; 1\; 1\; 1\; 1\; ~\; 0\; 1\; 0\; 0\; \backslash \backslash \; 0\; 1\; 1\; 1\; ~\; 0\; 1\; 0\; 0\; ~\; 1\; 0\; 1\; 0\; \backslash \backslash \; 1\; 1\; 0\; 0\; ~\; 1\; 0\; 1\; 1\; ~\; 0\; 0\; 0\; 1\; \backslash \; end\; \{array\}\}\; \backslash \; right)\}$., которое разделено на $w143\; =\; 3\; \{\backslash \; displaystyle\; 62>субблоки$ H\; 1\; \{\backslash \; displaystyle\; H\_\; \{1\}\}$$, $H\; 2\; \{\backslash \; displaystyle\; H\_\; \{2\}\}$, $H\; 3\; \{\backslash \; displaystyle\; H\_\; \{3\}\}$.

Алгоритм :

1. Мы разбиваем ввод $s\; \{\backslash \; displaystyle\; s\}$на $w\; =\; 3\; \{\backslash \; displaystyle\; w\; =\; 3\}$части длины $log\; 2\; \; (\; 12/3)\; =\; 2\; \{\backslash \; displaystyle\; \backslash \; log\; \_\; \{2\}\; (12/3)\; =\; 2\}$, и мы получаем $s\; 1\; =\; 01\; \{\backslash \; displaystyle\; s\_\; \{1\}\; =\; 01\}$, $s\; 2\; =\; 00\; \{\backslash \; displaystyle\; s\_\; \{2\}\; =\; 00\}$, $s\; 3\; =\; 11\; \{\backslash \; displaysty\; le\; s\_\; \{3\}\; =\; 11\}$.
2. Мы конвертируем каждый $si\; \{\backslash \; displaystyle\; s\_\; \{i\}\}$в целое число и получаем $s\; 1\; =\; 1\; \{\backslash \; displaystyle\; s\_\; \{1\; \}\; =\; 1\}$, $s\; 2\; =\; 0\; \{\backslash \; displaystyle\; s\_\; \{2\}\; =\; 0\}$, $s\; 3\; =\; 3\; \{\backslash \; displaystyle\; s\_\; \{3\}\; =\; 3\}$.
3. Из первой подматрицы $H\; 1\; \{\backslash \; displaystyle\; H\_\; \{1\}\}$, мы выбираем столбец 2 из второй подматрицы $H\; 2\; \{\backslash \; displaystyle\; H\_\; \{2\}\}$столбец 1 и из третьей подматрицы столбец 4.
4. Складываем выбранные столбцы и получаем результат $r\; =\; 0111\; \oplus \; 0001\; \oplus \; 1001\; =\; 1111\; \{\backslash \; displaystyle\; r\; =\; 0111\; \backslash \; oplus\; 0001\; \backslash \; oplus\; 1001\; =\; 1111\}$.

Доказано, что конструкция Меркла – Дамгарда основывает свою безопасность только на безопасности используемой функции сжатия. Таким образом, нам нужно только показать, что функция сжатия $\varphi \; \{\backslash \; displaystyle\; \backslash \; phi\}$безопасна.

Криптографическая хеш-функция должна быть защищена в трех различных аспектах:

1. Устойчивость к предварительному изображению: с учетом хэша h должно быть сложно найти сообщение m такое, что Hash (m) = h
2. Сопротивление второго прообраза: учитывая сообщение m 1, должно быть сложно найти сообщение m 2 такое, что Hash (m 1) = Хэш (m 2)
3. Устойчивость к столкновениям: должно быть трудно найти два разных сообщения m 1 и m 2, такие что Hash (m 1) = Hash (m 2)

Обратите внимание, что если злоумышленник может найти второй прообраз, то он обязательно найдет коллизию. Это означает, что если мы сможем доказать, что наша система устойчива к коллизиям, это обязательно будет второй прообраз.

Обычно в криптографии «жесткий» означает что-то вроде «почти наверняка вне досягаемости любого злоумышленника, которому необходимо предотвратить взлом системы». Однако нам потребуется более точное значение слова «жесткий». трудно иметь в виду «Время выполнения любого алгоритма, обнаруживающего коллизию или пре-иму ge будет экспоненциально зависеть от размера хеш-значения ». Это означает, что за счет относительно небольших добавлений к размеру хэша мы можем быстро достичь высокой безопасности.

Сопротивление прообразу и декодирование регулярного синдрома (RSD)

Как было сказано ранее, безопасность FSB зависит от проблемы, называемой декодирование обычного синдрома (RSD) . Синдромное декодирование изначально является проблемой из теории кодирования, но его NP-полнота делает его прекрасным приложением для криптографии. Декодирование обычного синдрома является частным случаем декодирования синдрома и определяется следующим образом:

Определение RSD: данные $w\; \{\backslash \; displaystyle\; w\}$матрицы $ЧАС\; я\; \{\backslash \; Displaystyle\; H\_\; \{i\}\}$измерения $r\; \times \; (n\; /\; w)\; \{\backslash \; displaystyle\; r\; \backslash \; times\; (n\; /\; w)\}$и a битовая строка $S\; \{\backslash \; displaystyle\; S\}$длины $r\; \{\backslash \; displaystyle\; r\}$такая, что существует набор из $w\; \{\backslash \; displaystyle\; w\}$столбцы, по одному в каждом $H\; i\; \{\backslash \; displaystyle\; H\_\; \{i\}\}$, в сумме до $S\; \{\backslash \; displaystyle\; S\}$. Найдите такой набор столбцов.

Доказано, что эта проблема NP-полная путем сокращения с 3-мерного сопоставления. Опять же, хотя неизвестно, существуют ли алгоритмы полиномиального времени для решения NP-полных задач, ни один из них не известен, и его обнаружение было бы огромным открытием.

Легко видеть, что поиск прообраза заданного хэша $S\; \{\backslash \; displaystyle\; S\}$в точности эквивалентен этой задаче, поэтому проблема поиска предварительных образы в ФСБ также должны быть NP-полными.

Нам все еще нужно доказать устойчивость к столкновениям. Для этого нам понадобится еще один NP-полный вариант RSD: декодирование 2-регулярного нулевого синдрома .

Устойчивость к столкновениям и декодирование 2-регулярного нулевого синдрома (2-RNSD)

Определение 2-RNSD: Для $w\; \{\backslash \; displaystyle\; w\}$матриц $H\; i\; \{\backslash \; displaystyle\; H\_\; \{i\}\}$размерности $r\; \times \; (n\; /\; w)\; \{\backslash \; displaystyle\; r\; \backslash \; times\; (n\; /\; w)\}$и битовая строка $S\; \{\backslash \; displaystyle\; S\}$длиной $r\; \{\backslash \; displaystyle\; r\}$такой, что существует набор из $w\; \prime \; \{\backslash \; displaystyle\; w\; \text{'}\}$столбцов, по два или ноль в каждом $H\; i\; \{\backslash \; displaystyle\; H\_\; \{i\}\}$, суммируя до нуля. . Найдите такой набор столбцов.

2-RNSD также оказался NP-полным путем сокращения с 3-мерного соответствие.

Точно так же, как RSD, по сути, эквивалентно поиску обычного слова $w\; \{\backslash \; displaystyle\; w\}$такого, что $H\; w\; =\; S\; \{\backslash \; displaystyle\; Hw\; =\; S\}$, 2-RNSD эквивалентно поиску 2-регулярного слова $w\; \prime \; \{\backslash \; displaystyle\; w\; \text{'}\}$такого, что $H\; w\; \prime \; =\; 0\; \{\backslash \; displaystyle\; Hw\text{'}\; =\; 0\; \}$. 2-правильное слово длины $n\; \{\backslash \; displaystyle\; n\}$и веса $w\; \{\backslash \; displaystyle\; w\}$- это бит строка длины $n\; \{\backslash \; displaystyle\; n\}$такая, что в каждом интервале $[(i\; -\; 1)\; w,\; iw)\; \{\backslash \; displaystyle\; [(i-1)\; w,\; iw)\}$ровно два или ноль элементов равны 1. Обратите внимание, что 2-правильное слово - это просто сумма двух правильных слов.

Предположим, что мы обнаружили коллизию, поэтому у нас есть Hash (m 1) = Hash (m 2) с $m\; 1\; \ne \; m\; 2\; \{\; \backslash \; Displaystyle\; m\_\; \{1\}\; \backslash \; neq\; m\_\; \{2\}\}$. Затем мы можем найти два обычных слова $w\; 1\; \{\backslash \; displaystyle\; w\_\; \{1\}\}$и $w\; 2\; \{\backslash \; displaystyle\; w\_\; \{2\}\}$такие, что $Час\; вес\; 1\; знак\; равно\; ЧАС\; вес\; 2\; \{\backslash \; Displaystyle\; Hw\_\; \{1\}\; =\; Hw\_\; \{2\}\}$. Тогда имеем $H\; (w\; 1\; +\; w\; 2)\; =\; H\; w\; 1\; +\; H\; w\; 2\; =\; 2\; H\; w\; 1\; =\; 0\; \{\backslash \; displaystyle\; H\; (w\_\; \{1\}\; +\; w\_\; \{2\})\; =\; Hw\_\; \{1\}\; +\; Hw\_\; \{2\}\; =\; 2Hw\_\; \{1\}\; =\; 0\}$; $(w\; 1\; +\; w\; 2)\; \{\backslash \; displaystyle\; (w\_\; \{1\}\; +\; w\_\; \{2\})\}$- сумма двух различных регулярных слова и, следовательно, должны быть 2-регулярным словом с нулевым хешем, поэтому мы решили экземпляр 2-RNSD. Мы пришли к выводу, что обнаружение коллизий в FSB не менее сложно, чем решение 2-RNSD, и поэтому должно быть NP-полным.

Последние версии FSB используют функцию сжатия Whirlpool для дальнейшего сжатия выходных хеш-данных. Хотя это не может быть доказано, авторы утверждают, что это последнее сжатие не снижает безопасность. Обратите внимание, что даже если бы можно было найти коллизии в Whirlpool, все равно нужно было бы найти предварительные изображения коллизий в исходной функции сжатия FSB, чтобы найти коллизию в FSB.

Примеры

Решая RSD, мы находимся в ситуации, противоположной той, что и при хешировании. Используя те же значения, что и в предыдущем примере, мы получаем $H\; \{\backslash \; displaystyle\; H\}$, разделенные на $w\; =\; 3\; \{\backslash \; displaystyle\; w\; =\; 3\}$sub -блоки и строка $r\; =\; 1111\; \{\backslash \; displaystyle\; r\; =\; 1111\}$. Нас просят найти в каждом субблоке ровно один столбец, чтобы все они в сумме составляли $r\; \{\backslash \; displaystyle\; r\}$. Ожидаемый ответ, таким образом, $s\; 1\; =\; 1\; \{\backslash \; displaystyle\; s\_\; \{1\}\; =\; 1\}$, $s\; 2\; =\; 0\; \{\backslash \; displaystyle\; s\_\; \{2\}\; =\; 0\}$, $s\; 3\; =\; 3\; \{\backslash \; displaystyle\; s\_\; \{3\}\; =\; 3\}$. Известно, что это сложно вычислить для больших матриц.

В 2-RNSD мы хотим найти в каждом подблоке не один столбец, а два или ноль, чтобы их сумма составляла 0000 (а не $r\; \{\backslash \; displaystyle\; r\}$). В этом примере мы можем использовать столбец (считая от 0) 2 и 3 из $H\; 1\; \{\backslash \; displaystyle\; H\_\; \{1\}\}$, без столбца из $H\; 2\; \{\backslash \; displaystyle\; H\_\; \{\; 2\}\}$столбец 0 и 2 из $H\; 3\; \{\backslash \; displaystyle\; H\_\; \{3\}\}$. Возможны и другие решения, например, можно не использовать столбцы из $H\; 3\; \{\backslash \; displaystyle\; H\_\; \{3\}\}$.

Linear cryptanalysis

доказуемая безопасность FSB означает, что поиск коллизии NP-полны. Но доказательство сводится к проблеме с асимптотически жесткой сложностью наихудшего случая. Это дает только ограниченную гарантию безопасности, поскольку все еще может существовать алгоритм, который легко решает проблему для подмножества проблемного пространства. Например, существует метод линеаризации, который можно использовать для создания коллизий за считанные секунды на настольном ПК для ранних вариантов системной шины с заявленной безопасностью 2 ^ 128. Показано, что хеш-функция обеспечивает минимальную стойкость к предварительному изображению или столкновениям, когда пространство сообщений выбирается определенным образом.

Практические результаты защиты

В следующей таблице показана сложность наиболее известных атак на FSB.

FSB - это ускоренная версия синдромальной хеш-функции (SB). В случае SB функция сжатия очень похожа на функцию кодирования версии Нидеррайтера из криптосистемы Мак-Элиса. Вместо использования матрицы проверки на четность переставленного кода Гоппы, SB использует случайную матрицу $H\; \{\backslash \; displaystyle\; H\}$. С точки зрения безопасности это может только укрепить систему.

• Размер блока хеш-функции и размер вывода полностью масштабируемы.
• Скорость можно регулировать, регулируя количество побитовых операций, используемых FSB на каждом входе бит.
• Безопасность можно настроить, настроив размер вывода.
• Существуют плохие экземпляры, и нужно соблюдать осторожность при выборе матрицы $H\; \{\backslash \; displaystyle\; H\}$.
• Матрица, используемая в функции сжатия, в определенных ситуациях может увеличиваться. Это может быть ограничением при попытке использовать FSB на устройствах с ограниченным объемом памяти. Эта проблема была решена в связанной хэш-функции под названием Improved FSB, которая по-прежнему доказуемо безопасна, но опирается на несколько более строгие предположения.

В 2007 году был опубликован IFSB. В 2010 году была опубликована S-FSB, которая на 30% быстрее оригинала.

В 2011 году D. J. Bernstein и Tanja Lange опубликовали RFSB, который в 10 раз быстрее, чем исходный FSB-256. Было показано, что RFSB работает очень быстро на Spartan 6 FPGA, достигая пропускной способности около 5 Гбит / с.

• Веб-сайт FSB для SHA -3 соревнование