Что требуется для восстановления зашифрованного текста

Что требуется для восстановления зашифрованного текста

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

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

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

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

Один из самых известных методов шифрования является метод Цезаря, который римский император если и не изобрел, то, по крайней мере, активно им пользовался. Не имея доверия к своим посыльным, он шифровал письма элементарной заменой А на D, В на Е и так далее по латинскому алфавиту. К примеру, при таком кодировании последовательность ABC была бы записана как DEF.

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

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

Основные термины и определения криптографии

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

Некоторые основные понятия и определения.

Алфавит — законченное множество используемых для кодирования информации символов.

Текст — упорядоченный последовательность из символов алфавита.

В качестве примеров алфавитов, используемых в современных ИС можно привести следующие:

• алфавит Z₃₃ — 32 буквы русского алфавита и пробел;
• алфавит Z₂₅₆ — символы, входящие в стандартные кодировки ASCII и КОИ-8;
• бинарный алфавит — Z₂ = ;
• восьмеричный алфавит или шестнадцатеричный алфавит;

Шифрование — процесс преобразования исходного текста (который носит также название открытого текста) в зашифрованный.

Дешифрование — обратный шифрованию процесс. На основе ключа зашифрованный текст преобразуется в исходный.

Ключ — информация, необходимая для беспрепятственного шифрования и дешифрования текстов.

Криптографическая система представляет собой семейство T преобразований открытого текста. Составные этого семейства индексируются, или обозначаются символом k; параметр k является ключом. Пространство ключей K — это набор возможных значений ключа. Обычно ключ представляет собой последовательный ряд букв алфавита.

Криптографичекие системы делят на симметричные и ассиметричные(шифрование с открытым ключом) .

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

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

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

Цифровой подписью является присоединенное к тексту его криптографическое преобразование, которое позволяет при получении текста другим пользователем проверить авторство и подлинность сообщения.

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

• общее количество всех возможных ключей;
• среднее время, необходимое для дешифрования сообщения.

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

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

Для современных криптографических систем информационной безопасности определены следующие общие требования:

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

Метод восстановления данных с диска, зашифрованного NotPetya с помощью алгоритма Salsa20

Атаки с использованием вирусов-шифровальщиков стали настоящим трендом 2017 года. Подобных атак было зафиксировано множество, однако самыми громкими из них оказались WannaCry и NotPetya (также известный под множеством других имен — Petya, Petya.A, ExPetr и другими). Освоив опыт предыдущей эпидемии, специалисты по всему миру оперативно среагировали на новый вызов и в считанные часы после заражения первых компьютеров принялись изучать экземпляры зашифрованных дисков. Уже 27 июня появились первые описания методов заражения и распространения NotPetya, более того — появилась вакцина от заражения.

При запуске NotPetya зашифровывает алгоритмом AES пользовательские файлы с определенными расширениями, но операционная система продолжает работать. На шифрование отводится ограниченное время (по умолчанию — 1 час). И если за это время процесс шифрования успеет завершиться, в корне диска будет размещен файл README.TXT с требованием выкупа. К сожалению, для восстановления файлов, зашифрованных таким способом, требуется знание секретного ключа RSA (который вроде бы предлагают купить в Даркнете за 100 биткойнов). Если же шифрование завершиться не успело, или было прервано, или не было прав на запись в корень диска — файл README.TXT (содержащий зашифрованный ключ) не будет создан, и зашифрованные алгоритмом AES файлы не получится восстановить, даже получив секретный ключ RSA.

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

Это второй слой шифрования. Однако расшифровать Salsa20 целесообразно по нескольким причинам:

• AES зашифровывает не все типы файлов (например, пропускает изображения).
• AES работает ограниченное время (обычно 1 час), и что не успело зашифроваться AES — потенциально восстановимо.
• AES работает от конкретного пользователя. Если на компьютере используются несколько учетных записей пользователей, AES может не иметь прав доступа к данным других пользователей.

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

Однако из-за некоторых особенностей применения алгоритма Salsa20 возможно восстановление данных без знания ключа.

Как работает Salsa20

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

Чтобы гамму можно было вычислять для любого смещения в потоке, генератор гаммы s20_expand32() формирует 64-байтовый массив keystream, в который вперемешку укладываются:

• 256 бит (32 байта) ключа шифрования,
• 8 байт несекретной случайной последовательности nonce (number used once),
• 16 байт константы sigma (“expand 32-byte k” или “-1nvalid s3ct-id”),
• 64 бита (8 байт) номера блока в потоке.

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

Следует отметить, что генерируемые фрагменты гаммы всегда выровнены на границу, кратную 64 байтам. И чтобы зашифровать, скажем, 7 байт начиная со смещения 100, надо найти номер блока, в который попадает первый байт (100/64 == 1), вычислить для этого блока гамму и использовать из нее 7 байт начиная со смещения (100%64 == 36). Если байтов в блоке не хватает, тогда генерируется гамма для следующего блока и т.д.

