9. Криптоанализ 1 Терминология и исходные допущения
 Скачать 280.5 Kb.
|
9.4.1 Метод встречи посерединеЕсли множество ключей криптоалгоритма замкнуто относительно композиции, то есть для любых ключей 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” с такой же сложностью, предложенный американским математиком Д.Шенксом. 9.4.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). Отсюда следует, что задача встречи на случайном ориентированном дереве не менее сложна, чем задача о встрече в цикле, то есть алгоритм Полларда не улучшаем за счет увеличения доступной памяти. 9.4.3 Дифференциальный метод криптоанализа Дифференциальный метод криптоанализа (ДКА) был предложен Э.Бихамом и А.Шамиром в 1990 г. Дифференциальный криптоанализ - это попытка вскрытия секретного ключа блочных шифров, которые основаны на повторном применении криптографически слабой цифровой операции шифрования r раз. При анализе предполагается, что на каждом цикле используется свой подключ шифрования. ДКА может использовать как выбранные, так и известные открытые тексты . Успех таких попыток вскрытия r-циклического шифра зависит от существования дифференциалов (r-1)-го цикла, которые имеют большую вероятность. Дифференциал i-го цикла определяется как пара ( , )i такая, что пара различных открытых текстов x, x* c разностью может привести к паре выходных текстов y, y* после i-ого цикла, имеющих разность (для соответствующего понятия разности ). Вероятность i-циклового дифференциала ( , )i - это условная вероятность P( y(i)= | x= ) того, что разность y(i) пары шифртекстов ( y, y*) после i-ого цикла равна при условии, что пара текстов (x, x*) имеет разность x= ; открытый текст x и подключи циклов к(1) , к(2) ,...., к(i) независимыми и равновероятными. Основная процедура ДКА r- циклического шифра с использованием выбранных открытых текстов может быть следующей : 1. На этапе предвычислений ищем множество (r-1)-цикловых дифференциалов ( 1, 1)r-1 , ( 2, 2)r-1 ,.... ( s, s)r-1 . Упорядочиваем это множество дифференциалов по величине их вероятности. 2. Выбираем открытый текст x произвольным образом и вычисляем x* так, чтобы разность между x и x* была равна 1. Тексты x и x* шифруется на подлинном ключе и после r циклов получаем пару шифртекстов y(r) , y*(r). Предполагаем, что на выходе предпоследнего (r-1)-ого цикла разность шифртекстов равна наиболее вероятной: y(r-1)= 1. Для тройки ( 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*, x) может быть легко вычислен, и существует (r-1)-цикловый дифференциал ( , )к-1 такой, что его вероятность удовлетворяет условию P( y(r-1)= | x= )>>2-n , где n-количество бит в блоке шифруемого текста. Сложность раскрытия ключа r-циклического шифра Q(r) определяется как число используемых шифрований с последующим вычислением ключа: Q(r) 2/ (Pmax - 1/(2n-1)), где Pmax=max( )max( )(P( y(r-1)= | x= )). В частности, если Pmax 1/(2n-1), то атака не будет успешной. Поскольку вычисление подключа - более трудоемкая операция, чем шифрование, то единицей измерения сложности является сложность нахождения возможных подключей одного цикла по известным ( y(r-1),y(r),y*(r)). Отличительной чертой дифференциального анализа является то, что он практически не использует алгебраические свойства шифра (линейность, аффинность, транзитивность, замкнутость и т.п.), а основан лишь на неравномерности распределения вероятности дифференциалов. 9.4.4 Линейный метод криптоанализа В открытой печати линейной метод криптоанализа впервые был предложен японским математиком Мацуи. Метод предполагает, что криптоаналитик знает открытые и соответствующие зашифрованные тексты. Обычно при шифровании используется сложение по модулю 2 текста с ключом и операции рассеивания и перемешивания. Задача криптоаналитика - найти наилучшую линейную аппроксимацию (после всех циклов шифрования) выражения xi1+ .... + xir + yj1 + yjs=zk1 + .... + zk t (1) Пусть pL - вероятность того, что (1) выполняется, при этом необходимо, чтобы pL 1/2 и величина | pL-1/2 | должна быть максимальна. Если | pL-1/2 | достаточно велика и криптоаналитику известно достаточное число пар открытых и соответствующих зашифрованных текстов, то сумма по модулю 2 бит ключа на соответствующей позиции в правой части (1) равна наиболее вероятному значению суммы по модулю 2 соответствующих бит открытых и зашифрованных текстов в левой части. Если pL > 1/2, то сумма бит ключа в правой части (1) равна нулю, если сумма бит в левой части равна нулю больше, чем для половины пар зашифрованных текстов, и сумма бит ключа в правой части (1) равна единице, если сумма бит в левой части равна единице больше, чем для половины текстов . Если pL< 1/2 , то наоборот : сумма бит ключа в правой части (1) равна нулю , если сумма бит в левой части равна единице больше , чем для половины пар открытых и зашифрованных текстов, и сумма бит ключа в правой части (1) равна единице, если сумма бит в левой части равна нулю больше, чем для половины текстов. Для нахождения каждого бита собственно ключа теперь нужно решить систему линейных уравнений для известных линейных комбинаций этих бит, но эта процедура не представляет сложности, так как сложность решения системы линейных уравнений описывается полиномом не более третьей степени от длины ключа. Требуемое для раскрытия ключа количество N пар открытых и зашифрованных текстов (блоков) оценивается выражением N | pL-1/2 | -2 . Для раскрытия ключа шифра DES этим методом необходимо 247 пар известных открытых и зашифрованных текстов. 9.5 Инструменты криптоанализа Для анализа шифров могут использоваться различные математические инструменты. Однако существуют общие принципы решения сложных вычислительных задач. Обычно задачу вычисления ключа можно переформулировать как задачу поиска внутри большого конечного множества М элемента m, обладающего нужными свойствами. Один из подходов к решению этой задачи получил название “разделяй и властвуй”. Суть его заключается в том, что исходная сложна задача поиска разделяется на две подзадачи. Для этого множество элементов разбивается на пересекающиеся или слабо пересекающиеся перечислимые подмножества, распознаваемые по отношению к свойствам, которыми обладает данный элемент. На первом этапе ищется подмножество, в котором находится требуемый элемент (решается первая подзадача), затем ищется требуемый элемент внутри найденного подмножества(решается вторая подзадача). Такого рода разбиение может применяться многократно. Примером такого подхода является известный способ угадывания произвольного слова из многотомной энциклопедии, если отгадывающий может задать 20 вопросов и получать на них ответы “да” или “нет”. Подход “разделяй и властвуй” может быть использован и при проведении анализа шифров. Естественно, его применение должно быть индивидуальным для каждого криптоалгоритма. Например, если множество М допускает разбиение на подмножества, распознаваемые в части свойства А, и существует сжимающее отображение, действующее на этих подмножествах и сохраняющее данное свойство А, то метод Полларда может быть применен не к элементам множества М, а к подмножествам, содержащим данный элемент. Другой эффективный метод решения вычислительных задач заключается в том, что множество М упорядочивается в порядке убывания вероятности того, что данный элемент обладает нужным свойством. Далее происходит опробование элементов М (перебор), начиная с наиболее вероятных. Это техника использована в дифференциальном методе анализа. Если вероятности распределены существенно неравномерно, то получается большой выигрыш по сложности. В частности, если вероятности образуют геометрическую прогрессию, то сложность нахождения нужного элемента оказывается линейной от размера задачи (логарифма мощности исходного множества). Общепринятым инструментом является также линеаризация задачи. Это часто обусловлено тем, что аффинные аппроксимации преобразований образуют полугруппу относительно композиции и имеют простые описания. Однако такую полугруппу образуют не только аффинные преобразования, но и другие объекты, например симметрические полиномы, решетки, некоторые классы форм (однородных полиномов, все слагаемые которых имеют одинаковую степень). Под композицией полиномов понимается подстановка полинома в качестве переменной в другой полином. Андельман и Ридс для анализа шифров предложили использовать переход от исходного дискретного шифратора к “непрерывному” шифратору, который совпадает с исходным на вершинах n-мерного единичного куба, и далее искать непрерывный ключ с использованием техники поиска экстремумов непрерывных отображений. Заметим, что здесь кроется определенная сложность . Это вызвано тем, что все элементы кольца полиномов Жегалкина или кольца булевых функций с операциями И, ИЛИ, НЕ является идемпотентными. Пусть переменные принимают значения из некоторого непрерывного подмножества А вещественных чисел. Для численных значений вещественных аналогов булевых формул необходимо обеспечить x2=x, для любого рационального числа r. Таким образом, все вещественные числа А оказываются равными, то есть элементы А являются элементами факторгруппы R/Q. Нетрудно видеть, что ни в одной вычислительной модели с конечной разрядностью числа из А непредставимы, поэтому такой метод не работает (по крайней мере, для вещественных и, следовательно, для комплексных чисел ). Каждый новый метод криптоанализа приводит к пересмотру безопасности шифров, к которым он применим. Если целью криптоаналитика является раскрытие возможно большего числа шифров (независимо от того, хочет ли он этим нанести ущерб обществу, предупредить его о возможной опасности или просто получить известность), то для него наилучшей стратегией является разработка универсальных методов анализа. Но эта задача является также и наиболее сложной. Алгоритмы (стандарты) шифрования периодически меняются (что видно на примере шифров LUCIFER, DES, FEAL, клиппер-чипов), а секретная информация часто имеет свойство стареть, то есть не представляет большого интереса для нарушителя спустя какое-то время после ее передачи по каналам связи в зашифрованном виде. Поэтому зависимость эффекта от нахождения способа раскрытия ключей данного шифра во времени имеет максимум: в начале срока своего действия криптоалгоритм не имеет широкого распространения, а в конце срока он перестает быть популярным, а основной объем зашифрованной информации не представляет интереса. 9.6 Проблема надежности криптосистем В современном программном обеспечении (ПО) криптоалгоритмы широко применяются не только для задач шифрования данных, но и для аутентификации и проверки целостности. На сегодняшний день существуют хорошо известные и апробированные криптоалгоритмы (как с симметричными, так и несимметричными ключами), криптостойкость которых либо доказана математически, либо основана на необходимости решения математически сложной задачи (факторизации, дискретного логарифмирования и т.п.). К наиболее известным из них относятся DES, ГОСТ, RSA. Таким образом, они не могут быть вскрыты иначе, чем полным перебором или решением указанной задачи. С другой стороны, в компьютерном и околокомпьютерном мире все время появляется информация об ошибках или "дырах" в той или иной программе (в т.ч. применяющей криптоалгоритмы), или о том, что она была взломана (cracked). Это создает недоверие как к конкретным программам, так и к возможности вообще защитить что-либо криптографичеcкими методами не только от спецслужб, но и от простых хакеров. Поэтому знание истории атак и "дыр" в криптосистемах, а также понимание причин, по которым они имели место, является одним из необходимых условий разработки защищенных систем. Перспективным направлением исследований в этой области является анализ успешно проведенных атак или выявленных уязвимостей в криптосистемах с целью их обобщения, классификации и выявления причин и закономерностей их появления и существования. По аналогии с таксономией причин нарушения безопасности ВС, выделим следующие причины ненадежности криптографических программ (см. рис. 9.6.1): Невозможность применения стойких криптоалгоритмов Ошибки в реализации криптоалгоритмов Неправильное применение криптоалгоритмов Человеческий фактор Отметим сразу, что рассматриваемые ниже причины покрывают только два вида потенциально возможных угроз: раскрытия и целостности, оставляя в стороне угрозу отказа в обслуживании, которая приобретает все большее значение по мере развития распределенных криптосистем. |