Криптоаналитические атаки

Криптоанализ заключается в получении доступа к открытому тексту шифрованного сообщения. В ходе успешного криптоаналитического исследования криптосистемы может быть найден не только открытый текст, но и ключ. Криптоаналитик занимается поисками слабостей в криптосистеме, которые могут позволить ему прочесть шифрованное сообщение, отыскать ключ. Если противник узнал ключ, то говорят, что ключ был скомпрометирован. Попытка криптоанализа называется атакой. Успешная криптоаналитическая атака – взломом, а кто ее провел - злоумышленником.

В криптологии принято считать, что надежность шифра определяется только секретностью используемого ключа. Принцип, сформулированный голландским криптографом О.Керкгоффсом - весь механизм шифрования, за исключением значения ключа, известен противнику.

Основные типы криптоаналитических атак:

1. Атака со знанием только шифротекста.

В распоряжении криптоаналитика имеются несколько сообщений, которые были зашифрованы с использованием алгоритма шифрования. Задача криптоаналитика состоит в нахождении открытого текста и ключей, которые применялись для шифрования этих сообщений.

Дано:

С ₁ = E _k1 (P ₁ ), С ₂ = E _k2 (P ₂ ),..., С _i = E _ki (P _i).

Найти:

P ₁ , P ₂ ,..., Р _i или К ₁ , К ₂ ,..., K _i.

2. Атака со знанием открытого текста.

Криптоаналитик имеет доступ не только к шифрованным текстам, но и знает их открытые тексты. Требуется найти ключи, которые использовались для шифрования этих сообщений.

Дано:

P 1, C ₁ = E _k1 (P ₁ ), P 2, C ₂ = E _k2 (P ₂ ),..., P i, C _i = E _ki (P _i).

Найти:

K 1, K 2,.., K i.

3. Атака с выбранным открытым текстом (адаптивная).

Криптоаналитик не только знает шифрованные и открытые тексты нескольких сообщений, но и может определять содержание этих сообщений. Данная разновидность криптоаналитической атаки является более мощной по сравнению с атакой со знанием открытого текста, поскольку здесь криптоаналитик может по своему усмотрению выбирать открытый текст, подлежащий зашифрованию, и получать больше информации об используемых ключах. Его задача состоит в нахождении ключей.

Дано:

P 1, C ₁ = E _{k 1} (P ₁ ), P 2, C ₂ = E _{k 2} (P ₂ ),..., P i,

где С _i = Е _{к i} (P _i), где P 1, P 2,..., Pi выбраны криптоаналитиком.

Найти: К 1, К 2,..., K i.

Атаки со знанием открытого текста и с выбранным открытым текстом не так уж редко встречаются на практике. Открытые тексты многих сообщений начинаются и заканчиваются стандартными фразами. Зашифрованная программа на языке С особенно уязвима, поскольку содержит множество зарезервированных слов типа # define, # include, if, do.

4. Атака с применением грубой силы.

Криптоаналитик занимается подкупом, шантажом, чтобы получить сведения, необходимые ему для взлома криптосистемы. Подкуп иногда выделяют в отдельную категорию и называют атакойс покупкой ключа. Эти атаки являются очень эффективными и зачастую предоставляют наиболее легкий путь для получения доступа к открытым текстам шифрованных сообщений.

Криптографические алгоритмы обладают разной надежностью (определяется стойкостью алгоритма шифрования или стойкостью шифра). Стойкость зависит от того, насколько легко криптоаналитик может взломать шифр. Если при этом стоимость затрат превышает ценность полученной в результате информации, то владельцу шифра беспокоиться не о чем. Если время, потраченное на взлом шифра, больше, чем период, в течение которого ваши данные должны храниться в секрете, то они вне опасности. Если противник не накопил достаточного количества ваших сообщений, зашифрованных с помощью одного ключа, чтобы суметь определить этот ключ, время его менять еще и не пришло. Ценность секретных данных должна быть всегда ниже, чем стоимость преодоления защитных средств, используемых для сохранения этих данных в тайне.

Под вскрытием (взломом ) шифра понимают решение одной из перечисленных ниже задач:

1. Полное вскрытие. Криптоаналитик нашел ключ К такой, что D _K (C)=P.

2. Глобальная дедукция. Не зная ключа К, криптоаналитик отыскал альтернативный D _k алгоритм А такой, что А(С) = Р.

3. Локальная дедукция. Криптоаналитику удалось определить открытый текст, соответствующий конкретному перехваченному шифротексту.