В процессе шифрования одного потока (а диск, с точки зрения NotPetya, это один поток) не происходит смены ключа или nonce. Следовательно, для каждого зашифрованного диска единственная варьируемая величина в keystream — это номер блока.

По задумке авторов шифра Salsa20, 2^64 блоков по 64 байта позволяют сгенерировать гамму с периодом 2^70 ~ 10^21 байт. Это достаточно большой период для почти любых практических применений, и жестких дисков такого объема не появится еще очень долго.

Однако в реализации не все так гладко.

Реальный период гаммы в NotPetya

Посмотрим на прототип функции s20_crypt32(), через вызовы которой и выполняется шифрование секторов диска.

enum s20_status_t s20_crypt32(uint8_t *key, uint8_t nonce[static 8], uint32_t si, uint8_t *buf, uint32_t buflen)

Через аргумент si (вероятно, Stream Index) передается байтовое смещение в потоке. И по типу аргумента понятно, что там не 64, а только 32 бита. Это значение попадает в keystream после деления на 64, то есть остается максимум 26 бит.

// Set the second-to-highest 4 bytes of n to the block number s20_rev_littleendian(n+8, si / 64);

А теперь посмотрим на еще одну картинку, взятую из того же отчета.

На ней серым цветом выделены те байты, которые не влияют на формирование гаммы вследствие ошибки реализации функции s20_rev_littleendian(). Таким образом, из 26 бит номера блока только 16 бит (байты по смещению 0x20-0x21) повлияют на keystream. Следовательно, максимальный период гаммы составит 2^16=65536 блоков по 64 байта, или 4 мегабайта.

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

И еще одна ошибка

На этом огрехи разработчиков не заканчиваются. При вызове функции s20_crypt32() они вместо значения смещения в байтах передают… номер 512-байтового сектора!

Секторы обычно зашифрованы парами (1024 байта за одно обращение), и значит, гамма применяемая для зашифрования двух соседних пар секторов, будет совпадать в 1022 байтах (со смещением в 2 байта).

Эвристики для Known Plaintext Attack

Современные версии Windows используют файловую систему NTFS, в которой применяется довольно много различных структур, львиную долю полей в которых можно легко предсказать.
Кроме того, на диске присутствует множество файлов, содержимое которых легко предсказать (частично или полностью).

Вступительные 512 байт гаммы

Для проверки правильности ключа шифрования NotPetya зашифровывает сектор 0x21, содержащий предопределенные значения (все байты 0x07). Это дает нам 512 байт гаммы.

Восстановление гаммы по MFT

NotPetya не зашифровывает первые 16 записей в MFT (32 сектора), но зашифровывает все остальные.

Известно, что каждая файловая запись начинается с последовательности “FILE”, затем обычно идут байты 30 00 03 00 (UpdateSequenceArrayOffset = 0x30, UpdateSequenceArrayLength = 3). Теоретически, эти 4 байта могут иметь и другие значения, но они почти всегда одинаковы для всех файловых записей в пределах одного логического тома NTFS.

Таким образом, из одной файловой записи (занимающей два сектора) мы можем получить 8 байт гаммы, а каждая соседняя запись даст нам два дополнительных байта (и возможность проверить 6 полученных ранее байтов). Последние записи почти полностью состоят из нулей, что может дать еще до 1024 байт гаммы.

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

Восстановление гаммы по известным файлам

Вымогатель шифрует и первые два сектора каждого файла, который длиннее 1024 байт. При этом размер кластера обычно больше, чем два сектора (например, 8). В таком случае, найдя зашифрованное начало любого файла и пропустив 1024 байта, мы можем легко получить следующие 3 килобайта в незашифрованном виде. И если у нас будет файл, в котором по смещению 1024 байта от начала находятся точно такие же 3 килобайта — с большой вероятностью и начало файла совпадет. И мы получим еще до 1024 байт гаммы.

Если поставить «чистую» Windows XP и заглянуть в папку Windows, там можно найти 8315 файлов. В активно используемой Windows 8.1 файлов будет больше 200 тысяч. Шансов, что многие из них совпадут с файлами на зашифрованном диске, более чем достаточно.

Так что, если проиндексировать DLL- и EXE-файлы из доступных инсталляций Windows (желательно той же версии и с близким набором обновлений), — возможно, этого хватит, чтобы восстановить гамму полностью.

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

Перспективы и подводные камни

Сложность «ручного» восстановления зашифрованного диска в том, что этот процесс занимает значительное время (часы) и требует больших объемов свободного дискового пространства. Мало у кого из пользователей есть пустой диск, объем которого не меньше, чем объем зашифрованного. А ставить эксперименты на пострадавшем оригинале сродни самоубийству.

Так что маловероятно, что в ближайшее время появится утилита, которая позволит все восстановить «быстро и без SMS». Скорее можно ожидать появления услуги по более полному восстановлению данных — в сравнении с тем, что предлагается сейчас.

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

Однако не надо забывать, что алгоритм выбора секторов, которые будут зашифрованы (а значит, нуждаются в расшифровании) тоже содержит ошибки (например, при разборе структур NTFS), и это может сказаться на результате.

