Fast Syndrome Based Hash

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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