Поиск линеаризующих множеств в алгебраическом криптоанализе как задача псевдобулевой оптимизации | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/38

Поиск линеаризующих множеств в алгебраическом криптоанализе как задача псевдобулевой оптимизации

Вводится понятие линеаризующего множества, которое можно рассматривать как обобщение известного понятия линеаризационного множества. Линеаризующие множества используются в основе алгебраических атак, относящихся к классу «угадывай и определяй» (guess-and-determine). В таких атаках угадываются значения переменных из некоторого множества, затем эти значения подставляются в систему алгебраических уравнений, которая связывает входные и выходные данные рассматриваемого шифра. В некоторых случаях результатом такой подстановки является линейная система, которая решается эффективно. Рассматриваются алгебраические уравнения над полем GF(2). Значения переменных из линеаризующего множества (в отличие от линеаризационного) линеаризуют систему уравнений с некоторой вероятностью, которая, вообще говоря, может быть существенно меньше 1. Оценка трудоёмкости атаки на основе конкретного линеаризующего множества строится через специально определяемую псевдобулеву функцию. Минимальное значение этой функции даёт оценку трудоёмкости лучшей по эффективности атаки. Для минимизации таких функций используется метаэври-стический алгоритм из класса «поиск с запретами». На данном этапе построены атаки описанного типа для ряда криптографических генераторов. В частности, для известного генератора A5/1 построена атака с оценкой трудоёмкости в 4,5 раз ниже трудоёмкости известной атаки Андерсона.

