Эта статья входит в число добротных статей

SWIFFT

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Криптографическая
хеш-функция
Название

SWIFFT

Разработчики

Вадим Любашевский, Даниель Мичьянчио, Крис Пейкерт, Алон Розен

Создан

2008

Опубликован

2008

Тип

хеш-функция

SWIFFT — это набор криптографических хеш-функций с доказанной стойкостью[1][2][3]. Они основываются на быстром преобразовании Фурье (БПФ, англ. Fast Fourier Transform, FFT) и используют алгоритм 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]

  1. Берётся неприводимый многочлен над
  2. На вход подаётся сообщение длины
  3. преобразуется в набор из полиномов в определённом кольце многочленов с двоичными коэффициентами
  4. Рассчитываются коэффициенты Фурье для каждого
  5. Задаются фиксированные коэффициенты Фурье в зависимости от семейства SWIFFT
  6. Попарно перемножаются коэффициенты Фурье с для каждого
  7. Используется обратное преобразование Фурье для того, чтобы получить многочленов степени не более
  8. Рассчитается по модулю и .
  9. преобразуется в битов и отправляются их на выход

Пример[править | править вики-текст]

Конкретные значения для параметров 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 должен быть степенью двойки
  • p должен быть простым числом
  • p-1 должно делиться на 2n
  • m

Можно взять, например, такие параметры: n=64, m=16, p=257. Мы берём пропускную способность на уровне 40Мб/с[6], защищённость от поиска коллизий — операций.

Статистические свойства[править | править вики-текст]

  • Универсальное хэширование. Семейство функций SWIFFT является универсальным[1]. Иными словами, для любых различных фиксированных и случайно выбранной функции из семейства вероятность, что выполнится равенство , обратно пропорциональна величине выбранного диапазона.
  • Регулярность. Функции из семейства сжимающих функций SWIFFT — регулярные[1].
  • Генератор энтропии. SWIFFT является генератором энтропии[en][1]. Для хэш-таблиц и приложений, связанных с ними, желательно, чтобы ключи для значений, поданных в функцию, были распределены равномерно (или близко к равномерному распределению), даже если входные значения распределены неравномерно. Хэш-функции, которые ведут себя подобным образом, называются генераторами энтропии, потому как они могут представить неравномерно распределённые параметры (почти) равномерными на выходе. Формально, данным свойством обычно обладает семейство функций, из которого была выбрана одна функция случайным образом.

Криптографический свойства и безопасность[править | править вики-текст]

  • SWIFFT не является псевдослучайной функцией[en] из-за линейности[1]. Для произвольной функции из семейства SWIFFT справедливо следующее: для двух входных параметров , таких, что тоже может быть входным параметром, выполнено . Выполнение данного соотношения не подходит к случайной функции, и злоумышленник сможет легко отличить нашу функцию от случайной.
  • Для семейства функций SWIFFT доказана криптографическая стойкость к коллизиям (в асимптотическом смысле) при относительно умеренном предположении о сложности задачи нахождения коротких векторов в циклических/идеальных решётках в худшем случае. Это значит, что семейство функций SWIFFT также устойчиво к атаке нахождения второго прообраза[4][16].

Теоретическая стойкость[править | править вики-текст]

SWIFFT — криптографические функции с доказанной стойкостью[en][1][3]. Как и в большинстве случаев, доказательство стойкости функций основывается на том, что математическую задачу, используемую в функциях, нельзя решить за полиномиальное время. Это значит, что стойкость SWIFFT заключается только в том, что в основе лежит сложная математическая задача.

В случае SWIFFT доказанная стойкость заключается в задаче поиска коротких векторов в циклических/идеальных решётках[en][17]. Можно доказать, что справедливо следующее утверждение: предположим, у нас есть алгоритм, который может найти коллизии функции для случайной версии SWIFFT, полученной от , за некоторое возможное время с вероятностью . Значит, алгоритм, работает только на небольшой, но заметной доле функций семейства. Тогда мы можем также найти алгоритм , который сможет всегда находить короткий вектор на любой идеальной решётке над кольцом за некоторое возможное время , зависящее от и . Это значит, что нахождение коллизий в SWIFFT не менее сложное, задача нахождения коротких векторов в решётке над , для решения которой существуют только экспоненциальные алгоритмы.

Практическая стойкость[править | править вики-текст]

Авторы данной хэш-функции исследовали её на уязвимости к различным атакам и установили, что атака «дней рождения» требует меньше всего операций подсчёта хэша (2106) для поиска коллизий.[18][1]. Атаки с перестановками требуют 2448 операций подсчёта для стандартных параметров. Полный перебор возможных значений потребует 2528 операций подсчёта хэша. Этого, как правило, достаточно для того, чтобы сделать нападение противника невозможным.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

Книги[править | править вики-текст]

  • Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.

Статьи[править | править вики-текст]