Криптоавтоматы с функциональными ключами | ПДМ. 2017. № 36. DOI: 10.17223/20710410/36/5

Криптоавтоматы с функциональными ключами

Определяется понятие криптографического автомата (называемого также крип-тоавтоматом) как некоторого класса C автоматных сетей с фиксированной структурой N, построенных с помощью операций последовательного, параллельного и с обратной связью соединений инициальных конечных автоматов с функциями переходов и выходов, принадлежащими произвольным функциональным классам. Ключ криптоавтомата может содержать в себе начальные состояния и функции переходов и выходов некоторых компонент в N так, что задание любого конкретного ключа k влечёт за собой выбор вполне определённой автоматной сети Nk в C в качестве нового криптографического алгоритма. В случае обратимого автомата сети этот алгоритм может выступать в роли алгоритма шифрования. Функционирование сети Nk в дискретном времени описывается канонической системой уравнений конечного автомата, сопоставляемого этой сети. Её структура описывается системой уравнений, объединяющей в себе системы канонических уравнений компонент сети. Криптоанализ криптоавтомата осуществляется путём решения функциональной или структурной системы уравнений сети Nk и доопределения возникающих при этом частичных функций её компонент в заданных классах. В роли одного из инструментов решения автоматных уравнений используется метод DSS, который в применении к некоторой системе уравнений E является итерацией следующей тройки действий: 1) E разделяется (Divided) на две подсистемы E/ и E//, где E/ легко решаема; 2) E/ решается (Solved); 3) решение E/ подставляется (Substituted) в E//. В криптографических системах криптоавтома-ты находят применение в качестве их компонент - криптографических генераторов, блоков замены, фильтров, комбайнеров, ключевых хеш-функций, а также систем шифрования, симметричных и с открытым ключом, и схем цифровой подписи. Определение и криптоанализ иллюстрируются на примере автономного криптоавтомата, обобщающего известную схему криптографического генератора с альтернативным управлением, или с перемежающимся шагом, построенного на регистрах сдвига с линейной обратной связью. Представлен ряд атак на этот крип-тоавтомат с ключами различных типов, сочетающих в себе комбинаторные или функциональные свойства, выраженные начальными состояниями или функциями выходов компонент в схеме криптоавтомата.

