Fast Syndrome Based Hash

FSB (Fast Syndrome-Based Hash Function) — это набор криптографических хеш-функций, созданный в 2003 году и представленный в 2008 году как кандидат на конкурс SHA-3. В отличие от многих хеш-функций, используемых на текущий момент, криптографическая стойкость FSB может быть доказана в определённой степени. Доказывает стойкость FSB то, что взломать FSB столь же трудно, как решить некоторую NP-полную задачу, известную как регулярное синдромное декодирование. Хоть всё же и не известно, являются ли NP-полные задачи разрешимы за полиномиальное время, как правило считается, что нет.

Fast Syndrome Based Hash
Разработчики	Даниэль Огот, Мэтью Финиаш, Николя Сандрие
Создан	2003
Опубликован	2008
Размер хеша	160, 224, 256, 384, 512
Тип	хеш-функция

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

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

Описание хеш-функции

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

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

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

Определения

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

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

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

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

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

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

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

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

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

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

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

Алгоритм:

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

Доказательство криптостойкости FSB

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

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

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

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

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

Устойчивость к нахождению прообраза

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

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

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

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

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

Устойчивость к коллизиям

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

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

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

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

Примеры

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

Линейный криптоанализ

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

Результаты безопасности на практике

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

Размер выхода (бит)	Сложность поиска коллизий	Сложность инверсии
160	2100.3	2163.6
224	2135.3	2229.0
256	2190.0	2261.0
384	2215.5	2391.5
512	2285.6	2527.4

Другие свойства

• Размер входного и выходного блока хеш-функции полностью масштабируемы.
• Скорость можно регулировать путём изменения количества битовых операций, используемых FSB на входной бит.
• Безопасность может быть отрегулирован путём регулировки выходного размера.
• Плохие случаи всё же существуют, и необходимо позаботиться при выборе матрицы $H$.
• Матрица, используемая в функции сжатия, может стать огромной в определённых случаях.

Варианты

Последнее может создавать затруднения при использовании FSB на устройствах с относительно небольшой памятью.

Эта проблема была решена в 2007 году, в соответствующей хеш-функции, называемой IFSB (Improved Fast Syndrome Based Hash), которая до сих пор доказуемо безопасна, но полагается на несколько более сильные предположения.

В 2010 году была представлена S-FSB, имеющая скорость, на 30 % превышающую FSB.

В 2011 году Дэниел Джулиус Бернштейн и Таня Ланге представили RFSB, что 10-кратно превышало скорость FSB-256. RFSB, будучи запущеным на машине Spartan 6 FPGA, достигал пропускной способности до 5 Гбит/с.