Как обратный инжиниринг неизвестного алгоритма CRC

Понимание основ CRC

Алгоритм CRC можно полностью определить несколькими ключевыми параметрами, которые необходимо выявить при обратном проектировании:

• Полином – генераторный полином, используемый в расчёте CRC
• Начальное значение – стартовое значение регистра CRC
• Финальный XOR – значение, применяемое к регистру CRC перед выводом
• Отражение входа – обрабатываются ли байты входа LSB‑first или MSB‑first
• Отражение выхода – отражаются ли конечные биты CRC
• Выходной XOR – XORится ли конечный CRC с константой

Согласно руководству Грега Эвингa по обратному проектированию CRC, алгоритмы CRC по сути являются делением над полиномами GF(2), где сообщение рассматривается как полином и делится на генераторный полином. Остаток от деления становится значением CRC.

Математическое соотношение можно записать так:

CRC = (Message × 2^n) mod Polynomial

где n – ширина CRC (в данном случае 32 бита).

Стратегия сбора данных от орклада

Систематическое тестирование входов

Чтобы успешно провести обратное проектирование алгоритма CRC, необходимо собрать систематические пары вход‑выход от вашего орклада. Начните с простых, контролируемых входов:

1. Тесты на один байт – проверка от 0x00 до 0xFF
2. Последовательные нулевые байты – 1, 2, 3, … до 32+ нулевых байтов
3. Паттерны степени двойки – 0x01, 0x02, 0x04, 0x08 и т.д.
4. Известные паттерны – 0xFF, 0xAA, 0x55

Как отмечено в исследовании, многие результаты контрольных сумм простых входов встречаются в онлайн‑таблицах остатков CRC, что может дать ценную подсказку о полиноме.

Использование свойств XOR

Ваше наблюдение о свойствах XOR имеет математическое значение:

• XOR‑инг нечётного количества валидных файлов с добавленным CRC создаёт ещё один валидный файл
• XOR‑инг чётного количества валидных файлов с добавленным CRC создаёт недействительный файл

Это поведение указывает на то, что алгоритм CRC линейный над GF(2), фундаментальное свойство CRC‑алгоритмов. Линейность позволяет использовать математические соотношения для вывода параметров алгоритма.

Математические техники анализа

Анализ изменения одного бита

Мощная техника, упомянутая в исследовании, – изменять только один бит данных и наблюдать изменение CRC. Как отметил один участник Stack Overflow: «когда я меняю только 1 бит данных и XOR‑ю его, результат – все нули, кроме этого бита и последних двух байтов».

Эта техника работает потому, что:

CRC(message с одним битовым изменением) = CRC(original message) XOR (полиномиальный эффект)

Постепенно меняя отдельные биты и записывая изменения CRC, можно определить коэффициенты полинома.

Извлечение коэффициентов полинома

Используя метод изменения одного бита, можно извлечь коэффициенты полинома:

1. Начните с простого входа (например, 0x00) и запишите его CRC
2. Измените бит i (начиная с бита 0) и запишите новый CRC
3. Разница между двумя CRC раскрывает полиномиальный эффект на позиции бита

Согласно обсуждениям на Reverse Engineering Stack Exchange, «если C1 соответствует сообщению с 1 в позиции i, а C2 – сообщению с 1 в позиции i+1, то C1 получается применением одного цикла сдвига‑XOR к C2».

Расширенный алгоритм Евклида

В документации CRC RevEng упоминается, что расширенный алгоритм Евклида может использоваться для вычисления q(x), что важно для обратного проектирования отношений полиномов. Этот алгоритм помогает найти математические обратные связи, необходимые для идентификации параметров CRC.

Методы идентификации параметров

Обнаружение полинома

После сбора достаточного количества данных вход‑выход вы можете определить полином несколькими подходами:

1. Сравнение с базой данных CRC – используйте собранные контрольные суммы для поиска в каталогах CRC, например, на reveng.sourceforge.io/crc-catalogue
2. Анализ математических соотношений – используйте факт, что CRC – это деление над полиномами GF(2), чтобы сформулировать уравнения и решить неизвестные коэффициенты полинома
3. Линейный алгебраический подход – рассматривайте задачу как систему линейных уравнений над GF(2) и решайте её для неизвестных параметров