4. Частичная дедукция. Криптоаналитик получил неполную информацию о ключе или открытом тексте. Это могут быть несколько битов ключа или дополнительные данные о структуре открытого текста.

Криптографический алгоритм называется безусловно стойким, если вне зависимости от того каким объемом перехваченного шифротекста располагает криптоаналитик, у него нет достаточной информации, чтобы восстановить исходный открытый текст.

Сложность криптоаналитической атаки на алгоритм шифрования может быть охарактеризована:

1. Сложность по данным. Количество входных данных, необходимое для успешной криптоаналитической атаки на алгоритм шифрования.

2. Вычислительная сложность. Время, требуемое для успешной криптоаналитической атаки на алгоритм шифрования.

3. Сложность по памяти. Объем памяти, которая нужна для успешной криптоаналитической атаки на алгоритм шифрования.

Под сложностью криптоаналитической атаки понимается максимальная среди этих величин. Сложность криптоаналитической атаки, как правило, выражается в виде экспоненциальной функции. Если атака имеет сложность 2 ¹²⁸ , то для взлома шифра требуется выполнить 2 ¹²⁸ операций.

При оценке сложности атаки часто приходится оперировать большими числами. В табл. 10.1 приведены некоторые физические аналогии.

Таблица 10.1. Физические аналогии для очень больших чисе л

Физическая аналогия	Число
Возраст Земли	10 ^9 (2 ^30) лет
Возраст Вселенной	10 ^10 (2 ^32) лет
Количество атомов, из которых состоит Земля	10 ^51 (2 ^170)
Количество атомов, из которых состоит наша Галактика	10 ^67 (2 ^223)
Количество атомов, из которых состоит Вселенная	10 ^77 (2 ^265)

Большинство криптоаналитических атак идеально подходят для реализации на параллельных компьютерах: полномасштабная атака на шифр разбивается на миллионы атак, которые ведутся независимо друг от друга и не требуют организации взаимодействия между процессорами.

Надежность симметричной криптосистемы зависит от стойкости используемого криптографического алгоритма и от длины секретного ключа. Если алгоритм идеален - вскрыть его можно только путем опробования всех возможных ключей. Этот вид криптоаналитической атаки называется методом тотального перебора.

Подсчитать сложность атаки методом тотального перебора достаточно просто. Если ключ имеет длину 64 бита, то компьютер, который может опробовать 1 млн ключей за 1 с, потратит более 5 тыс.лет на проверку всех возможных ключей. При увеличении длины ключа до 128 бит, этому же суперкомпьютеру понадобится 10 ²⁵ лет, чтобы перебрать все ключи.

Атака методом тотального перебора, как правило, представляет собой разновидность атаки со знанием открытого текста. Если предположить, что атака методом тотального перебора является наиболее эффективной среди возможных атак на используемый симметричный алгоритм шифрования, то ключ должен быть достаточно длинным, чтобы успешно отразить эту атаку.

Среди параметров, которые необходимо принимать во внимание при рассмотрении атаки методом тотального перебора, надо упомянуть об общем количестве проверяемых ключей и о времени, затрачиваемом на проверку одного ключа. Количество ключей для конкретного алгоритма обычно фиксировано. DES -алгоритм использует 56-битный ключ. Это означает, что его ключевое пространство содержит 2 ⁵⁶ ключей.

В 1977 г. американские криптологи У. Диффи (W.Diffie) и М. Хеллман (M.Hellman) заявили, что можно построить специализированный суперкомпьютер для вскрытия ключей DES-алгоритма методом тотального перебора. Имея в своем составе 1 млн микросхем, каждая из которых способна проверять 1 млн ключей в секунду, этот суперкомпьютер перебрал бы все 2 ⁵⁶ ключей за 20 час.

В 1996 г. Диффи и Винер опубликовали результаты своей исследовательской работы по определению длины ключа, необходимой для адекватной защиты информации от атаки методом тотального перебора (табл. 10.2).

Таблица 10.2. Стоимость и вычислительная сложность атаки методом тотального перебора

Кто атакует	Бюджет	Сложность атаки	Стойкий ключ
40 бит	56 бит
Хакер	1000 долл.	1 неделя	Никогда	45 бит
Малый бизнес	10 тыс. долл.	12 мин.	556 дней	64 бита
Крупная компания	10 млн долл.	0.005 с	6 мин	70 бит
Федеральное агентство	300 млн долл.	0.0002 с	12с	75 бит

Вывод: если кто-то захочет узнать ваш ключ, ему нужно всего лишь потратить достаточное количество денег.

Дата добавления: 2014-01-20