Подсчет контрольной суммы прошивки

Как посчитать контрольную сумму CRC32, CRC16, CRC8

В интернете существует большое количество вариантов расчёта контрольной суммы CRC. Но что же собственно такое контрольная сумма и почему она рассчитывается именно так? Давайте разберёмся. А заодно напишем программу, которая будет рассчитывать CRC с заданными параметрами.

Что такое контрольная сумма (Checksum) и что с ней делать?

Обзоры

Вы собираетесь нажать кнопку загрузки и замечаете рядом с ней странный код. Кажется, не имеет никакого отношения к тому, насколько велик файл или на что вы должны обратить внимание. Так что вперед, получите файл и беда! Это не похоже на то, что вы ожидали.

Если бы только был быстрый способ узнать, совпадает ли только что загруженный вами элемент с файлом, который был на веб-сайте. Что ж, есть. Добро пожаловать в мир контрольных сумм!

Что за контрольная сумма (Checksum)?

Rонтрольная сумма (Checksum) — это число в форме двоичного или шестнадцатеричного значения, полученное из источника данных. Важные моменты, которые следует знать: контрольная сумма обычно намного меньше, чем источник данных, а также почти полностью уникальна. Это означает, что вероятность того, что некоторые другие данные дадут точно такую ​​же контрольную сумму, крайне маловероятна.

Давайте рассмотрим несколько примеров, первый из которых — это простой текстовый файл (ниже), содержащий важную информацию! Все файлы содержат данные, которые охватывают не только, скажем, текст, который мы видим — будут выделены биты, чтобы сообщить нам, какой это тип файла, как данные расположены и так далее…

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

Но пока давайте посмотрим на значение, которое мы получаем:

Сам по себе этот код нам ничего не говорит. Мы не можем полностью «взломать» его, чтобы выяснить, из какого набора нулей и единиц состоит текстовый файл. Однако предполагается, что он специфичен для этого конкретного файла, поэтому теперь давайте изменим исходный текстовый файл, переставив некоторые слова.

Изображение выше ясно показывает, что это все тот же текст и, следовательно, те же данные технически, но последовательность битов теперь другая. Контрольная сумма на этот раз такова:

Обратите внимание, что это одинаковая длина — это ключевой аспект процесса получения кода, но это совершенно другая контрольная сумма. Те же данные, другой порядок, совершенно новая контрольная сумма.

Но, возможно, этого следовало ожидать; в конце концов, изменения в файле были не совсем тривиальными. Итак, давайте посмотрим, что произойдет, когда мы изменим только одну букву во всем: посмотрим, сможете ли вы определить, какую из них!

Наблюдайте за барабанной дробью на заднем плане, пока мы смотрим на контрольную сумму этого почти не измененного файла.

Это изменение всего одной буквы снова дало нам еще один уникальный код. Когда дело доходит до контрольных сумм, в этом вся суть системы: любые изменения в исходном источнике данных, какими бы маленькими они ни были, должны приводить к полностью новой контрольной сумме, что позволяет очень легко увидеть, было ли что-то изменено.

Разобравшись с этим, давайте посмотрим, как все это работает!

2 Расчёт контрольной суммы CRC методом побитового сдвига

На основании всего вышеизложенного, давайте напишем функцию на языке Visual Basic .NET, которая будет рассчитывать контрольную сумму CRC, принимая ряд параметров, которые я описал выше, и возвращая значение CRC в виде 32-разрядного беззнакового числа.

Код расчёта CRC методом побитового сдвига на языке VB.NET

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

Предлагаемая программа плохо масштабируема. То есть она работает хорошо при вычислении контрольной суммы CRC для коротких сообщений, длиной до нескольких десятков килобайтов. Я писал её с целью только продемонстрировать работу простого алгоритма, и не занимался оптимизацией. При расчёте CRC для длинного сообщения, размером десятки или сотни мегабайтов, программа будет сильно загружать процессор и память, т.к. всё сообщение целиком загружается в очередь. Этому способствует метод преобразования числа в битовую последовательность, используя Queue(Of Boolean). Для работы с такими большими сообщениями желательно реализовать промежуточный буфер, который будет передавать сообщение в программу небольшими порциями.

Зато у этой программы есть одно преимущество: она может быть использована для расчёта CRC любого порядка, не обязательно 8, 16 или 32. Это может быть CRC5 или CRC49. Только для чисел больше 32-х разрядов нужно изменить соответствующим образом входные параметры – допустим, poly передавать не как UInteger, а как ULong, или передавать его в виде битового массива (тогда теоретически порядок CRC вообще будет неограничен).

Так что же делать с контрольной суммой (Checksum)?

Контрольная сумма позволяет легко проверить целостность данных, составляющих файл.

Представьте себе такой сценарий: вам нужно загрузить важный файл, который имеет решающее значение для работы компьютера. Действительно критично, настолько, что вы не хотите, чтобы в нем были какие-либо ошибки или сбои. У вас также медленное и нестабильное интернет-соединение, и вы беспокоитесь, что это может повлиять на скачивание файла.

