В преддверии скорого очного тура NeoQUEST-2015 продолжаем разбирать задания online-этапа. В статье разбирается задание «Абракадабра», состоящее из двух частей. Обе части — на криптоанализ: первая — на частотный, вторая — на дифференциальный.

Участникам были даны два файла. Первый файл имел формат .docx, на его первой странице была та самая «абракадабра» — текст, состоящий сплошь из непонятных закорючек и символов, а на второй странице – не вполне понятный список. Глядя на него, одно можно было сказать точно: здесь описан некий алгоритм шифрования.

Второй файл был формата .txt, в нем содержались 2 столбца, озаглавленные как plaintext и cyphertext. Со всем этим надо было что-то делать…

Непонятный текст:

Ощыс щонныяыфЕoцътфюую pяокьюцфцъoхц дцхоягыьчc фц быяюсьфючьфлё юьфюиыфocё эывщг бёющфлэо яцхфючьсэo о яцхфючьcэo блёющц. Щбц юьфюиыфос кяыщчьцбъcпь рюфpяыьфлм oфьыяыч б цфцъохыМ щoнныяыфЕоцътфлм кяюнцмъ o ёцяцрьыяочьopц яцгфщц. ЩонныяыфЕoцътфлм кяюнцмъ кюрцхлбцыь быяюсьфючьфюы юьфюиыфоы эывщг бёющфлэo яцхфючьcэо o яцхфючьсэо блёющц дъюpц. Кющюдфлы кяюнцмъл эюугь дльт чюхщцфл щъc рцвщюую oх бючтэо дъюpюб б DЫS. Ёцяцрьыяoчьоpц яцгфщц кющюдфц щoнныяыфЕоцътфюэг кяюнцмъг, фю блжoчъсыьчc щъс Еыъюую яцгфщц. Юфц кюрцхлбцыь быяюcьфючьт, ч pюьюяюм ющфц бёющфцс яцхфючьт чюхщцъц дл яцхфючьт юкяыщыъaффюую блёющц. Юдяцьоьы бфoэцфоы, жью ёцяцрьыяoчьоpц ющфц o ьц вы щъc рцвщюую яцгфщц, кюьюэг жью ъпдюы юьфюиыфоы, pюьюяюы бръпжцыь яцхфючьo, фы хцбочoь юь pъпжым яцгфщц. Очкюътхгм щонныяыфЕoцътфлм ряокьюцфцъoх щъс кяюёювщыфоc бьюяюм жцчьo хцщцфос, oъо вы oщо фцкяюъюэ. Ц pъпж р йьюм жцчьo хцщцфоc М жцчьюьфлмцфцъoх.

Список:

1. Substitution (15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10)
2. Permutation P(i) = 9*i + 4 (mod 32)
3. 3 цикла: 2 цикла с [XOR with key + Substitution + Permutation], последний [XOR with key + Substitution + XOR with key]
4. Вход: S-box №1 (10; 1), второй: S-box №3 (8; 6).

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

«Абракадабра» №1

Разбор первой части задания, с непонятным текстом, следовало начинать с определения кодировки, с этим успешно справлялись многие онлайн-декодеры (в частности, этот).



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

Результат частотного анализа введенного текста
Проведен анализ текста
Количество символов в тексте 910
Количество пробелов 114
Количество цифр 0
Количество точек и запятых 16
Количество английских букв 53
Количество русских букв 715

Посимвольная статистика и частотный анализ
Символ встречается 114 раз. Частота 12.53%
Символ ю встречается 86 раз. Частота 9.45%
Символ ц встречается 80 раз. Частота 8.79%
Символ ф встречается 63 раз. Частота 6.92%
Символ ь встречается 52 раз. Частота 5.71%
Символ ы встречается 50 раз. Частота 5.49%
Символ я встречается 43 раз. Частота 4.73%
Символ щ встречается 38 раз. Частота 4.18%
Символ ъ встречается 31 раз. Частота 3.41%
Символ о встречается 30 раз. Частота 3.30%
Символ o встречается 28 раз. Частота 3.08%
Символ ч встречается 27 раз. Частота 2.97%
Символ б встречается 22 раз. Частота 2.42%
Символ х встречается 21 раз. Частота 2.31%
Символ л встречается 19 раз. Частота 2.09%
Символ к встречается 16 раз. Частота 1.76%
Символ м встречается 16 раз. Частота 1.76%
Символ э встречается 14 раз. Частота 1.54%
Символ н встречается 14 раз. Частота 1.54%
Символ г встречается 13 раз. Частота 1.43%
Символ ё встречается 12 раз. Частота 1.32%
Символ с встречается 11 раз. Частота 1.21%
Символ р встречается 11 раз. Частота 1.21%
Символ c встречается 11 раз. Частота 1.21%
Символ т встречается 11 раз. Частота 1.21%
Символ p встречается 11 раз. Частота 1.21%
Символ. встречается 9 раз. Частота 0.99%
Символ ж встречается 9 раз. Частота 0.99%
Символ д встречается 9 раз. Частота 0.99%
Символ в встречается 7 раз. Частота 0.77%
Символ, встречается 7 раз. Частота 0.77%
Символ е встречается 6 раз. Частота 0.66%
Символ у встречается 6 раз. Частота 0.66%
Символ п встречается 5 раз. Частота 0.55%
Символ и встречается 4 раз. Частота 0.44%
Символ й встречается 1 раз. Частота 0.11%
Символ a встречается 1 раз. Частота 0.11%
Символ d встречается 1 раз. Частота 0.11%
Символ s встречается 1 раз. Частота 0.11%

