[Введение]
Собственно хочу здесь описать реверс или если можно так назвать взлом одного программного продукта реализующего шифрование файлов. Программа довольно старая, просто товарищ откопал где-то зашифрованные ей файлы, на каком-то древнем серве и захотел прочитать их содержимое, но естественно пароль(ключ) на котором шифровались данные он давно забыл.
В данном случае интерес представляет метод определения открытого текста, который может использоваться при взломе (востановлении паролей) других программ.
Программа:
Endec Version 1.0 (разработка KLUdGE ToolWare), распространяется бесплатно.
скачать
[Алгоритм шифрования]
В результате анализа удалось выявить несложный алгоритм шифрования:
Код:
//Позиция символа в файле умножается на соответствующий
//символ пароля и ксорится с самим символом
//Счетчик символа пароля на каждой итерации
int j=0;
//Цикл по размеру файла
for(int i=0;i<FileLength;i++;j++)
{
//Обнуление счетчика при достижении конца пароля
if(j==PassLength)
j=0;
//Считывание символа из файла
symbol=fgetc(FileIn);
//Преобразование символа и запись в выходной файл
fputc(((i+1)*pass[j])^symbol,FileOut);
//Увеличение счетчика
}
При зашифровании текстового файла, все символы файла складываются по модулю два с числом X, равным произведению соответствующих, позиции этого символа в файле и символом пароля, в том числе самый часто встречаемый символ.
[Алгоритм дешифрования]
Операция сложения по модулю два является обратимой. Отсюда следует, что если сложить самый часто встречаемый символ с зашифрованным текстом, удастся выявить число X. Далее для получения гипотезы о символе пароля достаточно было бы поделить соответствующие X на соответствующие позиции этих X-ов в файле, но это не возможно, потому что при получении числа X, результат произведения помещается в переменную размером в 2 байта. Поэтому результат округляется и по нему не возможно с помощью деления восстановить символ пароля. Для этого потребуется таблица 256x256, значениями которой будут результаты произведения номера столбца на номер строки, причем номера столбцов – позиция символа в дешифруемом файле, а номера строк – вероятные символы пароля. Будем производить основной перебор по длине пароля. На каждой итерации для определения возможного символа пароля берем каждый соответствующий символ дешифруемого файла и складываем по модулю 2 с наиболее часто встречающимся символом, в зависимости от типа текста (пробел или 0). Затем получившийся результат сравниваем со значением из нашей таблицы и в соответствии с позицией из той же таблицы выбираем возможный символ пароля. Далее выбираем наиболее часто встречаемый возможный символ пароля и принимаем его за основную гипотезу о символе пароля на данной итерации. Далее дешифруем текст с полученной гипотезой. Считаем Хи2 статистику для данного текста и запоминаем. Гипотеза с наибольшей Хи2 статистикой будет считаться наиболее вероятным паролем.
Хи квадрат статистика - Сумма квадратов количества встречаемости каждого символа в тексте. Наибольшее число позволяет определить наиболее структурированный текст, а значит и наиболее открытый (т.е. правильный, а не случайный).
Алгоритм дешифрования будет выглядеть след. образом:
Код:
//Создание таблицы каждая ячейка, которой содержит произведение столбца
//на строку, где строка - номер символа дешифруемого файла, столбец -
//вероятный символ пароля
Begin
for i:=0 to 256 do
for j:=0 to 256 do
MultTable[i][j]=i*j;
end
end
End
//Инициализируем основные переменные:
//Позиция символа в дешифруемом файле
integer position;
//Гипотеза о пароле
character ProposedPassword[70];
//Наиболее вероятный пароль
character Password[70];
//Максимальная сумма частот встречаемости каждого символа в квадрате в
//гипотезе о дешифрованном тексте
double Xi2:=0;
//Переменная ксорится с наиболее частым символом зашифрованного файла
//она либо пробел либо ноль в зависимости от типа файла
character type;
//Основной перебор по длине пароля
for k:=4 to 70 do
begin
//Определение символа пароля при фиксированной длине пароля
for j:=0 to k do
begin
Заводим массив mas[256] из 256 символов для колонной маркеровки;
//Позиция символа с единицы
position:=j+1;
for m:=0 to (Длина файла/k) do
begin
CryptoSymbol:= Считываем символ из дешифруемого файла;
//Ксорим символ из дешифруемого файла с type
Symbol:=type XOR CryptoSymbol;
for s:=0 to 256 do
begin
//Сравнение значения и position
if (Symbol equals Multitable[position][s]) then mas[s]++;
end;
Перемещаем указатель позиции в файле на k-1;
position:=position+k;
//Позиция в файле ограничивается размером в байт
position:=position(mod256);
end;
//Для следующей итерации
Устанавливаем указатель в файле на начало;
//Находим самый большой по значению элемент массива
//он и будет наиболее часто встречающимся символом пароля.
max:=0;
for n:=32 to 256 do
begin
if max<mas[n] then
max:=mas[n];
ProposedPassword[j]:=n;
end;
end;
//Таким образом, мы получаем различные гипотезы на разных итерациях.
Расшифровываем файл с полученной гипотезой по известному алгоритму;
//Считаем Хи-квадрат для каждого такого файла на каждой итерации
Xi2:=Число встречаемости каждого символа возведенное в квадрат;
Находим максимальный из Xi2, тем самым находим наиболее вероятный пароль;
End;
Данный алгоритм является вероятностным и поэтому возможны ошибки. Но многократные эксперименты показали, что алгоритм хорошо работает на зашифрованных файлах размером более 1 Кб.
[ЗЫ]
Вообщем удалось восстановить старый пароль товарища.
Да кстати прога поддерживает максимальную длину пароля - 70 символов. Так что чем длиннее пароль - тем дольше время перебора.
Но например 7 - значный пароль подбирается за пару секунд
Если кому интересно программа дешифратор
MyEndec можете поиграться зашифровать и восстановить пароль. Или кому нибудь предложить зашифровать прогой, а сами угадаете пароль типа
А если будет совсем интересно могу выложить исходники на С.
![Аватар для [53x]Shadow](/avatars/avatar32248.jpg?407327){kind=avatar}
Криптография против криптографии.
Похожие темы
Древовидный вид