SWIFFT

SWIFFT — это набор криптографических хеш-функций с доказанной стойкостью. Они основываются на быстром преобразовании Фурье (БПФ, англ. Fast Fourier Transform, FFT) и используют алгоритм LLL-редуцированных базисов. Криптографическая стойкость функций SWIFFT (в асимптотическом смысле) математически доказана при использовании рекомендуемых параметров. Поиск коллизий в SWIFFT в худшем случае требует не меньше временных затрат, чем нахождение коротких векторов в циклических/идеальных решётках. Практическое применение SWIFFT будет ценно именно в тех случаях, когда стойкость к коллизиям особенно важна. Например, цифровые подписи, которые должны оставаться надёжными длительное время.

Данный алгоритм обеспечивает пропускную способность порядка 40 Мб/с на процессоре Intel Pentium 4 с тактовой частотой 3,2 ГГц. Было проведено исследование, направленное на ускорение БПФ, которое используется в SWIFFT. Как результат, скорость работы алгоритма удалось увеличить более чем в 13 раз. Данная реализация SWIFFT оказалась быстрее, чем реализации широко распространенных хеш-функций.

На конкурсе Национального института стандартов и технологий США 2012 года был предложен SWIFFTX (модификация SWIFFT) в качестве SHA-3 (на замену более старых SHA-2 и особенно SHA-1), но был отклонён в первом раунде.

Описание работы

Функции SWIFFT могут быть описаны как простое алгебраическое выражение над некоторым кольцом многочленов R {displaystyle R} . Семейство функций зависит от трёх основных параметров: пусть n {displaystyle n} будет степенью числа 2, m > 0 {displaystyle m>0} — небольшое целое число, и p > 0 {displaystyle p>0} — не обязательно простое число, но лучше выбрать его простым. Определим R {displaystyle R} как кольцо вида R = Z p [ α ] / ( α n + 1 ) {displaystyle R=mathbb {Z} _{p}[alpha ]/(alpha ^{n}+1)} . Например, кольцо многочленов в α {displaystyle alpha } , у которых коэффициенты — целые числа, p {displaystyle p} — число, на которое выполняем деление по модулю, и α n + 1 {displaystyle alpha ^{n}+1} . Элемент из R {displaystyle R} может быть многочленом степени меньшей n {displaystyle n} с коэффициентами из Z p {displaystyle Z_{p}} .

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

∑ i = 1 m ( a i ⋅ x i ) {displaystyle sum _{i=1}^{m}(a_{i}cdot x_{i})} ,

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

Алгоритм работы следующий:

Берётся α {displaystyle alpha } — неприводимый многочлен над Z [ α ] {displaystyle mathbb {Z} [alpha ]}

На вход подаётся сообщение M {displaystyle M} длины m n {displaystyle mn}

M {displaystyle M} преобразуется в набор из m {displaystyle m} полиномов p i {displaystyle p_{i}} в определённом кольце многочленов R {displaystyle R} с двоичными коэффициентами

Рассчитываются коэффициенты Фурье для каждого p i {displaystyle p_{i}}

Задаются фиксированные коэффициенты Фурье a i {displaystyle a_{i}} в зависимости от семейства SWIFFT

Попарно перемножаются коэффициенты Фурье p i {displaystyle p_{i}} с a i {displaystyle a_{i}} для каждого i {displaystyle i}

Используется обратное преобразование Фурье для того, чтобы получить m {displaystyle m} многочленов f i {displaystyle f_{i}} степени не более 2 n {displaystyle 2n}

Рассчитается f = ∑ i = 1 m ( f i ) {displaystyle f=sum _{i=1}^{m}(f_{i})} по модулю p {displaystyle p} и α n + 1 {displaystyle alpha ^{n}+1} .

f {displaystyle f} преобразуется в n log ⁡ ( p ) {displaystyle nlog(p)} битов и отправляются их на выход

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

Пример

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

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

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

F { f ∗ g } = F { f } ⋅ F { g } {displaystyle {mathcal {F}}{f*g}={mathcal {F}}{f}cdot {mathcal {F}}{g}}

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

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

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

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

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

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

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

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

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

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

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

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

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

• Для семейства функций SWIFFT доказана криптографическая стойкость к коллизиям (в асимптотическом смысле) при относительно умеренном предположении о сложности задачи нахождения коротких векторов в циклических/идеальных решётках в худшем случае. Это значит, что семейство функций SWIFFT также устойчиво к атаке нахождения второго прообраза.

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

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

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

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

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