Как подделывают CRC16-32

       

чем ломать CRC32, необходимо научиться


Прежде, чем ломать CRC32, необходимо научиться его считать. Из всех учебников и статей мне больше всего нравится "a painless guide to crc error detection algorithms", которое я настоятельно рекомендую для изучения. Имеется так же и русскоязычный перевод. Адреса обоих можно найти во врезке по ссылкам. Кстати говоря, в последнее время набирает силу CRC64, который рассчитывается аналогичным образом, но, естественно, другим полиномом. Кое-где используется даже CRC128, но пока он не стандартизован, а поэтому здесь не затрагивается.

Аббревиатура CRC расшифровывается как "Cyclic Redundancy Check" (проверка избыточности циклической суммы) и стягивает под свою крышу целую кучу самых разных алгоритмов, разработанных в "геральдические" времена с ориентацией на воплощение в железо. В практическом плане это означает, что большинство CRC алгоритмов представляют собой тривиальный подсчет контрольной суммы в стиле а-ля: "for(a=0,CRC=INIT_VALUE;a< len;a++) CRC+=DATA[a];", лишь с той оговоркой, что сложение выполняется не алгебраическим путем, а происходит в полях Галуа в тесном сотрудничестве с полиномиальной арифметикой. В "железе" все это хозяйство реализуется на сдвиговых регистрах и логических вентилях, что очень дешево стоит и еще быстрее работает.

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

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



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

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

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

название



разрядность, бит

poly

init

отражение

xorout

init

out

CRC-16

16

8005h

0000h

да

да

0000h

CRC-16/CITT

16

1021h

FFFFh

нет

нет

0000h

XMODEM

16

8408h

0000h

да

да

0000h

ARC

16

8005h

0000h

да

да

0000h

CRC-32

32

04C11DB7h

FFFFFFFFh

да

да

FFFFFFFFh

CRC-64

64

60034000F050Bh

FAC432B10CD5E44Ah

да

да

FFFFFFFFFFFFFFFFh

Таблица 1  параметры подсчета CRC, используемые в различных алгоритмах

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

04C11DB7h: 00000100110000010001110110110111

EDB88320h: 11101101101110001000001100100000

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

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


Содержание раздела