Лекция
Привет, Вы узнаете о том , что такое криптоанализ, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое криптоанализ, атаки на систему шифрования , настоятельно рекомендую прочитать все из категории Криптография и криптоанализ, Стеганография и Стегоанализ.
криптоанализ (от др.-греч. κρυπτός — скрытый и анализ) — наука о методах расшифровки зашифрованной информации без предназначенного для такой расшифровки ключа.
Системы шифрования могут подвергнуться атакам тремя следующими способами:
При проведении атаки на алгоритм криптоаналитик ищет уязвимости в методе преобразования открытого текста в шифр, чтобы раскрыть открытый текст без использования ключа. Алгоритмы, имеющие такие уязвимости, нельзя назвать достаточно мощными. Причина в том, что известная уязвимость может использоваться для быстрого восстановления исходного текста. Злоумышленнику в этом случае не придется использовать какие-либо дополнительные ресурсы.
Атаки "грубой силы" являются попытками подбора любого возможного ключа для преобразования шифра в открытый текст. В среднем аналитик с использованием этого метода должен проверить действие 50 процентов всех ключей, прежде чем добьется успеха. Таким образом, мощность алгоритма определяется только числом ключей, которые необходимо перепробовать аналитику. Следовательно, чем длиннее ключ, тем больше общее число ключей, и тем больше ключей должен перепробовать злоумышленник до того, как найдет корректный ключ. Атаки с использованием грубой силы теоретически всегда должны заканчиваться успешно при наличии необходимого количества времени и ресурсов. Следовательно, алгоритмы нужно оценивать по периоду времени, в течение которого информация остается защищенной при проведении атаки с использованием "грубой силы". Алгоритм расценивается как безопасный, если затраты на получение ключа с помощью атаки "грубой силы" превышают стоимость самой защищаемой информации.
Последний тип атак, реализуемый с использованием уязвимостей в компьютерной системе, как правило, не обсуждается в контексте шифрования. Тем не менее, на практике проще атаковать саму компьютерную систему, чем алгоритм шифрования. К примеру, рассмотрим следующую ситуацию: алгоритм является мощным и имеет длинный ключ, и для его раскрытия с помощью атаки "грубой силы" потребуются оборудование стоимостью в миллионы долларов и масса времени. Однако организация, использующая этот алгоритм, передает ключи через обычную электронную почту. Если известно, когда именно передается ключ, то легче будет перехватить сообщение и выяснить этот ключ.
Еще более ярким примером уязвимости является пакет шифрования, используемый многими пользователями. Этот пакет использует мощные алгоритмы шифрования для зашифровки электронной почты и файлов. Атаки на такую систему нельзя легко осуществить с помощью алгоритмов или атак "грубой силы". Тем не менее, ключ пользователя находится в файле на его компьютере. Файл защищен паролем. Принимая во внимание тот факт, что большинство пользователей не используют в своих паролях комбинации случайных символов, гораздо проще угадать пароль пользователя или получить его с помощью атак "грубой силы", чем получить таким же способом ключ пользователя.
Из этого необходимо сделать вывод о том, что система ничуть не меньше влияет на общую безопасность шифров, чем алгоритм шифрования и ключ.
Термин криптоанализ был введен американским криптографом Уильямом Ф. Фридманом в 1920 году в рамках его книги «Элементы криптоанализа» . Неформально криптоанализ называют также взломом шифра.
В большинстве случаев под криптоанализом понимается выяснение ключа; криптоанализ включает также методы выявления уязвимости криптографических алгоритмов или протоколов.
Первоначально методы криптоанализа основывались на лингвистических закономерностях естественного текста и реализовывались с использованием только карандаша и бумаги. Со временем в криптоанализе нарастает роль чисто математических методов, для реализации которых используются специализированныекриптоаналитические компьютеры.
Попытку раскрытия конкретного шифра с применением методов криптоанализа называют криптографической атакой на этот шифр. Криптографическую атаку, в ходе которой раскрыть шифр удалось, называют взломом или вскрытием.
Термины, связанные с шифрованием
На рис.1 показан общий принцип, согласно которому осуществляется шифрование.
Рис. 1
- Открытый текст ‑ информация в исходном виде.
- Шифрованный текст ‑ информация, подвергнутая действию алгоритма шифрования.
- Алгоритм ‑ метод, используемый для преобразования открытого текста в шифрованный текст.
- Ключ ‑ входные данные, посредством которых с помощью алгоритма происходит преобразование открытого текста в шифрованный или обратно.
- Шифрование ‑ процесс преобразования открытого текста в шифр.
- Дешифрование ‑ процесс преобразования шифра в открытый текст.
Существуют также четыре общих термина.
- Криптография ‑ наука о сокрытии информации с помощью шифрования.
- Криптограф ‑ лицо, занимающееся криптографией.
- Криптоанализ ‑ искусство анализа криптографических алгоритмов на предмет наличия уязвимостей.
- Криптоаналитик ‑ лицо, использующее криптоанализ для определения и использования уязвимостей в криптографических алгоритмах.
Криптоанализ эволюционировал вместе с развитием криптографии: новые, более совершенные шифры приходили на смену уже взломанным системам кодирования только для того, чтобы криптоаналитики изобрели более изощренные методы взлома систем шифрования. Понятия криптографии и криптоанализа неразрывно связаны друг с другом: для того, чтобы создать устойчивую ко взлому систему, необходимо учесть все возможные способы атак на нее.
Хотя понятие криптоанализ было введено сравнительно недавно, некоторые методы взлома были изобретены десятки веков назад. Первым известным письменным упоминанием о криптоанализе является «Манускрипт о дешифровке криптографических сообщений», написанный арабским ученым Ал-Кинди еще в 9 веке. В этом научном труде содержится описание метода частотного анализа.
Частотный анализ — основной инструмент для взлома большинства классических шифров перестановки или замены. Данный метод основывается на предположении о существовании нетривиального статистического распределения символов, а также их последовательностей одновременно и в открытом тексте, и в шифротексте. Причем данное распределение будет сохраняться с точностью до замены символов как в процессе шифрования, так и в процессе дешифрования. Стоит отметить, что при условии достаточно большой длины шифрованного сообщения моноалфавитные шифры легко поддаются частотному анализу: если частота появления буквы в языке и частота появления некоторого присутствующего в шифротексте символа приблизительно равны, то в этом случае с большой долей вероятности можно предположить, что данный символ и будет этой самой буквой. Самым простым примером частотного анализа может служить банальный подсчет количества каждого из встречающихся символов, затем следуют процедуры деления полученного числа символов на количество всех символов в тексте и умножение результата на сто, чтобы представить окончательный ответ в процентах. Далее полученные процентные значения сравниваются с таблицей вероятностного распределения букв для предполагаемого языка оригинала.
В период XV—XVI веков в Европе создавались и развивались полиалфавитные шифры замены. Наиболее известным является шифр французского дипломата Блеза де Виженера, в основу которого легло использование последовательности нескольких шифров Цезаря с различными значениями сдвига. На протяжении трех веков Шифр Виженера считался полностью криптографически устойчивым, пока в 1863 году Фридрих Касиски не предложил свою методику взлома этого шифра. Основная идеяметода Касиски заключается в следующем: если в открытом тексте между двумя одинаковыми наборами символов находится такой блок текста, что его длина кратна длине ключевого слова, то эти одинаковые наборы символов открытого текста при шифровании перейдут в одинаковые отрезки шифротекста. На практике это означает то, что при наличии в шифротексте одинаковых отрезков длиной в три и больше символов, велика вероятность того, что эти отрезки соответствуют одинаковым отрезкам открытого текста. Как применяется метод Касиски: в шифротексте ищутся пары одинаковых отрезков длины три или больше, затем вычисляется расстояние между ними, то есть количество символов, разделяющих стартовые позиции парных отрезков. В результате анализа всех пар одинаковых отрезков мы получим совокупность расстояний d1, d2, d3,… Очевидно, что длина ключевого слова будет делителем для каждого из расстояний и, следовательно, для их наибольшего общего делителя.
Следующий этап развития криптоанализа связан с изобретением роторных шифровальных машин таких как, например, изобретенная Артуром Шербиусом Энигма. Целью таких устройств было минимизировать количество повторяющихся отрезков шифротекста, статистика появления которых использовалась при взломе шифра Виженера. Польским криптоналитикам удалось построить прототип дешифровальной машины для версии Энигмы, используемой Нацистской Германией. Машина получила название «Бомба» за то, что при работе издавала звуки похожие на тиканье часов. Позже она была доработана и взята на вооружение английскими криптоаналитиками.
По мере развития новых методов шифрования математика становилась все более и более значимой. Так, например, при частотном анализе криптоаналитик должен обладать знаниями и в лингвистике, и в статистике. В то время как теоретические работы по криптоанализу Энигмы выполнялись преимущественно математиками, например, Аланом Матисоном Тьюрингом. Тем не менее благодаря все той же математике криптография достигла такого развития, что количество необходимых для взлома элементарных математических операций стало достигать астрономических значений. Современная криптография стала гораздо более устойчивой к криптоанализу, чем некогда используемые, устаревшие методики, для взлома которых было достаточно ручки и листа бумаги. Может показаться, что чистый теоретический криптоанализ не способен более эффективно взламывать современные шифры. Тем не менее историк Дэвид Кан в своей заметке к 50-й годовщине Агентства национальной безопасности пишет:
«В наши дни сотни фирм предлагают множество различных криптосистем, которые невозможно взломать ни одним из известных методов криптоанализа. Действительно, такие системы устойчивы даже к атаке по подобранному открытому тексту, то есть сравнение открытого текста и соответствующего ему шифротекста не позволяет узнать ключ шифрования, который бы позволил дешифровать другие сообщения. Таким образом, в некотором смысле криптоанализ мертв. Но это еще не конец. Криптоанализ может быть и мертв, но, выражаясь метафорически, с кошки можно снять шкурку несколькими способами.»
Далее в своей заметке описывает возросшее значение перехвата данных, закладки жучков, атак по сторонним каналам и квантовых компьютеров как методик, идущих на смену традиционным методам криптоанализа. В 2010 бывший технический директор Управления национальной безопасности Брайан Сноу отметил, что коммерческая криптография уже почти достигла уровня развития технологий, используемых разведывательными службами, и теперь они вместе «очень медленно продвигаются в уже полностью исследованной области».
Тем не менее, криптоанализ пока еще рано списывать со счетов. Во-первых, неизвестно, насколько эффективны применяемые спецслужбами методы криптоанализа, а во-вторых, за годы становления и совершенствования современной компьютерной криптографии было высказано множество претензий как к теоретическим, так и к практическим криптографическим примитивам:[источник не указан 1477 дней]
Таким образом, хотя наиболее надежные из современных шифров являются гораздо более устойчивыми к криптоанализу, чем Энигма, тем не менее криптоанализ по-прежнему играет важную роль в обширной области защиты информации.
Брюс Шнайер выделяет 4 основных и 3 дополнительных метода криптоанализа, предполагая знание криптоаналитиком алгоритма шифра:
Основные методы криптоанализа:
Дополнительные методы криптоанализа:
Допустим, криптоаналитик обладает некоторым числом шифротекстов, полученных в результате использования одного и того же алгоритма шифрования. В этом случае криптоаналитик может совершить только атаку на основе шифротекста. Целью криптографической атаки в этом случае является нахождение как можно большего числа открытых текстов, соответствующих имеющимся шифротекстам, или, что еще лучше, нахождение используемого при шифровании ключа.
Входные данные для подобного типа атак криптоаналитик может получить в результате простого перехвата зашифрованных сообщений. Если передача осуществляется по открытому каналу, то реализация задачи по сбору данных сравнительно легка и тривиальна. Атаки на основе шифротекста являются самыми слабыми и неудобными.
Пусть в распоряжении криптоаналитика есть не только шифротексты, но и соответствующие им открытые тексты.
Тогда существуют два варианта постановки задачи:
Получение открытых текстов играет решающую роль в осуществлении этой атаки. Открытые тексты извлекают из самых различных источников. Так, например, можно догадаться о содержимом файла по его расширению.
В случае взлома переписки можно сделать предположение, что письмо имеет структуру типа:
Следовательно, атака может быть организована путем подбора различных видов «Приветствия» (например, «Здравствуйте!», «Добрый день» и т. д.) и/или «Заключительной формы вежливости» (таких как «С уважением», «Искренне Ваш» и т. п.). Легко заметить, что данная атака сильнее атаки на основе одного лишь шифротекста.
Для осуществления такого типа атаки криптоаналитику необходимо иметь не только какое-то количество открытых текстов и полученных на их основе шифротекстов. Помимо прочего в данном случае криптоаналитик должен обладать возможностью подобрать несколько открытых текстов и получить результат их шифрования.
Задачи криптоаналитика повторяют задачи для атаки на основе открытого текста, то есть получить ключ шифрования, либо создать дешифрующий алгоритм для данного ключа.
Получить входные данные для такого вида атаки можно, например, следующим образом:
При осуществлении атаки подобного типа криптоаналитик имеет возможность подбирать блоки открытого текста, что при определенных условиях может позволить получить больше информации о ключе шифрования.
Атака такого типа является более удобным частным случаем атаки на основе подобранного открытого текста. Удобство атаки на основе адаптивно подобранного открытого текста состоит в том, что помимо возможности выбирать шифруемый текст, криптоаналитик может принять решение о шифровании того или иного открытого текста на основе уже полученных результатов операций шифрования. Другими словами, при осуществлении атаки на основе подобранного открытого текста криптоаналитик выбирает всего один большой блок открытого текста для последующего шифрования, а потом на основе этих данных начинает взламывать систему. В случае организации адаптивной атаки криптоаналитик может получать результаты шифрования любых блоков открытого текста, чтобы собрать интересующие его данные, которые будут учтены при выборе следующих отправляемых на шифрование блоков открытого текста и так далее. Наличие обратной связи дает атаке на основе адаптивно подобранного шифротекста преимущество перед всеми вышеперечисленными типами атак.
Допустим, что у криптоаналитика имеется временный доступ к дешифрующему средству или устройству. В таком случае за ограниченный промежуток времени криптоаналитик может получить из известных ему шифротекстов соответствующие им открытые тексты, после чего криптоаналитику нужно будет приступать к взлому системы. При осуществлении подобного типа атаки цель взлома — получить ключ шифрования.
Сжато сформулировать эту задачу можно таким образом:
Дано: С1, P1=Dk(С1), С2, P2=Dk(С2), С3, P3=Dk(С3), …, Сn, Pn=Dk(Сn),
где Сn — n-ый имеющийся шифротекст, Pn — соответствующий Сn открытый текст, а Dk — функция дешифрования при помощи ключа k.
Найти: используемый ключ шифрования k.
Интересным может быть тот факт, что атака на основе подобранного шифротекста также может носить название «Атаки в обеденное время» (lunchtime attack) или «Ночной атаки» (midnight attack). Скажем, в названии «Атаки в обеденное время» отражается тот факт, что легитимный пользователь может оставить свой компьютер с функцией дешифрования без присмотра на время обеда, а криптоаналитик может этим воспользоваться.
Вопреки своему названию атака на основе подобранного ключа не подразумевает под собой того, что криптоаналитик занимается простым перебором ключей в надежде найти нужный. Атака такого типа строится на том, что криптоаналитик может наблюдать за работой алгоритма шифрования, в котором используются несколько ключей. Криптоаналитик изначально ничего не знает о точном значении ключей, зато ему известно некоторое математическое отношение, связывающее между собой ключи. Примером тому может служить ситуация, когда криптоаналитик выяснил, что последние 80 битов у всех ключей одинаковы, хотя сами значения битов могут быть неизвестными.
Криптоаналитик может использовать так называемый «человеческий фактор», то есть пытаться с помощью шантажа, подкупа, пыток или иных способов получить информацию о системе шифрования или даже сам ключ шифрования. Например, дача взятки, как одна из разновидностей бандитского криптоанализа, может носить название «Вскрытие с покупкой ключа». Таким образом методика вскрытия построена на слабости людей как составной части системы защиты информации.
Бандитский криптоанализ считается очень мощным способом взлома системы, а зачастую и наилучшим путем вскрытия шифров.
За последние годы коллекция криптографических атак превратилась в зоопарк кричащих логотипов, набитых формулами научных статей и породила общее мрачное ощущение, что все сломано. Но на самом деле многие из атак основаны на нескольких общих принципах, а бесконечные страницы формул часто сводятся к простым для понимания идеям.
Рассмотрим различные типы криптографических атак, с акцентом на основные принципы. В общих чертах и не совсем в этом порядке, но мы рассмотрим следующее:
Эта конкретная статья охватывает вышеупомянутый материал вплоть до атаки Келси.
Следующие атаки просты в том смысле, что их можно практически полностью объяснить без особых технических деталей. Объясним каждый тип атаки в самых простых терминах, не углубляясь в сложные примеры или расширенные варианты использования.
Некоторые из этих атак в основном потеряли актуальность и не применялись уже много лет. Другие — старожилы, они все еще регулярно подкрадываются к ничего не подозревающим разработчикам криптосистем в 21 веке. Можно считать, что эпоха современной криптографии началась с появления IBM DES — первого шифра, который выдержал все атаки в этом списке.
Схема шифрования состоит из двух частей: 1) функция шифрования, которая принимает сообщение (открытый текст) в сочетании с ключом, а затем создает зашифрованное сообщение — шифротекст; 2) функция дешифрования, которая принимает шифротекст и ключ и создает открытый текст. И шифрование, и дешифрование должны быть легко вычисляемы с ключом — и трудно без него.
Предположим, что мы видим шифротекст и пытаемся расшифровать его без какой-либо дополнительной информации (это называется атакой «только шифротекст»). Об этом говорит сайт https://intellect.icu . Если мы каким-то волшебным образом найдем правильный ключ, то можем легко проверить, что он действительно правильный, если результат является разумным сообщением.
Обратите внимание, что здесь два неявных предположения. Во-первых, что мы знаем, как выполнить расшифровку, то есть, как работает криптосистема. Это стандартное предположение при обсуждении криптографии. Сокрытие деталей реализации шифра от злоумышленников может показаться дополнительной мерой безопасности, но как только злоумышленник выяснит эти детали, данная дополнительная безопасность незаметно и необратимо потеряна. Таков принцип Керчхоффса: попадание системы в руки врага не должно причинять неудобств.
Во-вторых, мы предполагаем, что правильный ключ является единственным ключом, который приведет к разумной расшифровке. Это также разумное предположение; оно выполняется, если шифротекст намного длиннее ключа и хорошо читаем. Как правило, так и бывает в реальном мире, за исключением огромных непрактичных ключей или других махинаций, которые лучше оставить в стороне (если вам не нравится, что мы отмахнулись от объяснений, пожалуйста, см. теорему 3.8 здесь).
Учитывая вышеизложенное, возникает стратегия: проверить каждый возможный ключ. Это называется брутфорсом, и такая атака гарантированно работает против всех практических шифров — в конечном итоге. Например, брутфорса достаточно, чтобы взломать шифр Цезаря, древний шифр, где ключом является одна буква из алфавита, что подразумевает чуть более 20 возможных ключей.
К сожалению для криптоаналитиков, увеличение размера ключа хорошо защищает от брутфорса. По мере роста размера ключа количество возможных ключей увеличивается экспоненциально. С современными размерами ключей простой брутфорс совершенно не практичен. Чтобы понять, что мы имеем в виду, возьмем самый быстрый известный суперкомпьютер на середину 2019 года: Summit от IBM, с пиковой производительностью порядка 1017 операций в секунду. Сегодня типичная длина ключа составляет 128 бит, что означает 2128 возможных комбинаций. Для перебора всех ключей суперкомпьютеру Summit потребуется время, которое примерно в 7800 раз превышает возраст Вселенной.
Считать ли брутфорс историческим курьезом? Вовсе нет: это необходимый ингредиент в поваренной книге криптоанализа. Редко встречаются настолько слабые шифры, что их можно взломать только умной атакой, без применения силы в той или иной степени. Многие успешные взломы используют сначала алгоритмический метод, чтобы ослабить целевой шифр, а затем запустить брутфорс.
Большинство текстов — это не тарабарщина. Например, в англоязычных текстах много букв 'e' и артиклей 'the'; в двоичных файлах — много нулевых байтов в качестве заполнителя между фрагментами информации. Частотный анализ — любая атака, которая использует этот факт.
Каноническим примером шифра, уязвимого для этой атаки, является простой шифр подстановки. В этом шифре ключ представляет собой таблицу с заменой всех букв. Например, 'g' заменяется на 'h', 'o' — на j, Поэтому слово 'go' превращается в 'hj'. Этот шифр трудно поддается простому брутфорсу, так как существует очень много возможных таблиц подстановки. Если вас интересует математика, эффективная длина ключа составляет около 88 бит: это
log2(26!). Но частотный анализ обычно быстро справляется с задачей.
Рассмотрим следующий шифротекст, обработанный простым шифром подстановки:
XDYLY ALY UGLY XDWNKE WN DYAJYN ANF YALXD DGLAXWG XDAN ALY FLYAUX GR WN OGQL ZDWBGEGZDO
Поскольку Y встречается часто, в том числе в конце многих слов, мы можем предварительно предположить, что это буква e:
Пара XD повторяется в начале нескольких слов. В частности, сочетание XDeLe явно предполагает слово these или there, поэтому продолжаем:
Далее предположим, что L соответствует r, A — a и так далее. Вероятно, придется сделать несколько попыток, но по сравнению с полным брутфорсом эта атака восстанавливает исходный текст в кратчайшие сроки:
Для некоторых решение таких «криптограмм» — увлекательное хобби.
Идея частотного анализа более фундаментальная, чем кажется на первый взгляд. И он применим к гораздо более сложным шифрам. На протяжении всей истории различные конструкции шифров пытались противостоять такой атаке с помощью «полиалфавитной подстановки». Здесь в процессе шифрования таблица замены букв изменяется сложными, но предсказуемыми способами, которые зависят от ключа. Все эти шифры в свое время считались трудными для взлома; и все же скромный частотный анализ в итоге все их одолел.
Самым амбициозным полиалфавитным шифром в истории и, наверное, самым известным, был шифр «Энигмы» во Второй мировой войне. Он был относительно сложным по сравнению с предшественниками, но в результате долгой и упорной работы британские криптоаналитики взломали его с помощью частотного анализа. Конечно, они не смогли разработать элегантную атаку, как показанная выше; им пришлось сравнивать известные пары открытых и зашифрованных текстов (так называемая «атака на основе открытых текстов») и даже провоцируя пользователей «Энигмы» на шифрование определенных сообщений с анализом результата («атака на основе подобранного открытого текста»). Но это не облегчило судьбу побежденных армий врагов и потопленных подводных лодок.
После этого триумфа частотный анализ исчез из истории криптоанализа. Шифры современной цифровой эпохи созданы для работы с битами, а не буквами. Что еще более важно, эти шифры разработаны с мрачным пониманием того, что позже стало известно как закон Шнайера: любой может создать алгоритм шифрования, который сам не сможет взломать. Недостаточно, чтобы шифровальная система казалась сложной: чтобы доказать свою ценность, она должна пройти безжалостный обзор безопасности от многих криптоаналитиков, которые сделают все возможное, чтобы взломать шифр.
Возьмем гипотетический город Преком Хайтс с населением 200 000 человек. В каждом доме города находятся ценные вещи в среднем на $30 000, но не более, чем на $50 000. Рынок безопасности в Прекоме монополизировала компания ACME Industries, которая производит легендарные дверные замки класса Coyote (tm). Согласно экспертному анализу, замок класса Coyote способна сломать только очень сложная гипотетическая машина, создание которой требует около пяти лет и $50 000 вложений. Город в безопасности?
Скорее всего,
продолжение следует...
Часть 1 Криптоанализ, Атаки на систему шифрования
Часть 2 Интерполяция - Криптоанализ, Атаки на систему шифрования
Часть 3 Брендовые уязвимости: CRIME, POODLE, DROWN - Криптоанализ, Атаки на систему
Выводы из данной статьи про криптоанализ указывают на необходимость использования современных методов для оптимизации любых систем. Надеюсь, что теперь ты понял что такое криптоанализ, атаки на систему шифрования и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Криптография и криптоанализ, Стеганография и Стегоанализ
Комментарии
Оставить комментарий
Криптография и криптоанализ, Стеганография и Стегоанализ
Термины: Криптография и криптоанализ, Стеганография и Стегоанализ