SWIFFT

SWIFFT
Разработчики	Вадим Любашевский, Даниель Мичьянчио, Крис Пейкерт, Алон Розен
Создан	2008
Опубликован	2008
Тип	хеш-функция

SWIFFT — набор криптографических хеш-функций с доказанной стойкостью^[1][2][3]. Они основываются на быстром преобразовании Фурье (БПФ, англ. Fast Fourier Transform, FFT) и используют алгоритм LLL-редуцированных базисов^[англ.]. Криптографическая стойкость функций SWIFFT (в асимптотическом смысле)^[4] математически доказана при использовании рекомендуемых параметров^[5]. Поиск коллизий в SWIFFT в худшем случае требует не меньше временных затрат, чем нахождение коротких векторов в циклических/идеальных решётках. Практическое применение 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 могут быть описаны как простое алгебраическое выражение над некоторым кольцом многочленов ${\displaystyle R}$^[1][11]. Семейство функций зависит от трёх основных параметров^{[см. «Выбор параметров»]}: пусть ${\displaystyle n}$ будет степенью числа 2, ${\displaystyle m>0}$ — небольшое целое число, и ${\displaystyle p>0}$ — не обязательно простое число, но лучше выбрать его простым. Определим ${\displaystyle R}$ как кольцо вида ${\displaystyle R=\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)}$. Например, кольцо многочленов в ${\displaystyle \alpha }$, у которых коэффициенты — целые числа, ${\displaystyle p}$ — число, на которое выполняем деление по модулю, и ${\displaystyle \alpha ^{n}+1}$. Элемент из ${\displaystyle R}$ может быть многочленом степени меньшей ${\displaystyle n}$ с коэффициентами из ${\displaystyle Z_{p}}$.

Определённая функция в семействе SWIFFT задаётся как ${\displaystyle m}$ фиксированных элементов ${\displaystyle a_{1},\ldots ,a_{m}\in R}$ кольца ${\displaystyle R}$, называемых мультипликаторами. Данную функцию над кольцом ${\displaystyle R}$ можно записать в следующем виде:

${\displaystyle \sum _{i=1}^{m}(a_{i}\cdot x_{i})}$,

где ${\displaystyle x_{1},\ldots ,x_{m}\in R}$ — многочлены с двоичными коэффициентами, соответствующие двоичному входному сообщению длины ${\displaystyle mn}$.

Алгоритм работы следующий:^[1][12][11]

1. Берётся ${\displaystyle \alpha }$ — неприводимый многочлен над ${\displaystyle \mathbb {Z} [\alpha ]}$
2. На вход подаётся сообщение ${\displaystyle M}$ длины ${\displaystyle mn}$
3. ${\displaystyle M}$ преобразуется в набор из ${\displaystyle m}$ полиномов ${\displaystyle p_{i}}$ в определённом кольце многочленов ${\displaystyle R}$ с двоичными коэффициентами
4. Рассчитываются коэффициенты Фурье для каждого ${\displaystyle p_{i}}$
5. Задаются фиксированные коэффициенты Фурье ${\displaystyle a_{i}}$ в зависимости от семейства SWIFFT
6. Попарно перемножаются коэффициенты Фурье ${\displaystyle p_{i}}$ с ${\displaystyle a_{i}}$ для каждого ${\displaystyle i}$
7. Используется обратное преобразование Фурье для того, чтобы получить ${\displaystyle m}$ многочленов ${\displaystyle f_{i}}$ степени не более ${\displaystyle 2n}$
8. Рассчитается ${\displaystyle f=\sum _{i=1}^{m}(f_{i})}$ по модулю ${\displaystyle p}$ и ${\displaystyle \alpha ^{n}+1}$.
9. ${\displaystyle f}$ преобразуется в ${\displaystyle n\log(p)}$ битов и отправляются их на выход

• Операцию быстрого преобразования Фурье на 4 шаге легко обратить. Она проводится для того, чтобы добиться путаницы^[англ.] — смешивания битов, поданных на вход.
• Линейная комбинация на 6 шаге приводит к путанице^[англ.], потому как она сжимает входные данные.

Пример

Конкретные значения для параметров n, m и p выбраны следующим образом: n = 64, m= 16, p= 257^[13]. Для данных параметров любая фиксированная сжимающая функция семейства примет на вход сообщение длины mn = 1024 бит(128 байт). Выходные данные лежат в диапазоне ${\displaystyle \mathbb {Z} _{p}^{n}}$, который имеет размер ${\displaystyle p^{n}=257^{64}}$. Выходные данные в ${\displaystyle \mathbb {Z} _{p}^{n}}$ могут быть представлены, используя 528 бит (66 байт).

Вычисление результата перемножения многочленов

Самое сложное в вычислении приведённого выше выражения — вычислить результат перемножения ${\displaystyle a_{i}\cdot x_{i}}$^[1][14]. Быстрый способ вычислить данное произведение — это использовать теорему о свёртке, которая утверждает, что при определённых условиях выполнено:

${\displaystyle {\mathcal {F}}\{f*g\}={\mathcal {F}}\{f\}\cdot {\mathcal {F}}\{g\}}$

