Быстрый синдром на основе хэша

В криптографии быстрые синдромные хэш-функции (FSB) представляют собой семейство криптографических хэш-функций, представленных в 2003 году Даниэлем Ого, Матье Финиасом и Николя Сендрие. ^[1] В отличие от большинства других криптографических хэш-функций, используемых сегодня, можно в определенной степени доказать, что FSB является безопасным. Точнее, можно доказать, что взлом FSB по крайней мере так же сложен, как решение определенной NP-полной задачи, известной как регулярное декодирование синдрома , поэтому FSB является доказуемо безопасным . Хотя неизвестно, разрешимы ли NP-полные задачи за полиномиальное время , часто предполагается, что это не так.

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

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

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

Основа этой функции состоит из (случайно выбранной) двоичной матрицы , которая действует на сообщение битов путем умножения матриц . Здесь мы кодируем -битное сообщение как вектор в , -мерном векторном пространстве над полем из двух элементов, поэтому на выходе будет сообщение битов.${\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}$
• Слово веса и длины называется регулярным , если в каждом интервале оно содержит ровно одну ненулевую запись для всех . Более интуитивно это означает, что если мы разобьем сообщение на w равных частей, то каждая часть будет содержать ровно одну ненулевую запись.${\displaystyle w}$${\displaystyle n}$${\ displaystyle [(i-1) (n/w), я (n/w))}$${\displaystyle 0<i<w+1}$

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

1. ввод: сообщение размером${\displaystyle с}$
2. преобразовать в обычное слово длины и веса${\displaystyle n}$${\displaystyle w}$
3. умножить на матрицу${\displaystyle H}$
4. вывод: хэш размера${\displaystyle r}$

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

1. Ввод: сообщение размером${\displaystyle с}$
2. Преобразовать в последовательность чисел от 1 до${\displaystyle с}$${\displaystyle w}$${\displaystyle s_{1},\точки ,s_{w}}$${\displaystyle н/б}$
3. Сложите соответствующие столбцы матриц, чтобы получить двоичную строку длиной${\displaystyle H_{i}}$${\displaystyle r}$
4. Вывод: хэш размера${\displaystyle r}$

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

Ситуация и инициализация : Хешировать сообщение, используя матрицу H , которая разделена на подблоки , , .${\displaystyle s=010011}$${\displaystyle 4\times 12}$
${\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 с}$${\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. Из первой подматрицы выбираем столбец 2, из второй подматрицы — столбец 1 и из третьей подматрицы — столбец 4.${\displaystyle H_{1}}$${\displaystyle H_{2}}$
4. Складываем выбранные столбцы и получаем результат .${\displaystyle r=0111\oplus 0001\oplus 1001=1111}$

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

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

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

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

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

Как уже было сказано, безопасность FSB зависит от проблемы, называемой регулярным декодированием синдрома (RSD) . Декодирование синдрома изначально является проблемой теории кодирования, но его NP-полнота делает его хорошим приложением для криптографии. Регулярное декодирование синдрома является частным случаем декодирования синдрома и определяется следующим образом:

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

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

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

Нам все еще нужно доказать устойчивость к коллизиям. Для этого нам понадобится еще одна NP-полная вариация RSD: 2-регулярное декодирование синдрома нуль .

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

Также было доказано, что 2-RNSD является NP-полной задачей путем сведения к 3-мерному соответствию .

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

Предположим, что мы нашли коллизию, поэтому у нас есть Hash( m ₁ ) = Hash( m ₂ ) с . Тогда мы можем найти два обычных слова и такие, что . Тогда у нас есть ; является суммой двух различных обычных слов и поэтому должно быть 2-регулярным словом, хеш которого равен нулю, поэтому мы решили пример 2-RNSD. Мы приходим к выводу, что поиск коллизий в FSB по крайней мере так же сложен, как решение 2-RNSD, и поэтому должен быть NP-полным.${\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 используют функцию сжатия Whirlpool для дальнейшего сжатия выходного хэша. Хотя это не может быть доказано, авторы утверждают, что это последнее сжатие не снижает безопасность. Обратите внимание, что даже если бы удалось найти коллизии в Whirlpool, все равно пришлось бы найти прообразы коллизий в исходной функции сжатия FSB, чтобы найти коллизию в FSB.

Решая RSD, мы оказываемся в ситуации, противоположной той, что и при хешировании. Используя те же значения, что и в предыдущем примере, нам дается разделение на подблоки и строку . Нас просят найти в каждом подблоке ровно один столбец, такой, чтобы все они в сумме давали . Таким образом, ожидаемый ответ — , , . Известно, что это трудно вычислить для больших матриц.${\displaystyle H}$${\displaystyle w=3}$${\displaystyle r=1111}$${\displaystyle r}$${\displaystyle s_{1}=1}$${\displaystyle s_{2}=0}$${\displaystyle s_{3}=3}$

В 2-RNSD мы хотим найти в каждом подблоке не один столбец, а два или ноль, чтобы их сумма равнялась 0000 (а не ). В этом примере мы могли бы использовать столбцы (отсчет от 0) 2 и 3 из , ни одного столбца из столбца 0 и 2 из . Возможны и другие решения, например, можно не использовать столбцы из .${\displaystyle r}$${\displaystyle H_{1}}$${\displaystyle H_{2}}$${\displaystyle H_{3}}$${\displaystyle H_{3}}$

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

В следующей таблице показана сложность наиболее известных атак на ФСБ.

FSB — это ускоренная версия синдромной хэш-функции (SB). В случае SB функция сжатия очень похожа на функцию кодирования версии криптосистемы Мак-Элиса Нидеррайтера . Вместо использования матрицы проверки четности переставленного кода Гоппы , SB использует случайную матрицу . С точки зрения безопасности это может только усилить систему.${\displaystyle H}$

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

В 2007 году был опубликован IFSB. ^[3] В 2010 году был опубликован S-FSB, который на 30% быстрее оригинала. ^[4]

В 2011 году DJ Bernstein и Tanja Lange опубликовали RFSB, который в 10 раз быстрее оригинального FSB-256. ^[5] Было показано, что RFSB работает очень быстро на Spartan 6 FPGA, достигая пропускной способности около 5 Гбит/с.> ^[6]

• Сайт ФСБ для конкурса SHA-3