Выявление начального значения и XOR

Для нахождения начального значения и финального XOR:

1. Тест с нулевым входом – начните с входа из всех нулей и наблюдайте вывод
2. Сравнение с и без данных – разница раскрывает влияние начального значения
3. Использование свойства XOR – поскольку XOR‑инг валидных файлов сохраняет валидность, можно вывести параметры XOR

Выявление отражения

Отражение входа и выхода можно определить, сравнивая:

1. Эффекты порядка байтов – тестируйте те же данные с разным порядком байтов
2. Анализ битовых паттернов – ищите систематические инверсии или вращения битов
3. Использование известных свойств отражения – как отмечено Jason Sachs, «полярность битов и байтов просто определяет, как байты переводятся в коэффициенты полинома».

Проверка и верификация

После того как вы получили кандидаты на параметры, необходимо их проверить:

1. Тест с известными входами – используйте входы из вашей коллекции и убедитесь, что рассчитанный CRC совпадает с выводом орклада
2. Тест крайних случаев – проверка всех нулей, всех единиц и случайных паттернов
3. Проверка математических свойств – убедитесь, что наблюдаемые свойства XOR сохраняются с вашими параметрами
4. Кросс‑валидация – используйте разные входные паттерны, чтобы подтвердить, что параметры работают последовательно

Продвинутые инструменты обратного проектирования

CRC RevEng

Инструмент CRC RevEng специально разработан для обратного проектирования алгоритмов CRC. Согласно его документации, он «вычисляет CRC для любого из 113 предустановленных алгоритмов или пользовательского алгоритма любой ширины» и «обратно проектирует любой алгоритм CRC из достаточного количества корректно отформатированных пар сообщение‑CRC».

Анализ LFSR

Поскольку алгоритмы CRC реализуются с помощью линейных обратных регистров (LFSR), можно проанализировать структуру LFSR:

• Используйте техники анализа LFSR для моделирования поведения регистра
• Применяйте математику конечных полей для понимания обратного полинома
• Используйте соотношения циклов сдвига‑XOR для вывода реализации

Пользовательский математический анализ

Если автоматические инструменты не справляются, возможно, понадобится реализовать собственный математический анализ:

1. Формулировка полиномиальных уравнений – представьте расчёт CRC как операции над полиномами GF(2)
2. Решение системы – примените линейные алгебраические методы для решения неизвестных коэффициентов
3. Реализация и тестирование – создайте реализацию CRC с вашими параметрами и протестируйте её против орклада

Заключение

Обратное проектирование неизвестного 32‑битного алгоритма CRC с использованием орклада требует систематического математического подхода, сочетающего несколько техник:

1. Соберите систематические данные вход‑выход с простыми паттернами и контролируемыми изменениями
2. Примените анализ изменения одного бита для извлечения коэффициентов полинома и понимания математических соотношений
3. Используйте линейные свойства (например, наблюдаемые свойства XOR) для вывода параметров алгоритма
4. Применяйте полиномиальную математику над GF(2) для решения неизвестного генераторного полинома и других параметров
5. Проверьте результаты через всестороннее тестирование против орклада

Ключевой вывод: CRC‑алгоритмы обладают чётко определённой математической структурой, которую можно раскрыть через систематический анализ. Даже если автоматические инструменты не дадут результата, фундаментальные свойства CRC предоставляют путь к обратному проектированию конкретной реализации.

Источники

1. Reverse‑engineering CRC checksum algorithm from an oracle – Stack Overflow
2. Linear Feedback Shift Registers for the Uninitiated, Part XVII: Reverse‑Engineering the CRC – Jason Sachs
3. README for CRC RevEng 3.0.6
4. Reverse Engineering a CRC Algorithm – Greg Ewing
5. Catalogue of parametrised CRC algorithms
6. CRC RevEng: arbitrary‑precision CRC calculator and algorithm finder
7. Reverse engineering CRC – Stack Overflow
8. Reverse engineering unknown CRC – Stack Overflow
9. Reverse Engineering a 16‑bit CRC algortitm – Reverse Engineering Stack Exchange
10. Reverse Engineering Cyclic Redundancy Codes | Hackaday