Применение ласки Докинза* для взлома простого шифра XOR

TryHackMe (n.d.) — это веб-сайт, целью которого является обучение начинающих специалистов по кибербезопасности методам, используемым в этой области, как с наступательной, так и с оборонительной точки зрения. В настоящее время я занимаюсь комнатой, где столкнулся с интересной проблемой, связанной с простым шифром XOR. Я нашел решение с моей версией ласки Докинза, которая представляет собой игрушечную модель, используемую для обучения эволюционной биологии на вводном уровне.

Обратите внимание, что в моей версии ласки Докинза есть некоторые «причуды», которые отличаются от основных ее реализаций. Я обсужу это позже.

Краткое содержание

Фон
Мое решение
Обсуждение
Краткое содержание
Рекомендации

Фон

Эта комната, или небольшая практичная лаборатория, была разработана cookiedragon234 (2020, задание 5) и призвана научить участников реконструировать программное обеспечение, которое должно выполняться Java Virtual. Машина (JVM). Одна из проблем ("crackme") в этой комнате состоит в том, чтобы определить "пароль" исполняемого файла Java .class с помощью комбинации стандартных методов дизассемблирования и декомпиляции и творчества пользователя.

Я запустил Crackme с паролем «test», и получил следующий вывод:

$ java BasicStringObfuscation
Please provide a password
$ java BasicStringObfuscation test
Incorrect

Проблема состоит в том, чтобы найти способ перенаправить выполнение крякмея на вывод чего-то отличного от [i]неправильного без использования патчей. Для начала я запустил Bytecode Disassembler (n.d.) и начал проверять исходный код. Рисунок 1 показывает, что дизассемблер сделал с исходным кодом Crackme:

Сосредоточив внимание на левой панели¹, я могу сказать, что crackme принимает строку в качестве аргумента, прогоняет ее через специальный² шифр XOR и, наконец, сравнивает строку XOR со строкой correctPassword. Если ввод XOR соответствует correctPassword, то решение «[c] правильно», и пароль был взломан без необходимости исправления исполняемого файла .class.

В частности, значение «пароль» должно быть найдено так, чтобы:

Это выражение просто формализует проблему: найти «пароль», который при прохождении через функцию xor давал бы результат correctPassword. Теперь необходим метод для определения того, что должно быть совмещено XOR с correctPassword, чтобы крякме распечатал желаемый результат «[c]orrect!»

Мое решение

Я думал о разных подходах, например, о простом алгоритме грубой силы, но потом решил, что этот подход может занять слишком много времени. Затем где-то по ходу дела я вспомнил простую игрушечную модель под названием ласка Докинза в честь биолога Ричарда Докинза, которая используется для ознакомления читателей с эволюционной биологией.

Реализация: постановка задачи

Прежде чем обсуждать мое решение, мне нужно сформулировать проблему. Ниже приведена настройка, которую я сохранил в файл с именем Dawkins.java:

import java.io.*;
import java.util.*;
public class Dawkins {
    public static final String correctPassword = "aRa2lPT6A6gIqm4RE";
    public static void main(String[] args) {
        // TODO
    }
}

Вместо того, чтобы портировать процедуру crackme XOR на другой язык программирования (что было моим первоначальным планом), я решил просто «скопировать и вставить» исходную процедуру XOR без каких-либо изменений, чтобы избежать ошибок при написании моего приложения ласки Докинза. :

    [... snip ...]
    // From the decompile dump of "BasicStringObfuscation.class"
    public static String xor(String var0) {
        char[] var1 = var0.toCharArray();
        char[] var2 = new char[var1.length];
        for (int var3 = 0; var3 < var2.length; ++var3) {
            char var4 = var1[var3];
            var2[var3] = (char)(var4 ^ var3 % 3);
        }
        return new String(var2);
    }
}

Наконец, мне нужно настроить функцию main, объявив переменные и настроив цикл while для повторения процесса до тех пор, пока solution — или «потомок» — не совпадет с target. Ниже показана установка:

[... snip ...]
public static void main(String[] args) {
[1]     Random random = new Random();
[2]     int counter = 1;
[3]     char[] target = correctPassword.toCharArray();
[4]     char[] solution = new char[target.length];
[5.1]   boolean done = false;
[5.2]   while (!done) { 
[5.3]      //TODO
[5.4]   }
} [... snip ...]

