Как изменить hash файла

Забавляемся с хешами

Привет. Я хочу показать вам небольшой фокус. Для начала вам потребуется скачать архив с двумя файлами. Оба имеют одинаковый размер и одну и ту же md5 сумму. Проверьте никакого обмана нет. Md5 хеш обоих равен ecea96a6fea9a1744adcc9802ab7590d. Теперь запустите программу good.exe и вы увидите на экране следующее.
Попробуйте запустить программу evil.exe.
Что-то пошло не так? Хотите попробовать сами?

О хешах и колллизиях

На самом деле ничего нового во всем этом нет. В действительности данный эффект достигается за счет методов быстрого поиска коллизий для хеш функции разработанных еще в 2004-2006 годах. Если кто не знает, коллизия это два разных набора данных, имеющих одно и тоже хеш-значение. Так вот, в 2004 году группа китайских исследователей разработала алгоритм, основанный на дифференциальном криптоанализе, позволяющий за относительно небольшое время находить два различных случайных блока данных, размером по 128 байт каждый, имеющих одну и ту же md5 сумму. И хотя алгоритм этот в свое время произвел эффект взорвавшейся бомбы быстродействие его оставляло желать лучшего. Но уже в 2006 году чешский криптограф Властимил Клима предложил для поиска коллизий новый метод, позволяющий найти разную пару случайных 128 байтных блоков с одной md5 суммой на персональном компьютере меньше чем за минуту.

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

Схематично это можно представить следующим образом:
s_i+1 = f(s_i, M_i), где s_i вектор инициализации для i-го блока.
Метод Властимила Клима позволяет для любого заданного значения s_i подобрать два 128-байтных блока M,M` и N,N` таких, что f(f(s, M), M’) = f(f(s, N), N’).

Таким образом, с помощью данной методики можно сконструировать два файла с одинаковой md5 суммой, но имеющих различные 128 байт в середине.
M₀, M₁, …, M_i-1, M_i, M_i+1, M_i+2, …, M_n,

M₀, M₁, …, M_i-1, N_i, N_i+1, M_i+2, …, M_n.
Обратите внимание что хеши обоих этих файлов совпадут, т.к. различающиеся блоки M_i, M_i+1 и
N_i, N_i+1 вернут в качестве s_i+2 одно и тоже значение, т.к. f(f(s, M_i), M_i+1) = f(f(s, N_i), N_i+1), а поскольку все последующие данные идентичны то последующие значения функции сжатия для обоих файлов будут совпадать.

Что это нам дает

Теперь перейдем от вещей абстрактных и отдаленных к вопросу практическому. Предположим, что у нас есть исполняемый файл M₀, M₁, X, X, …, M_n. Но его основе мы можем создать два разных файла M₀, M₁, N₁, N₁, …, M_n и M₀, M₁, N₂, N₁,…, M_n(просто меняем блоки X на N₁ и N₂). Если блоки N₁ и N₂ – это коллизии то хеш-сумма этих файлов будет совпадать.
Теперь представим, что этот исполняемый файл имеет следующую структуру:
if (X == X) then { good_program } else { evil_program }
Вот собственно и весь секрет данного фокуса.

Как сделать самостоятельно

Теперь немного поговорим о том как это сделать самому.
Шаг первый: пишем программу с двойным дном.

#include <stdafx.h> 
#include<iostream>
#include <string>
using namespace std;
//переменные str1 и str2 в данном примере являются теми самыми элементами X.
static char *str1="qwertyuioplkjhgfdaszxcvbnmkjhgfdsaqwertyuikjh"
"gbvfdsazxdcvgbhnjikmjhbgfvcdsazxdcfrewqikolkjnhgfqwertyuioplkjh"
"gfdaszxcvbnmkjhgfdsaqwertyuikjhgbvfdsazxdcvgbhnjikmjhbgfvcdsa"
"zxdcfrewqikolkjnhgfq123";
static char *str2="qaswderftgyhujikolpmnbvcxzasxdcfvgbhnjmkijuy"
"gtfdeswaqscfvgyjqaswderftgyhujikolpmnbvcxzasxdcfvgbhnjmkijuyg"
"tfdeswaqscfvgyjqaswderftgyhujikolpmnbvcxzasxdcfvgbhnjmkijuygt"
"fdeswaqscfvgyjqwertyuikja2";int good()
{
  int a;
  std::cout<<"Good, nice programme!";
  std::cin>>a;
  return 0;
}
int bed()
{
  int a;
  for(int i=0; i<1000; i++)
  {
  std::cout<<"Evil, evil code!";
  }
  std::cin>>a;
  return 0;
}
int _tmain(int argc, _TCHAR* argv[])
{
//строки s и s2 содержат только блоки с коллизиями без лишних элементов
  string s=str1;  
  string s2=str2;    
  s.erase(0,56);
  s.erase(128,8);
  s2.erase(0,64);
   if (s==s2) {
  return good();
 } else {
  return bed();
 }
  return 0;
}

* This source code was highlighted with Source Code Highlighter.

Особое внимание прошу обратить на переменные str1 и str2. Они служат для того, чтобы их можно было быстро найти в hex-редакторе и заменить нужными данными.
Функция main в зависимости от содержимого переменных s вызывает хорошую или плохую версию программы.

Шаг второй: После компиляции программы нужно будет немного поработать с hex-редактором для того чтобы найти в .exe файле наши строки str1 и str2. Скопируй полученный .exe файл. Пусть копия будет называется «обрезанная версия». Откройте копию в hex-редакторе и найди в ней строки str1 и str2. Удалите все данные идущие после первых 64 байт первой из строк. Последние строки полученного файла будут выглядеть вот таким образом: . Сохраните данный файл.

Шаг третий: Созданный на втором шаге файл будет служить так называемым префиксом для поиска коллизий. Чтобы найти коллизию с заданным префиксом нужно скачать отсюда программу fastcoll(Спасибо ее автору Marc Stevens). Исходники лежат тут.
Запустите программу с параметром –p. В качестве префикса укажите «обрезанную версию». В результате работы программы будут созданы два файла «обрезанная версия_msg1» и «обрезанная версия_msg2».

Шаг четвертый: создайте еще одну копию вашей программы. Пусть оригинал будет называться good.exe, а копия evil.exe. Откройте файлы msg1 и msg2 в hex редакторе. Сперва замените блок в котором хранится str2 данными из блока str1. Пусть теперь в них будет одинаковая информация. После этого скопируйте из файла msg1 последние 128 байт и вставьте их в ваш good файл так как показано на рисунке.

Обратите внимание, отступы должны соответствовать следующим параметрам: первый блок вставляется прямо в том месте где заканчивается файл «обрезанная версия», второй блок располагается в 96 байтах от первого. Важно: блоки вставлять одни и те же. Это будет доброй версией нашей программы. Сохраняем файл good.exe и открываем файл evil.exe. Блоки в файл evil.exe нужно будет вставить в те же места, что и в good.exe, единственное отличие заключается в том, что первый блок мы берем из файла msg2, а второй из файла msg1. Это различие и обеспечит нам невыполнение условия программы if (s==s2) и соответственно запустит злую версию программы.

Шаг пятый: Profit! Сравниваем md5 суммы файлов, наслаждаемся полученным результатом.

Список литературы:
1. Замечательный сайт с описанием данного метода
2. Сайт Властимила Клима
3. Сайт автора программы findcoll