Fast Syndrome Based Hash

Сообщением называется слово веса ${\displaystyle w}$ и длины ${\displaystyle n}$, если он состоит из ${\displaystyle n}$ битов и именно ${\displaystyle w}$ из этих битов являются ненулевыми.

Слово веса ${\displaystyle w}$ и длины ${\displaystyle n}$ называется регулярным, если в каждом интервале ${\displaystyle [(i-1)w,iw)}$ содержитcя ровно один ненулевой элемент для всех ${\displaystyle 0<i<n/w+1}$. Это означает, что если мы делим сообщение на w равных частей, то каждая часть содержит ровно один ненулевой элемент.

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

1. На вход подаётся сообщение размера ${\displaystyle s}$
2. Преобразование его в регулярное слово веса ${\displaystyle w}$ и длины ${\displaystyle n}$
3. Перемножение с матрицей ${\displaystyle H}$
4. На выходе получаем хеш размера ${\displaystyle r}$

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

1. На вход подаётся сообщение размера ${\displaystyle s}$
2. Преобразование его в последовательность ${\displaystyle w}$ чисел ${\displaystyle s_{1},\dots ,s_{w}}$ от 1 до ${\displaystyle n/w}$
3. Добавляем соответствующие столбцы матриц ${\displaystyle H_{i}}$ для получения двоичной строки длины ${\displaystyle r}$
4. На выходе получаем хеш размера ${\displaystyle r}$

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

Начальные условия:

Хешируем сообщение ${\displaystyle s=010011}$, используя ${\displaystyle 4\times 12}$ матрицу ${\displaystyle H}$
${\displaystyle H=\left({\begin{array}{llllcllllcllll}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\end{array}}\right)}$
которая делится на ${\displaystyle w=3}$ подматрицы ${\displaystyle H_{1}}$, ${\displaystyle H_{2}}$, ${\displaystyle H_{3}}$.

Алгоритм:

1. Делим входящее сообщение ${\displaystyle s}$ на ${\displaystyle w=3}$ части длины ${\displaystyle \log _{2}(12/3)=2}$ и получаем ${\displaystyle s_{1}=01}$, ${\displaystyle s_{2}=00}$, ${\displaystyle s_{3}=11}$.
2. Преобразуем каждую строку ${\displaystyle s_{i}}$ в число и получаем ${\displaystyle s_{1}=1}$, ${\displaystyle s_{2}=0}$, ${\displaystyle s_{3}=3}$.
3. Из первой подматрицы ${\displaystyle H_{1}}$ берём второй столбец, из второй ${\displaystyle H_{2}}$ берём первый, из третьей ${\displaystyle H_{3}}$ — четвёртый.
4. Добавляем выбранные столбцы и получаем результат: ${\displaystyle r=0111\oplus 0001\oplus 1001=1111}$.

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

Даны ${\displaystyle w}$ матриц ${\displaystyle H_{i}}$ размерности ${\displaystyle r\times (n/w)}$ и битовая строка ${\displaystyle S}$ длины ${\displaystyle r}$ такие, что существует набор ${\displaystyle w}$ столбцов, по одному в каждой ${\displaystyle H_{i}}$, составляющих ${\displaystyle S}$. Нужно найти такой набор столбцов.

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

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

Нам все ещё необходимо доказать устойчивость от коллизий. Для этого нам нужна другая NP-полная вариация регулярного синдромного кодирования, называемая «двурегулярное нулевое синдромной декодирование».

Даны ${\displaystyle w}$ матриц ${\displaystyle H_{i}}$ размерности ${\displaystyle r\times (n/w)}$ и битовая строка ${\displaystyle S}$ длины ${\displaystyle r}$. Тогда существует множество ${\displaystyle w'}$ столбцов, либо два, либо ни одного в каждом ${\displaystyle H_{i}}$, составляющих 0, где ${\displaystyle (0<w'<2w)}$. Нужно найти такой набор столбцов. Было доказано, что этот метод NP-полон, уходом от трёхмерного паросочетания.

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

Предположим, что мы нашли коллизию: Hash(m₁) = Hash(m₂) при ${\displaystyle m_{1}\neq m_{2}}$. Тогда мы можем найти два регулярных слова ${\displaystyle w_{1}}$ и ${\displaystyle w_{2}}$ такие, что ${\displaystyle Hw_{1}=Hw_{2}}$. Мы тогда получаем ${\displaystyle H(w_{1}+w_{2})=Hw_{1}+Hw_{2}=2Hw_{1}=0}$, где ${\displaystyle (w_{1}+w_{2})}$ является суммой двух разных регулярных слов и она должна быть двурегулярным словом, хеш которого нуль, так что мы решили задачу двурегулярного нулевого синдромного декодирования. Мы пришли к выводу, что найти столкновения в FSB по крайней мере так же сложно, как решить задачу двурегулярного нулевого синдромного декодирования, и поэтому алгоритм NP-полон.

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

Решая задачу регулярного синдромного декодирования, мы находимся как-бы в противоположно, относительно хеширования. Используя те же значения, что и в предыдущем примере, нам дается ${\displaystyle H}$ разделеная на ${\displaystyle w=3}$ подблока и строка ${\displaystyle r=1111}$. Нам нужно найти в каждом подблоке по одному столбцу, так что они будут представлять собой ${\displaystyle r}$. Таким образом, ожидаемый ответ будет ${\displaystyle s_{1}=1}$, ${\displaystyle s_{2}=0}$, ${\displaystyle s_{3}=3}$. Это, как известно, трудно вычислить для больших матриц. В двурегулярном нулевом синдромном декодировании мы хотим найти в каждом подблоке не одну колонку, а либо две, либо ни одну так, что они будут приводить к ${\displaystyle 0000}$ (а не к ${\displaystyle r}$). В примере, мы могли бы использовать второй и третий столбец (считая от 0) из ${\displaystyle H_{1}}$, ни одного столбца из ${\displaystyle H_{2}}$, нулевой и второй из ${\displaystyle H_{3}}$. Ещё решения возможны, например, не используя ни один столбец из ${\displaystyle H_{3}}$.

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

Таблица показывает сложность наиболее известных аттак против FSB: