[Перевод] Криптографические атаки: объяснение для смятённых умов04.08.2019 18:04

При слове «криптография» некоторые вспоминают свой пароль WiFi, зелёный замочек рядом с адресом любимого сайта и то, как трудно залезть в чужую почту. Другие вспоминают череду уязвимостей последних лет с говорящими аббревиатурами (DROWN, FREAK, POODLE…), стильными логотипами и предупреждением срочно обновить браузер.

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

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

• Базовые стратегии: брутфорс, частотный анализ, интерполяция, понижение и кросс-протоколы.
  
• «Брендовые» уязвимости: FREAK, CRIME, POODLE, DROWN, Logjam.
  
• Продвинутые стратегии: атаки оракула (атака Воденэ, атака Келси); метод встречи посередине (meet-in-the-middle), атака «дней рождения», статистическое смещение (дифференциальный криптоанализ, интегральный криптоанализ и т. д.).
  
• Атаки по сторонним каналам и их близкие родственники, методы анализа сбоев.
  
• Атаки на криптографию с открытым ключом: кубический корень, броадкаст, связанное сообщение, атака Копперсмита, алгоритм Полига — Хеллмана, числовое решето, атака Винера, атака Блайхенбахера.

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

Некоторые из этих атак в основном потеряли актуальность и не применялись уже много лет. Другие — старожилы, они всё ещё регулярно подкрадываются к ничего не подозревающим разработчикам криптосистем в 21 веке. Можно считать, что эпоха современной криптографии началась с появления IBM DES — первого шифра, который выдержал все атаки в этом списке.

Простой брутфорс

Схема шифрования состоит из двух частей: 1) функция шифрования, которая принимает сообщение (открытый текст) в сочетании с ключом, а затем создаёт зашифрованное сообщение — шифротекст; 2) функция дешифрования, которая принимает шифротекст и ключ и создаёт открытый текст. И шифрование, и дешифрование должны быть легко вычисляемы с ключом — и трудно без него.

Предположим, что мы видим шифротекст и пытаемся расшифровать его без какой-либо дополнительной информации (это называется атакой «только шифротекст»). Если мы каким-то волшебным образом найдём правильный ключ, то можем легко проверить, что он действительно правильный, если результат является разумным сообщением.

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

Во-вторых, мы предполагаем, что правильный ключ является единственным ключом, который приведёт к разумной расшифровке. Это также разумное предположение; оно выполняется, если шифротекст намного длиннее ключа и хорошо читаем. Как правило, так и бывает в реальном мире, за исключением огромных непрактичных ключей или других махинаций, которые лучше оставить в стороне (если вам не нравится, что мы отмахнулись от объяснений, пожалуйста, см. теорему 3.8 здесь).

Учитывая вышеизложенное, возникает стратегия: проверить каждый возможный ключ. Это называется брутфорсом, и такая атака гарантированно работает против всех практических шифров — в конечном итоге. Например, брутфорса достаточно, чтобы взломать шифр Цезаря, древний шифр, где ключом является одна буква из алфавита, что подразумевает чуть более 20 возможных ключей.

К сожалению для криптоаналитиков, увеличение размера ключа хорошо защищает от брутфорса. По мере роста размера ключа количество возможных ключей увеличивается экспоненциально. С современными размерами ключей простой брутфорс совершенно не практичен. Чтобы понять, что мы имеем в виду, возьмём самый быстрый известный суперкомпьютер на середину 2019 года: Summit от IBM, с пиковой производительностью порядка 1017 операций в секунду. Сегодня типичная длина ключа составляет 128 бит, что означает 2128 возможных комбинаций. Для перебора всех ключей суперкомпьютеру Summit потребуется время, которое примерно в 7800 раз превышает возраст Вселенной.

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

Частотный анализ

Большинство текстов — это не тарабарщина. Например, в англоязычных текстах много букв 'e' и артиклей 'the'; в двоичных файлах — много нулевых байтов в качестве заполнителя между фрагментами информации. Частотный анализ — любая атака, которая использует этот факт.

Каноническим примером шифра, уязвимого для этой атаки, является простой шифр подстановки. В этом шифре ключ представляет собой таблицу с заменой всех букв. Например, 'g' заменяется на 'h', 'o' — на j, Поэтому слово 'go' превращается в 'hj'. Этот шифр трудно поддаётся простому брутфорсу, так как существует очень много возможных таблиц подстановки. Если вас интересует математика, эффективная длина ключа составляет около 88 бит: это
. Но частотный анализ обычно быстро справляется с задачей.

Рассмотрим следующий шифротекст, обработанный простым шифром подстановки:

XDYLY ALY UGLY XDWNKE WN DYAJYN ANF YALXD DGLAXWG XDAN ALY FLYAUX GR WN OGQL ZDWBGEGZDO

Поскольку Y встречается часто, в том числе в конце многих слов, мы можем предварительно предположить, что это буква e:

XDeLe ALe UGLe XDWNKE WN DeAJeN ANF eALXD DGLAXWG XDAN ALe FLeAUX GR WN OGQL ZDWBGEGZDO

Пара XD повторяется в начале нескольких слов. В частности, сочетание XDeLe явно предполагает слово these или there, поэтому продолжаем:

theLe ALe UGLe thWNKE WN heAJeN ANF eALth DGLAtWG thAN ALe FLeAUt GR WN OGQL ZDWBGEGZDO

Далее предположим, что L соответствует r, A — a и так далее. Вероятно, придётся сделать несколько попыток, но по сравнению с полным брутфорсом эта атака восстанавливает исходный текст в кратчайшие сроки:

there are more things in heaven and earth horatio than are dreamt of in your philosophy

Для некоторых решение таких «криптограмм» — увлекательное хобби.

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

Самым амбициозным полиалфавитным шифром в истории и, наверное, самым известным, был шифр «Энигмы» во Второй мировой войне. Он был относительно сложным по сравнению с предшественниками, но в результате долгой и упорной работы британские криптоаналитики взломали его с помощью частотного анализа. Конечно, они не смогли разработать элегантную атаку, как показанная выше; им пришлось сравнивать известные пары открытых и зашифрованных текстов (так называемая «атака на основе открытых текстов») и даже провоцируя пользователей «Энигмы» на шифрование определённых сообщений с анализом результата («атака на основе подобранного открытого текста»). Но это не облегчило судьбу побеждённых армий врагов и потопленных подводных лодок.

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

Предварительные вычисления

Возьмём гипотетический город Преком Хайтс с населением 200 000 человек. В каждом доме города находятся ценные вещи в среднем на $30 000, но не более, чем на $50 000. Рынок безопасности в Прекоме монополизировала компания ACME Industries, которая производит легендарные дверные замки класса Coyote ^™. Согласно экспертному анализу, замок класса Coyote способна сломать только очень сложная гипотетическая машина, создание которой требует около пяти лет и $50 000 вложений. Город в безопасности?

Скорее всего, нет. В конце концов, появится достаточно амбициозный преступник. Он будет рассуждать так: «Да, я понесу большие авансовые расходы. Пять лет терпеливого ожидания, и $50 000. Но по окончании работы у меня будет доступ ко всему богатству этого города. Если я правильно разыграю свои карты, то эта инвестиция многократно окупится».

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

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

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

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

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

Интерполяция

Перед вами знаменитый детектив Шерлок Холмс, выполняющий атаку с интерполяцией на незадачливого доктора Ватсона:

Я сразу догадался, что вы приехали из Афганистана… Ход моих мыслей был таков: «Этот человек по типу — врач, но выправка у него военная. Значит, военный врач. Он только что приехал из тропиков — лицо у него смуглое, но это не природный оттенок его кожи, так как запястья у него гораздо белее. Лицо измождённое, — очевидно, немало натерпелся и перенёс болезнь. Был ранен в левую руку — держит её неподвижно и немножко неестественно. Где же под тропиками военный врач-англичанин мог натерпеться лишений и получить рану? Конечно же, в Афганистане». Весь ход мыслей не занял и секунды. И вот я сказал, что вы приехали из Афганистана, а вы удивились.

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

Проиллюстрируем на простом примере, как работает интерполяция. Предположим, что мы хотим прочитать личный дневник нашего врага, Боба. Он шифрует каждое число в своём дневнике с помощью простой криптосистемы, о которой узнал из рекламного объявления в журнале «Насмешка над криптографией». Система работает следующим образом: Боб выбирает два числа, которые ему нравятся: и . С этого момента, чтобы зашифровать любое число , он вычисляет . Например, если Боб выбрал и , то цифра зашифруется как .

Предположим, 28 декабря мы заметили, что Боб что-то царапает в своём дневнике. Когда он закончит, мы незаметно возьмём его и посмотрим последнюю запись:

Дата: 235/520

Дорогой дневник,

Сегодня был хороший день. Через 64 дня у меня свидание с Алисой, которая живёт в квартире 843. Я действительно думаю, что она может быть 26!

Поскольку мы очень серьёзно намерены проследить за Бобом на его свидании (в этом сценарии нам по 15 лет), то критически важно узнать дату, а также адрес Алисы. К счастью, мы замечаем, что криптосистема Боба уязвима для атаки интерполяции. Мы можем и не знать и , но мы знаем сегодняшнюю дату, поэтому у нас есть две пары «открытый текст — шифротекст». А именно, мы знаем, что  шифруется в , а  — в . Что и запишем:

Поскольку нам 15 лет, мы уже знаем о системе двух уравнений с двумя неизвестными, чего в данной ситуации достаточно для нахождения и  без особых проблем. Каждая пара «открытый текст-шифротекст» накладывает ограничение на ключ Боба, и двух ограничений вместе достаточно, чтобы полностью восстановить ключ. В нашем примере ответ и (при , так что 26 в дневнике соответствует слову 'the one', то есть «та самая» — прим. пер.).

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

Новички часто жалуются, что криптография — это «искусство проектирования как можно более уродливых вещей». Вероятно, во многом виноваты атаки интерполяции. Боб может или использовать элегантный математический дизайн, или сохранить конфиденциальность свидания с Алисой —, но увы, обычно нельзя получить и то, и другое. Это станет предельно ясно, когда мы в конце концов перейдём к теме криптографии с открытым ключом.

Кросс-протокол/понижение

В фильме «Иллюзия обмана» (2013) группа иллюзионистов пытается обманом выманить всё состояние коррумпированного страхового магната Артура Тресслера. Чтобы получить доступ к банковскому счёту Артура, иллюзионисты должны либо представить его имя пользователя и пароль, либо заставить его лично появиться в банке и принять участие в схеме.

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

(Согласно городской легенде, которую мы лично проверили и подтвердили, криптограф Эли Бихэм однажды столкнулся с кассиром банка, который настаивал на установке секретного вопроса. Когда кассир спросил имя бабушки по материнской линии, Бихэм начал диктовать: «Заглавная X, маленькая y, три…»).

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

В некоторых сложных случаях недостаточно просто связаться с сервером по более слабому протоколу, а требуется невольное участия легитимного клиента. Это можно организовать с помощью так называемой атаки на понижение (downgrade). Для понимания этой атаки предположим, что у наших иллюзионистов более сложная задача, чем в фильме. Предположим, что у сотрудника банка (кассир) и Артура возникли некие непредвиденные обстоятельства, в результате чего произошёл такой диалог:

Взломщик: Алло? Это Артур Тресслер. Я хотел бы восстановить свой пароль.

Кассир: Отлично. Пожалуйста, взгляните в свою персональную книгу секретных кодов, страница 28, слово 3. Все следующие сообщения будут зашифрованы с помощью этого конкретного слова в качестве ключа. PQJGH. LOTJNAM PGGY MXVRL ZZLQ SRIU HHNMLPPPV…

Взломщик: Эй-эй, погоди, погоди. Это действительно необходимо? Мы не можем просто говорить как нормальные люди?

Кассир: Не советую этого делать.

Взломщик: Я просто… слушай, у меня был паршивый день, ясно? Я VIP-клиент и не в настроении копаться в этих дурацких кодовых книгах.

Кассир: Хорошо. Если вы настаиваете, мистер Тресслер. Что вам угодно?

Взломщик: Пожалуйста, я хотел бы передать все свои деньги в Национальный фонд жертв Артура Тресслера.

(Пауза).

Кассир: Так, понятно. Пожалуйста, укажите свой пин-код для крупных транзакций.

Взломщик: Мой что?

Кассир: По вашей личной просьбе транзакции такого размера требуют ввода пин-кода для крупных транзакций. Этот код выдали вам при открытии счёта.

Взломщик: … Я его потерял. Это действительно необходимо? Разве вы не можете просто одобрить сделку?

Кассир: Нет. Прошу прощения, мистер Тресслер. Опять же, это мера безопасности, которую вы просили. Если хотите, можем выслать новый пин-код на почтовый ящик.

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

Тресслер: Здравствуйте. Я хотел бы оформить удалённую транзакцию, пожалуйста.

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

(Взломщик нажимает на кнопку; голос кассира превращается в неразборчивый шум).

Кассир:  — #@$#@$#*@$$@#* будет зашифрован с этим словом в качестве ключа. AAAYRR PLRQRZ MMNJK LOJBAN…

Тресслер: Простите, я не совсем понял. Ещё раз? На какой странице? Какое слово?

Кассир: Это страница @#$@#*$)#*#@()#@$(#@*$(#@*.

Тресслер: Что?

Кассир: Слово номер двадцать @$#@$#%#$.

Тресслер: Серьёзно! Да хватит уже! Вы со своим протоколом безопасности — это какой-то цирк. Я знаю, что ты можешь просто нормально поговорить со мной.

Кассир: Я не советую…

Тресслер: А я тебе не советую впустую тратить моё время. Не хочу больше слышать об этом, пока не исправите проблемы со своей телефонной линией. Можем мы оформить эту сделку или нет?

Кассир: … да. Хорошо. Что вам угодно?

Тресслер: Я хотел бы перевести $20 000 в компанию Lord Business Investments, номер счёта…

Кассир: Минутку, пожалуйста. Это большая сделка. Пожалуйста, укажите свой пин-код для крупных транзакций.

Тресслер: Что? А, точно. 1234.

Вот атака на понижение. Более слабый протокол «просто говорите прямо» предполагался как опция на крайний случай. И всё же мы здесь.

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

Именно такая история произошла с протоколом SSLv2 в 1995 году. Правительство США давно начало рассматривать криптографию как оружие, которое лучше держать подальше от внешних и внутренних врагов. Фрагменты кода по отдельности одобряли для экспорта из США, часто при условии намеренного ослабления алгоритма. Компании Netscape, разработчику самого популярного браузера Netscape Navigator, дали разрешение на SSLv2 только с изначально уязвимым ключом RSA 512 бит (и 40 бит для RC4).

К концу тысячелетия правила смягчили и доступ к современному шифрованию стал широко доступным. Тем не менее, клиенты и серверы в течение многих лет поддерживали ослабленную «экспортную» криптографию из-за той же инерции, из-за которой сохраняется поддержка любой устаревшей системы. Клиенты полагали, что могут встретить сервер, который не поддерживает ничего другого. Серверы делали то же самое. Конечно, протокол SSL диктует, что клиенты и серверы никогда не должны использовать слабый протокол, когда доступен лучший. Но та же предпосылка действовала для Тресслера и его банка.

Эта теория нашла применение в двух громких атаках, которые одна за другой потрясли безопасность протокола SSL в 2015 году, обе обнаружены исследователями Microsoft и INRIA. Сначала в феврале разгласили детали атаки FREAK, а через три месяца — ещё одной подобной атаки под названием Logjam, которую мы обсудим более подробно, когда перейдём к атакам на криптографию с открытым ключом.

Уязвимость FREAK (также известная как «Smack TLS») проявилась, когда исследователи проанализировали реализации клиента/сервера TLS и обнаружили любопытную ошибку. В этих реализациях, если клиент даже не просит использовать слабую экспортную криптографию, но сервер всё равно отвечает такими ключами — клиент говорит «Ну ладно» и переходит на слабый набор шифров.

