Атака на основе шифротекста

Атака на основе шифртекста (англ. Ciphertext-only attack ) — один из основных способов криптоатак. Предполагается что криптоаналитику известен только набор шифртекстов, целью является получение как можно большего количества открытых текстов, соответствующих имеющимся шифртекстам, или еще лучше — ключа, использованного при шифровании. Шифртексты могут быть получены простым перехватом сообщений по открытым каналам связи. Данный вид атаки является слабым и неудобным.

Примеры в истории

Британский Колосс

В 1940 году английской полиции удалось прослушать шифрованную немецкую радиопередачу необычного вида. Основная секретная переписка Третьего рейха велась с помощью шифратора «Энигма», но для более важных сообщений использовалась машина Lorenz SZ 40, передача текста происходила в коде Бодо. Перехваченные данные были отправлены криптоаналитикам, где новая криптосистема получила наименование «Рыба» (Fish). Специально под криптосистему FISH в Блечли-Парк было создано отдельное подразделение. Вскрывать шифр вручную было совершенно неэффективно, поэтому для автоматизации работ было создано специальное подразделение. Первым проектом была оптомеханическая машина-компаратор Heath Robinson, проблемы использования которой были решены при создании компьютера Colossus. Он состоял из 1500 электронных ламп и позволил сократить время вскрытия телеграмм с нескольких недель до 2-3 часов. Следующим этапом стало создание более продвинутой компьютера Colossus Mark II. Он работал примерно в 5 раз быстрее своего предшественника, содержал около 2500 электронных ламп и допускал перепрограммирование под самые разные задачи.

Примечательно, что «Colossus» созданный разработчиками Максом Ньюменом и Томми Флауэрсом, а также при активном участии английского математика Алана Тьюринга, был первой вычислительной машиной не только в Англии, но и во всем мире. Таким образом, можно считать, что информатика и вычислительная техника появились благодаря потребностям криптоанализа.

Атака на WEP

WEP – алгоритм обеспечения безопасности для сетей Wi-Fi.

Формат кадра для WEP:

1. Незашифрованная часть;
   1. Вектор инициализации (англ. Initialization Vector) (24 бита);
   2. Пустое место (англ. Pad) (6 бит);
   3. Идентификатор ключа (англ. Key ID) (2 бита);
2. Зашифрованная часть
   1. Данные;
   2. Контрольная сумма (32 бита).

При шифровании данных используется алгоритм RC4. Для атаки на WEP требуется выполнить перехват и анализ пересылаемых данных. Все атаки основаны на недостатках алгоритма RC4.

Существует 3 основных типа атак: Атака Фларера-Мантина-Шамира

Эта атака основывается на использовании слабых векторов инициализации. Получая вектор инициализации, злоумышленник, зная первый байт ключевого потока и первые m байт ключа, может определить (m+1)-й байт ключа благодаря слабости генератора псевдослучайных чисел, который используется при генерации ключевой последовательности. Поскольку первый байт открытого текста определяется из заголовка протокола SNAP, злоумышленник может определить первый байт ключевой последовательности как B ⊕ 0xAA.

В начале злоумышленник использует вектор инициализации как первые три элемента K[]. Он наполняет S-блок S[] последовательными значениями от 0 до n как это делаетс в RC4 когда инициализируется S-блок из известного K[]. Затем он выполняет 3 первые итерации алгоритма инициализации ключевой последовательности. После третьего шага, злоумышленник может пожет получить четвертый байт ключа (не обязательный шаг), используя ключевую последовательность О путем вычисления (O – j – S[i]) mod n = K[i] (i=3 на этом шаге). На данном шаге злоумышленнику еще не известен четвертый (пятый) байт ключа. Данный алгоритм не генерирует следующий байт ключа, он получает возможное значение ключа. Собирая множество WEP пакетов и повторяя эти шаги, злоумышленник генерирует некоторое число возможных значений. Верное значение появляется значительно чаще чем другие, таким образом злоумышленник может определить следующий байт ключа. Теперь он может начать атаку заново для определения последующего байта ключа. Снова, ему нужны только сообщения со слабыми векторами инициализации. Благодаря этому процессу, он может собрать большое количество сообщение для получения всего ключа; на самом деле, он может хранить только короткие отрывки из начала этих сообщений, ровно настолько, насколько необходимо для выполнения атак. В среднем для взлома необходимо перехватить около полумиллиона кадров. При анализе используются только слабые векторы. При их отсутствии данная атака неэффективна.

Атака KoreK