Cryptautomata with functional keys.pdf 1. Автоматные сети В современной криптографии важное место занимают криптосистемы и их компоненты, представляющие собой сети, построенные с помощью операций последовательного, параллельного и с обратной связью соединений инициальных конечных автоматов. Первые две операции бинарные. Для любых двух автоматов Aj = = (Xj, Sj, Yj, gj, fj, Sj (1)) с конечными входными алфавитами Xj, выходными алфавитами Yj, множествами состояний Sj, начальными состояниями sj(1) и c функциями переходов и выходов соответственно gj : Xj х Sj ^ Sj и fj : Xj х Sj ^ Yj, i G {1, 2}, их результатами являются автоматы A = (X, S, Y, g, f, s(1)), в которых S = S1 х S2, s(1) = s1(1)s2(1) и для любых x G X и s = s1 s2 G S: - для последовательного соединения A1 • A2 верно X = X1, Y = Y2, g(x, s) = (g1(x, s1), g2(f1(x,s1),s2)) и f(x,s) = f2(f1(x,s1),s2); - для параллельного соединения (A1 || A2)h с отображением связи h : Y1 x Y2 м Y верно X = X1 = X2, g(x,s) = (g1(x, s^, g2(x, S2)) и f (x,s) = h(f1(x, S1), f2(x, S2)). Третья операция унарная: в автомате A сети hA1 , являющейся результатом её применения к автомату A1 с отображением связи h : X x Y1 м X1, верно S = S1, Y = Y1, g(x, s) = g1(h(x, f1(s)), s), f (x, s) = f1(s) для произвольного X и любых x G X и s G S. В определении последнего соединения предполагается, что A1 есть автомат Мура, в нём функция выходов зависит только от состояния. Формально автоматная сеть и её компоненты определяются индуктивно следующим образом: 1. Всякий конечный автомат является автоматной сетью и одновременно её единственной компонентой. 2. Последовательное, параллельное и с обратной связью соединения автоматных сетей есть автоматная сеть. Её компонентами являются компоненты этих сетей. 3. Других автоматных сетей нет. По определению, всякая автоматная сеть однозначно определяется своими компонентами и отображениями связи между ними. 2. Канонические уравнения Функционально любую автоматную сеть можно описать системой уравнений, называемой её канонической системой уравнений (КСУ) и определяемой по индукции построения сети следующим образом. 1. Каноническая система уравнений автомата A = (X, S, Y, g, f, s(1)) есть система уравнений от переменных x(t), s(t), y(t), t = 1, 2,..., со значениями в X, S, Y соответственно, записываемая как y(t) = f (x(t),s(t)), s(t + 1) = g(x(t), s(t)), t ^ 1, s(1) - начальное условие. Далее эта система обозначается KCy(A; x, s,y, s(1)). 2. Каноническая система уравнений сети A1 • A2 записывается в виде KCy(A1; x, s1, y1, s1(1)), KCy(A2; yb s2, y, s2(1)) и обозначается KCy(A1 • A2; x, s1, s2, y, s1(1)s2(1). 3. Каноническая система уравнений сети (A1 || A2)h записывается в виде KCy(A1; x,s1,y1,s1(1)), KCy(A2; x, s2, У2, s2(1)), y(t) = h(y1(t),y2(t)), t ^ 1, и обозначается KCy((A1 || A2)h; x, s1, s2, y, s1(1)s2(1)). 4. Каноническая система уравнений сети hA1 записывается в виде KCy(A1;x1,s1,y1,s1(1)), x1(t) = h(x(t),y1(t)), y(t) = y1(t), t ^ 1, и обозначается KCy(hA1; x, s1, y, s1 (1)). По определению, переменные в КСУ любой автоматной сети N подразделяются на входную - x, выходную - y, внутренние - si (они же переменные состояний компонент в N) и вспомогательные - xo-, y^ (посредством их осуществляется связь между компонентами в N). Внутренние и вспомогательные переменные называются иногда промежуточными. Переменная t трактуется как дискретное время, а u(t) - как значение любой другой переменной u в момент времени t. Значение переменной состояния некоторой компоненты сети в момент t = 1 называется начальным состоянием этой компоненты. 3. Определение криптоавтомата Понятие криптоавтомата восходит к работе [1], где под ним подразумевается конечный автомат с ключом и приводятся примеры описания такими криптоавтоматами генераторов ключевого потока MUGI и KNOT - в поточных шифрах, блоков замены L, M, R, S и управляющего ими блока stepping - в японской шифрмашине Purple и симметричного конечно-автоматного шифра Закревского. Здесь мы расширяем это понятие, подразумевая под криптоавтоматом класс автоматных сетей с ключом, который может включать в себя и начальные состояния компонент сети, и их функции переходов и выходов так, что любое фиксирование значения ключа выделяет в классе некоторую конкретную сеть для выполнения соответствующего криптографического преобразования. Условимся далее множество всех функций, имеющих одинаковые области соответственно определения и значений и обладающих некоторыми фиксированными свойствами, называть (функциональным) классом. Так, можно говорить, например, о классах булевых функций, зависящих от одних и тех же множеств переменных и обладающих ограниченной сложностью задания или вычисления и одинаковыми криптографическими свойствами - нелинейностью, корреляционной иммунностью и т. п. Аналогично, можно говорить и об автоматных классах, или классах автоматов с функциями переходов и выходов из некоторых фиксированных функциональных классов. Наконец, можно говорить и о классах автоматных сетей, в которых между компонентами разных сетей существует взаимно однозначное соответствие, такое, что соответствующие компоненты принадлежат одному и тому же автоматному классу. Таким образом, автоматные сети из одного и того же класса имеют общую структуру (схему соединений компонент) и могут различаться лишь начальными состояниями компонент и их функциями переходов и выходов в своих классах. Принимая за ключ конкретные значения этих величин (начальных состояний и (или) функций переходов и выходов) в каких-либо компонентах автоматных сетей класса, мы тем самым выделяем в этом классе конкретную автоматную сеть, подобно тому как, фиксируя значение ключа в криптосистеме, мы превращаем её в конкретный криптоалгоритм. Эти рассуждения приводят нас к следующим определениям. Определим класс автоматной сети N как множество C(N) всех автоматных сетей, которые получаются из N с помощью операций замены в N начальных состояний некоторых компонент, и (или) функций переходов некоторых компонент, и (или) функций выходов некоторых компонент с сохранением их функциональных классов. Ясно, что этими операциями можно любую сеть в C(N) получить из любой другой сети в C(N), т.е. для любой сети N' в C(N) имеет место равенство C(N') = C(N), в связи с чем можно говорить о классе автоматных сетей как о любом таком их множестве C, в котором существует сеть N со свойством C(N) = C, или, что то же самое, для всех N в C верно это свойство. В дальнейшем класс автоматных сетей понимается именно в этом смысле. Тройка £ = (C, I,K) называется криптографическим автоматом, или сокращённо криптоавтоматом, если C есть некоторый класс автоматных сетей, C = C(N) для некоторой сети N, I = {Is, It, Io}, где Is, It и Io суть множества, некоторые из которых непустые и состоят из номеров компонент в N, чьи начальные состояния (s - state), функции переходов (t - transition) и функции выходов (o - output) соответственно составляют ключ криптоавтомата, и K - множество всех возможных значений этого ключа. В нём C называется сетевым классом, I - носителем ключа и K - ключевым пространством криптоавтомата. Так, пусть N состоит из компонент A1, A2,... , Ar, где Ai для каждого i E {1, 2,...,r} есть автомат с множеством состояний Si и с функциями переходов и выходов из некоторых функциональных классов Gi и Fi соответственно. Тогда Is, It, 1o суть подмножества в {1, 2,... , r}, такие, что для любого i E {1, 2,... , r} если i E Is, i E It или i E 1o, то соответственно для каждого s E Si, g E Gi или f E Fj найдётся сеть в C, в i-й компоненте которой s является начальным состоянием, g - функцией переходов или f - функцией выходов соответственно, а если i E Is, i E I или i E 1o, то соответственно начальные состояния, функции переходов или функции выходов i-й компоненты во всех сетях в C одинаковы. Кроме того, ключевое пространство криптоавтомата Е равно K = Ks х Kt х Ko, где Ks = П Si, Kt = П Gi, ieis ieit Ko = Fi и - символ декартова произведения. ieio Каждый ключ k = ksktko в ключевом пространстве K криптоавтомата Е состоит из трёх частей, не все из которых пустые: ks - набор значений начальных состояний компонент криптоавтомата с номерами в Is, kt - набор функций переходов компонент криптоавтомата с номерами в It и ko - набор функций выходов компонент криптоавтомата с номерами в Io. Его задание выделяет в C однозначно некоторую конкретную сеть N, в которой начальные состояния компонент Ai для i E Is принадлежат набору ks, функции переходов компонент Ai, i E It, - набору kt и функции выходов компонент Ai, i E Io, - набору ko. Мы допускаем к рассмотрению и автономные автоматы (в них функции переходов и выходов зависят только от состояния), и комбинационные автоматы (в них функция выходов не зависит от состояний и нет нужды ни в множестве последних, ни в функции переходов), и обратимые автоматы (в них входная последовательность однозначно определяется по выходной и, возможно, по начальному состоянию). По определению, каждая автоматная сеть является конечным автоматом, поэтому все понятия, введённые для автоматов, переносятся на автоматные сети и на криптоавтоматы, построенные на основе их классов. Так, в случае комбинационности, автономности или обратимости автомата сети сама сеть также называется комбинационной, автономной или обратимой соответственно. Можно говорить, следовательно, и о криптоавтоматах такого рода. 4. Примеры криптоавтоматов Кроме приведённых выше примеров однокомпонентных криптоавтоматов, под определение криптоавтомата на основе класса автоматных сетей подпадают и роторные машины, включая Энигму, и уже упоминавшаяся пурпурная шифрсистема Purple, и конечно-автоматные криптосистемы с открытым ключом для шифрования и цифровой подписи семейства FAPKC [1, 2]. Комбинационные криптоавтоматы обычно состоят из комбинационных компонент и в таком составе часто могут применяться в роли блоков замены в тех блочных шифрах с аддитивными раундовыми ключами, которые являются листьями «дерева», выросшего из корня DES. Более того, сами шифры на этом дереве допускают описание комбинационными криптоавтоматами. Чтобы это понять, достаточно заметить, что сложение бит раундового ключа со значениями на входе блока замены превращает функции последнего в функции, зависящие ещё и от ключа шифра. По определению, каждая автономная сеть является последовательным соединением автоматных сетей, в котором на месте первой компоненты (автомата A1) выступает автономный автомат. Автономные сети порождают последовательности выходных символов, и основанные на них криптоавтоматы мы называем конечно-автоматными криптографическими генераторами. Огромное множество примеров таких крипто-автоматов доставляют конечно-автоматные обобщения криптографических генераторов, построенных в виде схем из регистров сдвига с линейными обратными связями (LFSRs). Одно такое обобщение рассмотрено в [3, 4]. Далее, в п. 8, мы рассмотрим криптоавтоматное обобщение ещё одного генератора на LFSRs - криптографического генератора с альтернативным управлением [5], называемого в [6] the alternating step generator и в [7] -генератором с перемежающимся шагом. 5. Задачи криптоанализа Предполагается, что криптоаналитику, исследующему криптоавтомат (C, I, K), известны все составляющие его множества C, I и K. Для автономного криптоавтома-та Е = (C, I, K) есть только одна задача криптоанализа: по кратчайшему отрезку Y = y(1)y(2) ... y(l), l ^ 1, последовательности на выходе сети N в C узнать его ключ k Е K. Задача фактически распадается на три других: 1) сформулировать необходимые и достаточные условия единственности автоматной сети в C, порождающей y; 2) разработать метод, позволяющий по любому такому отрезку Y построить каждую из сетей в C, которая может сгенерировать эту y; 3) по любой сети N в C, порождающей y, вычислить ключ k. Умея это делать, можно сформулированную задачу криптоанализа автономного криптоавтомата Е = (C, I, K) решать следующим образом: последовательность на выходе неизвестной сети N в C наблюдается до тех пор, пока не будет получен отрезок Y, для которого выполнены условия единственности в задаче 1, после чего методом в задаче 2 строится искомая сеть, а потом методом задачи 3 по этой сети вычисляется искомый ключ. Для неавтономного криптоавтомата Е = (C, I, K) можно указать по меньшей мере две задачи криптоанализа: полное раскрытие - по заданным отрезкам а = = x(1)x(2).. . ж(/) и y = y(1)y(2).. .y(l), l ^ 1, соответствующих входной и выходной последовательностей неизвестной сети N в C вычислить ключ k, и раскрытие сообщения- по отрезку y на выходе сети N вычислить отрезок а на её входе, который она преобразует в y. Оптимизационный вариант каждой из этих задач формулируется аналогично задаче криптоанализа автономного криптоавтомата. Раскрытие ключа в любом случае возможно тривиальным методом - так называемой атакой грубой силы (от англ. Brute-Force Attack (BFA)), состоящей в опробовании каждого ключа в K на соответствие определяемой им сети в C исходным данным: выходной последовательности - в автономном случае или выходной и входной последовательностей - в неавтономном случае. Вычислительная сложность этого метода, естественно, оценивается мощностью ключевого пространства криптоавтомата. 6. Доопределение частичной функции в заданном классе Для произвольного класса F функций / : Vn м V над конечным множеством (алфавитом) V и для произвольной частичной функции /' : Df/ С Vn м V мы говорим, что /' доопределима в классе F, если существует функция / Е F, такая, что /'(v) = /(v) для всех v Е Df; в этом случае говорят, что /' доопределима до /. В криптоанализе криптографических систем с функциональными ключами, в том числе и криптоавтоматов, возникает проблема доопределения некоторых частичных функций до функций в заданном классе F, состоящая в выяснении существования и единственности такого доопределения и в построении всевозможных функций в классе, до которых доопределима заданная частичная функция. Решение этой проблемы для любого класса F возможно тривиальным методом - так называемым исчерпывающим поиском (от англ. Exhaustive Search Method (ESM)), который заключается в проверке для каждой функции в F, доопределима ли до неё заданная частичная функция. Вычислительная сложность этого метода, естественно, оценивается мощностью класса F. Других общих методов решения данной проблемы (для всех классов F) неизвестно. В [8, 9] можно найти её нетривиальное решение для класса F булевых функций от n переменных, в котором булевы функции зависят существенно от ограниченного числа k < n последних. Здесь мы продемонстрируем эту проблему в криптоанализе уже упоминавшегося криптоавтоматного генератора с альтернативным управлением. Основным инструментом в этом криптоанализе служит метод DSS решения систем автоматных уравнений. 7. Метод DSS 7.1. Определение Подмножество L переменных в некоторой системе уравнений E над конечным алфавитом называется эффективным множеством, если фиксирование любых возможных значений этих переменных превращает E в легко решаемую (например, за полиномиальное или меньшее время) систему (ЛРС). В частности, таковым является подмножество переменных, при любом фиксировании которых все уравнения в системе над конечным полем превращаются в линейные. Оно называется линеаризационным множеством переменных системы [5, 10]. Система уравнений E над k-элементным алфавитом с q-элементным эффективным множеством переменных L решается со сложностью kq методом DS (Devide and Solve), или по-русски «разделяй и решай», состоящим в подстановке в систему E поочерёдно различных наборов значений переменных в L и в решении получаемой каждый раз ЛРС. В случае совместности последней её решение, взятое вместе с подставленным в E набором значений переменных в L, является решением системы E. Метод DS на основе линеаризационного множества переменных со значениями в конечном поле называется линеаризационной атакой [5, 10]. В нём решается частный случай ЛРС - система линейных уравнений. Система уравнений E называется рекурсивно легко решаемой системой (РЛРС), если в ней существует непустая подсистема уравнений E/ с небольшим эффективным подмножеством (ныне это не более 3-4 десятков) переменных, такая, что подсистема уравнений E \ E/ подстановкой в неё любого решения подсистемы E/ преобразуется в РЛРС. По определению, такая система решается кратным применением метода DS к её подсистеме и подстановки полученных решений подсистемы в её дополнение. В [3] данный метод решения РЛРС назван DSS - Devide, Solve and Substitute («разделяй, решай и подставляй»). Можно сказать, что метод DS является частным случаем метода DSS, а именно методом DSS с однократным применением метода DS. Таким образом, и линеариза-ционная атака на систему уравнений над конечным полем - это тоже частный случай метода DSS. Далее мы продемонстрируем этот метод применительно к каноническим системам уравнений конечных автоматов и автоматных сетей над полем F2 из двух элементов. Переложение излагаемого материала на автоматные системы уравнений над произвольным алфавитом V возможно простой заменой F2 на V, которая не меняет существа метода и лишь увеличивает его вычислительную сложность. 7.2. Р е ш е н и е к а н о н и ч е с к о й с и с т е м ы у р а в н е н и й а в т о м а т а Покажем, как методом DSS может быть решена каноническая система уравнений E произвольного конечного автомата A = (F2, Fm, F2,g,f, s(1)) над F2 при известных функциях g и f, заданных начальном состоянии s(1) G Fm и выходной последовательности y(1)y(2) . ..y(l) G F'2 и неизвестной входной последовательности x(1)x(2)... x(l) G F2: y(t) = f (x(t), s(t)), s(t + 1) = g(x(t), s(t)), 1 ^ t ^ l. В самом деле, при t =1 имеем уравнение y(1) = f (x(1),s(1)), которое для x(1) имеет либо два решения -0 и 1, если y(1) = f (0,s(1)) = f (1,s(1)), либо одно решение - некоторое b(1) G F2, если y(1) = f (b(1),s(1)) = f (-b(1), s(1)), либо ни одного решения, если y(1) = f(0,s(1)) = f(1,s(1)). В последнем случае система E несовместна. При 2 ^ t ^ l для каждого из найденных решений для x(1)x(2) ... x(t - 1) вычисляем s(t) = g(x(t - 1), s(t - 1)) и получаем уравнение y(t) = f (x(t),s(t)), которое тоже может иметь одно (b(t)), два (0 и 1) или ни одного решения для x(t). В последнем случае рассматриваемый вариант частичного решения x(1)x(2)... x(t - 1) отвергается, а в остальных случаях из него получаются соответственно один или два варианта расширенного частичного решения x(1)x(2)... x(t - 1)x(t) - соответственно с x(t) = b(t) или с x(t) = 0 и с x(t) = 1. Если на некотором шаге с номером t ^ l множество полученных частичных решений оказывается пустым, система E объявляется несовместной; в противном случае все её решения для x(1)x(2)... x(l) находятся на l-м шаге. Алгоритмически метод представляет собой обход дерева решений высоты не более l со степенями исхода вершин не более 2. В нём на путях от корня к листьям, имеющих длину l, лежат все решения КСУ автомата - все его входные последовательности x(1)x(2)... x(l), преобразуемые им в выходную последовательность y(1)y(2) ... y(l). В случае, если A есть автомат Мура (в нём функция выходов зависит от входного символа фиктивно), то уравнение y(t) = f (x(t), s(t)) в его канонической системе имеет для x(t) два решения (0 и 1) или ни одного, вследствие чего в её дереве решений из каждой неконцевой вершины исходят ровно две дуги. Заметим также, что если A является автоматом некоторой автоматной сети, то метод DSS по выходной последовательности этой сети находит её возможные входные последовательности. Кроме того, если A есть некоторая компонента автоматной сети над F2, то метод DSS вычисляет входные последовательности этой компоненты по её выходной последовательности в сети. Далее мы покажем, как эти задачи решаются методом DSS непосредственно по канонической системе уравнений автоматной сети без построения её автомата. Ввиду индуктивности определения автоматных сетей достаточно показать это для базовых операций их построения - последовательного, параллельного и с обратной связью соединений автоматов над F2. 7.3. Р е ш е н и е к а н о н и ч е с к о й с и с т е м ы у р а в н е н и й п о с л е д о в а т е л ь н о й а в т о м а т н о й с е т и Начнём с рассмотрения канонической системы уравнений последовательного соединения автоматов A1 • A2 над F2: KCY(A1; x, s1, y1, s1(1)), KCY(A2; y1, s2, y, s2(1)). В ней подсистема y(t) = f2(y1(t),S2(t)), S2(t +1)= g2(x2(t),S2(t)), 1 ^ t ^ l, с начальным условием s2(1) является канонической системой уравнений автомата A2 и может быть решена методом DSS, как только что описано, при известных его функциях g2 и f2 и заданных его начальном состоянии s2(1) G F^2 и выходной последовательности y(1)y(2)... y(l) G F^. В результате будут найдены в F'2 возможные входные последовательности y1 (1)y1(2)... y1(1) автомата A2, среди которых присутствуют и все те выходные последовательности автомата A1 с неизвестными атрибутами s1(1),g1, f1, которые он может выработать в ответ на входные последовательности сети, вызывающие на её выходе последовательность y(1)y(2)... y(Z). При известных s1(1),g1,f1 аналогичным образом по выходной последовательности y1(1)y1(2) ...y1(/) автомата A1 вычисляются его входные последовательности x1(1)x1(2).. .x1(/), являющиеся одновременно входными последовательностями сети. 7.4. Решение канонической системы уравнений п а р а л л е л ь н о й а в т о м а т о й с е т и Рассмотрим теперь каноническую систему уравнений E = KCy((A1 || A2)h; x, s1, s2, y, s1(1)s2(1)) параллельного соединения автоматов (A1 || A2)h над F2 с отображением h : F2 x F2 м F2 KCy(A1; x,s1,y1,s1(1)), KCY(A2; x, s2, y2, s2(1)), y(t) = h(y1(t),y2(t)), 1 ^ t ^ l. Пусть далее Mh(t) = {(y!(t),y21 (t)), (y2(t), y|(t)),..., (y?(t),y?(t))} = h-1(y(t)) = = {(y1(t),y2(t)) G F2 : h(y1 (t),y2(t)) = y(t)}, t ^ 1. Здесь n = |Mfc(t)| ^ 4. После подстановки в систему E вместо пар переменных (y1 (t), y2 (t)) их возможных значений (y1 (t), y2(t)) для j G {1, 2,..., nt} из Mh(t) эта система принимает вид Ej: y(t) = h(y1 (t),y2(t)), yj (t) = f1(x(t),s1(t)), yj (t) = f2(x(t),s2(t)), s1(t + 1) = g1(x(t),s1(t)), s2(t + 1) = g2(x(t),s2(t)), 1 ^ t ^ l, s1(1), s2(1) - начальные условия. Последовательно для t со значениями 1, 2, ..., / из второго и третьего уравнений находим для неизвестного x(t) либо два решения - 0 и 1 (говорим, что имеет место случай 2), если yj(t) = f1(0, s1(t)) = f1(1, s1 (t)) и yj(t) = f2(0, s2(t)) = f2(1, s2(t)), либо одно решение - 0 или 1 (случай 1), если (yj(t) = f1(0,s1(t))) Л (yj(t) = f2(0,s2(t))) Л [(yj(t) = f1(1,s1(t))) V (yj(t) = f2(1,s2(t)))]V V(y1(t) = f1(1,s1(t))) Л (y2(t) = f2(1, s2(t))) Л [(y1(t) = f1(0,s1(t))) V (y2(t) = f2(0,s2(t)))], либо ни одного решения (случай 0), если [(yj (t) = f1(0, s1(t))) V (yj (t) = f2(0, s2(t)))] Л [(yj (t) = f1(1, s1(t))) V (yj (t) = f2(1, s2(t)))]. Найденное так множество решений для x(t) в Ej обозначим Bj (t) и положим B (t) = B1(t) U ... U Bnt (t). По построению B(t) С F2. В случае B (t) = 0 система E несовместна. В противном случае для каждого из найденных решений x(t) в B (t) вычисляем s1 (t + 1) = g1(x(t), s1(t)) и s2(t + 1) = g2(x(t), s1(t)) и аналогичным образом находим множество B(t + 1) решений в F2 для x(t + 1). После I таких шагов, т.е. при t = l, получаем множество {x(1)x(2) ...x(l) : x(t) Е B(t),t Е {1, 2,...,/}} всех решений системы уравнений E параллельного соединения автоматов. Его элементы суть всевозможные входные последовательности сети (A1 || A2)h, которые она с фиксированными компонентами и их начальными состояниями преобразует в выходную последовательность y(1)y(2).. .y(l). 7.5. Решение канонической системы уравнений автоматной с е т и с о б р а т н о й с в я з ь ю Рассмотрим наконец каноническую систему уравнений E = KCY(hA1; x, s^ y, s1(1)) автоматного соединения hA1 над F2 с обратной связью h : F2 х F2 ^ F2 KCy(A1; x1,s1,y1), x1 (t) = h(x(t),y1(t)), y(t) = y1 (t), 1 ^ t ^ l. В ней подсистема уравнений компоненты A1 с 1 ^ t ^ l решается методом DSS, как каноническая система уравнений автомата Мура (см. п. 7.2) при заданных s1(1),g1,f1 и выходной последовательности сети y(1)y(2) . . . y(l). Результатом решения являются входные последовательности x1(1)x1(2).. .x1(l) автомата A1. По каждой из них и выходной последовательности сети методом DSS решается система уравнений x1 (t) = h(x(t),y(t)), 1 ^ t ^ l, и находятся входные последовательности сети x(1)x(2)... x(l), а именно: для каждого целого j, 1 ^ j < l, и для каждого решения x(1)x(2) ... x(j - 1) её подсистемы с 1 ^ ^ t ^ j - 1 её подсистема с 1 ^ t ^ j имеет либо два решения x(1)x(2)... x(j - 1)x(j) c x(j) Е F2, если x1(j) = h(0,y(j)) = h(1,y(j)), либо одно решение c x(j) = b, b Е F2, если x1 (j) = h(b,y(j)) = h(-b,y(j)), либо ни одного решения, если x1(j) = h(0,y(j)) = = h(1,y(j)). 8. Криптогенератор с альтернативным управлением 8.1. Определение Рассмотрим автоматные сети с альтернативным управлением, представляющие собой последовательно-параллельные соединения трёх автоматов над полем F2. В каждой такой сети N = A1 • (A2 || A3)h один из автоматов, A1, управляющий, он является автономным: A1 = (F^1, F2, g1, f1, s1(1)), два других, A2 и A3, управляемые, они неавтономные: Ai = (F2, Fm, F2, gi, fi, si(1)), i Е {2, 3}. В ней выход автомата A1 соединён со входами автоматов A2 и A3 непосредственно, а выходы A2 и A3 соединены с выходом сети через отображение связи h : F2 х F2 ^ F2, такое, что для любых y2,y3 в F2 имеет место h(y2,y3) = y2 ф y3, где ф - операция сложения по mod 2. Альтернативность управления автоматами A2 и A3 со стороны автомата A1 в N выражается в следующих ограничениях на их функции переходов, справедливых для любого их входного символа x и любых их состояний s2 и s3 соответственно и называемых далее условиями альтернативности: g2(x, s2) = s2 ^ g3(x, s3) = s3. Автомат сети N = A1 • (A2 || A3)h с альтернативным управлением есть A = (Fm1 х х Fm2 х Fm3, F2,g,f,s1(1)s2(1)s3(1)), и в нём для любых si Е F^*, i Е {1, 2, 3}, верно: g(s1s2s3) = (g1(s1),g2(f1(s1),s2),g3(f1(s1 ),s3)) и f (s1s2s3) = f2(f1(s1),s2) ф f3(f1 (s1),s3). Каноническая система уравнений E этой сети записывается как y1(t) = ЛЫ*)), 51 (t +1) = g1(s1(t)), У2(*) = f2(y1 (*) , S2 (*)) , 52 (* +1) = g2(y1(*),S2(t)), Уз(*) = /з(У1(*),8з(*)), 53 (t + 1) = g3(y1(t),S3(t)), y(t)= У2 (t) 0 Уз(*), t ^ 1, s1 (1)s2(1)s3(1) - начальное условие, а каноническая система уравнений её автомата A - как y(t) = f2(f1(S1(t)), S2(t)) 0 f3(f1(S1(t)), S3(t)), S1(t + 1)S2(t + 1)S3(t + 1) = (g1(S1(t)), g2(f1(S1(t)), S2(t)), g3(f1(S1(t)), S3(t))), t ^ 1, s1(1)s2(1)s3(1) - начальное условие. В системе E подсистемы E1 из первого и второго уравнений, E2 из третьего и четвёртого уравнений и E3 из пятого и шестого уравнений описывают работу автоматов A1, A2 и A3 соответственно, седьмое уравнение описывет выход сети. Подсистема E' из уравнений с номерами от третьего до седьмого включительно и с начальными условиями s2(1) и s3(1) описывает работу параллельной подсети (A2 || A3)h сети N. Входные последовательности этой подсети можно вычислить по выходной последовательности сети применением к E' метода DSS, как это описано в п. 7.4 со следующими уточнениями, связанными со специфичностью отображения связи h и свойством альтернативного функционирования автоматов A2 и A3 в ней: 1) множество Mh(t), равное h-1(y(t)), состоит из двух пар в F2 - 00 и 11, если y(t) = 0, либо 01 и 10, если y(t) = 1; 2) система уравнений E несовместна не только когда B(t) = 0, но и когда (S2(t + 1) = S2(t)) Л (S3(t + 1) = S3(t)) V (S2(t + 1) = S2(t)) Л (S3(t + 1) = S3(t)) для некоторого t, 1 ^ t ^ /. Криптоавтомат £ = (C, I, K) называется криптогенератором с альтернативным управлением, если в нём C = C(N) для некоторой автоматной сети N с альтернативным управлением. По определению, всякая сеть в C является автоматной сетью A1 • (A2 || A3)h с альтернативным управлением, в ней для каждого i Е {1, 2, 3} состояния в i-й компоненте принадлежат множеству Si = F^1, а функции переходов и выходов - некоторым функциональным классам Gi и Fi соответственно. Элементы Is, It и Io носителя I ключа в £ являются подмножествами в {1, 2, 3}, а декартовы множители Ks, Kt и Ko ключевого пространства K - декартовыми произведениями множеств Sj для i Е Is, Gi для i Е It и Fi для i Е Io соответственно. Наконец, в ключе k = ksktko Е K имеем: ks Е Ks, kt Е Kt и ko Е Ko. 8.2. Криптоанализ Пусть далее £ = (C, I, K) есть произвольный криптогенератор с альтернативным управлением. Предполагается, что целью криптоанализа генератора является нахождение ключа по заданной его выходной последовательности 7 = y(1)y(2)... y(l), l ^ 1. Допуская, разумеется, существование иных методов решения этой задачи, мы остановимся здесь, главным образом, на применениях метода DSS и задачи доопределения частичных булевых функций в атаках на генератор Е с тем или иным носителем I - {/s,/t,/o} ключевого пространства K - Ks х Kt х Ko. Начнём с простейшего случая. 1. Is - {1}, It - 1o - 0; Ks - - Fm1, Kt - Ko - 0; K - Ks - Fm1; k - S1(1) € K. Атака 1: 1) по заданной 7 на выходе генератора методом DSS вычисляем входные последовательности параллельной подсети N' - (A2 || A3)h сети N, являющиеся одновременно выходными последовательностями автомата A1; 2) для любой из таких пооледовательностей атакой грубой силы (BFA) находим начальное состояние s1(1) автомата A1. Вычислительная сложность атаки равна 2mi. Примечание: если вычисление на шаге 2 выполнить для каждой последовательности, вычисленной на шаге 1, то будут получены все значения ключа k, при которых генератор Е вырабатывает данную 7. 2. Is - {1, 2}, It - Io - 0; Ks - х S2 - Fm1 х Fm2, Kt - Ko - 0; K - Ks - - Fm1 X Fm2; k - S1(1)S2(1) € K. В этом случае атака относится к разряду meet-in-the-middle - встреча посредине. Предварительно, до атаки, для каждого значения a переменной s1(1) в S1 вычисляются s1(t+1) - g1(s1(t)) и y1(t) - /1 (s1(t)) для t € {1, 2,..., /} и s1(1) - a, и это a сохраняется по адресу H(y1(1)y1(2)... y1(1)), где H : F2 м Fm1 есть некоторая хеш-функция. А т а к а 2: имея на выходе генератора последовательность , методом DSS вычисляем входные последовательности подсети N' при разных значениях переменной s2(1), выбираемых в S2 до тех пор, пока при некотором её значении b на входе N' не будет получена некоторая последовательность в с некоторым непустым содержимым a по адресу H(в), и тогда пару (a, b) принимаем за результат атаки - значение ключа k. Вычислительная сложность атаки равна 2m2. Примечание: атака остаётся в силе, если в ней автоматы A2 и A3 переставить местами. 3. 1а - {1, 2, 3}, It - Io - 0; Ks - x S2 x S3 - Fm1 х Fm2 х Fm3, Kt - K0 - 0; K - Ks - Fm1 X Fm2 X Fm3; k - S1(1)S2(1)S3(1) € K, и переменные y1(1),y1 (2),. ..,^(1) образуют линеаризационное множество системы уравнений E' подсети N' сети N. Атака 3: для каждого s1(1) в S1 1) вычисляем s1(t + 1) - g1(s1(t)) и y1(t) - - /1 (s 1 (t)) для t € {1, 2,...,/}; 2) осуществляем линеаризационную атаку на E', а именно: найденные на шаге 1 значения y1(1),y1(2),... ,y1(/) подставляем в E' и полученную систему E" линейных уравнений решаем (методом Гаусса, например) относительно булевых неизвестных в векторах s2(t) и s3 (t), t € {1, 2,...,/}; 3) из каждого из тех решений системы E", которые удовлетворяют условиям альтернативности для всех t, 1 ^ t ^ /, выписываем значения s2(1) и s3(1) и тройку s1 (1)s2 (1)s3(1) принимаем за одно из значений ключа k. Вычислительная сложность атаки равна 2m1 . Примечание: эффективным ключом автоматного криптогенератора с альтернативным управлением в этом случае является начальное состояние одного автомата - управляющего, его удлинение посредством начальных состояний управляемых автоматов не добавляет стойкости генератору. Для генератора с альтернативным управлением на регистрах сдвига с линейной обратной связью это показано в [5]. 4. Is - It - 0, Io - {1}; Ks - Kt - 0, Ko - F1; K - Ko - F1; k - /1 € K. Атака 4: 1) вычисляем s1(t+1) = g1 (s1(t)), t E {1, 2,... ,1 - 1}; 2) как в п. 1 атаки 1, методом DSS вычисляем входные последовательности подсети N сети N; 3) по любой из них y1(1)y1(2) .. .y1(1) и внутренней последовательности s1(1)s1(2)... s1(/) автомата A1 строим частичную функцию f1 как f1 (s1(t)) = y1(t) для t E {1, 2,...,/}; 4) доопределяем f1 до некоторой функции f1 в классе F1 ив случае успешности доопределения выдаём последнюю как одно из значений ключа k. Примечание: если вычисление на шаге 3 выполнить для каждой последовательности, вычисленной на шаге 2, то будут получены все значения ключа k, при которых генератор Е вырабатывает данную y. 5. Is = It = 0, Io = {2}; Ks = Kt = 0, Ko = F2; K = Ko = F2; k = E K. Атака 5: 1) вычисляем s1(t + 1) = g1(s1(t)), y1(t) = f1(s1(t)) в автомате A1 и S3 (t + 1) = g3(y1(t),ss(t)), ys(t) = fs(y1 ,ss(t)) в автомате A3 для t E {1, 2,...,/}; 2) строим частичную функцию f как f (y1(t), s2(t)) = y(t) ф y3(t) для t E {1, 2,...,/}; 3) доопределяем f до некоторой функции f2 в классе F2 ив случае успешности доопределения выдаём последнюю как значение ключа k. Примечание: атака остаётся в силе, если в ней автоматы A2 и A3 переставить местами. 6. Is = It = 0, Io = {2, 3}; Ks = Kt = 0, Ko = F2 х F3; K = Ko = F2 х F3; k = f2f3 E K. Атака 6: 1) вычисляем s1(t + 1) = g1(s1(t)), y1(t) = f1(s1(t)) в автомате A1 для t E {1, 2,... , /}, S2(t + 1) = g2(y1(t), S2(t)) в автомате A2 и S3(t + 1) = g3(y1(t), S3(t)) в автомате A3 для t E {1, 2,..., / - 1}; 2) вычисляем 21 пар последовательностей y2j (1) У2 j (2) . . .y2j (/), y3j (1)y3j (2) . . .y3j (/), j E {1, 2,. . . ,/}, таких, что y2j(t) = y3j(t) = 0 или y2j(t) = y3j(t) = 1, если y(t) = 0, либо y2j(t) = 0,y3j(t) = 1 или y2j(t) = 1, У3j(t) = 0, если y(t) = 1; 3) для каждого j E {1, 2,... ,/} строим частичные булевы функции f2j и f3j как f2j(У1 (t), S2(t)) = y2j(t) и f3j(y1 (t), S3(t)) = y3j(t), t E {1, 2,...,/}, доопределяем их до некоторых функций f2 и f3 в F2 и F3 соответственно и в случае успешности доопределения выдаём f2f3 как одно из значений ключа k. Вычислительная сложность атаки равна 21. Примечание: если на шаге 3 для каждого j хотя бы одна из функций f2j или f3j оказывается недоопределимой в соответствующем классе F2 или F3, то задача криптоанализа генератора Е в данных условиях не имеет решения.

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