В то время все считали экспортную криптографию устаревшей и запретной для использования, поэтому атака стала настоящим шоком и затронула многие важные домены, включая сайты Белого дома, налогового управления США и АНБ. Хуже того, оказалось, что многие уязвимые серверы оптимизировали производительность, повторно используя одни и те же ключи, а не создавая новые для каждого сеанса. Это позволило после понижения протокола провести ещё и атаку с предвычислением: взлом одного ключа оставался относительно дорогим ($100 и 12 часов на момент публикации), но практическая стоимость атаки на соединение значительно снизилась. Достаточно один раз подобрать серверный ключ — и взломать шифры для всех последующих соединений с этого момента.

И прежде чем двигаться дальше, нужно упомянуть одну продвинутую атаку…

Атака оракула

Мокси Марлинспайк наиболее известен как отец кросс-платформенного криптомессенджера Signal;, но лично нам нравится одно из его менее известных нововведений — принцип криптографической обречённости (Cryptographic Doom Principle). Слегка перефразируя, можно сказать так: «Если протокол выполняет любую криптографическую операцию над сообщением из потенциально вредоносного источника и ведёт себя по-разному в зависимости от результата, он обречён». Или в более резкой форме: «Не бери у врага информацию на обработку, а если пришлось, то хотя бы не показывай результат».

Оставим в стороне переполнения буфера, инъекции команд и тому подобное; они выходят за рамки этого обсуждения. Нарушение «принципа обречённости» приводит к серьёзным взломам криптографии из-за того, что протокол ведёт себя в точности так, как положено.

Для примера возьмём выдуманную конструкцию с уязвимым шифром подстановки, а затем продемонстрируем возможную атаку. Хотя мы уже видели атаку на шифр подстановки с помощью частотного анализа, это не просто «другой способ сломать тот же шифр». Наоборот, атаки оракула — гораздо более современное изобретение, применимое к множеству ситуаций, когда частотный анализ терпит неудачу, и мы увидим демонстрацию этого в следующем разделе. Здесь простой шифр выбран только для того, чтобы сделать пример более понятным.

Итак, Алиса и Боб общаются с помощью простого шифра подстановки, используя ключ, известный только им. Они очень строго относятся к длине сообщений: их длина ровно 20 символов. Поэтому они согласились, что если кто-то хочет отправить более короткое сообщение, то должен добавить какой-то фиктивный текст в конец сообщения, чтобы оно было ровно 20 символов. После некоторого обсуждения они решили, что будут принимать только следующие фиктивные тексты: a, bb, ccc, dddd и т. д. Таким образом, известен фиктивный текст любой необходимой длины.

Когда Алиса или Боб получает сообщение, они сначала проверяют, что сообщение имеет правильную длину (20 символов), а суффикс — правильный фиктивный текст. Если это не так, то отвечают соответствующим сообщением об ошибке. Если длина текста и фиктивный текст в порядке, получатель читает само сообщение и отправляет зашифрованный ответ.

В процессе атаки злоумышленник выдаёт себя за Боба и отправляет поддельные сообщения Алисе. Сообщения — полная ерунда — у злоумышленника нет ключа, и поэтому он не может подделать значимое сообщение. Но поскольку протокол нарушает принцип обречённости, злоумышленник всё равно может заманить Алису в ловушку, так что она раскроет информацию о ключе, как показано ниже.

Взломщик: PREWF ZHJKL MMMN. LA

Алиса: Неверный фиктивный текст.

Взломщик: PREWF ZHJKL MMMN. LB

Алиса: Неверный фиктивный текст.

Взломщик: PREWF ZHJKL MMMN. LC

Алиса: ILCT? TLCT RUWO PUT KCAW CPS OWPOW!

Взломщик понятия не имеет, что только что сказала Алиса, но отмечает, что символ C должен соответствовать a, поскольку Алиса приняла фиктивный текст.

Взломщик: REWF ZHJKL MMMN. LAA

Алиса: Неверный фиктивный текст.

Взломщик: REWF ZHJKL MMMN. LBB

Алиса: Неверный фиктивный текст.

После ряда попыток…

Взломщик: REWF ZHJKL MMMN. LGG

Алиса: Неверный фиктивный текст.

Взломщик: REWF ZHJKL MMMN. LHH