Из результатов анализа видно, что в тексте не две английские буквы (обратите внимание на загадочное DЫS, которое может быть DES, DOS, DNS и так далее), а целых 53! Можно было потрудиться и написать программку, перебирающую буквы, которые одинаково выглядят как в русском, так и в английском варианте (например, очевидные o, e, p), а можно было погуглить и найти программку , которая подсветит английские буквы:



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

щонныяыфЕoцътфюую
щoнныяыфЕоцътфлм
щoнныяыфЕоцътфюэг

Логично предположить, что наиболее краткая форма слова из этих трех – это именительный падеж, слово из 16 букв, в котором буквы 3 и 4 – одинаковые. Всего слов из 16 букв, если верить словарю, не так-то много: 759. А таких, чтобы третья и четвертые буквы совпадали, тем более. Можно было реализовать программку, подбирающую слова, подходящие по маске к зашифрованному, а можно было просто проверить слова из 16 букв с удвоенными на 3 и 4 позициях. Даже если проверять вручную, выбор невелик:

беззастенчивость
баллотировальник
гелленологофобия
коллаборационизм
коллаборационист
коллекционерство
целлофанирование
коммерциализация
пессимистичность
рассудительность
дифференцировать

Но буквы на позициях 2 и 10 также должны совпадать! По такому параметру подходит только слово «дифференцировать», и если попробовать осуществить такую замену символов, текст станет уже более читаемым, хоть и не до конца, откуда становится понятно, что искомое слово – не «дифференцировать», а «дифференциальный». Связав со второй частью задания, DЫS превращается в DES, еще немного упрощая задачу, а конечный вариант текста выглядит так:

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

Вот мы и получили ключ к первой части задания, однако если вводить «частотныйанализ» в поле ввода, выскакивает сообщение о том, что ключ неверен. Что делать? Все просто: от этой фразы нужно было взять MD5-хеш. Profit! Кстати, writeup по этому заданию уже опубликовал один из наших участников здесь, пройдя его немного по-другому, но, тем не менее, добившись успеха!

«Абракадабра» №2

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

• реализовать дифференциальный криптоанализ;
• забрутфорсить ключ, используя пары открытый-закрытый текст.

Большинство участников выбрали второй способ прохождения (и их можно понять, ведь реализовать криптоанализ все же трудозатратнее), поэтому этот способ мы разберем подробнее.

Дифференциальный криптоанализ

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

1. Разобраться в том, что такое дифференциал цикла шифрования.
2. Изучить понятие дифференциальной характеристики.
3. Понять, как работают подстановка и перестановка.

Дифференциал i-го цикла шифрования – это пара векторов a и b, такая, что пара открытых текстов (x₁ и x₂) с разностью a может перейти после i-го цикла в пару выходных текстов (y₁ и y₂) с разностью b. Дифференциальная характеристика представляет собой последовательность одноцикловых дифференциалов, при этом выходная разность текстов для предыдущего цикла совпадает с входной разностью текстов последующего цикла.

Блочный шифр имеет длину блока и ключа по 32 бита (об этом можно догадаться, посмотрев на условие 2 в списке). Зашифрование, как уже было указано в списке документа .docx, выполняется на 3 циклах, каждый из которых содержит XOR с ключом, замену 4-битовых слов (подстановка, Substitution), и два цикла содержат перестановку (Permutation). При выполнении перестановки бит с позиции i перемещается на позицию 9*i + 4 (mod 32).

К слову, перестановка вызвала значительные затруднения у участников из-за своей нетривиальности: на входе нумерация битов идет от 1 до 32, а на выходе — от 0 до 31 (пример: Permutation(0x12345678)=0хB3E29180). Однако после публикации подсказки в Twitter, участники стали активно проходить задание!

Общий алгоритм прохождения задания методом дифференциального криптоанализа:

