Алгебраические атаки

ПостНаука продолжает рассказывать о современных технологиях в проекте «Банк знаний», подготовленном совместно с Корпоративным университетом Сбербанка.

Есть два главных класса шифров: поточные и блочные. В поточных шифрах генерируется псевдослучайная последовательность и складывается с тем, что надо зашифровать, по какому-то модулю (как правило, по модулю 2). Бывают блочные шифры, когда сообщение, которое надо закодировать, разбивается на блоки, а каждый блок кодируется блоком такой же длины.

С одной стороны, противник не должен восстановить исходный код. А с другой стороны, необходимо кодировать эффективно и быстро. Поэтому блоки, как правило, используются большие: 64, 128 или 256 входов и выходов. Но такой оператор ни в какой памяти хранить невозможно, поэтому используются разные алгоритмы, использующие, как правило, много раундов. И на каждом раунде биты, которые надо закодировать, сначала перемешиваются, а потом к определенным кускам применяется булев оператор. Например, оператор на 8 входов и 8 выходов называется s-box (от S — substitution, «подстановка»). Часто таких раундов перемешивания и применения s-box бывает от 20. И все эти операции занимают какие-то доли секунд.

Архитектура блочного шифра очень сложная, перестановки могут осуществляться по-разному. Важно только, чтобы степень нелинейности была большой, а корреляции между битами — минимальны. Поэтому общих математических методов, чтобы анализировать произвольный шифр, нет. На практике криптоаналитики берут какой-то конкретный шифр, смотрят его архитектуру и пытаются проследить корреляцию между какими-то двумя конкретными битами. Если им удалось проследить корреляцию, это считается недостатком шифра.

Но вопрос характеристики достоинств и недостатков в случае криптографии очень спорный. Что с точки зрения обычного математика, это хорошо, с точки зрения того, кто работает с приложением в криптографии, это плохо, и наоборот.

Вообще, алгоритм шифрования в большинстве случаев считается известным. Стандарты шифрования, как правило, обнародованы, а неизвестны начальные данные — секретный ключ. Бывают открытые ключи, но все равно открытые ключи нужны, чтобы сгенерировать секретный.

Другим важным классом шифров являются поточные шифры. В них генерируется псевдослучайная последовательность, которая затем поэлементно комбинируется (например, в случае двоичных последовательностей складывается по модулю 2) с последовательностью, которую надо зашифровать. Самым простым инструментом для генерации псевдослучайной последовательности является регистр сдвига с линейной обратной связью. Однако содержимое его ячеек в любой момент времени является линейной функцией от начальных значений, поэтому нахождение начальных значений (то есть секретного ключа) проблемы не представляет.

Можно эту задачу усложнить, если взять выводы из разных ячеек регистра и подать их на вход булевой функции, а уже выход этой булевой функции использовать как псевдослучайную последовательность. Булева функция — это функция отображения множества двоичных наборов в числа 0 и 1. То есть на вход подается n двоичных переменных, но выходит одна.

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

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

Скажем, можно использовать аппроксимацию, то есть мысленно заменить в анализе полученную функцию на близкую к ней линейную функцию. И взять разницу, на скольких наборах она отличается от самой функции. Булева функция на каждом наборе принимает значение либо 0, либо 1. Поэтому функции на каждом наборе либо совпадают, либо различаются, и получается 2n наборов. Если на половине наборов значения совпадают, а на половине различаются, значит, расстояние до этой линейной функции составляет 2(n–1).

И если всего наборов возможно 2n, значит, нелинейность любой функции не превосходит 2(n–1) — 2(n/2–1). Функция, достигающая этой оценки, называется бент-функцией. На самом деле бент-функция с этой точки зрения идеальна, но в криптографии часто бывает, что-то, что идеально с одной точки зрения, неидеально с другой. Она неидеальна в том смысле, что у нее нулей и единиц на выходе разное число. Это недостаток, ведь чтобы функция была действительно случайная, она должна принимать значения поровну. Но есть разные методы, которые позволяют построить уравновешенную функцию с близкими свойствами.

Мы говорили об абсолютной нелинейности функции, но для задач криптографии важна также относительная нелинейность, равная нелинейности, деленной на общее число наборов (то есть на 2n). Из практических соображений, когда мы аппроксимируем и заменяем функцию на близкую к ней линейную, то на каких-то наборах может получиться неправильное значение, но большинство значений все-таки будет правильным. Тут привлекаются вероятностные методы, позволяющие с большой вероятностью правильно найти начальные значения ячеек регистра. На практике, чтобы такие атаки не проходили, желательно, чтобы относительная нелинейность функции была больше, чем 0,45.

В 2002–2003 годах был изобретен еще один вид атаки на поточный шифр. Зная используемую в поточном шифре булеву функцию, можно предпринять атаку, чтобы минимизировать степень нелинейности системы уравнений, которую надо решить для нахождения начальных значений ячеек регистра. Любая нелинейная функция, пусть и маленькой степени, зависит от какого-то числа переменных. Что такое степень функции? Это длина самого длинного монома в полиноме. И если степень функции маленькая, то можно использовать атаку линеаризации. Каждый моном заменяется на отдельную переменную, и получается из нелинейной системы линейная система с разумно большим числом переменных. А вот если степень будет уже выше, то такая атака приведет к линейной системе с неразумно большим числом переменных. Порядок такой «разумности» — это несколько сотен тысяч переменных.