Восстановление данных с жесткого диска по этой методике требует применения эвристик. Степень восстановления зависит от многих факторов (размера диска, степени его заполнения и фрагментации) и может достигать 100% для дисков большого объема, содержащих много «публичных» файлов (компонентов операционной системы и программных продуктов, одинаковых на многих машинах).

Повторим, что предложенный в статье метод, к сожалению, не позволит расшифровать файлы, которые были зашифрованы алгоритмом AES, используемым NotPetya, если он при запуске не смог получить административные привилегии.

Хочется выразить благодарность Александру Песляку (Solar Designer) за наводящие подсказки, позволившие придумать описанный выше метод.

Автор: Дмитрий Скляров, руководитель отдела анализа приложений Positive Technologies.

• Блог компании Positive Technologies
• Информационная безопасность

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

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

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

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

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

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

Базовые стратегии

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

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

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

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

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

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

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

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

К сожалению для криптоаналитиков, увеличение размера ключа хорошо защищает от брутфорса. По мере роста размера ключа количество возможных ключей увеличивается экспоненциально. С современными размерами ключей простой брутфорс совершенно не практичен. Чтобы понять, что мы имеем в виду, возьмём самый быстрый известный суперкомпьютер на середину 2019 года: Summit от IBM, с пиковой производительностью порядка 10 17 операций в секунду. Сегодня типичная длина ключа составляет 128 бит, что означает 2 128 возможных комбинаций. Для перебора всех ключей суперкомпьютеру 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 декабря мы заметили, что Боб что-то царапает в своём дневнике. Когда он закончит, мы незаметно возьмём его и посмотрим последнюю запись:

Сегодня был хороший день. Через 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 символов. Очевидно, что современная криптография требует работать с входными данными большего размера, и именно здесь появляются режимы шифрования. Режим шифрования — по сути хак: это способ каким-то образом применить блочный шифр, который принимает входные данные только определённого размера, к входным данным произвольной длины.

Атака Воденэ ориентирована на популярный режим работы CBC (Cipher Block Chaining, режим сцепления блоков шифротекста). Атака рассматривает базовый блочный шифр как волшебный неприступный чёрный ящик и полностью обходит его безопасность.

Вот диаграмма, которая показывает, как работает режим CBC:

Обведённый плюс означает операцию XOR (исключающее «ИЛИ»). Например, второй блок шифротекста получен:

1. Выполнением операции XOR на втором блоке открытого текста с первым блоком шифротекста.
2. Шифрованием полученного блока с помощью блочного шифра, используя ключ.

• Идемпотентность:
• Коммутативность:
• Ассоциативность:
• Самообратимость:
• Побайтовость: байт n из = (байт n из ) (байт n из )

Между нашим сценарием Алисы и атакой Воденэ есть два незначительных различия и одно главное отличие. Два незначительные:

• В сценарии Алиса ожидала, что открытые тексты заканчиваются символами a , bb , ccc и так далее. В атаке Воденэ жертва вместо этого ожидает, что открытые тексты заканчиваются N раз байтом N (то есть шестнадцатеричным 01 или 02 02, или 03 03 03 и так далее). Это чисто косметическое различие.
• В сценарии Алисы было легко сказать, приняла ли Алиса сообщение, по ответу «Неправильный фиктивный текст». В атаке Воденэ требуется больший анализ и важна точная реализация на стороне жертвы; но для краткости возьмём за данность, что этот анализ всё ещё возможен.

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

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

Учтите, что в сценарии Алисы у нас были следующие отношения:

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

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

Назовём это «уравнением CBC».

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

Предположим, мы действительно восстановили , что тогда? Ну, тогда мы можем сразу вывести весь последний блок открытого текста (), просто введя (который у нас есть) и
полученный в уравнение CBC.

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

Когда сервер принимает заполнение для одного из наших поддельных сообщений, это означает, что:

Теперь используем свойство побайтовости XOR:

Мы знаем первый и третий член. И мы уже видели, что это позволяет восстановить оставшийся член — последний байт из :

Это также даёт нам последний байт конечного блока открытого текста через уравнение CBC и свойство побайтовости.

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

Чтобы понять его, сначала обратите внимание, что в результате выведения правильного значения последнего байта у нас появилась новая способность. Теперь при подделке шифротекстов мы можем управлять последним байтом соответствующего открытого текста. Опять же, это связано с уравнением CBC и свойством побайтовости:

Поскольку мы теперь знаем второй член, то можем использовать наш контроль над первым для управления третьим. Мы просто вычисляем:

Раньше мы не могли этого сделать, потому что у нас ещё не было последнего байта .

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

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

Что насчёт остального текста? Обратите внимание, что значение на самом деле является . Мы можем поставить любой другой блок вместо , и атака всё равно будет успешной. Фактически, мы можем попросить сервер сделать для любых данных. В этот момент игра окончена — мы можем расшифровать любой шифротекст (ещё раз взгляните на диаграмму расшифровки CBC, чтобы убедиться в этом; и обратите внимание, что вектор IV общедоступен).

Этот конкретный метод играет решающую роль в атаке оракула, с которой мы столкнёмся позже.