Я объявил экземпляр класса Random (Ln. 1; см. Java Documentation, n.d.) с целью генерации случайных чисел. Я объявил переменную int с именем counter (Ln. 2) для подсчета количества поколений, которое потребовалось этому алгоритму для получения решения, массив char[] с именем target (Ln. 3), который берет correctPassword и разбивает его на массив, и другой массив char[] с именем solution (Ln. 4) для хранения окончательных результатов полностью разработанного решения. Цикл while настроен (Ln. 5.1–5.4) для повторения основной процедуры до тех пор, пока solution не совпадет с target.

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

Игрушечная модель для обучения биологии

В биологическом контексте эволюция относится к естественному процессу, объясняющему изменение частот аллелей. Биологические организмы должны проявлять определенные черты, чтобы наилучшим образом адаптироваться к окружающей среде. С точки зрения эволюции, ориентированной на гены, организмы с аллелями, которые, за неимением лучшего термина, вызывают признаки, лучше всего адаптирующиеся к окружающей среде, с большей вероятностью передадут указанные аллели посредством размножения. В статье Википедии оцентрированном на генах взгляде на эволюцию (Редакция от 15 сентября 2021 г.) содержится более подробное описание теории.

Некоторым может быть трудно представить себе, как будет работать такой процесс, поэтому Ричард Докинз выходит на сцену с игрушечной моделью, чтобы помочь тем, кто испытывает трудности. Докинз (1996, стр. 46–48) представляет читателю описание того, что теперь известно как ласка Докинза. Здесь определяется целевая строка, представляющая черты, которые лучше всего подходят для аналогичной среды. Моделирование начинается с определения случайной инициализированной строки, которая является полностью случайной и не похожа на целевую строку. Инициализированная строка представляет выраженные признаки гипотетических организмов, и для того, чтобы гипотетические организмы выжили, их выраженные признаки должны соответствовать целевой строке.

В случае Докинза целевая строка взята из пьесы, написанной Уильямом Шекспиром, которая гласит: «МНЕ ДУМАЕТСЯ, ЭТО КАК ЛАСКА». Моделирование начнется с исходной строки и целевой строки. Затем он «мутируется», случайным образом меняя отдельные буквы до тех пор, пока они не совпадут с целевой строкой. Когда Докинз запустил симуляцию, потребовалось около 64 итераций, или «поколений», прежде чем строка, состоящая из случайных символов, стала напоминать фразу «Думаю, это похоже на ласку».

Аналогия: можно ли «эволюционировать» решение?

Для этой проблемы я решил, что зашифрованная строка XOR может быть аналогией для среды. Затем я могу генерировать случайные строки, которые будут аналогичны генам, которые непосредственно вызывают признак.⁴ Этот игрушечный генетический алгоритм, на мой взгляд, можно использовать для «эволюции» ключа, который можно провести через процедуру xor, что приведет к correctPassword.

Реализация: случайная мутация

Начнем с первой подзадачи: она включала в себя генерацию случайной строки для прохождения через процедуру XOR. Реализация этого на Java оказалась немного сложной³, поэтому я использовал слегка модифицированную процедуру, созданную Paraschiv (n.d.). На панели кода ниже показана первая часть решения:

