BaikalCTF{M0r!turi_t3_$aLut@nt}

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

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

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

Исторически раньше появились симметричные шифры — фактически, к ним можно отнести и все исторические шифры, которые мы рассматривали ранее. Ключ в таком виде шифрования должен сохраняться в секрете обеими сторонами и передаваться в защищённом виде (например, при личной встрече).

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

Поточные шифры

В целом в криптографии, и в частности при реализации поточных шифров, часто применяется простая логическая операция XOR (англ. exclusive or — исключающее или). Эта операция обозначается символом ^ или ⊕. Мы будем чаще использовать второе обозначение, чтобы избегать путаницы с возведением в степень. XOR двух логических значений (битов) возвращает 0, если они равны, и 1, если различны.

Аналогично XOR работает и с числами: побитовая операция выполняется для каждой пары битов. Например, 53 ⊕ 26 = 110101₂ ⊕ 011010₂ = 101111₂ = 47. Важным свойством этой операции является то, что A ⊕ B ⊕ B = A. Например, 47 ⊕ 26 = 53. Проверьте это свойство для других чисел.

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

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

Безопасность

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

Если длина ключа не превышает 2, такие сообщения можно взламывать с помощью Кибершефа.

Предположим, что наш ключ состоит всего из одного байта. Тогда для шифротекста возможных вариантов исходного текста всего 256. Это больше, чем 26 вариантов в шифре Цезаря, но их всё равно можно перебрать и найти нужный. Таким образом, одного байта недостаточно.

Если увеличить длину ключа до четырёх байт, то вариантов станет уже 4 294 967 296 (2³²). На первый взгляд, это очень много. Но на самом деле безопаснее от этого шифр не станет, поскольку все ключи перебирать не обязательно: можно отсечь большую часть ключей, основываясь на предположениях об исходном файле. Можно догадаться, какие байты встречаются чаще всего, рассмотреть закономерности языка (например, частоты различных букв) для текстовых файлов и так далее. Делать вручную это достаточно сложно и, как правило, не нужно, поскольку существуют специальные утилиты. Одна из них — xortool.

В бинарных файлах чаще всего встречается нулевой байт, в текстовых — пробел.

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

Чтобы получить возможную длину ключа, запустим утилиту, передав ей файл единственным аргументом:

Редко длина ключа определяется однозначно, показываются наиболее вероятные варианты.

В нашем случае все возможные длины имеют вид 7n, поэтому есть смысл начать проверку с 7. Чтобы выяснить ключ, утилите недостаточно длины — ей нужен ещё и самый частоиспользуемый символ. Наш файл текстовый, попробуем пробел:

Нашёлся всего один ключ.

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

Абсолютно стойкое шифрование

А что если пойти дальше и увеличить ключ ещё больше? XOR-шифрование было придумано Гильбертом Вернамом в 1917 году. Он хранил ключи на бумажных лентах. При этом ленты были одноразовыми и уничтожались сразу после использования. Размер же таких лент совпадал с размером передаваемого сообщения.

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

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

Такое часто бывает и в CTF-соревнованиях.

Предположим, что мы использовали один и тот же ключ K для шифрования двух разных текстов A и B. Злоумышленнику попали зашифрованные тексты X = A ⊕ K и Y = B ⊕ K. Если он посчитает X ⊕ Y, то получит A ⊕ K ⊕ B ⊕ K. Но K ⊕ K = 0, а значит, X ⊕ Y = A ⊕ B. Таким образом, ключ K больше не используется, а исходные тексты можно восстановить частично или полностью уже знакомым нам частотным анализом.

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

Блочные шифры

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

Метод, при котором перебираются все возможные ключи, называется брутфорс (англ. bruteforce — грубая сила).

Первым стандартом блочного шифрования был алгоритм DES (англ. Data Encryption Standard — стандарт шифрования данных). Он был разработан компанией IBM в 1977 году. В своё время DES стал стандартом криптографии и широко использовался коммерческими компаниями. Главная проблема этого шифра в том, что размер ключа составляет всего 56 бит (7 байт), и к 1990 году развитие скорости техники привело к тому, что за относительно недолгое время стало возможно перебирать все варианты ключей. Тогда эта процедура занимала 39 дней, в 1998 году суперкомпьютер мог это делать за 3 дня, а сегодня для взлома DES достаточно пары часов работы обычного ноутбука. Однако более удивительно то, что за 40 лет исследователи не нашли других способов взлома, не требующих полного перебора ключей.

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

На смену DES в 1998 году пришёл AES (англ. Advanced Encryption Standard — продвинутый стандарт шифрования), ещё известный как Rijndael (голл. Рейндал). Он использует блоки длиной 128 бит и ключи длиной 128, 192 или 256 бит. Соответствующие варианты носят названия AES-128, AES-192 и AES-256. Этот шифр широко применяется и сегодня, при этом даже 128-битный ключ считается безопасным для использования. У AES существует несколько вариантов схемы шифрования (они называются режимами).

Выводы

1. Симметричные шифры бывают блочными и поточными.

2. XOR — простая логическая операция, на которой можно построить криптосистему. Однако если использовать короткие ключи, то она легко взламывается.

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

4. Сейчас широко применяется блочный шифр AES. Он достаточно надёжен даже при длине ключа в 128 бит.

Задачка:

1. Мы нашли пергамент с таким сообщением: pbmv_fijr_tjpm_cdnojmt_211z20111z.

2. — Николай, вот ваш флаг
— Оленька, у вас такой прекрасный флаг. Почему вы не шифруете?
— А что шифровать-то?
— Да например: 890926842300243943602406417785511809905044440005245593990055166711260178385314658616