Разбор PKZIP

[vasanov]

Сообщение от p51x

Вы хоть код выложите на котором тестируете.
Это явно CRC32, почитайте все-таки википедию.

Обязательно почитаю про CRC32. Покаместь был на работе было некогда.
Например из вышеприведенных отрывков из исходников для расчета key1 использую такой дилетантский код:

#include <stddef.h>
#include <stdint.h>
#include <conio.h>
  unsigned key0=0x12345678;
  unsigned key1=0x23456789;

void main()

{
key1 = (key1 + (key0 & 0xff)) * 0x08088405  +   1;
printf("%x \n",key1);
return (0);
}

По идее, при отсутствии пароля или байта ps, key1 должен получится 0x23456789. А получается key1=0xc2038c06.
Даже если взять подругому:
#include <stddef.h>
#include <stdint.h>
#include <conio.h>
  unsigned key0=0x78563412;
  unsigned key1=0x89674523;

void main()

{
key1 = (key1 + (key0 & 0xff)) * 0x08088405  +   1;
printf("%x \n",key1);
return (0);
}

Получится key1=0xc05bae0a. Си все правильно считает, при таких вычислениях никак 0x23456789 не получится. Явно, что то не то в алгоритме, но скорее всего я неправильно беру начальные условия key.
Хотя вроде правильно рассуждаю. Ну, а про расчеты crc32, я еще молчу. В программах считающих контрольную сумму файла CRC32 никакого второго аргумента нет, это меня и смутило.
Ну, а вообще разработчики, что-то темнят. Я еще помню, как долго морочился с исходниками для MD5, пришлось кое-что переделывать по своему, чтоб оно выдавало правильную хэш. Неужели и PKZIP обманывает. Правда я ихних полных исходников на Си нигде не нашел.

[Smogg]

crc8|16|32 все считают от бита, а когда входные аргументы в виде байтов, то это усовершенствование исключительно во имя скорости, и в бекграунде подразумеваются все равно операции над каждым битом последовательно)

И мне сомнительно, что в CRC используется умножение, а не операция XOR.

[vasanov]

Сообщение от Smogg

crc8|16|32 все считают от бита, а когда входные аргументы в виде байтов, то это усовершенствование исключительно во имя скорости, и в бекграунде подразумеваются все равно операции над каждым битом последовательно)
И мне сомнительно, что в CRC используется умножение, а не операция XOR.

Да, конечно программы считающие CRC32 работают с битами и в CRC используется XOR. Это в алгоритме PKZIP, для расчета key1 используются простые действия - это и у разработчика так же.Вот я и стал сначала проверять простые вычисления в ихнем алгоритме, перед этим основательно запутавшись с ихними crc32(...,...).

[Smogg]

У них, при беглом взгляде, правильно с алгоритмом:

6.1.5 Initializing the encryption keys

Key(0) <- 305419896
Key(1) <- 591751049
Key(2) <- 878082192

loop for i <- 0 to length(password)-1
update_keys(password(i))
end loop

Where update_keys() is defined as:

update_keys(char):
Key(0) <- crc32(key(0),char)
Key(1) <- Key(1) + (Key(0) & 000000ffH)
Key(1) <- Key(1) * 134775813 + 1
Key(2) <- crc32(key(2),key(1) >> 24)
end update_keys

Where crc32(old_crc,char) is a routine that given a CRC value and a
character, returns an updated CRC value after applying the CRC-32
algorithm described elsewhere in this document.

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

key0, key1, key2 слабо взаимосвязаны. Все их взаимное влияние - исключительно в одном последнем байте. В принципе, можно вообще избегнуть взаимовлияний через последний байт, а изменять ключи совершенно отдельно.

Поэтому и нельзя, зная один ансайнед интегер и изменчивый байт, получить полноценный второй ансайнед интегер (с диапазоном значений от 0 до 2^32-1). Из одного заданного интегера и случайного байта можно по жестко заданному алгоритму получить всего 2^8 вариантов второго интегера.

[vasanov]

По быстрому почитал в вики про CRC,лучше бы не читал, еще больше запутался, но так и не понял куда там приткнуть байт pt. Поищу может где-то есть готовая библиотека для подсчета ихних crc32(key0,pt). Хотя гложет сомнение, что будет правильный результат при вычислениях. Может получится найти готовые полные исходники для PKZIP на Си. Если нет, то дизассемблирую и буду разбираться с ассемблером.

[vasanov]

Сообщение от Smogg

У них, при беглом взгляде, правильно с алгоритмом:
Поэтому и нельзя, зная один ансайнед интегер и байт, получить полноценный второй ансайнед интегер (с диапазоном значений от 0 до 2^32-1). Из одного интегера и байта можно по жестко заданному алгоритму получить всего 2^8 вариантов второго интегера.

