CRC-32

CRC-32 — это циклический избыточный код (Cyclic Redundancy Check) длиной 32 бита, алгоритм вычисления контрольной суммы, предназначенный для обнаружения случайных или преднамеренных изменений в цифровых данных. CRC-32 является одной из наиболее распространённых разновидностей семейства CRC, широко применяется в сетевых протоколах, архиваторах, файловых системах и при передаче данных по каналам связи.

История

Алгоритмы циклического избыточного кода были разработаны в 1960-х годах и основаны на теории полиномиальных кодов. В 1975 году Уэсли Питерсон опубликовал фундаментальные работы, заложившие математическую основу CRC. Конкретная реализация CRC-32 с полиномом 0x04C11DB7 была стандартизирована в 1988 году в спецификации IEEE 802.3 для Ethernet. Впоследствии этот вариант получил название CRC-32/ISO-HDLC или просто CRC-32.

В 1990-х годах алгоритм стал обязательным компонентом многих протоколов и форматов данных, включая ZIP, Gzip, PNG, и TCP/IP. В 2000-х годах появились модификации, такие как CRC-32C (Castagnoli), используемые в современных файловых системах (NTFS, Btrfs) и протоколах (iSCSI).

Математические основы

CRC-32 основан на делении двоичного сообщения, представленного в виде полинома, на фиксированный порождающий полином 32-й степени. Остаток от деления длиной 32 бита и является контрольной суммой. Операция выполняется в поле Галуа GF(2) с использованием операции XOR (исключающее ИЛИ) без переносов.

Порождающий полином для стандартного CRC-32 (IEEE 802.3): \[ x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^{8} + x^{7} + x^{5} + x^{4} + x^{2} + x + 1 \] В шестнадцатеричной записи этот полином представляется как 0x04C11DB7.

Параметры алгоритма

Стандартный CRC-32 (ISO-HDLC) имеет следующие параметры:

• Длина выходного значения: 32 бита (4 байта)
• Полином: 0x04C11DB7
• Начальное значение: 0xFFFFFFFF
• Конечный XOR: 0xFFFFFFFF
• Порядок бит: от старшего к младшему (MSB first)
• Порядок байт: от старшего к младшему (big-endian)

Эти параметры обеспечивают детектирование всех однобитных и двухбитных ошибок, всех ошибок нечётной длины, а также любых пакетов ошибок длиной до 32 бит.

Вычисление

Табличный метод

Наиболее эффективный способ вычисления CRC-32 — использование таблицы поиска (lookup table). Алгоритм предварительно вычисляет таблицу из 256 значений, каждое из которых представляет CRC для одного байта. Затем для каждого байта входных данных выполняется операция XOR с текущим значением CRC, и результат используется как индекс в таблице.

Псевдокод табличного вычисления: ``` создать таблицу table[256] для i от 0 до 255: crc = i для j от 0 до 7: если crc & 1: crc = (crc >> 1) XOR полином иначе: crc = crc >> 1 table[i] = crc

crc = 0xFFFFFFFF для каждого байта data: index = (crc XOR data) & 0xFF crc = (crc >> 8) XOR table[index] crc = crc XOR 0xFFFFFFFF ```

Аппаратная реализация

В современных процессорах (например, Intel SSE4.2, ARM NEON) существуют инструкции для аппаратного вычисления CRC-32, что позволяет достигать скорости до нескольких гигабайт в секунду. Аппаратные реализации используют параллельные вычисления с несколькими байтами за такт.

Применение

Сетевые протоколы

CRC-32 является обязательным элементом кадра Ethernet (поле FCS — Frame Check Sequence), а также используется в протоколах PPP, ATM, Fibre Channel. В протоколе TCP/IP контрольная сумма заголовка вычисляется по алгоритму, отличному от CRC-32, но для целостности данных на канальном уровне применяется именно CRC-32.

Файловые системы

• NTFS (Windows): использует CRC-32 для проверки целостности метаданных и записей MFT (Master File Table).
• Btrfs (Linux): применяет CRC-32C для проверки целостности данных и метаданных.
• FAT32: не использует CRC-32, но в некоторых реализациях применяется для проверки загрузочного сектора.

Архиваторы и форматы сжатия

• ZIP: использует CRC-32 для проверки целостности каждого файла внутри архива.
• Gzip: применяет CRC-32 в конце сжатого потока.
• PNG: использует CRC-32 для проверки каждого чанка (куска) изображения.

Проверка целостности данных

CRC-32 широко применяется в утилитах проверки целостности файлов, таких как cksum (Unix/Linux), crc32 (Windows), а также в программах типа md5sum, хотя для криптографических целей CRC-32 не подходит.

Критика и ограничения

Некриптографическая стойкость

CRC-32 не является криптографической хеш-функцией. Он не обладает свойством необратимости и устойчивости к коллизиям. Для намеренного подбора данных с заданной контрольной суммой требуется всего около 2^32 операций, что делает алгоритм уязвимым для атак. Для защиты от злонамеренных изменений следует использовать SHA-256, SHA-3 или BLAKE2.

Коллизии

Из-за небольшой длины (32 бита) вероятность случайной коллизии для двух различных наборов данных составляет 1/2^32 ≈ 2.3×10^{-10}. Для больших объёмов данных (например, миллиарды файлов) коллизии становятся вероятными. В 2004 году было показано, что CRC-32 не может гарантировать отсутствие коллизий даже для файлов размером более 4 ГБ.

Ограниченная обнаруживающая способность

CRC-32 не обнаруживает некоторые типы ошибок, такие как:

• Ошибки, кратные длине полинома (32 бита)
• Ошибки, при которых изменённые биты образуют полином, кратный порождающему
• Ошибки в определённых комбинациях, характерных для конкретных каналов связи

Разновидности CRC-32

Существует несколько вариантов CRC-32, различающихся полиномом, начальным значением и порядком бит:

CRC-32C, предложенный в 1993 году, обладает лучшей обнаруживающей способностью для пакетов ошибок длиной до 32 бит и рекомендуется для использования в современных системах хранения данных.

Интересные факты

• Алгоритм CRC-32 может быть реализован на языке C всего в нескольких десятках строк кода, что делает его одним из самых компактных алгоритмов контрольной суммы.
• В 1996 году в протоколе TCP была обнаружена ошибка, связанная с неправильным вычислением CRC-32 в заголовках, что привело к необходимости патча для всех реализаций стека.
• CRC-32 используется в формате PNG для проверки каждого чанка, что позволяет обнаруживать ошибки при передаче изображений даже при частичной загрузке.
• В некоторых системах (например, в старых версиях Microsoft Windows) CRC-32 применялся для проверки целостности исполняемых файлов, но был заменён на SHA-1 из-за низкой криптостойкости.

Источники

• Peterson, W. W., & Brown, D. T. (1961). Cyclic Codes for Error Detection. Proceedings of the IRE.
• IEEE Standard 802.3-2018: Ethernet.
• RFC 3385: Internet Protocol Small Computer System Interface (iSCSI) CRC Considerations.
• Koopman, P. (2002). 32-Bit Cyclic Redundancy Codes for Internet Applications. Proceedings of the International Conference on Dependable Systems and Networks.
• Castagnoli, G., et al. (1993). Optimization of Cyclic Redundancy-Check Codes with 24 and 32 Parity Bits. IEEE Transactions on Communications.