Изменяем запретное

Крис Касперски

Хакер, номер #090, стр. 090-122-3

Программная "эмуляция" CRC на IBM PC мягко говоря... неоправданна. Приходится прибегать к табличным алгоритмам или сложным математическим преобразованиям, но первое требует памяти, второе — процессорного времени, и в конечном счете мы раздуваем муху до размеров слона. Почему же тогда CRC пользуется такой популярностью? Его можно найти в zip, arj, различных защитных механизмах. Такое впечатление, что кому-то некуда девать свои курсовые работы, а кто-то просто использует готовые библиотеки, пропуская теорию кодирования мимо ушей. Зачем она ему? Ведь все и так работает!

Но это все лирика. Вернемся к нашим баранам. Никакого единого стандарта на CRC не было, и нет. Даже когда говорят о CRC16 или CRC32, то подразумевают всего лишь разрядность контрольной суммы, для вычисления которой необходимо знать два фундаментальных параметра: полином (poly) и начальное значение контрольной суммы (init).

Параметр reflection указывает на то, используется ли зеркальное битовое отражение или нет. Отражаться могут как входные данные, так и выходные. Если байт отражен, то нумерация в нем ведется слева направо, то есть наименее значимый бит располагается по меньшему адресу (как, например, на x86), и, соответственно, наоборот. Наиболее быстрыми будут те алгоритмы, которые соответствуют выбранной "железной" архитектуре. В противном случае приходится прибегать к довольно дорогостоящей, в плане процессорных ресурсо, эмуляции.

Параметр XorOut — это то значение, которым XOR'ится рассчитанная контрольная сумма. Обычно она равна 0 или -1 (то есть FFFFh для CRC16 и FFFFFFFFh для CRC32).

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

Постой! Но ведь "стандартный" полином для CRC32 равен EDB88320h, а совсем не 4C11DB7h. Это каждый студент знает! Все правильно, никакого противоречия здесь нет, закрой забрало и не высаживайся! Число EDB88320h представляет собой зеркально отраженный полином 4C11DB7h, в соответствии со словом "да" в колонке "отражение" (см. таблицу). Давай переведем его в битовый вид и посмотрим, что получится. А получится у нас вот что:

Стандартный CRC-32 полином и его общепринятая отображенная версия

04C11DB7h: 00000100110000010001110110110111

EDB88320h: 11101101101110001000001100100000

Готовую процедуру расчета СRC приводить не будем, поскольку ее можно найти в любой книжке и в ссылках, приведенных ниже. Как уже говорилось, ее программная эмуляция на IBM PC не наглядна.

Подделка CRC32, не преследуемая по закону.