Решение warsaw - Java Crackme 1.1

Сложность: 3 - Getting harder
Платформа: Multiplatform
Язык: Unspecified/other
Дано: Java Crackme 1.1

Простой jar-файл, который принимает в качестве входных данных при запуске в командной строке одно число. Цель – выяснить, какое число вам нужно, чтобы получить ответ "Correct".
Это несложно сделать, если вы понимаете байт-код Java, но я кое-что вставил в код, чтобы затруднить дизассемблирование.

Решение (автор aodrulez)
опубликовано 04.09.2012

От переводчика - свои объяснения и примечания я буду выделять курсивом.

Ну, если быть откровенным, crackme оказался забавным. Я скачал его шутки ради и к моему удивлению, все существующие Java-декомпиляторы впали в ступор. И я подумал, что, черт возьми, происходит! И вот мои действия. Первое, что я сделал, открыл crackme в моем любимом Java-декомпиляторе jd-gui? Как и ожидалось, jd-gui не cмог справиться с crackme. Смотрите результат на рисунке.

image01.jpg

Конечно, декомпилятор не отказывается работать, он действительно показывает некоторые интересные вещи, но я считаю, что это не вариант. Итак, что же делать дальше? По мне, следующий очевидный шаг использовать тяжелую артиллерию. IDA Pro выделяется среди себе подобных, когда вы думаете о серьезном инструменте для реверса и на то есть причины. Со своей работой он справляется на отлично. Итак, я извлек файл Code.class из crackme1.1.jar (берем любой zip-архиватор и вытаскиваем файл). Осталось импортировать его в IDA и проанализировать. На следующем рисунке видно, что из этого получилось.

image02.jpg

Первое, что бросается в глаза – IDA жалуется, что что-то пошло не так, когда он попытался дизассемблировать файл класса. Не удивительно ;) Давайте прокрутим листинг и посмотрим, что там дальше.

image03.jpg

И проблема никуда не исчезла. Обратите внимание, что существуют строки кода (прямо в самом начале), которые IDA выделяет красным. Не торопитесь впадать в панику, давайте более детально проанализируем листинг IDA.

image04.jpg

Много мусора. И вполне возможно, в этом причина, почему jd-gui не смог справиться с crackme. Если не ошибаюсь, такой способ обфускации называют «junk-byte-injection» в терминологии сегодняшнего дня. Забавно то, как большинство существующих инструментов не способно обработать такой простой мусорный код. Итак, следующий большой вопрос.. а что дальше? Я вроде как уверен, что нахожусь на правильном пути. Поэтому, просто ради своего спокойствия, давайте попробуем исправить файл класса. Для этого, прежде всего, посмотрим, какой байт-код соответствует инструкции "getstatic 37".

image05.jpg

Как выяснилось – это hex-код «B2 00 25» (или в десятичной нотации 178 0 37). Хм. Еще один важный момент – это единственная мусорная инструкция на весь дизассемблированный код. Так что, если мы просто заменим эту инструкцию на байт-код команды NOP, то теоретически файл класса будет исправлен. Все, что я сделал – запустил мой любимый hex-редактор (автор пользуется Hex Workshop, я же использовал WinHex, меню Search -> Replace Hex Values…) и выбрал опцию «Заменить все».

Найти: «B2 00 25»
Заменить на: «00 00 00»

Ну, да … это было быстро. NOP в байт-коде Java является 0x00. Вот почему я просто заменил эти 3 байта на 0x00. И мы убрали мусор в один миг. А сейчас пришло время посмотреть на результат – анализируется ли файл декомпилятором или мы только что убили файл класса :D. Пробуем открыть crackme в jd-gui.

import java.io.PrintStream;
 
public final class Code extends PrintStream
{
  public static final synchronized void main(String[] paramArrayOfString)
  {
    try
    {
      jsr 6;
      paramArrayOfString = returnAddress;
      System.out.println(Integer.decode(paramArrayOfString[0]).intValue() * -37 + 42 == 1720653869 ? "Correct!" : "Incorrect");
      return;
    }
    finally
    {
      while (true)
        tmpTernaryOp = "Please enter a 32bit signed int";
    }
  }
}


