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

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

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

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

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

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

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

Определения

Сообщением называется слово веса ${\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

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

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

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

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

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

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

Как было сказано ранее, криптостойкость 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:

Размер выхода (бит)	Сложность поиска коллизий	Сложность инверсии
160	2 100.3	2 163.6
224	2 135.3	2 229.0
256	2 190.0	2 261.0
384	2 215.5	2 391.5
512	2 285.6	2 527.4

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

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

Варианты

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

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

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

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

Примечания