Форум АНТИЧАТ - Криптография против криптографии.

[Введение]

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

Программа:
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 можете поиграться зашифровать и восстановить пароль. Или кому нибудь предложить зашифровать прогой, а сами угадаете пароль типа ;)
А если будет совсем интересно могу выложить исходники на С.