Атака Келси

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

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

Чтобы увидеть принцип в действии, рассмотрим два открытых текста:

Открытый текст 1: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

Открытый текст 2: ATVXCAGTRSVPTVVULSJQHGEYCMQPCRQBGCYIXCFJGJ

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

Шифротекст 1: PVOVEYBPJDPVANEAWVGCIUWAABCIYIKOOURMYDTA

Шифротекст 2: DWKJZXYU

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

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

Опять же, как и в других атаках оракула, у нас есть соотношение:

Опять же, мы контролируем один член (), видим небольшую утечку информации о другом члене (шифротексте) и пытаемся восстановить последний (открытый текст). Несмотря на аналогию, это несколько необычная ситуация по сравнению с другими атаками оракула, которые мы видели.

Чтобы проиллюстрировать, как такая атака может работать, используем вымышленную схему сжатия, которую мы только что придумали: TOYZIP. Он ищет строки текста, которые уже появлялись ранее в тексте, и заменяет их тремя байтами-заполнителями, которые указывают, где найти более ранний экземпляр строки и сколько раз он там встречается. Например, строка helloworldhello может быть сжата в helloworld[00][00][05] длиной 13 байт по сравнению с оригиналом 15-ти байт.

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

Взломщик: Пожалуйста, сожми и зашифруй открытый текст без каких-либо заполнений.

Сервер: Длина результата 14.

Взломщик: Пожалуйста, сожми и зашифруйте открытый текст, к которому добавлено password=a .

Сервер: Длина результата 18.

Взломщик отмечает: [оригинал 14] + [три байта, которые заменили password= ] + a

Взломщик: Пожалуйста, сожми и зашифруй открытый текст, к которому добавлено password=b .

Сервер: Длина результата 18.

Взломщик: Пожалуйста, сожми и зашифруй открытый текст, к которому добавлено password=с .

Сервер: Длина результата 17.

Взломщик отмечает: [оригинал 14] + [три байта, которые заменили password=c ]. Это предполагает, что оригинальный открытый текст содержит строку password=c . То есть пароль начинается с буквы c

Взломщик: Пожалуйста, сожми и зашифруй открытый текст, к которому добавлено password=сa .

Сервер: Длина результата 18.

Взломщик отмечает: [оригинал 14] + [три байта, которые заменили password=с ] + a

Взломщик: Пожалуйста, сожми и зашифруй открытый текст, к которому добавлено password=сb .

Сервер: Длина результата 18.

(… некоторое время спустя…)

Взломщик: Пожалуйста, сожми и зашифруй открытый текст, к которому добавлено password=со .

Сервер: Длина результата 17.

Взломщик отмечает: [оригинал 14] + [три байта, которые заменили password=co ]. По той же логике взломщик делает вывод, что пароль начинается с букв co

И так далее до тех пор, пока не будет восстановлен весь пароль.

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

Брендовые уязвимости: CRIME, POODLE, DROWN

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

CRIME

Если атака нацелена на браузер и сеть жертвы, что-то будет проще, а что-то — сложнее. Например, увидеть трафик жертвы легко: достаточно сидеть с ней в одном и том же кафе с WiFi. По этой причине потенциальным жертвам (т. е. всем) обычно рекомендуется использовать зашифрованное соединение. Будет посложнее, но всё равно возможно, выполнение HTTP-запросов от имени жертвы на какой-то сторонний сайт (например, Google). Злоумышленник должен заманить жертву на вредоносную веб-страницу со скриптом, который сделает запрос. Веб-браузер автоматически предоставит соответствующую сеансовую куку.

Это кажется удивительным. Если Боб зашёл на evil.com , неужели скрипт на этом сайте может просто попросить Google отправить пароль Боба по электронной почте на attacker@evil.com ? Ну, в теории да, но на самом деле нет. Такой сценарий называется атакой на подделку межсайтовых запросов (Cross-Site Request Forgery, CSRF), и он был популярен примерно в середине 90-х. Сегодня, если evil.com попробует такой трюк, Google (или любой уважающий себя сайт) обычно ответит: «Отлично, но ваш токен CSRF для этой транзакции будет… ммм… три триллиона и семь . Пожалуйста, повторите это число». Современные браузеры применяют нечто под названием «политика одинакового происхождения» (same-origin policy), согласно которой скрипты на сайте A не получают доступа к информации, отправленной веб-сайтом B. Поэтому скрипт на evil.com может отправлять запросы к google.com , но не может прочитать ответы или на самом деле завершить транзакцию.

Мы должны подчеркнуть, что если Боб не использует зашифрованное соединение, все эти защиты бессмысленны. Взломщик может просто прочитать трафик Боба и восстановить сеансовую куку Google. С этой кукой он просто откроет новую вкладку Google, не выходя из собственного браузера, и выдаст себя за Боба, не встречаясь с досадными политиками same-origin policy. Но, к сожалению для взломщика, такое встречается всё реже. Интернет в целом давно объявил войну незашифрованным соединениям, и исходящий трафик Боба, вероятно, зашифрован, нравится ему это или нет. Кроме того, с самого начала внедрения протокола трафик также сжимался перед шифрованием; это была обычная практика для уменьшения задержки.