конечный автомат, автоматная сеть, криптоавтомат, криптоавтомат с альтернативным управлением, криптоанализ, метод DSS, доопределение частичных функций, finite automaton, automata network, cryptautomaton, cryptautomaton generator with alternative control, cryptanalysis, linearization attack, "devide-and-solve-and-substitute", partially defined function completion

Авторы

ФИООрганизацияДополнительноE-mail
Агибалов Геннадий ПетровичТомский государственный университетдоктор технических наук, профессор, профессор кафедры защиты информации и криптографииagibalov@isc.tsu.ru
Всего: 1

Ссылки

Агибалов Г. П. Конечные автоматы в криптографии // Прикладная дискретная математика. Приложение. 2009. №2. С. 43-73.
Tao R. Finite Automata and Application to Cryptography. TSINGHUA University Press, 2009. 406 p.
Агибалов Г. П., Панкратова И. А. О двухкаскадных конечно-автоматных криптографических генераторах и методах их криптоанализа // Прикладная дискретная математика. 2017. №35. С. 38-47.
Агибалов Г. П., Панкратова И. А. К криптоанализу двухкаскадных конечно-автоматных криптографических генераторов // Прикладная дискретная математика. Приложение. 2016. №9. С. 41-43.
Агибалов Г. П. Логические уравнения в криптоанализе генераторов ключевого потока // Вестник Томского государственного университета. Приложение. 2003. №6. С. 31-41.
Menezes A, van Oorshot P., and Vanstone S. Handbook of Applied Cryptography. CRC Press Inc., 1997. 661 p.
Фомичёв В. М. Дискретная математика и криптология. М.: ДИАЛОГ-МИФИ, 2003. 400 с.
Агибалов Г. П. О некоторых доопределениях частичной булевой функции // Труды Сибирского физико-технического института. 1970. Вып. 49. С. 12-19.
Агибалов Г. П., Сунгурова О. Г. Криптоанализ конечно-автоматного генератора ключевого потока с функцией выходов в качестве ключа // Вестник Томского государственного университета. Приложение. 2006. № 17. С. 104-108.
Агибалов Г. П. Методы решения систем полиномиальных уравнений над конечным полем // Вестник Томского государственного университета. Приложение. 2006. № 17. С. 4-9.
 Криптоавтоматы с функциональными ключами | ПДМ. 2017. № 36. DOI: 10.17223/20710410/36/5

Криптоавтоматы с функциональными ключами | ПДМ. 2017. № 36. DOI: 10.17223/20710410/36/5