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

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

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

Функция сжатия${\displaystyle \varphi }$ обладает параметрами${\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 \varphi }$ была функцией сжатия, поэтому вход должен быть больше, чем выход. Позже мы используем конструкциюМеркла-Дамгарда для расширения входного домена для сообщений произвольной длины.

Основой этой функции состоит из (случайно выбранной)${\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)}$ содержится ровно один ненулевой элемент для всех. Это означает, что если мы делим сообщение на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 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}$.

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

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

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^{\prime }}$ столбцов, либо два, либо ни одного в каждом${\displaystyle H_i}$, составляющих 0, где. Нужно найти такой набор столбцов.Было доказано, что этот метод NP-полон, уходом от трёхмерного паросочетания.

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

Предположим, что мы нашли коллизию: Hash(m₁) = Hash(m₂) при${\displaystyle m_1\ne m_2}$. Тогда мы можем найти два регулярных слова${\displaystyle w_1}$ и${\displaystyle w_2}$ такие, что${\displaystyle H{w}_1=H{w}_2}$. Мы тогда получаем${\displaystyle H(w_1+w_2)=H{w}_1+H{w}_2=2H{w}_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:

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

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

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

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

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

• Хеш-функции
• Алгоритмы

• Википедия:Cite web (не указан язык)
• ПРО:ИТ:Статьи по алфавиту
• ПРО:ИТ:Последняя правка: в прошлом году