Хэш на основе быстрого синдрома

Хэш-функция на основе быстрого синдрома (FSB)
Общий
Дизайнеры	Даниэль Ого , Матье Финиас , Николя Сендрие
Впервые опубликовано	2003
Получено из	Криптосистема МакЭлиса и криптосистема Нидеррайтера
Преемники	Улучшена хэш-функция на основе быстрого синдрома.
Связано с	Хэш-функция на основе синдрома
Деталь
Размеры дайджеста	Масштабируемый

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

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

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

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

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

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

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

ввод: сообщение размера $s$
преобразовать в обычное слово длины $n$ и вес $w$
умножить на матрицу $H$
вывод: хеш размера $r$

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

Входные данные: сообщение размера $s$
Конвертировать $s$ к последовательности $w$ цифры $s_{1},\dots ,s_{w}$ между 1 и $n/w$
Добавьте соответствующие столбцы матриц $H_{i}$ чтобы получить двоичную строку длиной $r$
Вывод: хэш размера $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}$ .

Алгоритм :

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

Доказательство безопасности ФСБ

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

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

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

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

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

Сопротивление прообразу и декодирование регулярного синдрома (RSD)

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

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

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

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

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

Устойчивость к коллизиям и декодирование 2-регулярного нулевого синдрома (2-RNSD)

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

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

Точно так же, как RSD по сути эквивалентен поиску обычного слова $w$ такой, что $Hw=S$ , 2-RNSD эквивалентно нахождению 2-правильного слова $w'$ такой, что $Hw'=0$ . 2-правильное слово длины $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})$ представляет собой сумму двух разных правильных слов и, следовательно, должно быть 2-правильным словом, хэш которого равен нулю, поэтому мы решили случай 2-RNSD. Мы приходим к выводу, что поиск коллизий в FSB по крайней мере так же сложен, как и решение 2-RNSD, и поэтому должен быть NP-полным.

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

Примеры

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

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

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

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

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

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

Размер вывода (биты)	Сложность поиска коллизий	Сложность инверсии
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 — это ускоренная версия хеш-функции на основе синдрома (SB). В случае SB функция сжатия очень похожа на функцию кодирования Нидеррайтера версии криптосистемы МакЭлиса . Вместо использования матрицы проверки четности перестановочного кода Гоппы , SB использует случайную матрицу. $H$ . С точки зрения безопасности это может только укрепить систему.

Другие объекты недвижимости

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

Варианты

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

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

Ссылки

^ Ого, Д.; Финиас, М.; Сендриер, Н. (2003), Быстрая доказуемо безопасная криптографическая хеш-функция.
^ Сааринен, Маркку-Юхани О. (2007), «Атаки линеаризации против хэшей, основанных на синдромах», Progress in Cryptology – INDOCRYPT 2007 (PDF) , Конспекты лекций по информатике, том. 4859, стр. 1–9, номер домена : 10.1007/978-3-540-77026-8_1 , ISBN. 978-3-540-77025-1 , получено 12 ноября 2022 г.
^ Jump up to: ^а ^б Финиас, М.; Габорит, П.; Сендриер, Н. (2007), Улучшенные криптографические хеш-функции на основе быстрого синдрома (PDF) , ECRYPT Hash Workshop 2007, заархивировано из оригинала (PDF) 3 марта 2016 г. , получено 4 января 2010 г.
^ Мезиани, Мохаммед; Дагделен, Озгюр; Кайрел, Пьер-Луи; Эль Юсфи Алауи, Сиди Мохамед (2011). «S-FSB: улучшенный вариант семейства хэшей FSB» (PDF) . Информационная безопасность и гарантия . Коммуникации в компьютерной и информатике. Том. 200. С. 132–145. дои : 10.1007/978-3-642-23141-4_13 . ISBN 978-3-642-23140-7 . Архивировано из оригинала (PDF) 22 декабря 2015 г. Проверено 10 декабря 2014 г.
^ Бернштейн, Дэниел Дж.; Ланге, Таня; Петерс, Кристиана; Швабе, Питер (2011), «Действительно быстрое хеширование на основе синдромов», Progress in Cryptology – AFRICACRYPT 2011 (PDF) , Конспекты лекций по информатике, том. 6737, стр. 134–152, номер документа : 10.1007/978-3-642-21969-6_9 , ISBN. 978-3-642-21968-9 , получено 12 ноября 2022 г.
^ фон Маурих, Инго; Гюнейсу, Тим (2012), «Встроенное хеширование на основе синдромов», Progress in Cryptology - INDOCRYPT 2012 (PDF) , Конспекты лекций по информатике, том. 7668, стр. 339–357, номер doi : 10.1007/978-3-642-34931-7_20 , ISBN. 978-3-642-34930-0 , заархивировано из оригинала (PDF) 2 мая 2015 г. , получено 10 декабря 2014 г.

Внешние ссылки

Сайт ФСБ конкурса ША-3

[1] Ого, Д.; Финиас, М.; Сендриер, Н. (2003), Быстрая доказуемо безопасная криптографическая хеш-функция.

[2] Сааринен, Маркку-Юхани О. (2007), «Атаки линеаризации против хэшей, основанных на синдромах», Progress in Cryptology – INDOCRYPT 2007 (PDF) , Конспекты лекций по информатике, том. 4859, стр. 1–9, номер домена : 10.1007/978-3-540-77026-8_1 , ISBN. 978-3-540-77025-1 , получено 12 ноября 2022 г.

[Finiasz-2007-3] Jump up to: ^а ^б Финиас, М.; Габорит, П.; Сендриер, Н. (2007), Улучшенные криптографические хеш-функции на основе быстрого синдрома (PDF) , ECRYPT Hash Workshop 2007, заархивировано из оригинала (PDF) 3 марта 2016 г. , получено 4 января 2010 г.

[4] Мезиани, Мохаммед; Дагделен, Озгюр; Кайрел, Пьер-Луи; Эль Юсфи Алауи, Сиди Мохамед (2011). «S-FSB: улучшенный вариант семейства хэшей FSB» (PDF) . Информационная безопасность и гарантия . Коммуникации в компьютерной и информатике. Том. 200. С. 132–145. дои : 10.1007/978-3-642-23141-4_13 . ISBN 978-3-642-23140-7 . Архивировано из оригинала (PDF) 22 декабря 2015 г. Проверено 10 декабря 2014 г.

[5] Бернштейн, Дэниел Дж.; Ланге, Таня; Петерс, Кристиана; Швабе, Питер (2011), «Действительно быстрое хеширование на основе синдромов», Progress in Cryptology – AFRICACRYPT 2011 (PDF) , Конспекты лекций по информатике, том. 6737, стр. 134–152, номер документа : 10.1007/978-3-642-21969-6_9 , ISBN. 978-3-642-21968-9 , получено 12 ноября 2022 г.

[6] фон Маурих, Инго; Гюнейсу, Тим (2012), «Встроенное хеширование на основе синдромов», Progress in Cryptology - INDOCRYPT 2012 (PDF) , Конспекты лекций по информатике, том. 7668, стр. 339–357, номер doi : 10.1007/978-3-642-34931-7_20 , ISBN. 978-3-642-34930-0 , заархивировано из оригинала (PDF) 2 мая 2015 г. , получено 10 декабря 2014 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]