Здесь в игру вступает CRIME (Compression Ratio Infoleak Made Easy, простая утечка через коэффициент сжатия). Уязвимость, которую показали в сентябре 2012 года исследователи безопасности Джулиано Риццо (Juliano Rizzo) и Тай Дуонг (Thai Duong). Мы уже разобрали всю теоретическую базу, которая позволяет понять, что они сделали и как. Взломщик может заставить браузер Боба отправлять запросы в Google, а затем прослушивать ответы в локальной сети в сжатом, зашифрованном виде. Поэтому у нас есть:

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

Понимая теорию, авторы CRIME создали эксплоит, который может украсть сеансовые куки для широкого спектра сайтов, включая Gmail, Twitter, Dropbox и Github. Уязвимость затронула большинство современных веб-браузеров, в результате чего были выпущены патчи, которые молча похоронили функцию сжатия в SSL, чтобы она вообще не использовалась. Единственным защищённым от уязвимости стал почтенный Internet Explorer, который вообще никогда не использовал сжатие SSL.

POODLE

В октябре 2014 года команда безопасности Google навела шороху в сообществе безопасности. Они смогли эксплуатировать уязвимость в протоколе SSL, исправленную более десяти лет назад.

Оказалось, что хотя на серверах работает замечательный новенький TLSv1.2, многие оставили поддержку устаревшего SSLv3 ради обратной совместимости с Internet Explorer 6. Мы уже говорили об атаках на понижение, так что можете представить себе происходящее. Хорошо организованный саботаж протокола рукопожатия — и серверы готовы вернуться на старый добрый SSLv3, по сути отменив последние 15 лет исследований в сфере безопасности.

Transport Layer Security (TLS) — самый важный протокол безопасности в интернете. [..] почти каждая транзакция, которую вы проводите в интернете, зависит от TLS. [..] Но TLS не всегда был TLS. Протокол начал свою жизнь в Netscape Communications под названием «Secure Sockets Layer» или SSL. Ходят слухи, что первая версия SSL оказалась настолько ужасной, что разработчики собрали все распечатки кода и закопали на секретной свалке в Нью-Мексико. Как следствие, первая общедоступная версия SSL на самом деле является версией SSL 2. Она довольно страшненькая, и [..] это был продукт середины 90-х, которые современные криптографы рассматривают как «тёмные века криптографии». Многие из самых отвратительных криптографических атак, о которых мы знаем сегодня, ещё не были обнаружены. В результате разработчикам протокола SSLv2 пришлось по существу нащупывать путь в темноте, и они столкнулись с множеством ужасных монстров — к их огорчению и нашей выгоде, поскольку атаки на SSLv2 оставили бесценные уроки для следующего поколения протоколов.

После этих событий, в 1996 году, разочарованная компания Netscape переработала протокол SSL с нуля. Результатом стал SSL версии 3, который исправил несколько известных проблем безопасности своего предшественника.

К счастью для взломщиков, «несколько» не означает «все». В целом, SSLv3 предоставлял все необходимые строительные блоки для запуска атаки Воденэ. Протокол использовал блочный шифр в режиме CBC и небезопасную схему заполнения (это исправили в TLS; следовательно, возникла необходимость в атаке на понижение). Если вы помните схему заполнения в нашем первоначальном описании атаки Воденэ, схема SSLv3 очень похожа.

Но, к несчастью для взломщиков, «похожая» не означает «идентичная». Схема заполнения SSLv3 имеет вид «N произвольных байт, за которыми следует число N». Попробуйте в таких условиях выбрать воображаемый блок зашифрованного текста и пройти через все этапы оригинальной схемы Воденэ: вы обнаружите, что атака успешно извлекает последний байт из соответствующего блока открытого текста, но дальше не проходит. Расшифровка каждого 16-го байта зашифрованного текста — отличный фокус, но это не победа.

Столкнувшись с неудачей, команда Google прибегла к крайнему варианту: они переключились на более мощную модель угроз — ту, которая использовалась в CRIME. Если предположить, что злоумышленник — это скрипт, запущенный на вкладке браузера жертвы, и он может извлечь сеансовые куки, атака всё равно остаётся впечатляющей. Хотя более широкая модель угроз менее реалистична, но в предыдущем разделе мы уже видели, что эта конкретная модель осуществима.

Учитывая такие более мощные возможности взломщика, теперь атака может продолжиться. Учтите, что злоумышленник знает, где в заголовке отображается зашифрованный сеансовый файл куки, и управляет длиной предшествующего ему HTTP-запроса. Поэтому он способен манипулировать HTTP-запросом так, чтобы выровнять последний байт куки в соответствии с концом блока. Теперь этот байт подходит для расшифровки. Можно просто добавить к запросу один символ, а предпоследний байт куки останется на том же месте и пригоден для подбора тем же методом. Атака продолжается таким образом, пока файл куки не будет восстановлен полностью. Это называется POODLE: Padding Oracle on Downgraded Legacy Encryption, заполняющий оракул на пониженном устаревшем шифровании.

