From cryptanalysis to cryptographic property of a Boolean function.pdf Введение На протяжении полувека сформировалось достаточно много требований к булевым функциям, использующимся в системах шифрования. Функции, удовлетворяющие данным требованиям, стали называть «криптографическими булевыми функциями». Основная задача работы - привести исходные связи между различными методами криптоанализа шифров и математическими требованиями, которые накладываются на булевы функции, используемые в этих шифрах, для противодействия этим атакам. Таблица отражает основное содержание настоящей работы. Для более основательного знакомства с теоретическими результатами в области различных криптографических свойств можно рекомендовать работы О. А. Логачева, А. А. Сальникова, С.В.Смышляева, В. В. Ященко [11], Г. П. Агибалова [1], И.А.Панкратовой [14], Ю. В. Таранникова [19], Н.Н.Токаревой [42], C. Carlet [24, 25], T. W. Cusick, P. Sta-nica [30], A. Braeken [23]. Рассматриваемые криптографические свойства и их назначение № п/п Свойство Цель 1 Высокая алгебраическая степень Повышение линейной сложности генерируемой последовательности; повышение степени системы нелинейных уравнений, описывающих шифр 2 Уравновешенность Улучшение статистических свойств последовательностей, вырабатываемых поточными генераторами 3 Совершенная уравновешенность 4 Лавинные характеристики Обеспечение изменения значений большого числа выходных переменных при изменении значений малого числа входных переменных 5 Отсутствие линейных структур Улучшение нелинейных свойств функций 6 Корреляционная иммунность, устойчивость Препятствие проведению корреляционной атаки на поточные шифры 7 Высокая нелинейность Препятствие проведению быстрой корреляционной атаки на поточные шифры и линейного криптоанализа блочных шифров 8 Статистическая независимость Препятствие проведению статистических методов криптоанализа шифров Окончание таблицы № п/п Свойство Цель 9 Алгебраическая иммунность Препятствие проведению алгебраического криптоанализа шифров 10 Уровень аффинности и k-нор-мальность Препятствие методу линеаризации без введения новых переменных для решения булевых уравнений 11 Дифференциальная равномерность Препятствие проведению дифференциального криптоанализа блочных шифров 12 Разложимость в сумму специальных функций Маскирование данных с целью защиты от атак по сторонним каналам 13 Мультипликативная сложность Минимизация размера и стоимости аппаратной реализации криптоалгоритмов 14 Высокие мощности линеаризаци-онных множеств Препятствие линеаризационной атаке 1. Основные определения и обозначения 1.1. Булевы функции Введём обозначения: n - натуральное число; F2 - множество, состоящее из 0 и 1; x = (xi,... , xn) -двоичный вектор c координатами из F2; F^ - множество всех двоичных векторов длины n; 0 = (0,..., 0) -нулевой вектор; ф - сложение по модулю 2. Весом Хэмминга wt(x) двоичного вектора x называется количество единиц, соn держащихся в x: wt(x) = x^ Расстоянием Хэмминга d(x, y) между двумя вектораi=1 ми x, y называется число позиций, в которых они различаются, или, что эквивалентно, d(x, y) = wt(xфy). Скалярное произведение (x, y) двоичных векторов x, y определяется как (x, y) = xiyi ф ... ф xnyn. Векторной булевой функцией ((n, т)-функцией) F называется произвольное отображение F : Fn ^ Fm. В случае m =1 говорят, что F - булева функция от n переменных. Можно рассматривать (n, т)-функцию как набор из m координатных булевых функций от n переменных: F = (/1,...,/m). Компонентной функцией называется любая ненулевая линейная комбинация координатных функций, т. е. булева функция (b, F), где b e Fm b = 0. Вес функции wt(/) равен мощности её носителя supp(/) = {x e Fn : /(x) = 1}. Расстоянием Хэмминга d(/, g) между булевыми функциями / и g является расстояние Хэмминга между векторами их значений: d(/,g) = |{x e Fn : /(x) = g(x)}|. Пусть Mn - некоторое множество булевых функций от n переменных. Расстояние от функции g до множества функций Mn определяется как d(g, Mn) = min {d(/, g) : / e Mn}. Для любой булевой функции / производная по направлению а, где a e Fn, определяется следующим образом: Da/(x) = /(x) ф /(x ф a). Любую (n, т)-функцию можно единственным образом записать в виде полинома Жегалкина, или алгебраической нормальной формы (АНФ): F(x1,...,xn) = n = ai1,...,ikxii . . . xik ф ^ где {ib . . . , ik} С {1, . . . , n} и ai1,...,ik e F™. k=0 ii,...,ik Алгебраической степенью deg(F) функции F называется количество переменных в самом длинном слагаемом АНФ, при котором коэффициент не равен нулевому вектору. Функция степени не выше 1 называется аффинной. В случае a0 = 0 функция линейна. Для каждого y e Fn коэффициентом Уолша - Адамара Wf (y) булевой функции / от n переменных называется величина, определяемая равенством Wf (y) = = Yl (-1)f(x)®^x'y). Набор коэффициентов Wf (y) по всем y Е F^ называется спектжек? ром Уолша - Адамара булевой функции f. Справедливо равенство Парсеваля: Wf (y) = 22n. Спектр Уолша - Адамара векторной функции состоит из всех коyeF'^ эффициентов Уолша - Адамара всех её компонентных булевых функций: Wf (u,v) = = ( -1 ){v,F(x))®{u,x) xeF^ 1.2. Блочные шифры Блочный шифр преобразует блок открытого текста (сообщения) длины N в блок шифртекста также длины N с использованием некоторого секретного ключа. Процесс шифрования состоит из нескольких повторяющихся раундов, определяющихся, как правило, одинаковой раундовой функцией, зависящей от раундового подключа Ki, вырабатываемого по специальному правилу из исходного ключа K. Наиболее распространённые типы блочных шифров, SP-сеть и сеть Фейстеля, схематично приведены на рис. 1 [20]. Обе эти схемы отражают в себе два принципа построения шифрующих преобразований, которые определил в своей работе Клод Шеннон, - рассеивание и перемешивание. Приведём объяснение этих принципов по работе [5]: «Качественно можно сказать, что перемешивание усложняет восстановление взаимосвязи статистических и аналитических свойств открытого и шифрованного текстов, а рассеивание распространяет влияние одного знака открытого текста на большое число знаков шифртекста, что позволяет сгладить влияние статистических свойств открытого текста на свойства шифртекста». На примере SP-сети хорошо видно, что P-блок обеспечивает рассеивание, а набор небольших S-блоков - перемешивание. В то время как в качестве P-бло-ка обычно выбирается линейная функция, S-блоки составляют нелинейные преобразования шифра. По сути, S-блок - это векторная (n, т)-функция, причём значения n и m небольшие, например 4, 6, 8 битов. Несмотря на столь небольшой размер, найти такой S-блок с «хорошими» криптографическими свойствами достаточно трудно. Для наглядности заметим, что всевозможных отображений из в себя существует 22048, что в настоящее время не поддаётся полному перебору! При этом даже аналитические рассуждения пока не могут привести к ответу на некоторые важные для криптографических приложений вопросы. Например, не известно, существуют ли взаимно однозначные почти совершенно нелинейные отображения из F^ в себя при чётных n ^ 8, подробнее об этом сказано в п. 12. 1.3. Поточные шифры Приведём широко используемую модель поточного шифра - шифр гаммирова-ния [5]. В основе таких систем лежит метод «наложения» (например, сложение по модулю 2) ключевой последовательности (гаммы) на открытый текст (шифруемое сообщение). Из работ Клода Шеннона следует, что если ключ имеет такую же длину, как и сообщение, выбирается случайно и равновероятно и при этом используется только один раз, то данная система шифрования является абсолютно стойкой к атакам на основе шифртекста. Поскольку такая модель неприменима для широкого распространения в силу того, что затруднительно генерировать такой же объём ключа, как и сообщения, а тем более его передавать, перед разработчиками стоит задача получать из короткой случайной последовательности битов ключа некоторую длинную последовательность (гамму), которая будет близка к случайной. Заметим, что именно от свойств данной последовательности зависит криптографическая стойкость шифра. ■ кв ■ г 5-блоки дц ,U ±4 и (S Аблок К, S-блоки CD о :2 ft tJ J'-блок -К, S-Ёлоки CD t р i] 1 1 Р- блок А", SP-сеть Раундовая функция сети Фейстеля Рис. 1 Часто в качестве компонент поточного шифра используются регистры сдвига с обратной связью. Общая схема их работы приведена на рис.2, где f - булева функция от n переменных, являющаяся функцией обратной связи [20]. Рис. 2 Перед стартом работы происходит начальное заполнение состояния регистра некоторыми n битами. Далее на каждом такте работы вычисляется очередное значение а = f (xn-1,... , x0), затем все биты регистра сдвигаются влево, при этом в крайний правый бит записывается значение а, а крайний левый бит становится очередным битом выходной последовательности u = {u0,u1, u2 ...}. Наибольшее распространение получили регистры сдвига с линейной обратной связью (LFSR), т.е. те, в которых f линейна, скажем, f (xn-1,... ,x0) = (c, x), где c G F^. Заметим, что последовательность, порождаемая любым регистром с обратной связью, всегда периодическая. Легко видеть, что на самом деле любую периодическую последовательность можно породить LFSR подходящей длины. При этом линейной сложностью Lu последовательности u называют минимальную длину LFSR, который её порождает. Линейная сложность последовательности - это основной параметр, характеризующий сложность её аналитического строения [5]. Напомним, что для генерации «хорошей» гаммы не используется лишь один LFSR. Действительно, если мы знаем функцию обратной связи f (x) = (c, x), c G F^, то достаточно лишь n подряд идущих битов последовательности для того, чтобы восстановить начальное состояние регистра путём решения системы линейных уравнений. А начальное состояние, как правило, и является секретным ключом шифра. Кроме того, известен более сильный результат, который позволяет найти линейную функцию обратной связи для любой периодической последовательности. Допустим, что мы перехватили достаточно длинный отрезок некоторой периодической последовательности. Тогда с помощью широко известного алгоритма Берлекэмпа - Месси можно за полиномиальное от длины конечной последовательности время найти закон рекурсии, её порождающий, что эквивалентно нахождению линейного регистра, который вырабатывает данный отрезок последовательности. При этом если длина последовательности не меньше 2L, где L - её линейная сложность, то найденный LFSR вырабатывает и всю бесконечную последовательность, отрезок которой нам известен. С другой стороны, линейная сложность вырабатываемой последовательности должна быть высокой при почти любом начальном состоянии регистра - неизвестном ключе. В силу этого используют некоторые усложнения. Выделяют две основные модели генераторов, построенных на основе регистров сдвига с линейной обратной связью [20] (рис.3). Булева функция h называется соответственно комбинирующей и фильтрующей. LFSR • • • Гамма Фильтрующий генератор Рис. 3 Комбинирующий генератор 2. Высокая алгебраическая степень Опишем, опираясь на обзор C. Carlet [24], теоретические результаты, которые показывают, что в качестве комбинирующей и фильтрующей функции h следует выбирать те, чья алгебраическая степень не мала. Рассмотрим сначала комбинирующий генератор, состоящий из n регистров с линейной обратной связью длин Ll,...,Ln. Пусть комбинирующая функция h задана в виде алгебраической нормальной формы n h(xi, ...,xn) = 0 0 «ii,...,ifc Xii . ..Xik, где {ii, ...,ik} С {1,... ,n} и aib...,ik G F2. То-k=l ii,...,ik гда линейная сложность L вырабатываемой последовательности оценивается сверху через длины регистров следующим образом: n L aii,...,ik Lil . . . Lik , k=l ii,...,ik при этом известны условия, при которых данная оценка достигается: если Li совпадает с линейной сложностью генерируемой LFSRi последовательности для любого i и числа Ll,... , Ln попарно взаимно просты. Можно видеть, что чем выше степень АНФ, тем большую линейную сложность можно получить. В случае фильтрующей модели аналогичного точного результата нет, хотя также известна оценка линейной сложности L генерируемой последовательности через стеdeg(h) пень фильтрующей функции deg(h), а именно: L ^ ClL, где L - длина регистра, а i=0 C%L - биномиальный коэффициент. Кроме того, если L - простое число, то верна оценка снизу: L ^ C?g(h). В блочных шифрах следует также выбирать функции с достаточно большой степенью. «Параметр deg(F) булевой функции должен быть большим. Для блочных шифров это условие накладывается, как правило, для того, чтобы система уравнений на биты ключа, построенная путём анализа структуры шифра - в том числе функции F, использующейся в качестве его компоненты, -имела высокую степень. Чем выше степень системы, тем сложнее её решить, а значит, определить ключ» [20]. 3. Уравновешенность Определение 1. Булева функция f от n переменных называется уравновешенной, если её вес равен 2n-i, т. е. функция принимает значения 0 и 1 одинаково часто. Это, пожалуй, одно из самых естественных необходимых свойств, накладываемых на булевы функции, использующиеся в поточных шифрах. Если булева функция уравновешена, то вероятность того, что она примет значение 0 или 1 , одинакова и равна 1/2. Это позволяет ослабить статистические зависимости между входом функции и её выходом. В противном случае у криптоаналитика есть возможность, используя вероятностное соотношение, провести криптоанализ шифра. Данное определение обобщается на векторный случай. Определение 2. Векторная (n, т)-функция F называется уравновешенной, если |F-i(y)| = |{x E Fn : F(x) = y}| = 2n-m для любого y E Fm При этом справедливо следующее Утверждение 1. Векторная (n, т)-функция F уравновешена тогда и только тогда, когда уравновешены все её компонентные функции (v, F), v E Fm, v = 0. Заметим, что при n = m класс уравновешенных векторных функций совпадает с классом взаимно однозначных функций. Как правило, именно они представляют наибольший интерес для использования в блочных шифрах в качестве S-блоков для обеспечения однозначного расшифрования. 4. Совершенная уравновешенность Свойство совершенной уравновешенности булевой функции является естественным обобщением обычной уравновешенности, когда данная функция выступает, например, в качестве фильтрующей функции генератора. Данное свойство было формализовано С. Н. Сумароковым [18] . Пусть f - фильтрующая функция генератора от n переменных, x = (xi,..., x^+n-i) - отрезок входной последовательности длины t + n - 1, где t - некоторое натуральное число. Тогда генератор выработает по нему отрезок последовательности u = = (ui,...,u^) длины t, где и = f (xi,xi+i, ...,xi+n-i), i = 1,...,t. Определим для функции f и числа t векторную (t + n - 1, t)-функцию f^, сопоставляющую вектору x вектор и по описанному выше правилу. Определение 3. Булева функция f называется совершенно уравновешенной, если для любого натурального числа t функция f уравновешена. В частности, если функция совершенно уравновешена, то она уравновешена и в обычном смысле. Обратное неверно. Запретом булевой функции f называется такой вектор u = (ui,... , и^) для некоторого t, для которого множество прообразов f-i(u) пусто. Следующая теорема отражает критерий совершенной уравновешенности в терминах запретов функции. Теорема 1. Булева функция совершенно уравновешена тогда и только тогда, когда она является функцией без запрета. Интуитивно понятно, что наличие запрета у фильтрующей функции генератора делает её «слабее» с точки зрения порождения последовательностей с хорошими статистическими свойствами. Однако следует быть осторожными, поскольку совершенно уравновешенная фильтрующая функция в том или ином виде переносит свойства входной последовательности в свойства генерируемой последовательности [11]. Например, С. В. Смышляевым в работе [17] установлен новый критерий, который идейно говорит следующее: «фильтрующая функция сохраняет запреты (в соответствующем смысле) тогда и только тогда, когда она совершенно уравновешена». Соответственно если на вход функции поступает «далёкая» от случайной последовательность, то и на выходе её статистические свойства будут плохие. Заметим, что если фильтрующая функция линейна по своей первой и/или последней существенной переменной, то она совершенно уравновешена. Но в обратную сторону это неверно, поскольку найдены конструкции совершенно уравновешенных функций, нелинейно зависящих от своих крайних переменных (ссылки можно найти в [11]). Актуальность поиска широкого класса таких функций подтверждается тем, что известна так называемая инверсионная атака на фильтрующие генераторы, использующие линейные по первой или последней существенной переменной функции в качестве фильтрующих. Данную атаку предложил J. Dj. Golic [34]. 5. Лавинные характеристики Концепция лавинных характеристик булевой функции отражает один из принципов Шеннона построения шифрующих преобразований, сформулированных в п. 1.2, а именно принцип рассеивания. Следующее определение ввели A. F. Webster, S. E. Tavares в работе [43]. Определение 4. Булева функция f от n переменных удовлетворяет строгому лавинному критерию (SAC), если для любого направления а Е F^, где wt(a) = 1, производная Da(f) уравновешена. Если все координатные функции векторной (n, т)-функции удовлетворяют SAC, то при изменении одного входного бита с вероятностью 1/2 изменится каждый из выходных битов. Следовательно, можно ожидать, что примерно половина выходных битов изменится. Обобщением данного критерия является следующий, который стали рассматривать B. Preneel и др. [39]. Определение 5. Булева функция f от n переменных удовлетворяет критерию распространения степени k (PC(k)), если для любого направления а Е F^, где 1 ^ ^ wt(a) ^ k, производная Da(f) уравновешена. По определению PC(1) совпадает с SAC. Забегая вперёд, можно отметить, что функции, удовлетворяющие PC(n),-это в точности бент-функции (см. определение 11, п. 8 и теорему 16, п. 12). Если функция удовлетворяет данным критериям, то это означает, что изменение входного вектора в нескольких битах меняет значение функции с вероятностью 1/2. Как отмечается в [11], строгий лавинный критерий и его обобщения «явились в конечном счёте индикаторами локальных свойств для исследуемых криптографических функций». Более правильно требовать, чтобы в среднем у функции были «хорошие» лавинные характеристики, которые выражаются в том, что модуль функции автокорреляции А/(a) = (-1)f(x)®f(x®a) был равен или близок к нулю для большинства xeFr; векторов а Е F^. Такой подход предложили X.-M. Zhang и Y. Zheng в работе [45]. Определение 6. Глобальными лавинными характеристиками (GAC) булевой функции f от n переменных называются числа а/ = А 2(а) и А/ = max А/(а). Понятно, что чем меньше данные величины, тем лучше функция для использования в шифре, поскольку GAC отражают лавинные показатели в среднем. В [11] можно найти основные свойства GAC произвольной функции, а также их некоторые связи с другими криптографическими свойствами, в частности с нелинейностью и порядком устойчивости. 6. Линейные структуры Определение 7. Векторная (n, т)-функция обладает линейной структурой, если существует вектор а Е F^, а = 0, такой, что Da(F) = const. В качестве компонент шифра следует выбирать функции, которые не обладают линейной структурой [32], несмотря на то, что, как отмечается в [24], к настоящему моменту данные слабости не были использованы в атаках. Действительно, наличие линейной структуры у функции свидетельствует о её «похожести» на линейную функцию в том смысле, что она линейно эквивалентна функции, у которой есть переменная, от которой она зависит линейно или фиктивно. Как уже отмечалось, близость функций в различных смыслах к линейным неприемлема для использования в криптографических системах. 7. Корреляционная иммунность и устойчивость Рассматриваемые здесь свойства возникли из разных прикладных задач, но, как оказалось, тесно связаны. Термин корреляционной иммунности ввёл T. Siegenthaler в работе [40]. Он показал, что функции с высоким порядком корреляционной иммунности, используемые в качестве комбинирующей функции генератора в поточном шифре, делают шифр стойким к корреляционной атаке. Суть атаки состоит в поиске подмножества переменных комбинирующей функции, о значениях которых можно получить информацию, зная значение функции. Устойчивые функции были введены в открытой литературе также в 1980-х годах, но, как отмечается в [11], «были связаны с такими областями исследований, как распределённые вычисления, устойчивые относительно ошибок, и выработка общих ключей для квантово-криптографических каналов связи». Из работы К. Н. Панкова [13] известно, что в СССР аналогичные функции исследовались Л. В. Ларионовым в 1970-х годах. В качестве комбинирующей функции генератора в поточном шифре необходимо использовать функции, обладающие свойством устойчивости. При этом чем выше порядок устойчивости, тем выше стойкость шифра к корреляционному криптоанализу. Приведём формальные определения данных свойств на языке комбинаторики. Определим сначала понятие подфункции. Подфункцией булевой функции f от переменных xi,...,xn называется булева функция, полученная из f подстановкой вместо переменных xil,... , xik конкретных констант а1,... ,ак, принимающих значения 0 или 1. Такая подфункция обозначается fa1'"^. Определение 8. Булева функция f называется корреляционно-иммунной порядка k, если вес подфункций fiH'."^ удовлетворяет соотношению wtfai'.'^) = wt(f)/2k для любого набора индексов 1 ^ i1 < ... < ik ^ n и любых значений а1,..., ak Е F2. Другими словами, булева функция f называется корреляционно-иммунной порядка k, если P[f = 1] = Р/^'''^ = 1], где P - функция вероятности, т.е. знание некоторых входных битов не даёт статистической информации о значении функции. Определение 9. Булева функция f называется k-устойчивой (k-эластичной), если любая её подфункция, полученная фиксацией не более k переменных, является уравновешенной. Нетрудно убедиться, что булева функция f является k-устойчивой тогда и только тогда, когда она уравновешена и корреляционно-иммунна порядка k. 7.1. Идея корреляционной атаки Рассмотрим общую идею данного криптоанализа, следуя [14]. Пусть f - комбинирующая функция генератора, LFSRi, ..., LFSR - его регистры сдвига с линейной обратной связью длин L1,...,Ln соответственно, а u = = U0,Ui,U2,... -выходная последовательность регистра. Трудоёмкость криптоанализа «грубой силой», т. е. полного перебора всех начальных состояний регистров, оценивается как 2Ll+-+Ln. Если регистр построен «правильно», то последовательность u очень близка к случайной, поэтому можно считать, что P [u^ = 0] ~ 1/2. Следовательно, если z = z0, z1, z2,... -произвольная не зависящая от u последовательность, то можно считать, что P[u = Zj] ~ 1/2, поскольку P[u = Zj] = P[u = 0] P[zj = 0] + + P[u = 1] P[Zj = 1] « 1/2 (P[Zj = 0] + P[Zj = 1]) = 1/2. Предположим, что функция f коррелирует с функцией £(x1,..., xn) = x1, что означает P[f = £] = 1/2 + e = 1/2. Тогда утверждается, что можно восстановить неизвестное начальное состояние регистра LFSR1. Для этого будем перебирать все возможные начальные состояния первого регистра (их 2Ll), для каждого из них генерировать выходную последовательность данного регистра z = z0, z1, z2, ... и считать, сколько раз выполнено Zj = uj. Тогда если начальное состояние было предположено неправильно, то P[zj = uj] ~ 1/2, а если правильно, то P[zj = uj] ~ 1/2 + e. Таким образом, чем больше значение корреляции | e| , тем с большей вероятностью мы найдём правильное состояние регистра. Тем самым мы уменьшили сложность перебора до 2Ll + 2L2+-"+Ln. Если при этом есть корреляция f и других переменных, то сложность можно ещё понижать. Если же у f нет корреляции с функциями £(x) = xj, можно искать корреляции с другими линейными функциями (c, x), у которых wt(c) = k мал, скажем, c = (1,..., 1,0,..., 0). Тогда сложность перебора уменьшается до 2Ll+-+Lfc +2Lk+i+---+Ln. Но если k достаточно большое, то особого выигрыша для криптоаналитика может и не быть. Заметим, что в [11] приводятся также известные результаты о том, что фильтрующий генератор с функцией f можно свести к специально построенному комбинирующему генератору c той же функцией f, выступающей уже в качестве комбинирующей. При этом новый генератор вырабатывает ту же последовательность при определённом начальном заполнении состояний его регистров. Следовательно, корреляционную атаку можно обобщать и на случай фильтрующих генераторов. 7.2. Основные теоремы и связь с нелинейностью Утверждение 2. Корреляционно-иммунная порядка k булева функция является также корреляционно-иммунной порядка £ для всех £ < k. В силу этого утверждения естественно ввести определение порядка корреляционной иммунности cor(f) функции f как cor(f) = max{0 ^ k ^ n : f - корреляционно-иммунная порядка k}. Следующая широко известная теорема даёт спектральную характеризацию корреляционно-иммунных и устойчивых функций. Теорема 2 (спектральная характеризация). Пусть f - булева функция от n переменных. Справедливо cor(f) = k тогда и только тогда, когда Wf (y) = 0 для всех векторов y, таких, что 1 ^ wt(y) ^ k. Кроме того, f является уравновешенной тогда и только тогда, когда Wf (0) = 0. Данная теорема наглядно связывает определение корреляционно-иммунных порядка k функций и способность противостоять корреляционной атаке при использовании их в качестве комбинирующих функций поточного генератора. Действительно, для проведения атаки необходимо найти линейную функцию £(x) = (c, x), с которой есть корреляция у комбинирующей функции f, т.е. P[f = £] = 1/2. Так как P[f = £] = (2n - d(f,£)) /2n = 1/2 + (2n-1 - d(f,£)) /2n = 1/2, это эквивалентно тому, что d(f, £) = 2n-1. Кроме того, легко получить, что расстояние между f и линейной функцией £(x) = (c, x) выражается как d(f, £) = 2n-1 - Wf(c)/2. Таким образом, d(f, £) = 2n-1 тогда и только тогда, когда Wf(c) = 0. Следовательно, если порядок устойчивости комбинирующей функции достаточно высокий, то корреляционную атаку на данный шифр провести будет сложно. Связь порядка cor(f) и степени функции deg(f) отражается в следующей теореме. Теорема 3 (Siegenthaler). Пусть f - булева функция от n переменных. 1. Если cor(f) = к, то выполняется deg(f) + к ^ n. 2. Если cor(f) = к, f уравновешена и к ^ n - 2, то выполняется deg(f) + к ^ n - 1. Из теоремы следует, что чем выше степень функции, тем меньше порядок её корреляционной иммунности, и наоборот. Но, как мы видели, оба этих параметра должны быть высокими для функций усложнения криптографических генераторов. Следствие 1. Пусть f - булева функция от n переменных. Если cor(f) = n, то f = const. Если cor(f) = n - 1, то f (x) = x1 ф ... ф xn ф const. Известна следующая оценка cor(f), полученная Д. Г. Фон-дер-Флаассом [33]. Теорема 4 (Фон-дер-Флаасс). Пусть f - неуравновешенная булева функция от n переменных. Тогда cor(f) ^ (2n/3) - 1. Здесь естественно также упомянуть про нелинейность Nf (см. определение 10, п. 8) корреляционно-иммунных функций. Теорема 5 (связь cor(f) и Nf). Пусть f - булева функция от n переменных. 1. Если cor(f) = к, к ^ n - 1, то выполняется Nf ^ 2n-1 - 2k. 2. Если cor(f) = к, f уравновешена и к ^ n - 2, то выполняется Nf ^ 2n-1 - 2fc+1. Как видно из теоремы, нелинейность функции с ростом порядка устойчивости падает. Это интуитивно понятно из того, что с ростом cor(f) становится всё больше нулевых коэффициентов Уолша - Адамара функции f, что ведёт к увеличению максимального значения |Wf (а)| в силу равенства Парсеваля, а следовательно, к снижению нелинейности. При этом интересен и актуален вопрос о достижимости оценок из теоремы 5. Известно, что если оценка для к-устойчивых функций достигается, то (n - 3)/2 ^ к ^ n - 2, но примеров для всех таких возможных параметров пока не найдено. Ю. В. Таранниковым [41] разработан и обобщён метод, который в настоящий момент позволяет строить к-устойчивые функции с нелинейностью 2n-1 - 2fc+1 для всех к ^ cn(1 + o(1)), где c = 0,5789 ... 8. Высокая нелинейность Определение 10. Нелинейностью булевой функции f от n переменных называется величина Nf, равная расстоянию Хэмминга от f до множества An всех аффинных функций от n переменных. В п. 7.2 мы уже упоминали связь расстояния между произвольной функцией и линейной функцией d(f, (c, x)) = 2n-1 - Wf (c)/2. Основываясь на ней, легко получить, что нелинейность f выражается через её коэффициенты Уолша - Адамара следующим образом: Nf = d(f, An) = 2n-1 - max |Wf (c)|/2. Более того, из равенства Парсеваля 2 c€F можно найти оценку снизу: max |W/(c)| ^ 2n/2. Таким образом, нелинейность функции всегда удовлетворяет неравенству Nf ^ 2n-1 - 2n/2-1. Определение 11. Максимально нелинейной называется функция, нелинейность которой достигает максимально возможного значения. В случае чётного числа переменных максимально нелинейные функции также называются бент-функциями. Вопрос о том, кто первым начал изучение максимально нелинейных функций, остаётся открытым. Признанный авторитет в ответе на этот вопрос имеет Oscar S. Rothaus. В 1960-х годах он работал математиком в Институте оборонного анализа США и в то же время написал свою первую работу о бент-функциях, которая появилась в открытой печати лишь в 1976 г. Однако с недавнего времени стало известно [8], что бент-функции также изучались в Советском Союзе в 1960-х годах. Среди первых исследователей- В. А. Елисеев и О. П. Степченков, но их работы по-прежнему засекречены. Известно, что они называли бент-функции минимальными функциями и получили ряд утверждений о их свойствах, а также предложили аналог известной конструкции Майорана - МакФарланда. Подробно с историей изучения максимально нелинейных функций, их связи с различными комбинаторными объектами, применении в криптографии, известными конструкциями и открытыми вопросами можно познакомиться по работе Н. Н. Токаревой [42], посвящённой бент-функциям. Чем выше значение нелинейности булевой функции, тем предпочтительнее её использовать как в поточных, так и в блочных шифрах. Приведём далее две атаки на различные виды шифров. 8.1. И д е я б ы с т р о й к о р р е л я ц и о н н о й а т а к и Данный вид атаки на комбинирующий генератор появился вскоре после простой корреляционной атаки (рассмотренной в п. 7.1). Опишем её основную идею, не вдаваясь в подробности теории кодов, исправляющих ошибки [24]. Будем оперировать с тем же комбинирующим генератором, что был описан в п. 7.1. Как и для корреляционной атаки, для быстрой корреляционной атаки необходимо найти линейную функцию £(ж) = (с,ж), с которой у f есть корреляция, т.е. P[f = £] = = 1/2 + е = 1/2. Отличие в том, что нам теперь не важно, каково значение wt(c), а важно лишь, чтобы значение корреляции |е| было как можно больше. Будем считать далее, что е > 0 (иначе вместо £ рассмотрим функцию £ ф 1). Пусть и = ио,и1,и2,... -последовательность, вырабатываемая генератором. Тогда можно представить, что эта «правильная» последовательность (т. е. которую мы можем действительно наблюдать) является результатом внесения помех в «неправильную» последовательность z = z0, z1, z2,... с вероятностью ошибки 1/2 - е, где z получена тем же генератором, но с комбинирующей функцией £ вместо f. Так как мы выбрали е достаточно большим, вероятность ошибки будет маленькой. Допустим, мы можем наблюдать отрезок последовательности и^,... , u&+n-1. Множество всевозможных значений Zk,...,Zk+N-1 является линейным кодом длины N. Тогда, наблюдая фрагмент последовательности и, путём исправления ошибок можно восстановить последовательность z. А это даёт выигрыш в том, что линейная сложность z гораздо ниже линейной сложности и, и достаточно отрезка последовательности гораздо меньшей длины, чтобы восстановить закон рекурсии и начальное состояние регистра с помощью алгоритма Берлекэмпа - Месси. Отметим здесь сразу, что значение корреляции е функции f с аффинными функциями можно оценить снизу через её нелинейность: |е| ^ 2n - 2Nf. Следовательно, чем выше нелинейность, тем меньше максимальная корреляция, а значит, больше вероятность ошибки в моделируемом канале с шумом, что делает менее возможным проведение быстрой корреляционной атаки на комбинирующий генератор с комбинирующей функцией f. 8.2. Идея линейного криптоанализа В 1993 г. японский криптограф M. Matsui предложил статистический метод анализа шифра DES, названный линейным криптоанализом. Опишем идею самой простой его модификации по работе [20] (алгоритм 1). Пусть P, C, K - блоки открытого текста, шифртекста и ключа некоторого блочного шифра. Линейным приближением шифра называется соотношение (а,Р) ф (в, C) = = (y, K), выполняющее с некоторой вероятностью 1/2+е, е = 0, где а, в, Y - некоторые двоичные вектора соответствующих длин. Алгоритм 1. Линейный криптоанализ 1: Находим линейное приближение шифра, для которого |е| как можно больше. 2: При фиксированном неизвестном ключе K набираем выборку из N пар (P, C). 3: Для каждой пары выборки вычисляем значение левой части выбранного на шаге 1 соотношения. Пусть No - количество полученных нулей, а Ni - единиц, N0 + Ni=N. 4: Полагаем (y, K) = 0, если (N0 - Ni)e > 0, и (y, K) = 1 иначе. В результате находим одно линейное соотношение на биты неизвестного ключа, следовательно, можем сократить полный перебор с 2k до 2k-i, где k - количество бит ключа K. Существуют более сильные модификации линейного криптоанализа, которые позволяют находить сразу группу неизвестных битов ключа, но суть остаётся прежней - поиск линейного приближения, но уже не всего шифра, а его части. Основная сложность метода в том, как находить линейное приближение. На практике поступают так: анализируют соотношения, которые выполняются для S-блоков, а затем расширяют их на несколько раундов и на большую часть битов P, C, K. Пусть S-блок шифра задан векторной (n, т)-функцией F. Требуется найти соотношение вида (a, x) ф (b, F(x)) = 0, выполняющееся с некоторой вероятностью p = 1/2+е, где е = 0. Распишем p = P[(a,x) = (b, F(x))] = 1/2 + (2n-i - d((a,x), (b, F(x)))) /2n. Опять, как и для поточного шифра, для того чтобы успешно провести атаку, т. е. максимизировать |е|, необходимо минимизировать расстояние d((a,x), (b, F(x))) по всем возможным ненулевым a E Fn, b E Fm. Соответственно противодействием данной атаке является выбор в качестве S-блоков таких векторных функций, у которых минимальное расстояние d((a,x), (b, F(x))) по всем возможным ненулевым a,b как можно больше. Заметим, что это эквивалентно рассмотрению нелинейности компонентных функций (b, F) функции F. 8.3. Те о р е т и ч е с к и е р е з у л ь т а т ы и о т к р ы т ы е в о п р о с ы Приведём некоторые факты, опираясь на работы [42, 25]. Пусть f - булева функция от n переменных. Ранее мы получили оценку нелинейности Nf ^ 2n-i - 2n/2-i, которая достигается при чётном n для бент-функций. Для нечётного числа переменных точного значения максимальной нелинейности в общем случае не известно. Например, установлено, что при n = 1, 3, 5, 7 для f от n переменных Nf ^ 2n-i - 2(n-i)/2, и данная оценка достигается для квадратичных функций; но при нечётных n > 7 существуют функции, нелинейность которых строго больше 2n-i - 2(n-i)/2. Теорема 6 (нелинейность случайной функции). Существует константа с, такая, что для почти всех булевых функций от n переменных Nf ^ 2n-1 - 2cy/n2n/2-1. Данный результат говорит о том, что нелинейность произвольной функции близка к верхней границе, но, как это часто бывает, нахождение конкретных функций с высокой нелинейностью является нетривиальной задачей. В следующей теореме приведём некоторые известные факты о бент-функциях. Теорема 7. 1. Бент-функции существенно зависят от всех своих переменных. 2. Для бент-функции / от n переменных верно wt(/) = 2n-1 ± 2n/2-1. 3. Для бент-функции / от n переменных верно deg(/) ^ n/2. 4. Конструкция Мэйорана - МакФарланда. Пусть п - любая перестановка на множестве Flf; h - произвольная булева функция от n/2 переменных. Тогда /(x',x//) = (x',n(x//)) ф h(x") является бент-функцией от n переменных. Из утверждений 3 и 4 теоремы 7 можно получить оценки мощности класса Bn бент-функций от n переменных. Утверждение 3 (оценки |Bn|). Справедливо: 22"/2(2n/2)! ^ |Bn| ^ 22"-1+cn/2/2. Известны некоторые улучшения данных оценок, но на качественном уровне они остаются такими же. Видно, что с ростом n разрыв в оценках становится очень большим. Самым насущным открытым вопросом в этой области является установление точного количества бент-функций или хотя бы нахождение более приемлемых оценок мощности класса бент-функций. А это, в свою очередь, связано с поиском новых конструкций. Более подробно об этом можно найти в [42]. Рассмотрим теперь случай векторной булевой (n, т)-функции F. Как мы видели, для того чтобы противостоять линейному криптоанализу, следует выбирать в качестве S-блоков функции, нелинейность компонентных функций которых высока. Поэтому нелинейность векторной функции определяется как Nf = min Nv f) . СлеveFm,v=0 ' довательно, также справедлива оценка Nf ^ 2n-1 - 2n/2-1. Функции, нелинейность которых достигает данной оценки, также называются векторными бент-функциями. Вопрос состоит в том, а всегда ли они существуют? Теорема 8 (существование бент-функций). Векторные бент-функции из Fn в Fm существуют только при m ^ n/2, где n чётно. Теорема 9 (Сидельников). При m ^ n - 1 для нелинейности произвольной век- 1 I (2n - 1)(2n-1 - 1) торной (n, m)-функции F верна оценка NF ^ 2n-1 - - у 3 • 2n - 2 - 2-----. При n = m из оценки Сидельникова следует, что NF ^ 2n-1 - 2(n-1)/2. При этом известно, что оценка точная. Максимально нелинейные (n, ^-функции существуют при нечётных n и называются почти бент-функциями (AB-функциями). Но до сих пор остаётся открытым вопрос о максимальной нелинейности в случаях, если: а) n нечётное и m < n - 1; б) n чётное и n/2 < m < n - 1. 9. Статистическая независимость Понятие статистической независимости введено в [4] в связи с рассмотрением статистических аналогов функций. Определение 12. Булева функция f от n переменных статистически не зависит от подмножества своих пе

Скачать электронную версию публикации

Агибалов Г. П. Избранные теоремы начального курса криптографии: учеб. пособие. Томск: Изд-во НТЛ, 2005. 116с.

Агибалов Г. П. Методы решения систем полиномиальных уравнений над конечным полем // Вестник Томского государственного университета. Приложение. 2006. № 17. С. 4-9.

Агибалов Г. П. Логические уравнения в криптоанализе генераторов ключевого потока // Вестник Томского государственного университета. Приложение. 2003. №6. С. 31-41.

Агибалов Г. П., Панкратова И. А. Элементы теории статистических аналогов дискретных функций с применением в криптоанализе итеративных блочных шифров // Прикладная дискретная математика. 2010. №3. C. 51-68.

Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. Основы криптографии. М.: Гелиос АРВ, 2002. 480с.

Буряков М. Л. Алгебраические, комбинаторные и криптографические свойства параметров аффинных ограничений булевых функций: дис..канд. физ.-мат. наук. М., 2007.

Глухов М. М. О совершенно и почти совершенно нелинейных функциях // Математические вопросы криптографии. 2016. (в печати)

Глухов М. М. Планарные отображения конечных полей и их обобщения. Презентация для конф. «Алгебра и логика, теория и приложения». Красноярск, 21-27 июля, 2013.

Городилова А. А. Характеризация почти совершенно нелинейных функций через подфункции // Дискретная математика. 2015. Т. 27. Вып.3. C.3-16.

Лобанов М. С. Точное соотношение между нелинейностью и алгебраической иммунностью // Дискретная математика. 2006. Т. 18. Вып.3. C. 152-159.

Логачев О. А., Сальников А. А, Смышляев С. В., Ященко В. В. Булевы функции в теории кодирования и криптологии. 2-е изд. М.: МЦНМО, 2012. 584с.

Логачев О. А., Сальников А. А., Ященко В. В. Корреляционная иммунность и реальная секретность // Математика и безопасность информационных технологий. Материалы конф. в МГУ 23-24 октября 2003 г. М.: МЦНМО, 2004. С. 165-171.

Панков К. Н. Асимптотические оценки для чисел двоичных отображений с заданными криптографическими свойствами // Математические вопросы криптографии. 2014. Т. 5. Вып. 4. С. 73-97.

Панкратова И. А. Булевы функции в криптографии: учеб. пособие. Томск: Издательский Дом Томского государственного университета, 2014. 88 с.

Сачков В. Н. Комбинаторные свойства дифференциально 2-равномерных подстановок // Математические вопросы криптографии. 2015. Т. 6. Вып. 1. С. 159-179.

Селезнева С. Н. Мультипликативная сложность некоторых функций алгебры логики // Дискретная математика. 2014. Т. 26. Вып. 4. C. 100-109.

Смышляев С. В. О криптографических слабостях некоторых классов преобразований двоичных последовательностей // Прикладная дискретная математика. 2010. №1. С. 5-15.

Сумароков С. Н. Запреты двоичных функций и обратимость для одного класса кодирующих устройств // Обозрение прикладной и промышленной математики. 1994. Т. 1. Вып. 1. С. 33-55.

Таранников Ю. В. О корреляционно-иммунных и устойчивых булевых функциях // Математич. вопросы кибернетики. 2002. Вып. 11. С. 91-148.

Токарева Н. Н. Симметричная криптография. Краткий курс: учеб. пособие. Новосибирск: Новосибирский государственный университет, 2012. 232 с.

Bilgin B., NikovaS., Nikov V., et al. Threshold implementations of small S-boxes // Cryptography and Communications. 2015. V. 7. No. 1. P. 3-33.

Blondeau C. and Nyberg K. Perfect nonlinear functions and cryptography // Finite Fields and their Applications. 2015. V. 32. P. 120-147.

Braeken A. Cryptographic Properties of Boolean Functions and S-boxes. PhD Thesis, Katholieke Universiteit Leuven, 2006.

Carlet С. Boolean functions for cryptography and error correcting codes // Ch. 8 of the Monograph "Boolean Methods and Models in Mathematics, Computer Science, and Engineering", Cambridge Univ. Press, 2010. P. 257-397.

Carlet C. Vectorial Boolean functions for cryptography // Ch. 9 of the Monograph "Boolean Methods and Models in Mathematics, Computer Science, and Engineering", Cambridge Univ. Press, 2010. P. 398-472.

Carlet C., Charpin P., and Zinoviev V. Codes, bent functions and permutations suitable for DES-like cryptosystems // Des. Codes Cryptogr. 1998. V. 15. P. 125-156.

Charpin P. Normal Boolean functions //J. Complexity. 2004. V. 20. P. 245-265.

Courtois N., Hulme D., and Mourouzis T. Solving Circuit Optimisation Problems in Cryptography and Cryptanalysis. Cryptology ePrint Archive. Report 2011/475 (2011).

Courtois N. and Meier W. Algebraic attack on stream ciphers with linear feedback // LNCS. 2003. V. 2656. P. 345-359.

Cusick T. W. and Stanica P. Cryptographic Boolean Functions and Applications. Acad. Press. Elsevier, 2009. 245 p.

Dobbertin H. Construction of bent functions and balanced Boolean functions with high nonlinearity // FSE'95. LNCS. 1995. V. 1008. P. 61-74.

Evertse J.H. Linear structures in block ciphers // EUROCRYPT'87. LNCS. 1988. V.304. P. 249-266.

Fon-Der-Flaass D. G. A bound on correlation immunity // Siberian Elektron. Mat. Izv. 2007. No. 4. P. 133-135.

Golic J.Dj. On the security of nonlinear filter generators // FSE'96. LNCS. 1996. V. 1039. P. 173-188.

Gorodilova A. On a Remarkable Property of APN Gold Functions. Cryptology ePrint Archive. Report 2016/286 (2016).

Mihaljevic M., Gangopadhyay S., Paul G., and Imai H. An algorithm for the internal state recovery of Grain-v1 // Proc. CECC'2011. Debrecen, Hungary, June 30-July 2, 2011. P. 7-20.

Nikova S., Rechberger C., and Rijmen V. Threshold implementations against side-channel attacks and glitches // LNCS. 2006. V. 4307. P. 529-545.

Nyberg K. Differentially uniform mappings for cryptography // Eurocrypt'93. LNCS. 1994. V. 765. P. 55-64.

Preneel B., Van Leekwijck W., Van Linden L., et al. Propagation characteristics of Boolean functions // Eurocrypt'90. LNCS. 1991. V.473. P. 161-173.

Siegenthaler T. Correlation-immunity of nonlinear combining functions for cryptographic applications // IEEE Trans. Inform. Theory. 1984. V.30. No. 5. P. 776-780.

Tarannikov Y. V. Generalized proper matrices and constructing of m-resilient Boolean functions with maximal nonlinearity for expanded range of parameters // Siberian Elektron. Mat. Izv. 2014. No. 11. P. 229-245.

Tokareva N. Bent Functions: Results and Applications to Cryptography. Acad. Press. Elsevier, 2015. 220 p.

Webster A. F. and Tavares S. E. On the design of S-boxes // Crypto'85. LNCS. 1986. V. 218. P. 523-534.

Zajac P. and Jokay M. Multiplicative complexity of bijective 4 x 4 S-boxes // Cryptography and Communications. 2014. V. 6. No. 3. P. 255-277.

Zhang X.-M. and Zheng Y. GAC - the criterion for Global Avalanche Characteristics of cryptographic functions //J. Universal Computer Science. 1995. V. 1. No. 5. P. 320-337.