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

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

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

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

Основная статья: Colossus (компьютер)

Во второй половине 1940 года британская служба радиоэлектронной разведки заметила появление шифрованных немецких радиосообщений необычного вида. Основная секретная переписка нацистской Германии велась с использованием шифровальной машины «Энигма», к тому моменту уже достаточно изученной британской разведкой, и передавалась азбукой Морзе; новые же сообщения, как выяснилось позже, использовали значительно более сложное шифрование, осуществляемое машиной «Лоренц», и передавались в телетайпном коде ITA2.

Перехваченные радиотелеграммы отправлялись в Правительственную школу кодов и шифров в Блетчли-парке. Поскольку дешифрование сообщений вручную было крайне малоэффективно, было решено построить специальные машины для автоматизации этого процесса. Первой из них стала оптомеханическая машина-компаратор Heath Robinson[англ.], которая хоть и справлялась с поставленной задачей, но оказалась недостаточно быстрой и надёжной из-за принятых проектных решений и впоследствии дорабатывалась. Полученный опыт был учтён при создании следующей машины — компьютера «Колосс», содержавшего 1500 электронных ламп и позволившего сократить время дешифрования с нескольких недель до 2-3 часов. Следующим этапом его развития стала модернизация Colossus Mark 2, содержавшая уже около 2500 электронных ламп и работавшая примерно в 5 раз быстрее своего предшественника; кроме того, она программировалась с помощью соединительных проводов и элементов коммутации, расположенных на специальных панелях управления.

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

Атака на 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].

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

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

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

Литература

  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. Архивировано 16 ноября 2012 года.

Ссылки