Метод встречи посередине
Если множество ключей криптоалгоритма замкнуто
относительно композиции, то есть для любых ключей z i
и z j найдется ключ zk такой, что результат
шифрования любого текста последовательно на z i и z
j равен шифрограмме этого же числа на zk
, то есть F(z j ,F(z i , x))= F(z k
, x), то можно воспользоваться этим свойством. Пусть нам нужно найти
ключ zk. Тогда для нахождения ключа zk, необходимо
найти эквивалентную ему пару ключей zi , zj.
Данный метод криптоанализа основан на “парадоксе дней рождения”.
Известно, что если считать, что дни рождения распределены равномерно, то
в группе из 24 человек с вероятностью 0,5 у двух человек дни рождения совпадут.
В общем виде этот парадокс формулируется так: если a Ц
n предметов выбираются с возвращением
из некоторой совокупности размером n, то вероятность того что два из них
совпадут, равна 1-exp(-a2 / 2) .
Пусть известен открытый текст x и его шифрограмма
y. Для текста x строим базу данных, содержащую случайное множество ключей
z| и соответствующих шифрограмм w=F(z|
, x), и упорядочиваем ее по шифрограммам w. Объем базы данных выбираем
О( Ц
# {z} ). Затем подбираем случайным образом
ключи z| | для расшифровки текстов y и результат расшифровани
v = F(z| | , y) сравниваем с базой данных. Если текст
v окажется равным одной из шифрограмм w, то ключ z| z|
| эквивалентен искомому ключу z. Временная сложность метода составляет
О( Ц
# {z} log#{z}). Множитель log#{z}
учитывает сложность сортировки. Требуемая память равна О( Ц
# {z} log#{z}) бит или ОЦ
# {z}) блоков ( предполагается, что длина
блока и длина ключа различаются на ограниченную константу ).
Этот же метод применим, если множество ключей
содержит достаточно большое подмножество, являющееся полугруппой.
Другое применение этого метода для множества,
не являющегося полугруппой, можно продемонстрировать на хэш-функциях. Например,
для подделки подписи надо найти два текста, обладающих одним хэш-образом.
После этого можно подписанное сообщение заменить на другое, обладающее
таким же хэш-образом. Поиск двух таких сообщений можно выполнить с использованием
метода “встречи посередине”. Сложность поиска равна О(Ц
#{h}), где #{h} — число всевозможных
хэш-образов.
Этот алгоритм является вероятностным. Однако
существуют и детерминированный аналог этого алгоритма “giant step - baby
step” с такой же сложностью, предложенный американским математиком Д.Шенксом.
2.1.2. Метод Полларда.
Этот вероятностный метод основан на следующем
факте. Если на некотором конечном множестве М определить случайное отображение
f и применить его поочередно ко всем элементам М, а ребрами соответстви
- y=f(x) для x,yН
М. Поскольку множество М конечно, то
этот граф должен содержать деревья, корни которых соединены в циклы. Дл
случайного отображения f длина цикла равна О(Ц
#М ) и высота дерева в среднем равна
О(Ц
#М ).
Для нахождения ключа, например в криптоалгоритме,
основанном на задаче логарифма на некоторой группе, достаточно решить задачу
о встрече на графе случайного отображения. Для этого из двух разных стартовых
точек x0|, x0| | строятс
траектория до входа в цикл. Затем одна из двух конечных точек, лежащих
в цикле, фиксируется, а траектория другой продолжается до встречи с фиксированной
точкой. Для функции f и точки входа x0 длина траектории составляет
О(Ц #М ) шагов.
Типичный вид этой траектории содержит предельный цикл длины О(Ц
#М ) и отрезок до входа в цикл примерно такой же длины. В качестве индикатора
замыкания траектории Поллард предложил использовать равенство xi
= x2i , где xi - i-я точка траектории для входа x0.
Это равенство будет выполняться всегда. Значение индекса i не превышает
суммы длины пути до входа в цикл.
В среднем сложность нахождения равенства xi
= x2i равна 3Ц
(p /8)#М.
Сложность встречи, когда обе точки лежат в цикле, равна 0,5Ц
(p /8)#М.
Таким образом, итоговая сложность равна 6,5Ц
(p /8)#М.
Метод Полларда применяется для решения задачи
логарифма на циклической группе, поиска частично эквивалентных ключей (коллизий),
для нахождения двух аргументов, дающих одинаковое значение хэш-функции,
и в некоторых других случаях. Применительно к задаче логарифмирования этот
метод позволяет отказаться от использования большого объема памяти по сравнению
с методом встречи посередине. Кроме того, пропадает необходимость сортировки
базы данных. В результате временная сложность по сравнению с методом встречи
посередине снижается на множитель О(log#М). Сложность этого метода в данном
случае составляет О(Ц
#М ) шагов и требует памяти объема О(1) блоков. Однако не всегда требуетс
малая память.
Рассмотрим в
качестве иллюстрации метода Полларда алгоритм нахождения коллизии (двух
аргументов, дающих одинаковое значение хэш-функции) для вычислительной
модели с объемом памяти О(v). Такими аргументами будут элементы множества
М, стрелки от которых под действием хэш-функции f ведут в точку входа в
цикл. Практически алгоритм сводится к нахождению точки входа в цикл.
1. Войти в цикл, используя равенство xi
= x2i = t .
2. Измерить длину цикла m, применяя последовательно
отображение f к элементу t до получения равенства fm(t)=t
.
3. Разбить цикл m на v интервалов одинаковой
или близкой длины и создать базу данных, запомнив и упорядочив начальные
точки интервалов.
4. Для стартовой вершины п.1 выполнять одиночные
шаги до встречи с какой-либо точкой из базы данных п.3. Отметить начальную
и конечную точки интервала, на котором произошла встреча.
5. Стереть предыдущую и создать новую базу данных
из v точек, разбив интервал, на котором произошла встреча, на равные по
длине части, запомнив и отсортировав начальные точки интервалов.
6. Повторить процедуры пп.4,5 до тех пор, пока
не получится длина интервала, равная 1. Вычислить точку встречи в цикле,
вычислить коллизию как пару вершин, одна из которых лежит в цикле, а друга
- нет.
Этот алгоритм требует многократного выполнени
О( Ц
#М ) шагов до входа в цикл и выполнени
сортировки базы данных. На каждом этапе при создании новой базы данных
длина интервала сокращается в v раз, то есть количество повторов равно
О( logv #М ). Если v << Ц
#М, то сложностью сортировки базы данных
можно пренебречь. Тогда сложность алгоритма равна О(Ц
#М logv #М).
Рассмотрим возможность улучшения оценки сложности
этого метода за счет увеличения доступной памяти. Напомним, что почти все
вершины графа случайного отображения лежат на одном дереве. Поэтому будем
решать задачу о встрече на случайном ориентированном дереве. С ростом глубины
h ширина дерева b(h) уменьшается, то есть случайное отображение обладает
сжимающими свойствами. Поэтому с ростом глубины вершины, с одной стороны,
увеличивается сложность встречи за счет многократного применения отображения,
с другой стороны, увеличивается вероятность встречи в силу сжимающих свойств.
Доля вершин с глубиной не менее h равна О(1/h).
Рассмотрим два алгоритма для решения задачи о
встрече. Первый алгоритм предусматривает выбор множества m случайных начальных
вершин, применение к ним к раз отображения, сортировку множества конечных
вершин и поиск среди них равных. Второй алгоритм предусматривает запоминание
всей траектории спуска для каждой вершины, сортировку множества вершин,
составляющих траектории, и поиск среди равных. Второй алгоритм являетс
не менее сложным, чем первый, в силу сжимающих свойств случайного отображения.
Сложность первого алгоритма равна km (log
m). Множитель log m учитывает сложность сортировки. В силу парадокса
дней рождения m = О(#M/h)0.5. Для одного шага сложность
алгоритма равна О(Ц
#M log#M), то есть этот алгоритм более
эффективный, чем алгоритм встречи посередине.
После первого шага от листа глубины становитс
равной О( log#М ). Однако в дальнейшем рост глубины с каждым шагом
замедляется. Это объясняется существенно разрывным характером условной
вероятности р(h|H) получения глубины h при исходной глубине H. Действительно,
из определения глубины следует, что каждая вершина с глубиной H+1 связана
ребром с вершиной с глубиной H. Из каждой вершины исходит единственное
ребро. Поэтому в силу количественных оценок ширины графа
р(H+1|H)=[O(H-2 - (H+1)-2)]/O(H-2)=1-O(H-1).
Числитель этого выражения равен разности ширины
графа на глубинах H и H+1, знаменатель учитывает то, что исходная глубина
равна Н. Вероятность попасть на глубину h>H+1 определяется вероятностью
непопадания на глубину H+1 и шириной графа,
р(h|H)=O(H-1h-2).
Сравним вероятность pk(h) получени
глубины h после k шагов при спуске от листа и вероятность pk(h|Mk-1)
глубины h после k шагов при условии, что на шаге k-1 глубина равнялась
математическому ожиданию. Имеет место оценка pk(h)»
pk(h|Mk-1). Поэтому
место вероятности сложного события pk(h) можно рассматривать
вероятность простого события pk(h|Mk-1).
Пусть стартовая вершина лежит на глубине H=O(
log#M). Какова будет глубина после очередного шага? Непосредственные
вычисления показывают, что математическое ожидание глубины равно H+1+O(1),
то есть второй и последующий шаги увеличивают глубину спуска на О(1). Подстановка
в качестве исходной глубины математического ожидания глубины спуска на
предыдущем шаге дает оценку математического ожидания глубины спуска после
к шагов :
h=O( log#M ) + O(k).
Поскольку оптимальное число шагов при спуске
к алгоритма определяется равенством сложности спуска mk и сложности сортировки
m log m, то копт=O(log#M). Отсюда следует, что
задача встречи на случайном ориентированном дереве не менее сложна, чем
задача о встрече в цикле, то есть алгоритм Полларда не улучшаем за счет
увеличения доступной памяти.
2.1.3. Дифференциальный
метод криптоанализа.
Дифференциальный метод криптоанализа (ДКА) был
предложен Э.Бихамом и А.Шамиром в 1990 г. Дифференциальный криптоанализ
- это попытка вскрытия секретного ключа блочных шифров, которые основаны
на повторном применении криптографически слабой цифровой операции шифровани
r раз. При анализе предполагается, что на каждом цикле используется свой
подключ шифрования. ДКА может использовать как выбранные, так и известные
открытые тексты .
Успех таких попыток вскрытия r-циклического шифра
зависит от существования дифференциалов (r-1)-го цикла, которые имеют большую
вероятность. Дифференциал i- го цикла определяется как пара ( a
, b )i
такая, что пара различных открытых текстов
x, x* c разностью a
может привести к паре выходных текстов y, y* после i-ого цикла, имеющих
разность b (дл
соответствующего понятия разности ). Вероятность i-циклового дифференциала
(a ,b
)i - это условная вероятность
P(D y(i)=b
| D x= a
) того, что разность D
y(i) пары шифротекстов ( y, y*) после i-ого цикла равна b
при условии, что пара текстов (x, x*) имеет разность D
x=a ; открытый
текст x и подключи циклов к(1) , к(2) ,...., к(i)
независимыми и равновероятными.
Основная процедура ДКА r- циклического шифра
с использованием выбранных открытых текстов может быть следующей :
1. На этапе предвычислений ищем множество (r-1)-цикловых
дифференциалов (a
1,b
1)r-1 , (a
2,b
2)r-1 ,.... (a
s,b
s)r-1 . Упорядочиваем
это множество дифференциалов по величине их вероятности.
2. Выбираем открытый текст x произвольным образом
и вычисляем x* так, чтобы разность между x и x* была равна a
1. Тексты
x и x* шифруется на подлинном ключе и после r циклов получаем пару шифртекстов
y(r) , y*(r). Предполагаем, что на выходе предпоследнего (r-1)-ого цикла
разность шифртекстов равна наиболее вероятной: D
y(r-1)=b 1.
Для тройки (D
y(r-1), y(r) , y*(r)) находим каждое
возможное (если их несколько) значение подключа последнего цикла к(r).
Добавляем его к количеству появлений каждого такого значения подключа к(r).
3. Повторяем п.2 до тех пор, пока одно или несколько
значений подключа к(r) не станет появляться чаще других. Берем
этот подключ или множество таких подключей в качестве криптографического
решения для подключа к(r).
4. Повторяем пп.1-3 для предпоследнего цикла,
при этом значения y(r-1) вычисляются расшифрованием шифртекстов на найденном
подключе последнего цикла к(r). Далее действуем аналогично,
пока не будут раскрыты ключи всех циклов шифрования.
Предложенный впервые для анализа конкретного
шифра, ДКА оказался применимым для анализа широкого класса марковских шифров.
Марковским называется шифр, у которого уравнение шифрования на одном
цикле удовлетворяет условию: вероятность дифференциала не зависит от выбора
открытых текстов. Тогда, если подключи циклов независимы, то последовательность
разностей после каждого цикла образует марковскую цепь, где последующее
состояние определяется только предыдущим. Примерами марковских шифров являютс
DES и FEAL .
Можно показать, что марковский r-цикловый шифр
с независимыми подключами является уязвимым для ДКА тогда и только тогда,
когда для одного цикла шифрования ключ по известной тройке (y,y*,D
x) может быть легко вычислен, и существует (r-1)-цикловый дифференциал
(a ,b
)к-1 такой, что его вероятность удовлетворяет условию
P(D
y(r-1)=b | D
x=a )>>2-n
,
где n-количество бит в блоке шифруемого текста.
Сложность раскрытия ключа r-циклического шифра
Q(r) определяется как число используемых шифрований с последующим вычислением
ключа:
Q(r)і
2/ (Pmax - 1/(2n-1)),
где Pmax=max(a
)max(b )(P(D
y(r-1)=b | D
x=a )).
В частности, если Pmax »
1/(2n-1), то атака не будет успешной. Поскольку вычисление подключа
- более трудоемкая операция, чем шифрование, то единицей измерения сложности
является сложность нахождения возможных подключей одного цикла по известным
(D y(r-1),y(r),y*(r)).
Отличительной чертой дифференциального анализа
является то, что он практически не использует алгебраические свойства шифра
(линейность, аффинность, транзитивность, замкнутость и т.п.), а основан
лишь на неравномерности распределения вероятности дифференциалов.