1. Используя пару открытых текстов, смотрим разность для этой пары на выходе 2 цикла
2. Используя пару выходных шифртекстов после 3 цикла, выполняем их обратные преобразования, вычисляя обратную подстановку и делая XOR с ключом.
3. Вычисляем разность для преобразованных шифртекстов.
4. Сравниваем разности для преобразованных шифртекстов и для пары открытых текстов.
5. Ищем совпадающие биты, если они есть, увеличиваем счетчик числа совпадений.
6. Перебрав все кусочки ключа (2 по 4 бита, итого — 8 битов), смотрим, для какого (или для каких) наибольшее количество совпадений. Это и будет искомой частью ключа.
7. Повторяем, выбирая другие активные блоки и строим новую характеристику, для определения уже другой части ключа. Делаем, пока либо все 32 бита не будут вскрыты, либо пока не будет вскрыта большая часть ключа — остальное можно забрутить.

Брутфорс

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

using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

namespace ConsoleApplication2
{
    static class Program
    {
        static long progress = 0;
        static long prev_progress = 0;
        static DateTime prev_date;
        static bool complete = false;

        static byte reverse_bits( this byte b)
        {
            byte r = 0;
            for (int i = 0; i < 8; i++)
            {
                byte mask = (byte)(1 << i);
                byte mask_neg = (byte)(1 << (7 - i));
                if ((b & mask) == mask)
                {
                    r |= mask_neg;
                }
            }
            return r;
        }


        static byte[] reverse_bits(this byte[] array)
        {
            byte[] r = new byte[array.Length];
            for (int i = 0; i < array.Length; i++)
            {
                r[i] = array[i].reverse_bits();
            }
            return r;
        }

        static void Main(string[] args)
        {
            DateTime start_date = DateTime.Now;
            progress = 0;
            prev_progress = 0;
            prev_date = DateTime.Now;
            Thread monitor = new Thread(a => 
            {
                while (progress != 0xFFFFFFFF && complete == false)
                {
                    Thread.Sleep(5000);
                    long long_percent = ((progress * 100 * 1000) / 0xFFFFFFFF);
                    long sec = (long)(DateTime.Now - prev_date).TotalSeconds;
                    long speed = (long)((progress - prev_progress) / sec);
                    Console.WriteLine("{0}.{1}% ... speed={2} left={3}", long_percent / 1000, long_percent % 1000,
                        speed,
                        0x100000000 - progress);
                    prev_date = DateTime.Now;
                    prev_progress = progress;
                }
            });
            monitor.Start(0);
            Parallel.For(0x00000000, 0xFFFFFFFF, i =>
            {
                byte[] text = BitConverter.GetBytes((UInt32)0x5ABF054B);
                Array.Reverse(text);
                
                byte[] key = BitConverter.GetBytes((UInt32)i);
                Array.Reverse(key);

                Crypt(ref text, key);
                Array.Reverse(text);
                if (BitConverter.ToUInt32(text, 0) == (UInt32)0x4CD3CA17)
                {
                    complete = true;
                    Console.WriteLine("KEY {0}", i.ToString("X"));
                    File.WriteAllText(i.ToString("X") + ".txt", i.ToString());
                    Console.WriteLine("Complete! time = " + (DateTime.Now - start_date).ToString());
                    Console.ReadKey();
                }
                Interlocked.Increment(ref progress);
            }
            );
            
            Console.WriteLine("Complete! time = " + (DateTime.Now - start_date).ToString());
            Console.ReadKey();
        
      }

        static int[] substitution_table = { 15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10};

        static void Crypt(ref byte[] text, byte[] key)
        {
            Xor(ref text, key);
            Substitution(ref text);
            Permutation(ref text);
            Xor(ref text, key);
            Substitution(ref text);
            Permutation(ref text);
            Xor(ref text, key);
            Substitution(ref text);
            Xor(ref text, key);
        }

        static void Substitution(ref byte[] text)
        {
            for (int i = 0; i < 8; i += 2)
            {
                int h = (text[i / 2] >> 4) & 0xF;
                int l = (text[i / 2] >> 0) & 0xF;

                h = substitution_table[h];
                l = substitution_table[l];
                text[i / 2] = (byte)((h << 4) | l);
            }
        }


        static void Permutation(ref byte[] text)
        {
            BitArray bits = new BitArray(text.reverse_bits());
            text = new byte[text.Length];
            for (int i = 0; i < 32; i++)
            {
                int idx = ((i + 1) * 9 + 4) % 32;
                text[idx / 8] |= (byte)((bits[i] ? 1 : 0) << (idx % 8));
                idx = idx;
            }
            text = text.reverse_bits();
        }

        static void Xor(ref byte[] text, byte[] key)
        {
            for (int i = 0; i < text.Length; i++)
            {
                text[i] ^= key[i];
            }
        }

    }
}

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