DROWN

Как мы уже упоминали, у SSLv3 были недостатки, но он кардинально отличался от предшественника, поскольку дырявый SSLv2 представлял собой продукт другой эпохи. Там можно было прервать сообщение на середине: соглашусь на это только через мой труп превращалось в соглашусь на это ; клиент и сервер могли встретиться в интернете, установить доверие и обменяться секретами перед глазами злоумышленника, который потом легко выдавал себя и за того, и за другого. Ещё и проблема с экспортной криптографией, которую мы упомянули при рассмотрении FREAK. Это были криптографические Содом и Гоморра.

В марте 2016 года команда исследователей из разных технических областей собралась вместе и сделала поразительное открытие: SSLv2 по-прежнему используется в системах безопасности. Да, злоумышленники больше не могли понижать современные сеансы TLS до SSLv2, поскольку эту дыру закрыли после FREAK и POODLE, но они всё ещё могут подключаться к серверам и инициировать сеансы SSLv2 самостоятельно.

Вы спросите, какое нам дело, что они там делают? У них уязвимый сеанс, но это не должно влиять на другие сеансы или безопасность сервера — правильно? Ну, не совсем. Да, так и должно быть в теории. Но нет — потому что генерация сертификатов SSL накладывает определённое бремя, в результате чего многие серверы используют одни и те же сертификаты и, как следствие, одни и те же ключи RSA для соединений TLS и SSLv2. Что ещё хуже, из-за бага OpenSSL в этой популярной реализации SSL фактически не работала опция «Отключить SSLv2».

Это сделало возможной кросс-протокольную атаку на TLS, которую назвали DROWN (Decrypting RSA with Obsolete and Weakened eNcryption, расшифровка RSA с помощью устаревшего и ослабленного шифрования). Напомним, что это не то же самое, что атака на понижение; взломщику не нужно действовать как «человек в середине» и не нужно вовлекать клиента для участия в небезопасном сеансе. Злоумышленники просто сами инициируют небезопасный сеанс SSLv2 с сервером, атакуют слабый протокол и восстанавливают закрытый серверный ключ RSA. Этот ключ также действителен для соединений TLS, и с этого момента никакая безопасность TLS не спасёт его от взлома.

Но для взлома нужна рабочая атака против SSLv2, которая позволяет восстановить не только конкретный трафик, но и секретный серверный ключ RSA. Хотя это и сложная постановка, но исследователи могли выбрать любую уязвимость, которую полностью закрыли после SSLv2. В конечном итоге они нашли подходящий вариант: атака Блайхенбахера, о которой мы упоминали ранее и которую подробно объясним в следующей статье. SSL и TLS защищены от этой атаки, но некоторые случайные функции SSL в сочетании с короткими ключами в криптографии экспортного класса, сделали возможным определённую реализацию DROWN.

На момент публикации уязвимости DROWN были подвержены 25% топ-сайтов интернета, и атаку можно было провести со скромными ресурсами, доступными даже для озорных хакеров-одиночек. Для извлечения ключа RSA сервера требовалось восемь часов вычислений и $440, а SSLv2 сменил статус с «устаревшего» на «радиоактивный».

Погодите, а что насчёт Heartbleed?

Это не криптографическая атака в том смысле, как описанные выше; это переполнение буфера.

Cделаем перерыв

Мы начали с некоторых базовых методов: брутфорс, интерполяция, понижение, кросс-протокол и предвычисления. Затем рассмотрели одну продвинутую технику, возможно, главный компонент современных криптографических атак: это атака оракула. Мы довольно долго с ней разбирались — и поняли не только принцип в основе, но и технические детали двух конкретных реализаций: атаки Воденэ на режим шифрования CBC и атаки Келси на протоколы шифрования с предварительным сжатием.

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

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

Затем мы обратили внимание на кросс-протокольную атаку DROWN, которая устанавливает с сервером соединение по устаревшему протоколу SSLv2, а потом восстанавливает секретные серверные ключи с помощью атаки Блайхенбахера. На данный момент мы пропустили технические детали этой атаки; как и Logjam, ей придётся подождать, пока мы хорошенько не изучим криптосистемы с открытым ключом и их уязвимости.

В следующей статье поговорим о продвинутых атаках — таких как метод встречи посередине (meet-in-the-middle), дифференциальный криптоанализ и атака «дней рождения». Совершим короткий набег на атаки по сторонним каналам, а затем примемся за самую вкуснятину — криптосистемы с открытым ключом.

• Информационная безопасность
• Криптография
• Алгоритмы
• Серверное администрирование
• Тестирование веб-сервисов

Исследование учащихся Загадочные письма

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

Гипотеза

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

План проведения исследования

1. Подобрать необходимую информацию.

2. Изучить историю развития криптографии.

3. Изучить принципы шифрования и дешифрования информации.

4. Зашифровать исходное сообщения различными методами.

5. Сделать вывод.

Исследование

Введение

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

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

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