Search for linearizing sets in algebraic cryptanalysis as a problem of pseudo-boolean optimization.pdf Понятие линеаризационного множества введено Г. П. Агибаловым в 2003 г. [1] в контексте проблемы построения атак на некоторые генераторы ключевого потока. Атаки, рассмотренные в [1], относятся к классу алгебраических [2]. В основе алгебраических атак лежат эффективные процедуры, сводящие задачи обращения (поиска прообразов) рассматриваемых криптографических функций к поиску решений алгебраических уравнений. Обычно такие уравнения - это уравнения над полем GF(2). Как правило, в результате такой сводимости получается система, не все уравнения которой являются линейными. Известно (см., например, [3]), что задача определения совместности даже квадратичной системы над GF(2) является NP-полной и соответственно не может быть решена в общем случае за полиномиальное время известными алгоритмами. Тем не менее может оказаться так, что угадывание значений относительно небольшого числа переменных в такой системе с последующими эффективными преобразованиями превратит эту систему в линейную. Решая все возможные такие линейные системы, в ряде случаев можно построить атаки, которые существенно эффективнее атаки методом грубой силы. Более точно, рассмотрим всюду определённую функцию / : {0,1}n ^ {0,1}m, заданную некоторым алгоритмом. Требуется по произвольному 7 Е Range / найти такой а Е {0,1}n, что /(а) = 7. Известны теоретические результаты (аналогичные теореме Кука - Левина [3]), в соответствии с которыми сформулированную задачу можно эффективно свести к проблеме поиска решения совместной системы алгебраических уравнений над полем GF(2) (кратко мы опишем такую сводимость ниже). Обозначим такую систему через Ef (7). Пусть X - множество переменных, присутствующих в системе Ef (7). В соответствии с [1], множество B С X называется линеаризацион-ным (для системы Ef(7)), если подстановка любого в Е {0,1}|B| в Ef(7) превращает эту систему в линейную. Через {0,1}|B| обозначено множество всех наборов значений переменных, входящих в B. Подстановка подразумевается в том смысле, как в [1] (или, по сути, в том же смысле, как в [4]). В [1] предъявлены примеры линеаризаци-онных множеств для целого ряда генераторов ключевого потока (Геффе, пороговый, генератор переменного шага). Следует отметить, что в каждом из этих примеров вид множества B не зависит от 7 Е Range f (как правило, такое множество образовано переменными, соответствующими одному или нескольким LFSR, входящим в состав генератора). Получаемые на основе данных множеств атаки оказываются существенно более эффективными, чем атаки методом грубой силы. Введём понятие линеаризующего множества. Главное отличие таких множеств от линеаризационных множеств из [1] заключается в том, что «вероятность линеаризации» рассматриваемой системы наборами значений переменных, образующих такое множество, вообще говоря, меньше 1. Для понимания сути вводимого понятия удобно задать функцию f схемой Sf из функциональных элементов базиса {Л, -}. Припишем входным полюсам схемы переменные, образующие множество X = {x1,...,xn}. Внутренним узлам схемы, которые соответствуют функциональным элементам, припишем переменные, образующие множество V = {v1,...,v^}, V П X = 0. В множестве V выделим подмножество Y = {y1,... ,ym}, переменные которого приписаны выходам Sf. Отметим, что любому а Е {0,1}|X|, поданному на вход Sf, однозначно соответствует набор значений всех переменных из V , получаемый в результате последовательного вычисления значений функций, соответствующих внутренним узлам Sf. Построим по Sf систему алгебраических уравнений над полем GF(2) = ({0, 1}, ф, Л) по следующим правилам. Пусть g - произвольный внутренний узел схемы Sf и v(g) Е Е V - приписанная ему переменная. Если g - это И-узел, то он имеет в графе, представляющем Sf, двух прямых предшественников, пусть им приписаны переменные u и w. Если g - это НЕ-узел, то g имеет единственного предшественника, пусть u - приписанная ему переменная. Сопоставим каждому g уравнение над GF(2): 1) если g - И-узел, то ему сопоставляется уравнение u Л w ф v(g) = 0; 2) если g - НЕ-узел, то ему сопоставляется уравнение u ф v(g) = 1. Объединим уравнения по всем внутренним узлам схемы Sf в общую систему, которую обозначим через Ef. В систему Ef будем подставлять значения некоторых переменных из множества U = X U V. Подстановку определим в соответствии с [4], т.е. для произвольной переменной x Е U и константы Л Е {0,1} скажем, что происходит подстановка x = Л в систему Ef, если все вхождения переменной в Ef заменены вхождением константы Л. После подстановки к соответствующим уравнениям применяются преобразования, называемые элементарными. Например, результат подстановки w = 1 и соответствующего элементарного преобразования в отношении уравнения u Л w ф v = 0 - линейное уравнение u ф v = 0. Иногда результатом подстановки и последующих преобразований могут стать значения некоторых переменных. Например, подстановка v = 1 и последующие преобразования в отношении u Л w ф v = 0 дают уравнение u Л w = 1, откуда следует u = w = 1. Назовём эти значения индуцированными подстановкой v = 1. Индуцированные значения также могут быть подставлены в систему. Подстановка значений для упорядоченного множества переменных определяется индуктивно: подставляется значение первой переменной и все индуцированные данной подстановкой значения, затем значение второй переменной и т. д. Рассмотрим произвольный 7 Е Range / как набор значений переменных из Y и подставим его в Ef. Обозначим полученную систему через Ef (7). Можно показать, что система Ef (7) совместна, и если найдено некоторое её решение, то из него можно эффективно выделить такой а Е {0,1}n, что / (а) = 7. Зададим на {0,1}n равномерное распределение и выберем в соответствии с ним а Е {0,1}n. Пусть 7а = /(а) и B - произвольное подмножество в множестве U \\ Y. Как было сказано выше, подав а на вход схеме Sf, мы эффективно (в общем случае за линейное от числа узлов в Sf время) вычислим значения всех переменных из V, в том числе значения переменных, входящих в B. Обозначим соответствующий набор через в«. Теперь подставим в Ef наборы 7а и в«. Результат этой подстановки и последующих элементарных преобразований обозначим через Ef (y„ , в«). Действуя по аналогии с [5], введём случайную величину £, которая принимает значение 1, если система Ef(7«,в«) -линейная система над GF(2). В противном случае полагаем, что £ = 0. Пусть рв -доля таких векторов а Е {0,1}n, для которых £ =1. Таким образом, рв -это некоторая числовая характеристика множества B. Очевидно, что рв = M[£]. Тогда для конкретного B по схеме, которая аналогична предложенной в [5], можно оценить рв при помощи метода Монте-Карло [6]. Определение 1. В контексте рассмотренной задачи назовём множество B линеаризующим множеством с вероятностью линеаризации рв. Для произвольного B С U \\ Y и вероятности линеаризации рв можно описать следующую стратегию поиска прообразов функции /. Полагаем, что а выбран из {0,1}n в соответствии с равномерным распределением. Известен алгоритм вычисления / и 7« = /(а). Требуется найти а. Пусть известно некоторое множество B с вероятностью линеаризации рв. Для каждого в Е {0,1}|в| будем рассматривать систему Ef (7^, в). Если Ef (7а,в) не является линейной системой, то не делаем в её отношении никаких действий и переходим к следующему в. Вероятность события «Ef (7«,в«) -линейная» равна рв. Если Ef (7«,в«) -линейная, то, решив её, найдём а. Таким образом, для конкретного 7а и конкретного B, перебрав всё множество {0,1}|в|, мы линеаризуем систему с помощью вектора в« Е {0,1}|в| (и соответственно находим а) с вероятностью рв. Если для конкретного 7а описанная стратегия не даёт результата (то есть при переборе всех векторов из {0,1}|в| вектор в« не линеаризует соответствующую систему), то рассматриваем следующий выход функции / (полагаем, что он также построен по случайно выбранному из {0,1}n входу). Вероятность того, что для случайно и независимо выбранных входов а1,''' , аг при помощи описанной стратегии удастся обратить хотя бы один 7а1,''' , 7ar (y^. = / ^j) , j Е {1,''' , r}) есть Pв(r) = 1 - (1 - рв)r и стремится к 1 с ростом r. Если мы хотим, чтобы Pв(r) > 95%, то, как нетрудно видеть, при малых рв (рв < 0,2) r должно быть не меньше 3/рв (аналогичная ситуация разобрана в [5]). Будем считать единицей трудоёмкости операцию подстановки в в систему Ef (7^) и проверки получаемой системы на линейность. Тогда трудоёмкость описанной атаки при условии, что Pв(r) > 95%, составит ^ 2|в| • 3/рв таких единиц. Отметим, что линеаризационные множества, примеры которых приведены в [1] в отношении генераторов Геффе, порогового и переменного шага (Alternating Step Generator), -это линеаризующие множества с рв = 1. Нетрудно понять, что, например, B = X - это тривиальный пример линеаризующего множества с рв = 1. Соответственно нетривиальные такие множества, вероятность рв для которых может быть существенно меньше 1, можно искать как подмножества X. С этой целью, действуя по аналогии с [5], введём специальную функцию Ф(В), оценивающую трудоёмкость атаки описанного типа и использующую множество B. На вход она получает булев вектор, единицы в котором означают присутствие переменных из X в множестве В. Значение функции - это оценка величины 2|в| • 3/рв, для построения которой вероятность рв оценивается методом Монте-Карло. Функция Ф(В) -это «псевдобулева» функция [7]. Множество В, на котором значение Ф(В) минимально, даст атаку описанного типа с лучшей трудоёмкостью. Для минимизации псевдобулевых функций, которые не заданы аналитически (как в нашем случае), используются различные метаэвристические алгоритмы. Мы использовали для этих целей метаэвристику, известную как «поиск с запретами» (Tabu Search) [8]. Соответствующий алгоритм реализован в форме многопоточного приложения и запускался на одном рабочем узле кластера «Академик В. М. Матросов» Иркутского суперкомпьютерного центра [9] (36 ядер процессора Intel Xeon E5-2695). Для построения систем вида Ef использовались возможности программы Transalg [10, 11] (в частности, схема Sf строилась в виде И-НЕ-графа). Полученные на данном этапе вычислительные результаты можно оценивать как предварительные. Так, для ASG-192 (генератора переменного шага с ключом длиной 192 бит) в автоматическом режиме (как результат минимизации функции Ф(В)) найдено линеаризующее множество, состоящее из переменных управляющего регистра (т. е. фактически линеаризационное множество из [1]). Для ASG-96 лучшая оценка трудоёмкости достигнута для множ^хества с рв ^^ 99%. Интересный результат получен для известного генератора A5/1. Одна из первых атак на данный генератор, описанная в [12] (атака Андерсона), фактически использовала линеаризационное множество, состоящее из 53 бит (в A5/1 используется ключ длиной 64 бита). То есть «множество Андерсона» из [12] -это линеаризующее множество с рв = 1. С использованием процедуры минимизации функции вида Ф(В) для A5/1 было найдено линеаризующее множество, состоящее из 47 переменных с рв ~ 0,071. Оценка трудоёмкости атаки на основе этого множества оказалась примерно в 4,5 раз ниже, чем трудоёмкость атаки Андерсона.

Ключевые слова

атаки из класса «угадывай и определяй», линеаризующие множества, псевдобулева оптимизация, guess-and-determine attacks, linearizing sets, pseudo-Boolean optimization

Авторы

ФИООрганизацияДополнительноE-mail
Семёнов Александр АнатольевичИнститут динамики систем и теории управления им. В. М. Матросоваандидат технических наук, доцент, заведующий лабораторией 6.2biclop.rambler@yandex.ru
Антонов Кирилл ВалентиновичИркутский государственный университетстудент ИМЭИaknitr@mail.ru
Отпущенников Илья ВладимировичИнститут динамики систем и теории управления им. В. М. Матросовакандидат технических наук, научный сотрудник лаборатории 6.2otilya@yandex.ru
Всего: 3

Ссылки

Агибалов Г. П. Логические уравнения в криптоанализе генераторов ключевого потока // Вестник Томского госуниверситета. Приложение. 2003. №6. С. 31-41.
Bard G. Algebraic Cryptanalysis. Springer Publishing Company, Inc., 2009.
Goldreich O. Computational Complexity: A Conceptual Perspective. Cambridge: Cambridge University Press, 2008.
Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983.
Semenov A., Zaikin O., Otpuschennikov I., et al. On cryptographic attacks using backdoors for SAT // Thirty-Second AAAI Conf., 2018. P. 6641-6648. https://arxiv.org/abs/1803. 04646.
Metropolis N. and Ulam S. The Monte Carlo method // J. Amer. Statistical Association. 1949. V. 44. No. 247. P. 335-341.
Boros E. and Hammer P. Pseudo-Boolean optimization // Discr. Appl. Math. 2002. V. 123, Iss. 1-3. P. 155-225.
Glover F. and Laguna M. Tabu Search. Norwell: Kluwer Academic Publishers, 1997.
ЦКП Иркутский суперкомпьютерный центр СО РАН. http://hpc.icc.ru
Отпущенников И. В., Семенов А. А. Технология трансляции комбинаторных проблем в булевы уравнения // Прикладная дискретная математика. 2011. №1(11). С. 96-115.
Otpuschennikov I., Semenov A, Gribanova I., et al. Encoding cryptographic functions to SAT using TRANSALG system // Frontiers in Artificial Intelligence and Applications. 2016. V. 285. P. 1594-1595.
Anderson R. A5 (Was: Hacking digital phones). Newsgroup Communication. 1994. http: //yarchive.net/phone/gsmcipher.html.
 Поиск линеаризующих множеств в алгебраическом криптоанализе как задача псевдобулевой оптимизации | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/38

Поиск линеаризующих множеств в алгебраическом криптоанализе как задача псевдобулевой оптимизации | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/38