Здесь ${\displaystyle {\mathcal {F}}}$ обозначает преобразование Фурье, а операция ${\displaystyle \cdot }$ означает перемножение коэффициентов с одинаковым индексом. В общем случае теоремы о свёртке ${\displaystyle *}$ имеет значение свёртки, а не перемножения. Однако, можно показать, что перемножение многочленов является свёрткой.

Быстрое преобразование Фурье

Для нахождения преобразования Фурье мы используем Быстрое преобразование Фурье (БПФ), которое выполняется за ${\displaystyle O(n\log(n))}$^[1]. Алгоритм перемножения следующий^[14]: мы рассчитываем все коэффициенты Фурье для всех многочленов сразу с помощью БПФ. Затем мы попарно перемножаем соответствующие коэффициенты Фурье двух многочленов. После мы используем обратное БПФ, после чего получим многочлен степени не выше ${\displaystyle 2n}$.

Дискретное преобразование Фурье

Вместо обычного преобразования Фурье в SWIFFT используется дискретное преобразование Фурье (ДПФ)^[1][14]. Оно использует корни из единицы в ${\displaystyle \mathbb {Z} _{p}}$ вместо комплексных корней из единицы. Это будет справедливо, если ${\displaystyle \mathbb {Z} _{p}}$ — конечное поле, и его 2n^th простых корня из единицы существуют в данном поле. Данные условия будут выполнены, если взять такое простое число ${\displaystyle p}$, что ${\displaystyle p-1}$ делится на ${\displaystyle 2n}$.

Выбор параметров

Параметры m,p,n должны удовлетворят следующим требованиям^[15]:

• n должен быть степенью двойки
• p должен быть простым числом
• p-1 должно делиться на 2n
• ${\displaystyle \log(p)<}$m

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

Статистические свойства

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

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

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

Теоретическая стойкость

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

В случае SWIFFT доказанная стойкость заключается в задаче поиска коротких векторов в циклических/идеальных решётках^[17]. Можно доказать, что справедливо следующее утверждение: предположим, у нас есть алгоритм, который может найти коллизии функции ${\displaystyle f}$ для случайной версии SWIFFT, полученной от ${\displaystyle f}$, за некоторое возможное время ${\displaystyle T}$ с вероятностью ${\displaystyle p}$. Значит, алгоритм, работает только на небольшой, но заметной доле функций семейства. Тогда мы можем также найти алгоритм ${\displaystyle f_{2}}$, который сможет всегда находить короткий вектор на любой идеальной решётке над кольцом ${\displaystyle \mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)}$ за некоторое возможное время ${\displaystyle T_{2}}$, зависящее от ${\displaystyle T}$ и ${\displaystyle p}$. Это значит, что нахождение коллизий в SWIFFT не менее сложное, задача нахождения коротких векторов в решётке над ${\displaystyle \mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)}$, для решения которой существуют только экспоненциальные алгоритмы.

Практическая стойкость

Авторы данной хеш-функции исследовали её на уязвимости для различных атак и установили, что атака «дней рождения» требует меньше всего операций подсчёта хэша (2¹⁰⁶) для поиска коллизий.^[18][1]. Атаки с перестановками требуют 2⁴⁴⁸ операций подсчёта для стандартных параметров. Полный перебор возможных значений потребует 2⁵²⁸ операций подсчёта хэша. Этого, как правило, достаточно для того, чтобы сделать нападение противника невозможным.

См. также

• Быстрое преобразование Фурье

Примечания

Литература

Книги

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

Статьи

• Lyubashevsky V., Micciancio D., Peikert C., Rosen A. SWIFFT: A Modest Proposal for FFT Hashing (англ.) // (unknown type) — 2008. — Vol. 5086. — P. 54—72. — doi:10.1007/978-3-540-71039-4_4
• Arbitman Y., Dogon G., Lyubashevsky V., Micciancio D., Peikert C., Rosen A. SWIFFTX: A Proposal for the SHA-3 Standard (англ.) — 2008.
• Buchmann J., Lindner R. Secure Parameters for SWIFFT (англ.) // Progress in Cryptology — INDOCRYPT 2009: 10th International Conference on Cryptology in India, New Delhi, India, December 13-16, 2009. Proceedings / B. Roy, N. Sendrier — Springer Berlin Heidelberg, 2009. — P. 1—17. — ISBN 978-3-642-10627-9 — doi:10.1007/978-3-642-10628-6_1
• Šarinay J. Interpreting Hash Function Security Proofs (англ.) // Provable Security: 4th International Conference, ProvSec 2010, Malacca, Malaysia, October 13-15, 2010. Proceedings / S. Heng, K. Kurosawa — Springer Berlin Heidelberg, 2010. — P. 119—132. — ISBN 978-3-642-16279-4 — doi:10.1007/978-3-642-16280-0_8
• Győrfi T., Cret O., Hanrot G., Brisebarre N. High-Throughput Hardware Architecture for the SWIFFT / SWIFFTX Hash Functions (англ.) // Cryptology ePrint Archive — International Association for Cryptologic Research, 2012.