Вау! Этот способ работает! Пока что, нам потребовалось всего лишь 20 минут, и у нас на руках уже есть читабельный код. Хорошо. Наша логика оказалась верной. Теперь рассмотрим алгоритм работы crackme.
Входное значение paramArrayOfString[0] – число, которое мы передаем в командной строке. Умножаем его на (-37), складываем результат с 42 и сравниваем с константой «1720653869» Но! Вот здесь есть хитрость. Наше число преобразуется в целое (Integer) до того, как оно умножается на (-37). Вы скажете, ну и что? Дело в том, брат, что наше число в этом случае не так-то легко вычислить. Если вы просто посмотрите на это уравнение с математической точки зрения, то оказывается:

Значение * (-37) + 42 = 1720653869
Значение = 1720653869 – 42 / (-37)
Значение = -46504157.4864865

Таким образом, судя по вычислениям, если мы введем -46504157.4864865 в качестве входного значения, то мы должны получить goodboy-сообщение «Correct». Но ничего не произойдет, код не принимает значение с плавающей запятой. Даже если вы как ниндзя обойдете проверку ввода, то далее нас ждет принудительное преобразование к типу Integer. Ах так! Откуда я это знаю наверняка? Я даже еще не пытался запустить crackme на выполнение. Не вопрос. Проверим.

image07.jpg

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

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

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

solution.java

public class solution {
  public static void main(String[] args)  {
    int x = 46504157;
    while (true) {
      if ((-1)*x*(-37)+42 == 1720653869) { 
        System.out.println("\nSolved! Correct value = -"+x+"\n"); break; }
      x++;
    }
  }
}


И вот результат:
# сначала компилируем исходный код
javac solution.java
# а теперь выполняем
java solution.java

Solved! Correct value = -975145735

Я же предложу еще один вариант нахождения нашего числа. Через поиск обратного числа (multiplicative inverse). Обратное число – это число, на которое надо умножить данное число, чтобы получить единицу. Пара чисел, произведение которых равно единице, называются взаимно обратными.
Возьмем наше уравнение:
Х * (-37) + 42 = 1720653869
Х * (-37) = 1720653869 - 42
Х * (-37) = 1720653827

Или так:

Х * (-37) = 1720653827 по модулю 232 (тип Integer – это 32-битное целое число)

Поиск обратного числа:

  • A * B = Z (mod 232)
  • A, Z известны. Надо найти B???
  • Упрощаем выражение -> A * A(-1) * B = Z * A(-1) (mod 232) -> B = Z * A(-1) (mod 232)
  • A(-1) – ЭТО ОБРАТНОЕ ЧИСЛО. Найти значение A(-1) можно с помощью расширенного алгоритма Евклида

Откажемся от «-», просто будем держать в уме, что Х тоже отрицательное число.
Х * 37 = 1720653827 mod 232
Х * 37 * 37(-1) = 1720653827 * 37(-1) mod 232
Х = 1720653827 * 37(-1) mod 232

Используя расширенный алгоритм Евклида (Python-реализация алгоритма euclidean.py), находим обратное число для 37(-1).
37(-1) = 2437684141
Тогда
Х = 1720653827 * 2437684141 mod 232
Х = 975145735

# -*- coding: cp1251 -*-
import euclidean
 
# Число, для которого ищем обратное значение
a = 37
# Модуль
p = (1<<32)
# Обратное число
a_inv = euclidean.invmod(a, p)
 
# Результат
b = (a_inv * 1720653827) % p
print ("[+]Solved! Correct value = -" + str(b))


Добавляем «-»:
Х = -975145735

image08.jpg
Пока не указано иное, содержимое этой страницы распространяется по лицензии Creative Commons Attribution-ShareAlike 3.0 License