Еще больше ничего не понял.
Но из алгоритма который порусски , вначале топика. Выходит, что key1 должно получаться из текушего key0 и начального key1, но почемуто не выходит, это если файл пустой тоесть pt вообще нет, тоесть пароль пустой.

[Smogg]

Сообщение от vasanov

Еще больше ничего не понял.
Но из алгоритма который порусски , вначале топика. Выходит, что key1 должно получаться из текушего key0 и начального key1, но почемуто не выходит, это если файл пустой тоесть pt вообще нет, тоесть пароль пустой.

Выходит, что новый key1 должно получаться из текушего key0 и начального key1

Читайте оригиналы) Переводы - исключительно для прояснений мутности оригиналов.

Из приведенного мной алгоритма, если пароль пустой, то и ключи не изменяются. Понимаете? Ведь просто не было ни одной итерации.

А каждый новый key, по задумке авторов, должен быть максимально отличен от любого предыдущего keyN.

[vasanov]

Сообщение от Smogg

Читайте оригиналы)
Из приведенного мной алгоритма, если пароль пустой, то и ключи не изменяются. Понимаете? Ведь просто не было ни одной итерации.

В английском я к сожелению совсем никак, поэтому прочесть оригинал не в состоянии. А всякие программные переводчики только еще больше путают.
Я тоже подозревал, что для пустого пароля ничего не считается. А вот проверить, простой пример, например, когда файл 1 и пароль 1 не могу.Потому, что так и не понял как считается функция из алгоритма crc32(key0,pt). Если только crc32(key0), еще можно вычислить, а куда эту pt приткнуть, которая символьная 1, или 16 ричн 31, двоичн 0011 0001, ну никак не пойму.
Если бы Си воспринял бы эти crc32(... , ...) у меня и голова не болела бы, просто бы кодировал бы побитно и все. Но Си ругается и не принимает эту функцию. Для кого же написан такой код
unsigned char PKZIP_stream_byte (unsigned char pt) {
unsigned short temp;
key0 = crc32 (key0, pt);
key1 = (key1 + (key0 & 0xFF)) * 0x08088405 + 1;
key2 = crc32 (key2, key1 » 24);
temp = (key2 & 0xFFFC) | 2;
return ((temp * (temp ^ i )) » 8) & 0xFF;
}
если Си его не воспринимает, может нужна специальная библиотека для Си, где есть расчеты по такой функции crc32(... , ...) ?

[Smogg]

передача аргумента pt - это следствие табличного расчета CRC. Я целый вечер втыкал в десяток описаний, пока не вкурил, как оказывается, достаточно примитивную идею:

В основе табличного алгоритма лежит свойство ассоциативности операции XOR и предварительное вычисление промежуточных данных.
Рассмотрим, как будет вести себя алгоритм при размере регистра более одного байта. На каждой итерации производится выдвигание старшего бита и в зависимости от того, равен он нулю или нет, производится XOR регистра с полиномом или не производится соответственно. Таким образом, за восемь итераций (количество битов в байте) порядок применения или не применения XOR однозначно определяется только значением старшего байта.
Таким образом, при выполнении операции XOR регистра с постоянной величиной при различных ее сдвигах всегда будет существовать некоторое значение, которое при применении операции "исключающее ИЛИ" с исходной величиной регистра даст нам тот же самый результат.
Например, последовательность операций:
0100110 регистр
...0110 XOR
..0110. XOR
.0110.. XOR
0110... XOR
-------
0100100

Можно заменить на одну операцию:
0100110 регистр
0000010 XOR
-------
0100100

Произведя предварительно вычисления всех вариантов использования/не использования XOR полинома самого с собой (в зависимости от значения первого байта регистра) и занеся их в таблицу, можно заменить 8 операций битового сдвига одной операцией поиска в таблице по индексу.


Ну, а после общего понимания CRC уже можно копипастить вики)

[vasanov]

Уже много начитал, про эти CRC, но с каждым разом все больше и больше запутываюсь. Всеравно не понимаю, что же делать с этим байтом pt. Это, что номер индекса таблицы значений стандартного полинома для CRC32 ? И мне, что нужно побитно перемножить полином от key0=0x12345678 на значения полинома из таблицы? Нормальные исходники Cи для подсчета CRC32, тоже не получилось найти, те, что нашел совершенно не хотят компилироваться- явно они написаны не для моего компилятора, да и они для профессионалов, которые поймут как к ним дописать код, чтоб все работало. Наверное у программистов так принято, в интернете писать только, то что не работает, или требует специфического компилятора. Так сказать, разберись и доделай сам.