11-05-2023
Криптографическая хеш-функция |
|
Название |
SWIFFT |
---|---|
Разработчики |
Вадим Любашевский, Даниель Мичьянчио, Крис Пейкерт, Алон Розен |
Создан |
2008 |
Опубликован |
2008 |
Тип |
SWIFFT — это набор криптографических хеш-функций с доказанной стойкостью[1][2][3]. Они основываются на быстром преобразовании Фурье (БПФ) и используют алгоритм LLL-редуцированных базисов[en]. Криптографическая стойкость SWIFFT (в асимптотическом смысле)[4] математически доказана при использовании рекомендуемых параметров [5]. Поиск коллизий в SWIFFT в худшем случае требует не меньше временных затрат, чем нахождение коротких векторов в циклических/идеальных решётках[en]. Практическое применение SWIFFT будет ценно именно в тех случаях, когда стойкость к коллизиям особенно важна. Например, цифровые подписи, которые должны оставаться надёжными длительное время.
Данный алгоритм обеспечивает пропускную способность порядка 40 Мб/с на процессоре Intel Pentium 4 с тактовой частотой 3,2 ГГц[6][1]. Было проведено исследование, направленное на ускорение БПФ, которое используется в SWIFFT[7]. Как результат, скорость работы алгоритма удалось увеличить более чем в 13 раз[6]. Данная реализация SWIFFT оказалась быстрее, чем реализации широко распространенных хэш-функций[8].
На конкурсе Национального института стандартов и технологий США[2] 2012 года был предложен SWIFFTX (модификация SWIFFT) в качестве SHA-3 (на замену более старых SHA-2 и особенно SHA-1[9]), но был отклонён в первом раунде[10].
Функции SWIFFT могут быть описаны как простое алгебраическое выражение над некоторым кольцом многочленов [1][11]. Семейство функций зависит от трёх основных параметров : пусть будет степенью числа 2, — небольшое целое число, и — не обязательно простое число, но лучше выбрать его простым. Определим как кольцо вида . Например, кольцо многочленов в , у которых коэффициенты — целые числа, — число, на которое выполняем деление по модулю, и . Элемент из может быть многочленом степени не меньше с коэффициентами из .
Определённая функция в семействе SWIFFT задаётся как фиксированных элементов кольца , называемых мультипликаторами. Данную функцию над кольцом можно записать в следующем виде:
,
где — многочлены с двоичными коэффициентами, соответствующие двоичному входному сообщению длины .
Алгоритм работы следующий:[1][12][11]
Конкретные значения для параметров n, m и p выбраны следующим образом: n = 64, m= 16, p= 257[13]. Для данных параметров любая фиксированная сжимающая функция семейства примет на вход сообщение длины mn = 1024 бит(128 байт). Выходные данные лежат в диапазоне , который имеет размер . Выходные данные в могут быть представлены, используя 528 бит (66 байт).
Самое сложное в вычисление приведённого выше выражения — вычислить результат перемножения [1][14]. Быстрый способ вычислить данное произведение — это использовать теорему о свёртке[en], которая утверждает, что при определённых условиях выполнено:
Здесь обозначает преобразование Фурье, а операция означает перемножение коэффициентов с одинаковым индексом. В общем случае теоремы о свёртке имеет значение свёртки, а не перемножения. Однако, можно показать, что перемножение многочленов является свёрткой.
Для нахождения преобразования Фурье мы используем Быстрое преобразование Фурье (БПФ), которое выполняется за [1]. Алгоритм перемножения следующий[14]: мы рассчитываем все коэффициенты Фурье для всех многочленов сразу с помощью БПФ. Затем мы попарно перемножаем соответствующие коэффициенты Фурье двух многочленов. После мы используем обратное БПФ, после чего получим многочлен степени не выше .
Вместо обычного преобразования Фурье в SWIFFT используется дискретное преобразование Фурье (ДПФ)[1][14]. Оно использует корни из единицы в вместо комплексных корней из единицы. Это будет справедливо, если — конечное поле, и его 2nth простых корня из единицы существуют в данном поле. Данные условия будут выполнены, если взять такое простое число , что делится на .
Параметры m,p,n должны удовлетворят следующим требованиям[15]:
Можно взять, например, такие параметры: n=64, m=16, p=257. Мы берём пропускную способность на уровне 40Мб/с[6], защищённость от поиска коллизий — операций.
SWIFFT — криптографические функции с доказанной стойкостью[en][1][3]. Как и в большинстве случаев, доказательство стойкости функций основывается на том, что математическую задачу, используемую в функциях, нельзя решить за полиномиальное время. Это значит, что стойкость SWIFFT заключается только в том, что в основе лежит сложная математическая задача.
В случае SWIFFT доказанная стойкость заключается в задаче поиска коротких векторов в циклических/идеальных решётках[en][17]. Можно доказать, что справедливо следующее утверждение: предположим, у нас есть алгоритм, который может найти коллизии функции для случайной версии SWIFFT, полученной от , за некоторое возможное время с вероятностью . Значит, алгоритм, работает только на небольшой, но заметной доле функций семейства. Тогда мы можем также найти алгоритм , который сможет всегда находить короткий вектор на любой идеальной решётке над кольцом за некоторое возможное время , зависящее от и . Это значит, что нахождение коллизий в SWIFFT не менее сложное, задача нахождения коротких векторов в решётке над , для решения которой существуют только экспоненциальные алгоритмы.
Авторы данной хэш-функции исследовали её на уязвимости к различным атакам и установили, что атака «дней рождения» требует меньше всего операций подсчёта хэша (2106) для поиска коллизий.[18][1]. Атаки с перестановками требуют 2448 операций подсчёта для стандартных параметров. Полный перебор возможных значений потребует 2528 операций подсчет хэша. Этого, как правило, достаточно для того, чтобы сделать нападение противника невозможным.
Хеш-функции | |
---|---|
Общего назначения | |
Криптографические |
CubeHash • BLAKE • BMW • ECHO • FSB • Fugue • Grøstl • JH • Hamsi • HAVAL • Keccak (SHA-3) • Kupyna • LM-хеш • Luffa • MD2 • MD4 • MD5 • MD6 • N-Hash • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 • SHA-1 • SHA-2 • SHABAL • SHAvite-3 • SIMD • Skein • Snefru • SWIFFT • Tiger • Whirlpool • ГОСТ Р 34.11-94 • ГОСТ Р 34.11-2012 |
Функции формирования ключа |