Хост файла знает все это, поэтому он запускает алгоритм контрольной суммы для файла и помещает ответ на веб-страницу загрузки. Получив его, вы можете запустить тот же процесс и сравнить значения — если они совпадают, вы будете знать, что с файлом, который вы скачали, все в порядке.

И это основное использование контрольной суммы: проверка целостности данных, составляющих файл. Это можно сделать вручную, как мы вскоре увидим, или это может быть часть автоматизированной операции. Valve использует контрольные суммы на платформе Steam как часть процесса проверки файлов.

4 «Взлом» контрольной суммы CRC32 и CRC16

Кратко затронем вопрос «взлома» CRC32. И прежде всего давайте определимся с понятием «взлом» применительно к данному вопросу.

Если задача определения контрольной суммы некоторого массива данных – прямая задача, то «взлом» – это обратная задача, а именно: подгонка контрольной суммы под определённый массив данных.

Допустим, вы имеете файл и рассчитали его контрольную сумму. Вам нужно изменить в нём произвольное число байтов, сохранив при этом контрольную сумму. Сделать это совсем не сложно.

Для начала нужно посчитать обычным образом контрольную сумму CRC32, CRC16 или любую другую, какая вам нужна, для этого изменённого файла. Пусть это будет C1. Теперь нужно добавить такое же число нулевых байтов в конец файла, которое содержится в контрольной сумме (для CRC32 – 4 байта, для CRC16 – 2 байта, и т.д.). Можно простым перебором подобрать такое число C2, которое мы и запишем в эти нулевые байты. Ведь понятно, что полный диапазон всех допустимых значений CRC32 укладывается в 2 32

4,295 млрд. То есть за 4 с небольшим миллиарда итераций расчёта контрольной суммы с начальным содержимым регистра, равным С1, мы брутфорсом («в лоб», методом грубой силы) подберём нужное значение. При современных вычислительных мощностях это не составит проблемы. А уж «взломать» с помощью перебора CRC16 вообще дело нескольких секунд.

Можно ли разместить нулевые байты в середине или начале файла? Можно. К операции XOR применим сочетательный закон: a XOR (b XOR c) = (a XOR b) XOR c, поэтому можно с успехом разбить файл на 3 части: до вставки, после вставки, и сама вставка. Посчитать CRC для первых двух частей (C1 и C2 на иллюстрации), объединить их операцией XOR, заполнить этим числом начальное содержимое регистра, а затем «сбрутфорсить» CRC оставшейся третьей части X.

Есть более интеллектуальный и изящный способ подогнать CRC под нужное значение. Суть его в том, что вместо последовательного перебора всех подряд значений мы «прокручиваем назад» несколько раз (по числу байтов или битов контрольной суммы) наш табличный алгоритм или алгоритм побитового сдвига до тех пор, пока CRC не будет желаемой. На эту тему есть подробные и качественные материалы в сети.

Таким образом, напрашивается вывод: контрольная сумма типа CRC хорошо подходит для проверки целостности данных при случайных искажениях информации в канале передачи данных, но совершенно не подходит для защиты от намеренного взлома.

5 Программа для расчёта контрольной суммы по алгоритмам CRC32, CRC16 и CRC8

На основе приведённого алгоритма была написана программа – калькулятор для расчёта контрольных сумм по алгоритмам CRC32, CRC16 и CRC8 . Внешний вид окна приведён на рисунке. Программа работает под ОС Windows и требует .NET версии 3.5 .

Интерфейс программы для расчёта контрольной суммы по алгоритмам CRC32, CRC16 и CRC8

Программа позволяет рассчитывать CRC массива байтов (введённого в поле «Сообщение») или указанного файла. Все рассмотренные выше параметры контрольной суммы настраиваются через интерфейс программы.

Ну и напоследок выкладываю ссылки на архив, в архиве лежат: программа «Калькулятор CRC», оригинальная статья “A Painless Guide to CRC Error Detection Algorithms”, класс RocksoftCrcModel() на Visual Basic.NET и на C#.

Содержимое архива “CRC calculator”

Итак, подведём итоги. В этой статье мы:
– узнали, что такое контрольная сумма CRC и какие бывают её виды;
– научились считать CRC методом побитового сдвига и табличным методом;
– узнали алгоритмы «взлома» CRC и сделали вывод об области применимости контрольной суммы типа CRC.

Linux

Если вам нравятся прелести Linux, вам будет приятно узнать, что это тот же процесс, что и выше — запустите Терминал и введите sha1sum, sha256sum или sha512sum, а затем адрес файла, чтобы сгенерировать требуемый хэш.

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

Заключение

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

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

Но если хосты предлагают это, то, по крайней мере, теперь вы знаете, как использовать хеш — любая дополнительная вещь, которая дает вам немного больше уверенности, всегда хорошо.