После появления FMS-атаки разработчики изменили алгоритм генерации векторов инициализации так, что слабые ключи уже не возникали. В августе 2004 года хакер, называющий себя KoreK опубликовал на форумах NetStumbler'а новый метод получения ключа, реализовав утилиту под названием chopper. Данная реализация использует 17 различных атак, которые позволяют определить K[l], если известны предыдущие байты ключа и первые 2 слова зашифрованного текста. Некоторые из них уже были известны ранее, но большая часть была создана самим хакером.

Все атаки, которые использовал KoreK можно поделить на 3 группы:

1. Первая группа используют первые [l–1] байтов ключа и первое слово текста для определения K[l]. К данной группе относится и FMS-атака;
2. Вторая группа использует также второе слово зашифрованного текста;
3. Третья группа атак (inverse attacks) помогают исключить определенные значения K[l].

Особенность нового алгоритма в том, что теперь не требуются слабые веторы инициализации. Для влома необходимо всего несколько сотен тысяч пакетов.

Cуществует множество утилит реализующих KoreK атаку. Наиболее успешными являются WepLab и aircrack.

Атака Тевса-Вайнмана-Пышкина В 2007 году трое специалистов с кафедры криптографии и компьютерной алгебры Дармштадтского технического университета — Эрик Тевс, Ральф-Филип Вайнман и  Андрей Пышкин, предложили новый алгоритм, реализовав утилиту aircrack-ptw (усовершенствованная версия  aircrack-ng ). Данная атака использует возможность инъекции ARP запросов в беспроводную сеть. Является наиболее эффективной атакой, для взлома требуется всего несколько десятков тысяч кадров.

Полный перебор

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

Пределы использования полного перебора

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

Предел, основанный на выделяемой Солнцем энергии. Все вычисления потребляют энергию.Согласно принципам классической термодинамики и статистической механики, потребление энергии при осуществлении необратимого преобразования (вычисления) имеет порядок k ⋅T , где T — температура окружающей среды (по абсолютной шкале Кельвина), а k — постоянная Больцмана (равная 1,4 · $10^{-23}$ Дж/K). Мощность излучения Солнца составляет приблизительно 3,86 · $10^{26}$ Вт, таким образом, за весь свой предполагаемый период существования, 10 млрд лет, Солнце выделит около $10^{44}$ Дж. Количество вычислительных операций, которые можно осуществить с использованием всей выделяемой Солнцем энергии, равно выделяемой мощности, поделенной на количество энергии, необходимой для осуществления одной операции (всего $10^{73}$ операций). Такое количество операций потребовалось бы на взлом ключа из 73 десятичных цифр (или около 250 бит) методом прямого перебора при грубом предположении, что для проверки одного значения ключа необходима всего одна операция (на самом деле — сотни).

Предел, основанный на массе Земли. Масса Земли составляет порядка 6 · $10^{24}$ кг, масса протона — 1,6 · $10^{-27}$ кг, вся Земля содержит приблизительно 4 · $10^{51}$ протонов. Сопоставим каждому протону отдельный компьютер и примем за скорость выполнения операции на таком компьютере время, за которое луч света проходит расстояние, равное диаметру этого протона, и получим, что каждый компьютер может выполнять 3 · $10^{25}$ операций в секунду. Если все эти компьютеры будут работать параллельно, их суммарное быстродействие составит 4 · $10^{51}$ + 3 · $10^{25}$ операций в секунду — $10^{77}$ операций в секунду. Возраст Вселенной приблизительно равен 3 · $10^{17}$ секунд. За весь период существования Вселенной такие гипотетические компьютеры размером с протон смогли бы выполнить 3 · $10^{94}$ операций. При описанных в предыдущем ограничении предположениях относительно количества операций, необходимых на проверку значения ключа, такое количество операций позволит взломать ключ длиной 95 десятичных цифр, или 320 бит.

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

Литература

1. Erik Tews Attacks on the WEP protocol.
2. Feng-Tse Lin, Cheng-Yan Kao A Genetic Algorithm for Ciphertext-Only Attack in Cryptanalysis.
3. Scott Fluhrer, Itsik Mantin and Adi Shamir Weaknesses in the Key Scheduling Algorithm of RC4.

Ссылки

• Веб-сайт английского инженера-энтузиаста Тони Сэйла - http://www.codesandciphers.org.uk/
• Атаки на WEP, Майкл Оссман - http://www.securitylab.ru/analytics/216384.php
• Беспроводные сети и их взлом - http://www.insidepro.com/kk/045/045r.shtml
• КОЛОСС БРИТАНСКИЙ: СЕКРЕТНЫЙ ПРЕДОК КОМПЬЮТЕРОВ - http://www.popmech.ru/article/387-koloss-britanskiy/