Криптография (от греч. κρυπτός — скрытый и γράφω — пишу) — наука о методах обеспечения конфиденциальности (невозможности прочтения информации посторонним) и аутентичности (целостности и подлинности авторства, а также невозможности отказа от авторства) информации.

Шифрование — это способ изменения сообщения или другого документа, обеспечивающее искажение (сокрытие) его содержимого. (Кодирование – это преобразование обычного, понятного, текста в код. При этом подразумевается, что существует взаимно однозначное соответствие между символами текста(данных, чисел, слов) и символьного кода – в этом принципиальное отличие кодирования от шифрования. Часто кодирование и шифрование считают одним и тем же, забывая о том, что для восстановления закодированного сообщения, достаточно знать правило подстановки(замены). Для восстановления же зашифрованного сообщения помимо знания правил шифрования, требуется и ключ к шифру.Знание ключа дает возможность прочтения секретного сообщения.

Идея шифрования состоит в предотвращении просмотра истинного содержания сообщения(текста, файла и т.п.) теми , у кого нет средств его дешифрования. А прочесть файл сможет лишь тот, кто сможет его дешифровать.

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

Итак, криптография дает возможность преобразовать информацию таким образом, что ее прочтение (восстановление) возможно только при знании ключа. Перечислю вначале некоторые основные понятия и определения.

Основные понятия и определения

Алфавит — конечное множество используемых для кодирования информации знаков.

Текст — упорядоченный набор из элементов алфавита.

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

Дешифрование — обратный шифрованию процесс. На основе ключа шифрованный текст преобразуется в исходный.

Ключ — информация, необходимая для беспрепятственного шифрования и дешифрования текстов.

Криптографическая система представляет собой семейство T преобразований открытого текста. xлены этого семейства индексируются, или обозначаются символом k; параметр k является ключом. Пространство ключей K — это набор возможных значений ключа. Обычно ключ представляет собой последовательный ряд букв алфавита.

Криптосистемы разделяются на симметричные и с открытым ключом ( или асимметричесские) .

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

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

Существует множество (не менее двух десятков) алгоритмов симметричных шифров, существенными параметрами которых являются:

длина обрабатываемого блока;

сложность аппаратной/программной реализации;

Симметричные системы шифрования

Рассмотрим симметричные системы шифрования использующие алгоритм замены (подстановки.)

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

Зашифруем сообщение «Это мой первый проект» с использованием ключа k = 3. Буква «Э» «сдвигается» на три буквы вперед и становится буквой «А». Буква «т», перемещённая на три буквы вперед, становится буквой «х», и так далее.

Шифрованный текст: Ахс рсм тзуеюм тусзнх

Вывод: С точки зрения современного криптоанализа, шифр Цезаря не имеет приемлемой стойкости.

Спустя 500 лет шифрование стало повсеместно использоваться при оставлении текстов религиозного содержания, молитв и важных государственных документов.

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

Естественным развитием шифра Цезаря стал шифр Виженера.

Шифр Виженера — метод полиалфавитного шифрования буквенного текста с использованием ключевого слова. Этот метод является простой формой многоалфавитной замены. Шифр Виженера изобретался многократно. Впервые этот метод описал Джован Баттиста Беллазо в книге La cifra del. Sig. Giovan Battista Bellasо в 1553 году, однако в XIX веке получил имя Блеза Виженера, швейцарского дипломата. Метод прост для понимания и реализации, он является недоступным для простых методов криптоанализа.

В шифре Цезаря каждая буква алфавита сдвигается на несколько строк; например в шифре Цезаря при сдвиге +3, А стало бы Г, Б стало бы Д и так далее. Шифр Виженера состоит из последовательности нескольких шифров Цезаря с различными значениями сдвига. Для зашифровывания может использоваться таблица алфавитов, называемая tabula recta или квадрат (таблица) Виженера. Применительно к кириллическому алфавиту таблица Виженера составляется из строк по 33 символа, причём каждая следующая строка сдвигается на несколько позиций. Таким образом, в таблице получается 33 различных шифров Цезаря. На разных этапах кодировки шифр Виженера использует различные алфавиты из этой таблицы. На каждом этапе шифрования используются различные алфавиты, выбираемые в зависимости от символа ключевого слова.

Зашифруем сообщение «Это мой первый проект» методом Виженера. Человек, посылающий сообщение, записывает ключевое слово («модуль») циклически до тех пор, пока его длина не будет соответствовать длине исходного текста:

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

Исходный текст: Это мой первый проект

Ключ: Мод уль модуль модуль

Шифрованный текст: Йбт аэё ьуфхжё ьятшцо

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

Вывод: Шифр Виженера «размывает» характеристики частот появления символов в тексте, но некоторые особенности появления символов в тексте остаются. Главный недостаток шифра Виженера состоит в том, что его ключ повторяется.

• скорость;
• простота реализации (за счёт более простых операций);
• меньшая требуемая длина ключа для сопоставимой стойкости;
• изученность (за счёт большего возраста).

• сложность управления ключами в большой сети;
• сложность обмена ключами.

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

Системы с открытым ключом (ассиметричные системы)

Рассмотрим алгорит RSA криптографической системы с открытым ключом. В данной системе используются два ключа — открытый и закрытый, которые математически связаны друг с другом.

Алгоритм RSA (по первым буквам фамилий его создателей Rivest-Shamir-Adleman) основан на свойствах простых чисел (причем очень больших).

В 1993 году алгоритм RSA был принят в качестве стандарта.

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

Простыми называются такие числа, которые не имеют делителей, кроме самих себя и единицы. А взаимно простыми называются числа, не имеющие общих делителей, кроме 1.

Для начала выберем два очень больших простых числа (большие исходные числа нужны для построения больших криптостойких ключей. Определим параметр n как результат перемножения р и q. Выберем большое случайное число и назовем его d, причем оно должно быть взаимно простым с результатом умножения (р -1)*(q -1). Отыщем такое число e, для которого верно соотношение

(e*d) mod ((р -1) *(q -1)) = 1

(mod — остаток от деления, т. е. если e, умноженное на d, поделить на ((р -1) *(q -1)), то в остатке получим 1).

Открытым ключом является пара чисел e и n, а закрытым — d и n. При шифровании исходный текст рассматривается как числовой ряд, и над каждым его числом мы совершаем операцию

В результате получается последовательность C(i), которая и составит криптотекст. Декодирование информации происходит по формуле

M(i) = ( C(i)d ) mod n.

Как видите, расшифровка предполагает знание секретного ключа.

Давайте попробуем на маленьких числах. Установим р=5, q=7. Тогда n=р*q=85. Выбираем d как 13. Найдем (p-1)*(q-1)=4*16=64. Из формулы (e*13) mod 64=1 вычисляем e=5. Открытый ключ (5,85) секретный — (13,85).

Зашифруем наше сообщение «Это мой первый проект»:

Для этого переведем наше сообщения в цифровой вид по таблице кириллического алфавита.

(31, 20, 16, 14, 16, 11, 17, 6, 18, 3, 29, 11, 17, 18, 16, 6, 12, 20)

C(1)= 31^5 mod 85 = 46

C(2)= 20^5 mod 85 = 5

C(3)= 16^5 mod 85 = 16

C(4)= 14^5 mod 85 = 29

C(5)= 16^5 mod 85 = 16

C(6)= 11^5 mod 85 = 61

C(7)= 17^5 mod 85 = 17

C(8)= 6^5 mod 85 = 41

C(9)= 18^5 mod 85 = 18

C(10)= 3^5 mod 85 = 73

C(11)= 29^5 mod 85 = 54

C(12)= 11^5 mod 85 = 61

C(13)= 17^5 mod 85 = 17

C(14)= 18^5 mod 85 = 18

C(15)= 16^5 mod 85 = 16

C(16)= 6^5 mod 85 = 41

C(17)= 12^5 mod 85 = 37

C(18)= 20^5 mod 85 = 5

Криптотекст — (46, 5, 16, 29, 16, 61, 17, 41, 18, 73, 54, 61, 17, 18, 16, 41, 37, 5)

Проверим расшифровкой:

M(1)= 46^13 mod 85 = 31

M(2)= 5^13 mod 85 = 20

M(3)= 16^13 mod 85 = 16

M(4)= 29^13 mod 85 = 14

M(5)= 16^13 mod 85 = 16

M(6)= 61^13 mod 85 = 11

M(7)= 17^13 mod 85 = 17

M(8)= 41^13 mod 85 = 6

M(9)= 18^13 mod 85 = 18

M(10)= 73^13 mod 85 = 3

M(11)= 54^13 mod 85 = 29

M(12)= 61^13 mod 85 = 11

M(13)= 17^13 mod 85 = 17

M(14)= 18^13 mod 85 = 18

M(15)= 16^13 mod 85 = 16

M(16)= 41^13 mod 85 = 6

M(17)= 37^13 mod 85 = 12

M(18)= 5^13 mod 85 = 20

(31, 20, 16, 14, 16, 11, 17, 6, 18, 3, 29, 11, 17, 18, 16, 6, 12, 20)

Для этого переведем наше цифровое сообщения в буквенный вид по таблице кириллического алфавита.

Полученное сообщение: «Это мой первый проект».

Как видим, результат совпал.

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

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

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

Асимметричный шифр — система шифрования и/или электронной цифровой подписи (ЭЦП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу, и используется для проверки ЭЦП и для шифрования сообщения. Для генерации ЭЦП и для расшифрования сообщения используется секретный ключ. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), в SSH. Также используется в PGP, S/MIME.

Вывод

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

Наиболее простой критерий такой эффективности — вероятность раскрытия ключа или мощность множества ключей (М). По сути это то же самое, что и криптостойкость. Для ее численной оценки можно использовать также и сложность раскрытия шифра путем перебора всех ключей.

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

Ресурсы

• Криптография

• Шифр Цезаря

• Шифр Виженера

• Симметричные криптосистемы

• Криптосистема с открытым ключом

• Алгоритм RSA