On parallel computations in implementation of the meat-in-the-middle attack.pdf Метод согласования [1-4] применяется для определения ключа криптосистемы,как правило, по известным открытому и шифрованному тексту. Он менее трудоемокпо сравнению с полным опробованием ключей, если функция шифрования E(q,x) от-крытого текста x по ключу q Е = {0,1}n допускает декомпозицию на две функциикак E(q,x) = g(q, g'(q, x)), где для множеств существенных ключевых переменных Kи K' соответственно функций g и g' выполнено K \ K' = 0 и K' \ K = 0. Наибольшийэффект от применения метода достигается, если множества K и K' равномощны иK П K' = 0. При этом опробование ключа выполняется как независимое опробованиепеременных из множеств K и K' и ключ q определяется с вычислительной сложностьюпорядка O(2n/2) операций типа зашифрования-расшифрования при использовании па-мяти, достаточной для хранения порядка O(2n/2) ключей.Оценим среднее время параллельных вычислений и размер памяти для реализацииметода согласования применительно к некоторым итеративным симметричным блоч-ным шифрам (СБШ) при условии, что ключ выбирается случайно равновероятно изключевого множества.Задача: для r-раундового СБШ вычислить n-битовый ключ q по известнымt-битовым блокам x и y открытого и шифрованного текстов, где числа r, n,t - на-туральные, t ^ n и ключ q по блокам x и y определяется однозначно. В условияхметода согласования сделаем следующие предположения и обозначения:1) ключ q есть конкатенация независимых ключей: q = v w, где v Е Vm, w Е Vn_mи m ^ n/2;2) функции шифрования первых l раундов и остальных r - l раундов шифрованиясуть подстановки соответственно gv и zw, определяемые бинарными ключами vи w, где l < r.Тогда зашифрование блока x в блок y с помощью подстановки Eq имеет видy = Eq (x) = gv Zw (x) = Zw (gv (x)). (1)Корректность предлагаемых алгоритмов следует из (1).В модели вычислительной системы используются N идентичных вычислите-лей с неограниченной памятью, с одинаковыми производительностью и скоростьючтения/записи данных и др. Различаются два случая: кластерные вычисления (КВ) ираспределенные вычисления (РВ). Преимущество модели КВ заключается в возмож-ности активного обмена данными между вычислителями. Преимущество модели РВ,где координатор распределяет задания между процессорами - участниками вычисле-ний и объединяет результаты выполнения заданий, в том, что число участников РВможет заметно превосходить число процессоров в кластерной системе. Вместе с темобмен данными участник осуществляет только с координатором.Кластерные вычисленияПусть кластерная система имеет 2k вычислителей, снабженных блоками памяти,k ^ m. Каждый вычислитель имеет номер, являющийся его адресом (число от 0до 2k - 1). Для реализации алгоритма каждый вычислитель использует адресную па-мять размера 2t -k ячеек, в ячейке могут быть записаны несколько вариантов ключей -элементов V^. Адреса ячеек суть элементы Vt_fc.Для любого двоичного вектора (a^a2,...) размерности больше k обозначим. ( « 1 , ^ 2 ,...) = (ab . . . , a f c ) , .(ab « 2 , . . . ) = (afc+i ,afc+2,...).Для вектора a = (а1,..., ak) Е Vk и пространства векторов VS, где s ^ k, обозначимVs(a) = {. Е VS : .(0 = a}.Алгоритм состоит из предварительного и оперативного этапов.Предварительный этап (заполнение блоков памяти вычислителей).Вычислитель с номером a Е Vk последовательно опробует ключи v из Vm(a) и вы-числяетgv (x) для блока x. Затем пара (v, gv (x)) направляется вычислителю с номером.(gv (x)), который записывает ключ v в свою память по адресу $(gv (x)).По завершении этапа множество ключей из Vm распределено по ячейкам памятивсех вычислителей. Обозначим через Q(a,e) множество ключей из Vm, записанныхв памяти вычислителя с номером a по адресу в.Оперативный этап (определение ключа).1) Вычислитель с номером a Е Vk последовательно опробует ключи w из Vn-m(a)и вычисляет (zw)-1(у) для блока у, затем пара (w, (z- 1)(y)) направляется вы-числителю с номером .((z-1)(y)).2) Вычислитель с номером $((z-1)(y)) обращается в свою память по адресу.((z- 1 )(у)). Конкатенация v w для каждого ключа v из множества Q == Q(^((z-1)(y)), ^((zW1)(y))) есть кандидат на значение искомого ключа q = vw.Если Q = 0, то вычислитель отбраковывает все ключи вида v w (например, покритерию соответствия известным парам открытого и шифрованного текстов).Характеристики метода.Пусть тз, тп, то - время реализации зашифрования, пересылки и обращения в па-мять в некоторых условных единицах, и тах{тз , тп, то} = т. Тогда минимум среднеговремени реализации метода T(m) достигается при m = [n/2j:T = T (|_n/2_|) = 0(т 2n / 2 - k). (2)Надёжность метода равна 1. Каждому вычислителю достаточно иметь порядка2n / 2 - k ячеек, в которые записываются элементы V^/2. Таким образом, совокупный объ-ем требуемой памяти 2n/2 ячеек также распределяется между 2k процессорами.Распределенные вычисленияВ системе РВ с 2p участниками (вычислителями), p ^ m, каждый участник имеетномер, являющийся его адресом (число от 0 до 2p-1). Алгоритм использует 2* ячеекадресной памяти координатора, в каждую из которых может быть записано нескольковариантов ключей - элементов V^. Участники могут отправлять данные координатору,но не могут обращаться к его памяти.Алгоритм состоит из предварительного и оперативного этапов.Предварительный этап (заполнение памяти координатора).Вычислитель с номером a Е Vp последовательно при каждом ключе v из Vm(a)вычисляет (x) для блока x и направляет пару (v,gv(x)) координатору, где ключ vзаписывается в память координатора по адресу (x). По завершении этапа множествоключей из Vm распределено по ячейкам памяти координатора. Обозначим через Q(5)множество ключей из Vm, записанных в памяти координатора по адресу в.Оперативный этап (определение ключа).1) Вычислитель с номером a Е Vp последовательно при каждом ключе w изVn-m(a) вычисляет (zW1)(y) для блока у и направляет пару (w, (z-1)(y)) ко-ординатору.2) Координатор обращается в память по адресу (z-1)(y). Конкатенация каждогоключа v из Q((z- 1)(y)) с ключом w есть кандидат на значение искомого ключаq = v^w. Если Q((zW1)(y)) = 0, то координатор подвергает отбраковке все ключивида v w (например, по критерию соответствия известным парам открытого ишифрованного текстов).Характеристики метода.Положим, что в каждый такт на 1-м этапе в любую ячейку памяти записываетсяне более одного варианта ключа v, на 2-м этапе из любой ячейки памяти извлека-ется не более одного варианта ключа v, т. е. замедления «из-за очередей» в работевычислителей не происходит.Тогда среднее время T (m) алгоритма достигает минимума при m = |_n/2j:T = T(|_n/2j) « 2п/2-р(тз + тп + 2рТо). (3)Координатору достаточно иметь 2n/2 ячеек, в которые записываются элементы V^/2.Отсюда среднее время алгоритма согласования по сравнению с полным опробованиемключей сокращается не более чем в 2p раз и сокращение зависит от соотношениявеличин то, тз и тп. Надёжность метода равна 1.Комбинирование кластерных и распределенных вычисленийВ данной модели РВ система использует 2p участников, p ^ m. Каждый участникимеет номер, являющийся его адресом (число от 0 до 2p - 1). Координатор располага-ет кластерной подсистемой 2k вычислителей, k ^ p, каждый вычислитель кластернойсистемы имеет номер, являющийся его адресом (число от 0 до 2k - 1), и блок памятиразмера 2t - k ячеек (адрес ячейки есть элемент Vt_k). В каждую ячейку могут бытьзаписаны несколько вариантов ключей - элементов V^. Участники РВ могут отправ-лять данные кластерным вычислителям, но не могут обращаться в память кластерныхвычислителей.Предварительный этап (заполнение памяти координатора).Участник с номером a Е Vp последовательно при каждом ключе v из Vm(a) вы-числяет gv(x) для блока x и направляет пару (v,gv(x)) кластерному вычислителюс номером .(gv (x)), который вычисляет адрес .(gv (x)) и записывает по этому адре-су ключ v. По завершении этапа множество ключей из Vm распределено по блокампамяти кластерных вычислителей координатора. Обозначим через Q(a,e) множествоключей из Vm, записанных в блоке памяти вычислителя с номером a по адресу в.Оперативный этап (определение ключа).1) Вычислитель с номером a Е Vp последовательно при каждом ключе w ЕЕ Vn_m(a) вычисляет (z^_1)(y) для блока y и направляет пару (w, (z_1)(y)) кла-стерному вычислителю с номером .((zW_1)(y)).2) Кластерный вычислитель с номером .((z-1)(y)) обращается к своему блокупамяти по адресу .((z^-1)(y)). Конкатенация каждого ключа v из множестваQ = Q(.((z-1)(y)), .((z- 1)(y)) с ключом w есть кандидат на значение ключа. Ес-ли Q = 0, то вычислитель с номером .((z^-1)(y)) все ключи вида v w подвергаетотбраковке (например, по критерию соответствия известным парам открытогои шифрованного текстов).Характеристики метода.Минимум T(m) достигается при m = |_n/2j, и верны оценкиO((T3 + Tn)2n/2-p) ^ minT(m) ^ O(TO2n/2-k).Следовательно, min T(m) может быть сокращен в несколько раз по сравнению с КВи РВ (ср. с формулами (2), (3)). Коэффициент сокращения определяется соотношениемскоростей шифрования, пересылки данных и обращения к памяти. Надёжность методаравна 1.Кластерному вычислителю достаточно иметь 2n / 2 - k ячеек, в которые записываютсяэлементы V^/2.ВыводыВремя определения ключа блочного шифра методом согласования может быть су-щественно сокращено по сравнению с однопроцессорной вычислительной системой:1) при использовании КВ с числом процессоров 2k - примерно в 2k раз;2) при использовании РВ с 2p участниками - до 2p раз, сокращение определяетсясоотношением скоростей шифрования, пересылки данных и обращения к памя-ти координатора;3) при использовании РВ с 2p участниками и подсистемы КВ координатора с чис-лом процессоров 2k, где k ^ p, - от 2k до 2p раз, сокращение определяется со-отношением скоростей шифрования, пересылки данных и обращения к памятикластерных вычислителей.При использовании КВ память распределяется по вычислителям кластерной си-стемы.Подробное изложение представленных результатов можно найти в [5].

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