[... snip ...]
while (!done) {
[1.1] char[] seed = random.ints(48, 123)                                                 
[1.2]   .filter(k -> (k <= 57 || k >= 65) && (k <= 90 || k >= 97))                                               
[1.3]   .limit(target.length)                                               
[1.4]   .collect(StringBuilder::new,     
            StringBuilder::appendCodePoint, StringBuilder::append)                                                      
[1.5]   .toString().toCharArray();
[... snip ...]

Приведенную выше часть может быть трудно читать, но char[] seed представляет собой одну строку кода. Он генерирует число от 48 до 123 (Ln. 1.1), затем отфильтровывает целые числа в определенном диапазоне (Ln. 1.2), сопоставляет длину строки target (Ln. 1.3), строит ее в строку (Ln. 1.4) и наконец, взрывает строку в массив. Это строка, которая генерирует случайные буквы, которые должны быть объединены XOR со строкой target.

Реализация: оценка пригодности и функция XOR

После строки char[] seed вся оценка пригодности выполняется одной строкой кода:

char[] nextGen = xor(new String(seed)).toCharArray();

Напомним, что символ, являющийся частью случайной строки, можно рассматривать как ген, кодирующий определенный признак. Указанная «черта» должна адаптироваться к своей «окружающей среде». В этом случае случайный символ должен пройти операцию xor, и значение символа должно совпадать со значением символа correctPassword с учетом его позиции в массиве char[] для всех символов и их соответствующих позиций.

Эта строка кода просто запускает случайную строку, сгенерированную с помощью операции xor, а затем разбивает решение на массив char[] с именем nextGen.

Реализация: выбор «наиболее подходящих» персонажей

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

for (int k = 0; k < solution.length; k++) {
    if (solution[k] != Character.MIN_VALUE) {
        continue;
    }
    else {
        emptySlots = true;
        if (nextGen[k] == target[k]) {
            solution[k] = seed[k];
        }
    }
}
System.out.printf("Generation %d: %s\n", counter, new String(solution));
counter++
if (!emptySlots) {
    done = true;
}

Этот код просто перебирает массив char[] nextGen и добавляет символы, соответствующие их позициям в переменной target. Каждое поколение распечатывается, и процесс повторяется до тех пор, пока все символы, созданные случайной строкой, не могут быть объединены XOR, чтобы соответствовать их соответствующей позиции в массиве char[] target.

Конечный продукт

Исходный код готового решения этой задачи:

Обсуждение

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

Elaq (ок. 2013?)» разработал решение на языке программирования Python, которое в некоторой степени повлияло на то, как я думал о подходе к созданию своего решения.
Блог Like a Weasel (n.d.) имеет несколько реализаций; все их сообщения были сделаны в 2009 году.
Rosetta Code (редакция от 27 августа 2022 г.) имеет запись со списком реализаций на более чем 100 языках программирования с августа 2022 года (первоначальная запись была в 2009 году).

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

Наконец, я хочу отметить, что эта статья не предназначена для обучения. Скорее, это скорее рецензия, в которой обсуждается мой опыт решения этой проблемы. Я обсуждал почти точную версию того, что отправил в комнату TryHackMe. Готовый исходный код Java (почти) точно такой же, который я скомпилировал для разработки correctPassword— с добавлением комментариев. Я знаю, что этот код можно оптимизировать еще больше.⁵

Краткое содержание

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

Благодарности

За их отзывы о моих описаниях ласки Докинза и геноцентрическом взгляде на эволюционную биологию (в ранних набросках этой статьи) я хотел бы поблагодарить биолога растений Кевина А. Бёрда. Я несу полную ответственность за любые ошибки в этой статье.

Затыкать

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

Женский медицинский фонд в Висконсине: https://wiabortionfund.org/
Фонд Texas Equal Access в… ну… Техасе: https://teafund.org/

Сноски

Потому что исходный код высокого уровня Java легче читать, чем сборку JVM.
Их процедура XOR использует модульную арифметику. Я думаю, что это для того, чтобы результаты были буквенно-цифровыми.
По крайней мере для себя 😋
Обратите внимание, что в реальном мире биологии наследственность гораздо сложнее, чем в моей версии ласки Докинза.
Например, удаление избыточных скобок в некоторых операторах потока управления с выполнением только одной инструкции и создание моей прикладной ласки немного «умнее», не генерируя случайные символы для индексов случайной строки, где правильный символ для операции XOR приведет к характер соответствующего индекса. Вероятно, я мог бы использовать многопоточность и многозадачность для каждого из символов в строке и реорганизовать свое решение.

Применение ласки Докинза* для взлома простого шифра XOR

Краткое содержание

Фон

Мое решение

Реализация: постановка задачи

Игрушечная модель для обучения биологии

Аналогия: можно ли «эволюционировать» решение?

Реализация: случайная мутация

Реализация: оценка пригодности и функция XOR

Реализация: выбор «наиболее подходящих» персонажей

Конечный продукт

Обсуждение

Краткое содержание

Благодарности

Затыкать

Сноски

Рекомендации

Вопросы по теме