Даже если используемая в шифре булева функция имеет большую степень, ее можно понизить, например домножая на какую-то другую функцию невысокой степени. И чтобы при этом получился либо ноль, либо функция тоже невысокой степени. При этом примерно половина уравнений, конечно, пропадет, но если мы перехватили достаточно большое количество информации, то это не страшно. То же самое происходит, если мы домножим функцию на ее отрицание, заменяя 1 и 0 на выходе на 0 и 1 соответственно. Если мы имеем функцию, можно считать, мы имеем и ее отрицание.

И таким образом, каждая функция характеризуется алгебраической иммунностью — это наименьшая степень ненулевого аннигилятора (аннигилятор — это функция, на которую мы домножаем), при умножении на который мы получаем ноль. То есть функцию f домножаем на функцию g, получаем ноль. Либо функцию не f (отрицание) умножаем на g и получаем ноль. Наименьшая степень такого ненулевого аннигилятора называется алгебраической иммунностью функции. Если функция имеет низкую алгебраическую иммунность, то она считается нестойкой к алгебраическим атакам.

Сразу доказали, что алгебраическая иммунность не превосходит верхнего целого n/2, где n — количество переменных. Верхнее целое — это ближайшее целое число по оценке сверху. Например, целая часть 2,5 — это 2, а верхнее целое — это 3. То есть если функция примерно от 256 переменных, то до степени 128 понизить всегда можно. Но возникает вопрос: можно ли понизить еще больше? Любопытно, что, когда только придумали алгебраическую иммунность, верхнюю оценку n/2 доказали сразу. А существует ли функция с алгебраической иммунностью ровно верхнее целое n/2 — несколько лет было открытой проблемой. И она решилась. Сначала индийцы построили функции, которые достигают этой оценки, но они были сложными и запутанно устроенными. А потом неожиданно оказалось, что этим свойством обладает функция голосования.

Функция голосования — это функция от n переменных, которая принимает то значение, за которое голосует большинство переменных. То есть если большинство переменных — это единички, функция принимает значение единичка. Если большинство переменных ноль, функция принимает значение ноль. Оказалось, что функция голосования обладает максимально возможной алгебраической иммунностью, и это очень легко доказывается. Но криптографы этого не замечали несколько лет: функция голосования им была известна, но она с точки зрения криптографии считалась плохой функцией из-за низкой нелинейности. И применительно к абстрактной математической задаче криптографы даже не пытались ее использовать, а когда использовали, все получилось.

Сейчас уже нашли много других функций либо с максимально возможной алгебраической иммунностью, либо с близкой к ней. И большинство работ на эту тему устроено так, что ученые пытаются построить функцию, обладающую одновременно несколькими свойствами, примерно четырьмя: уравновешенностью (функция принимает каждое из значений 0 и 1 ровно на половине наборов), как можно большей нелинейностью, как можно большей алгебраической иммунностью, некоторой устойчивостью и еще, возможно, чем-то. В каждой работе пытаются применить три, четыре, пять свойств. И с математической точки зрения это, конечно, получается громоздко и специфично, но таковы стандарты современных теоретических статей в этой прикладной области.

Есть многие работы, в которых показывается, что случайная функция самая хорошая. На самом деле почти все случайные функции обладают идеальными характеристиками. Но как взять случайную функцию? И что значит «случайно»? Можно для каждого набора подбросить монетку и занести в таблицу. Поскольку число переменных большое, таблица будет большой. То есть такой функцией на практике пользоваться нереально, потому что надо ею пользоваться быстро. Поэтому стараются строить функцию, которая имеет простую структуру и обладает хорошими свойствами. За счет того, что структура простая, бывают какие-то побочные изъяны.

Мой ученик Михаил Лобанов доказал оценку, связывающую нелинейность с алгебраической иммунностью. Для данного фиксированного числа переменных и для данной фиксированной алгебраической иммунности он получил нижнюю оценку на нелинейность. Подобные оценки выводили и до него, но он доказал достижимую оценку. Он доказал, кроме того, что эта оценка достигается для любых значений параметров. То есть для любого числа переменных и любого возможного значения алгебраической иммунности (то есть не превосходящего верхнего целого от половины числа переменных) существует функция с нелинейностью, достигающая этой нижней оценки.

И вот функция голосования достигает этой нижней оценки. Можно сказать, что функция голосования худшая из лучших. То есть среди всех функций с максимальной алгебраической иммунностью она обладает наихудшей нелинейностью.

Естественно, алгебраическая иммунность — это такая абстрактная характеристика, которую сформулировали из запросов того, что надо криптоаналитикам на практике. То есть криптоаналитикам надо атаковать шифр, а тем, кто разрабатывает шифры, надо, чтобы система была устойчива к этим атакам. Вот поэтому и удалось выделить такое понятие. Но некоторые криптоаналитики еще на заре исследований считали, что это слишком абстрактное свойство: даже если функция обладает хорошей алгебраической иммунностью, на практике можно что-то еще придумать. Шифр всегда конкретный, поэтому многие практики ко всей этой теории относятся с некоторым недоверием. Возможно, это правильно, но все равно развитие теоретических методов что-то дает для развития общих соображений.