[53x]Shadow
08.07.2007, 00:05
[Введение]
Собственно хочу здесь описать реверс или если можно так назвать взлом одного программного продукта реализующего шифрование файлов. Программа довольно старая, просто товарищ откопал где-то зашифрованные ей файлы, на каком-то древнем серве и захотел прочитать их содержимое, но естественно пароль(ключ) на котором шифровались данные он давно забыл.
В данном случае интерес представляет метод определения открытого текста, который может использоваться при взломе (востановлении паролей) других программ.
Программа:
Endec Version 1.0 (разработка KLUdGE ToolWare), распространяется бесплатно.
скачать (http://www.safesite.com/product.download.php?id=331&url=endec100.zip&itn=1&SiteID=digibuy)
[Алгоритм шифрования]
В результате анализа удалось выявить несложный алгоритм шифрования:
//Позиция символа в файле умножается на соответствующий
//символ пароля и ксорится с самим символом
//Счетчик символа пароля на каждой итерации
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 (http://rapidshare.com/files/41600473/MyEndec2.zip.html) можете поиграться зашифровать и восстановить пароль. Или кому нибудь предложить зашифровать прогой, а сами угадаете пароль типа ;)
А если будет совсем интересно могу выложить исходники на С.
Собственно хочу здесь описать реверс или если можно так назвать взлом одного программного продукта реализующего шифрование файлов. Программа довольно старая, просто товарищ откопал где-то зашифрованные ей файлы, на каком-то древнем серве и захотел прочитать их содержимое, но естественно пароль(ключ) на котором шифровались данные он давно забыл.
В данном случае интерес представляет метод определения открытого текста, который может использоваться при взломе (востановлении паролей) других программ.
Программа:
Endec Version 1.0 (разработка KLUdGE ToolWare), распространяется бесплатно.
скачать (http://www.safesite.com/product.download.php?id=331&url=endec100.zip&itn=1&SiteID=digibuy)
[Алгоритм шифрования]
В результате анализа удалось выявить несложный алгоритм шифрования:
//Позиция символа в файле умножается на соответствующий
//символ пароля и ксорится с самим символом
//Счетчик символа пароля на каждой итерации
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 (http://rapidshare.com/files/41600473/MyEndec2.zip.html) можете поиграться зашифровать и восстановить пароль. Или кому нибудь предложить зашифровать прогой, а сами угадаете пароль типа ;)
А если будет совсем интересно могу выложить исходники на С.