Алиса: TLQO JWCRO FQAW SUY LCR C OWQXYJW. IW PWWR TU TCFA CHUYT TLQO JWFCTQUPOLQZ.

Опять же, взломщик понятия не имеет, что только что сказала Алиса, но отмечает, что H должен сопоставляться с b, поскольку Алиса приняла фиктивный текст.

И так далее, пока злоумышленник не узнает значение каждого символа.

На первый взгляд, метод напоминает атаку на основе подобранного открытого текста. В конце концов, злоумышленник подбирает шифротексты, а сервер послушно их обрабатывает. Основное различие, которое делает эти атаки жизнеспособными в реальном мире, состоит в том, что злоумышленнику не требуется доступ к фактической расшифровке — достаточно ответа сервера, даже такого безобидного, как «Неправильный фиктивный текст».

Хотя эта конкретная атака поучительна, не следует слишком зацикливаться на специфике схемы «фиктивного текста», конкретной используемой криптосистеме или точной последовательности сообщений, отправленных злоумышленником. Основная идея заключается в том, как Алиса реагирует по-разному, основываясь на свойствах открытого текста, и делает это без проверки того, что соответствующий зашифрованный текст действительно получен от доверенной стороны. Таким образом, Алиса позволяет злоумышленнику выжать секретную информацию из её ответов.

В этом сценарии можно многое изменить. Символы, на которые реагирует Алиса, или саму разницу в её поведении, или даже используемую криптосистему. Но принцип останется тем же, и атака в целом останется жизнеспособной в той или иной форме. Базовая реализация этой атаки помогла обнаружить несколько ошибок безопасности, которые мы скоро рассмотрим;, но прежде следует усвоить некоторые теоретические уроки. Как использовать этот выдуманный «сценарий Алисы» в атаке, которая способна работать на реальном современном шифре? Возможно ли это вообще, даже в теории?

В 1998 году швейцарский криптограф Даниель Блайхенбахер (Daniel Bleichenbacher) ответил на этот вопрос утвердительно. Он продемонстрировал атаку оракула в широко используемой криптосистеме с открытым ключом RSA, при использовании определённой схемы сообщений. В некоторых реализациях RSA сервер отвечает разными сообщениями об ошибках, в зависимости от того, соответствует открытый текст схеме или нет; этого было достаточно, чтобы провести атаку.

Четыре года спустя, в 2002 году, французский криптограф Серж Воденэ (Serge Vaudenay) продемонстрировал атаку оракула, почти идентичную той, что описана выше в сценарии Алисы — за исключением того, что вместо выдуманного шифра он взломал целый респектабельный класс современных шифров, которые люди действительно используют. В частности, атака Воденэ нацелена на шифры с фиксированным размером ввода («блочные шифры»), когда они используются в так называемом «режиме шифрования CBC» и с определённой популярной схемой заполнения, в основном эквивалентной той, что в сценарии Алисы.

Также в 2002 году американский криптограф Джон Келси (John Kelsey) — соавтор Twofish — предложил различные атаки оракула на системы, которые сжимают сообщения, а затем шифруют их. Наиболее заметной среди них была атака, которая использовало то, что часто можно вывести исходную длину открытого текста от длины зашифрованного текста. В теории это позволяет провести атаку оракула, которая восстанавливает части исходного открытого текста.

Далее мы приводим более подробное описание атак Воденэ и Келси (дадим более подробное описание атаки Блайхенбахера, когда перейдём к атакам на криптографию с открытым ключом). Несмотря на все наши усилия, текст становится несколько техническим; поэтому, если вышеизложенного для вас достаточно, пропустите следующие два раздела.

Атака Воденэ

Чтобы понять атаку Воденэ, сначала нужно немного подробнее поговорить о блочных шифрах и режимах шифрования. «Блочный шифр» — это, как уже упоминалось, шифр, который принимает ключ и ввод определённой фиксированной длины («длина блока») и выдаёт зашифрованный блок той же длины. Блочные шифры широко используются и считаются относительно безопасными. Ныне вышедший на пенсию DES, который считают первым современным шифром, был блочным. Как упоминалось выше, то же самое верно и для AES, широко используемого сегодня.

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

© Habrahabr.ru