1. Общие сведения
2. Побитовый метод вычисления
3. CRC32 с использованием таблиц
4. Как получить на выходе нуль
5. Применение на практике
6. Послесловие
1. Общие сведения
CRC или "Cyclic Redundancy Check" (контроль циклически избыточным кодом) - это одна из разновидностей подсчёта контрольной суммы блока данных. Например, простейшей проверкой целостности информации можно считать использование бита чётности (или паритета, что одно и то-же). Это когда суммируются все биты передаваемого сообщения, и если сумма оказывается чётной, то в конец сообщения добавляется 0, если нечётной – то 1. При приёме повторно пересчитывается сумма битов, и сравнивается с принятым битом чётности. Если они отличаются, значит при передаче имеем потери.
Но такой способ определения ошибок оставляет желать лучшего, т.к. во-первых на каждый байт требуется лишний бит паритета(9), а во-вторых при искажении не одного, а нескольких битов сообщения, чётность суммы может не измениться. Поэтому существует множество более продвинутых проверок, в том числе CRC.
По сути CRC это не сумма, а остаток от деления некоего объёма информации на константу. Тем не менее, CRC исторически называют "контрольная сумма". Алгоритм считается потоковым (а не блочным), когда в итоговое значение CRC вносит вклад каждый бит. Если хоть один из них сломается, контрольная сумма тут-же слетит, причём существенно.
Что такое исходное сообщение понятно - это последовательность бит произвольной длины. Но что за константа, на которую мы должны делить сообщение?
Это число в диапазоне 16/32/64-бита, которое назвали "Полином". В таблице ниже представлены общепринятые из них. Значения с зеркальным отражением бит используются, когда данные поступают от младшего бита к старшему "Little Endian". Для тех кто в танке, little endian - это способ хранения многобайтных чисел в памяти компьютера, при котором младший байт записывается по наименьшему адресу, а старший - по наибольшему. Это основной стандарт для компьютеров на базе х86. Например число
Как видно из этой таблички, помимо полинома в расчётах принимает участие значение инициализации, а так-же значение XOR уже готового CRC на выходе. Значение Init - это CRC на старте, что позволяет вычислять контрольную сумму данных со-значением нуль (на случай, если данные начинаются с нуля). Соответственно на выходе из функции нужно будет внести эту поправку, для чего и предусмотрено значение "XOR out".
CRC-32 настолько популярен, что начиная с м/архитектуры "Nehalem" в набор SSE4.2 процессоров Intel была включена специальная инструкция
2. Побитовый метод вычисления CRC-32
В простом варианте вычисление контрольной суммы сводится к следующему:
Вот реализация этого алгоритма, которая оформлена в процедуру:
Недостатком данного метода является XOR над каждым из 8-битов байта. Так, если блок данных имеет размер 1 МБ, то придётся прокрутить 8 млн.операций, что несомненно окажет отрицательное влияние на скорость выполнения расчёта. Поэтому алго побитового вычисления CRC32 рекомендуют для небольших объёмов данных, а в идеале нужно использовать т.н. "Табличный метод".
3. CRC32 с использованием таблиц
Таблица играет ключевую роль в оптимизации вычисления CRC - разберём её подробно.
Значение байта данных может лежать в диапазоне 0-255. Суть в том, что мы заранее в цикле вычисляем CRC32 для всех возможных значений 0-255, и помещаем эти шаблоны в таблицу, которая займёт в памяти
Теперь у нас есть таблица, и можно выбирать из неё значения CRC32 для каждого из возможных байтов так. Адресация вида
Для лучшего понимания проведём аналогию.
Пусть нам нужно умножить числа от 0 до 255 на 43:
Таблица CRC делает то же самое: предвычисляет результат всех возможных комбинаций из 256 вариантов, чтобы не тратить время на побитовые операции.
4. Как на выходе получить CRC32 = нуль
У обоих методов выше (по-битовый, табличный) есть один общий недостаток - если мы хотим периодически проверять контрольную сумму блока данных, то оригинальный CRC приходится где-то хранить, что не есть гуд. Поэтому после повторного пересчёта, CRC данных в идеале должна быть равна нулю, тогда и оригинал будет не нужен.
Учитывая, что в основе алгоритма CRC лежит XOR, получить на выходе нуль довольно легко - для этого достаточно пересчитать сумму блока как обычно, после чего применив операцию
5. Применение CRC32 на практике
Рассмотрим пример, когда алгоритмом CRC32 охраняется критический блок в секции-кода нашего приложения. Такой расклад можно наблюдать, если взломщик планирует обратить условие перехода
Если собрать сейчас этот исходник по F9 в окне fasm'a, то получим мессагу, мол в охраняемую зону проник нарушитель. Оно и ясно, ведь доп.поток приложения проверяет CRC на нуль, и пока мы не добавим исходный "CRC32 value" в хвост блока (конец охранной зоны), окно с ошибкой так и будет всплывать.
Пропатчить экзешник можно прямо в отладчике x64dbg. Значит открываем бинарь, и спустившись до
Теперь можно сказать, что код нашей прожки защищён от модификации, т.к. доп.поток с периодом 1-сек будет в цикле пересчитывать его контрольную сумму CRC32. Попробуйте по аналогичной схеме изменить сейчас
6. Послесловие
Под занавес приведём пример расчёта CRC32 аппаратным способом через инструкцию SSE4.2
Линк по теме:
Неплохой обзор алгоритма CRC32
2. Побитовый метод вычисления
3. CRC32 с использованием таблиц
4. Как получить на выходе нуль
5. Применение на практике
6. Послесловие
1. Общие сведения
CRC или "Cyclic Redundancy Check" (контроль циклически избыточным кодом) - это одна из разновидностей подсчёта контрольной суммы блока данных. Например, простейшей проверкой целостности информации можно считать использование бита чётности (или паритета, что одно и то-же). Это когда суммируются все биты передаваемого сообщения, и если сумма оказывается чётной, то в конец сообщения добавляется 0, если нечётной – то 1. При приёме повторно пересчитывается сумма битов, и сравнивается с принятым битом чётности. Если они отличаются, значит при передаче имеем потери.
Но такой способ определения ошибок оставляет желать лучшего, т.к. во-первых на каждый байт требуется лишний бит паритета(9), а во-вторых при искажении не одного, а нескольких битов сообщения, чётность суммы может не измениться. Поэтому существует множество более продвинутых проверок, в том числе CRC.
По сути CRC это не сумма, а остаток от деления некоего объёма информации на константу. Тем не менее, CRC исторически называют "контрольная сумма". Алгоритм считается потоковым (а не блочным), когда в итоговое значение CRC вносит вклад каждый бит. Если хоть один из них сломается, контрольная сумма тут-же слетит, причём существенно.
Что такое исходное сообщение понятно - это последовательность бит произвольной длины. Но что за константа, на которую мы должны делить сообщение?
Это число в диапазоне 16/32/64-бита, которое назвали "Полином". В таблице ниже представлены общепринятые из них. Значения с зеркальным отражением бит используются, когда данные поступают от младшего бита к старшему "Little Endian". Для тех кто в танке, little endian - это способ хранения многобайтных чисел в памяти компьютера, при котором младший байт записывается по наименьшему адресу, а старший - по наибольшему. Это основной стандарт для компьютеров на базе х86. Например число
0x12345678 будет храниться в ОЗУ как: 78 56 34 12. В отличие от него "Big-Endian" располагает байты в порядке убывания (как мы пишем на листе бумаги), и в комп.системах используется при передачи данных по сети. Таким образом, документированным полиномом для CRC-32 является значение 0xEDB88320 - именно его мы и будем использовать в своём коде.
Как видно из этой таблички, помимо полинома в расчётах принимает участие значение инициализации, а так-же значение XOR уже готового CRC на выходе. Значение Init - это CRC на старте, что позволяет вычислять контрольную сумму данных со-значением нуль (на случай, если данные начинаются с нуля). Соответственно на выходе из функции нужно будет внести эту поправку, для чего и предусмотрено значение "XOR out".
CRC-32 настолько популярен, что начиная с м/архитектуры "Nehalem" в набор SSE4.2 процессоров Intel была включена специальная инструкция
CRC32, которая служит для аппаратного ускорения вычисления контрольной суммы. Она использует полином от Castagnoli = 0x1EDC6F41, и позволяет обрабатывать байты, слова или двойные слова в потоке данных, всего за один такт. Перед использованием инструкции необходим тест на поддержку через cpuid eax,1 - если взведён бит(20) в регистре ECX, значит ок, иначе задействуем перечисленные ниже программные методы вычисления CRC-32.
2. Побитовый метод вычисления CRC-32
В простом варианте вычисление контрольной суммы сводится к следующему:
1. Начинаем с 32-битной контрольной суммы 0xffffffff.
2. Сдвинуть предыдущее 32-битное значение CRC вправо на 8-бит.
3. XOR значения из пункта(2) с полиномом, чтобы получить новое значение CRC.
4. Повторить пункты(2,3) по всей длине данных.
5. После завершения цикла выполните XOR вычисленного значения CRC с 0xffffffff (можно NOT).
6. Это окончательный результат CRC32.
Вот реализация этого алгоритма, которая оформлена в процедуру:
C-подобный:
;//==============================================
;// Версия для малых объёмов данных (медленная)
;// На входе: ESI = адрес данных, ECX = длина
;// На выходе: EAX = CRC32
;//==============================================
calc_crc32_slow:
push ebx ecx edx
mov eax, 0xFFFFFFFF ;// начальное значение CRC32
or ecx, ecx ;// есть что считать?
jz @done_slow ;// нет - на выход.
@calc_loop_slow:
movzx ebx, byte[esi] ;// загружаем очередной байт данных
xor eax, ebx ;// ксор с CRC
mov edx, 8 ;// обрабатываем все 8-бит байта
@bit_loop:
shr eax, 1 ;// сдвиг вправо на 1
jnc @no_xor ;// пропустить, если выдвинулся нуль
xor eax, 0xEDB88320 ;// иначе: ксор с полиномом
@no_xor:
dec edx ;// счётчик бит -1
jnz @bit_loop ;// повторить для всех 8-бит
inc esi ;// следующий байт данных
dec ecx ;// длина -1
jnz @calc_loop_slow ;// на повтор, если не конец.
@done_slow:
xor eax, 0xFFFFFFFF ;// финальный "XOR out" на выходе (см.таблицу выше)
pop edx ecx ebx
retНедостатком данного метода является XOR над каждым из 8-битов байта. Так, если блок данных имеет размер 1 МБ, то придётся прокрутить 8 млн.операций, что несомненно окажет отрицательное влияние на скорость выполнения расчёта. Поэтому алго побитового вычисления CRC32 рекомендуют для небольших объёмов данных, а в идеале нужно использовать т.н. "Табличный метод".
3. CRC32 с использованием таблиц
Таблица играет ключевую роль в оптимизации вычисления CRC - разберём её подробно.
Значение байта данных может лежать в диапазоне 0-255. Суть в том, что мы заранее в цикле вычисляем CRC32 для всех возможных значений 0-255, и помещаем эти шаблоны в таблицу, которая займёт в памяти
256х4=1КБ. Теперь когда будем читать поток данных по-байтно, то значение этого байта можно будет использовать в качестве (!)индекса в таблице (порядкового номера), чтобы выбрать из неё уже предвычисленное значение CRC. Как результат мы избавляемся от проходов по всем 8-битам байта, что увеличит скорость в ~8 раз. Табличный метод оправдывает себя на больших массивах данных, и его нецелесообразно использовать, например, для строки "Hello World!". Вот как это дело реализовать на практике:
C-подобный:
;//=============================
;// Для начала создаём таблицу
;//=============================
init_crc_table:
mov ecx, 0 ;// для всех байтов от 0 до 255
@create:
mov eax, ecx ;// текущий байт
;// Обрабатываем по 8-бит (как в медленном методе)
mov edx, 8
@process_bit:
shr eax,1
jnc @skip_xor
xor eax, 0xEDB88320
@skip_xor:
dec edx
jnz @process_bit
;// Сохраняем результат для этого байта в таблице
mov [crc_table + ecx*4], eax
inc ecx
cmp ecx, 256
jb @createТеперь у нас есть таблица, и можно выбирать из неё значения CRC32 для каждого из возможных байтов так. Адресация вида
esi+ebx*4 называется базово-индексной с масштабированием (Base-Indexed with Scale), или адресацией SIB (Scale-Index-Base). Она используется для доступа к элементам массивов, где esi = базовый адрес, ebx = индекс, а 4 = масштаб (размер элемента 4 байта):
C-подобный:
calc_crc32_fast:
mov eax, 0xFFFFFFFF
@calc_loop:
movzx ebx, byte[esi] ;// 1. загружаем байт
xor bl, al ;// 2. xor с младшим байтом CRC
movzx ebx,bl ;// 3. индекс в таблице (0-255)
shr eax,8 ;// 4. сдвигаем CRC
xor eax,[crc_table + ebx*4] ;// 5. xor с табличным значением
inc esi ;// следующий байт
dec ecx ;// конец данных?
jnz @calc_loop ;// нет - продолжить.
xor eax,0xFFFFFFFF ;// финальный "xor out"Для лучшего понимания проведём аналогию.
Пусть нам нужно умножить числа от 0 до 255 на 43:
Таблица CRC делает то же самое: предвычисляет результат всех возможных комбинаций из 256 вариантов, чтобы не тратить время на побитовые операции.
4. Как на выходе получить CRC32 = нуль
У обоих методов выше (по-битовый, табличный) есть один общий недостаток - если мы хотим периодически проверять контрольную сумму блока данных, то оригинальный CRC приходится где-то хранить, что не есть гуд. Поэтому после повторного пересчёта, CRC данных в идеале должна быть равна нулю, тогда и оригинал будет не нужен.
Учитывая, что в основе алгоритма CRC лежит XOR, получить на выходе нуль довольно легко - для этого достаточно пересчитать сумму блока как обычно, после чего применив операцию
not crc32, добавить инверсный CRC в хвост блока данных, младшим байтом вперёд Little-Endian. Если после этого обратно пересчитать CRC с учётом добавленного дворда, то получим нуль, что собственно и требовалось доказать. Вот пример:
C-подобный:
format pe console
entry start
include 'win32ax.inc'
section '.data' data readable writeable
crc_table dd 256 dup(0)
test_string db 'Hello, World!',0
test_len = $ - test_string -1
data_with_crc rb 256 ;// буфер для данных + CRC
;//----------
section '.code' code readable executable
;// ======================================
;// Инициализация таблицы CRC32
;// ======================================
init_crc_table:
push ebx ecx edx
xor ecx,ecx ;// байт(0) из 256
@generate_table:
mov eax,ecx ;// текущий байт
mov edx,8 ;// счётчик бит
@process_bit:
shr eax,1 ;// сдвиг на 1-бит вправо
jnc @skip_xor ;// если бит не был установлен
xor eax,0xEDB88320 ;// иначе ксор с полиномом
@skip_xor:
dec edx ;// повтор для всех 8-бит
jnz @process_bit
mov [crc_table + ecx*4],eax ;// сохраняем в таблицу
inc ecx
cmp ecx,256 ;// заполняем всю таблицу до 256 двордов
jb @generate_table
pop edx ecx ebx
ret
;//==================================
;// Вычисление CRC32
;// Вход: ESI - данные, ECX - длина
;// Выход: EAX - CRC32
;//==================================
align 16
calc_crc32:
push ebx edx esi ecx
mov eax,0xFFFFFFFF ;// начальное значение CRC-32
or ecx,ecx
jz @done
@calc_loop:
movzx ebx,byte[esi] ;// берём очередной байт данных
xor bl,al ;// XOR с младшим байтом CRC
movzx ebx,bl ;// расширяем до 32-бит
shr eax,8 ;// сдвиг CRC вправо на 8-бит
xor eax,[crc_table + ebx*4] ;// XOR с значением из таблицы!
inc esi ;// следующий байт данных..
dec ecx ;// это конец данных?
jnz @calc_loop ;// нет на повтор
@done: xor eax,0xFFFFFFFF ;// финальный: CRC32 xor -1
pop ecx esi edx ebx
ret
;//===============================
;// Точка входа в программу
;//===============================
align 16
start: call init_crc_table
cinvoke printf,<10,' Length of the data string: %d byte',0>,test_len
;// 1. Вычисляем CRC для исходной строки
mov esi,test_string
mov ecx,test_len
call calc_crc32
push eax
cinvoke printf,<10,' CRC32 of "Hello, World!" : 0x%08X',10,0>,eax
;// 2. Копируем данные в буфер (без нуль-терминатора)
mov esi,test_string
mov edi,data_with_crc
mov ecx,test_len
rep movsb
;// 3. Добавляем CRC в конец данных
pop eax
not eax ;// обязательная инверсия!
mov [edi],eax ;// записываем 4 байта CRC
;// 4. Обратно вычисляем CRC теперь для всего буфера
cinvoke printf,<10,' Buffer length (data+CRC) : %d bytes',0>,test_len +4
mov esi,data_with_crc
mov ecx,test_len +4
call calc_crc32
xor eax,-1 ;// 0xFFFFFFFF
cinvoke printf,<10,' Result CRC32 (data+CRC) : 0x%08X',0>,eax
cinvoke getch
cinvoke exit,0
;//-------------
section '.idata' import data readable writeable
library msvcrt, 'msvcrt.dll'
import msvcrt, printf,'printf', getch,'_getch',exit,'exit'5. Применение CRC32 на практике
Рассмотрим пример, когда алгоритмом CRC32 охраняется критический блок в секции-кода нашего приложения. Такой расклад можно наблюдать, если взломщик планирует обратить условие перехода
JZ на JNZ при проверке, скажем, пароля. Значит пишем обычное приложение для запроса секретного слова (точнее суммы его байт, аля хэша), а в дополнительном потоке с периодом 1-сек будем пересчитывать контрольную сумму охраняемого блока (защита от on-line патча). Если получим CRC32 отличную от нуля, сразу включаем сирену, выводим мессагу и на выход. Чтобы реализовать эту схему, нужно:1. Встроить в код отладочную процедуру, которая покажет исходную сумму CRC32(1).
2. Теперь делаем not crc32(1) и записываем получившееся значение в хвост блока данных.
C-подобный:
format pe console
entry start
include 'win32ax.inc'
section '.data' data readable writeable
crc_table dd 256 dup(0)
pass dd 'C'+'o'+'d'+'e'+'b'+'y' ;// хэш пароля
align 16
buff db 0
;//----------
section '.code' code readable executable
;//================================
;// Инициализация таблицы CRC32
;//================================
init_crc_table:
push ebx ecx edx
xor ecx,ecx ;// байт(0) из 256
@generate_table:
mov eax,ecx ;// текущий байт
mov edx,8 ;// счётчик бит
@process_bit:
shr eax,1 ;// сдвиг на 1-бит вправо
jnc @skip_xor ;// если бит не был установлен
xor eax,0xEDB88320 ;// иначе ксор с полиномом
@skip_xor:
dec edx ;// повтор для всех 8-бит
jnz @process_bit
mov [crc_table + ecx*4],eax ;// сохраняем в таблицу
inc ecx
cmp ecx,256 ;// заполняем всю таблицу до 256 двордов
jb @generate_table
pop edx ecx ebx
ret
;//==================================
;// Вычисление CRC32
;// Вход: ESI - данные, ECX - длина
;// Выход: EAX - CRC32
;//==================================
align 16
calc_crc32:
push ebx edx esi ecx
mov eax,0xFFFFFFFF ;// начальное значение CRC-32
or ecx,ecx
jz @done
@calc_loop:
movzx ebx,byte[esi] ;// берём очередной байт данных
xor bl,al ;// XOR с младшим байтом CRC
movzx ebx,bl ;// расширяем до 32-бит
shr eax,8 ;// сдвиг CRC вправо на 8-бит
xor eax,[crc_table + ebx*4] ;// XOR с значением из таблицы!
inc esi ;// следующий байт данных..
dec ecx ;// это конец данных?
jnz @calc_loop ;// нет на повтор
@done: xor eax,0xFFFFFFFF ;// финальный: CRC32 xor -1
pop ecx esi edx ebx
ret
;//==============================
;// Поток для проверки CRC32
;//==============================
proc CheckCrcThread lpParam
@@: invoke Sleep,1000
mov esi,@testPass
mov ecx,@endBlock - @testPass
add ecx,4
call calc_crc32
not eax
or eax,eax
jz @b
invoke MessageBox,0,<'Warning! Code is modified!',0>,0,0
invoke ExitThread,0
ret
endp
;//===============================
;// Точка входа в программу
;//===============================
align 16
start: call init_crc_table
mov esi,@testPass ;//<--------- Дебаг код (потом можно убрать)
mov ecx,@endBlock - @testPass
call calc_crc32
not eax ;//<--------- Это значение нужно добавить по адресу @endBlock
cinvoke printf,<10,' CRC32 value : 0x%08X',0>,eax
invoke CreateThread,0,0,CheckCrcThread,0,0,0 ;// создаём поток
cinvoke printf,<10,' Type password: ',0>
xor ebx,ebx
mov eax,ebx
@@: cinvoke getch ;// принимаем пасс у юзера
cmp al,13 ;// это Enter?
je @stop ;// да - на выход
add ebx,eax ;// считаем сумму
jmp @b ;// продолжить..
@stop: cmp ebx,[pass] ;//<-------------- Проверка пароля
;//*****************************************
;// Начало охранной зоны
;//*****************************************
@testPass:
jz @01 ;//<-------------- Уязвимое условие
cinvoke printf,<'Wrong password!',0>
jmp @end
@01: cinvoke printf,<'Pass Okey!',0>
@end: cinvoke getch
cinvoke exit,0
@endBlock:
;//*****************************************
;// Конец охранной зоны
;//*****************************************
section '.idata' import data readable writeable
library kernel32,'kernel32.dll', user32,'user32.dll', msvcrt,'msvcrt.dll'
include 'api\kernel32.inc'
include 'api\user32.inc'
import msvcrt, printf,'printf', scanf,'scanf',\
getch,'_getch' , exit, 'exit'Если собрать сейчас этот исходник по F9 в окне fasm'a, то получим мессагу, мол в охраняемую зону проник нарушитель. Оно и ясно, ведь доп.поток приложения проверяет CRC на нуль, и пока мы не добавим исходный "CRC32 value" в хвост блока (конец охранной зоны), окно с ошибкой так и будет всплывать.
Пропатчить экзешник можно прямо в отладчике x64dbg. Значит открываем бинарь, и спустившись до
call exit жмём пробел = "Ассемблирование". В появившемся окне вводим значение дворда dd 8b9116f6 --> OK, и далее применим патч комбинацией Ctrl+P. Сохранять пропатченный EXE нужно под другим именем, и если потом запустить его, то окно с ошибкой уже пропадёт.Процесс добавления CRC32 в хвост кода
Окно применения патча по Ctrl+P
Окно применения патча по Ctrl+P
Теперь можно сказать, что код нашей прожки защищён от модификации, т.к. доп.поток с периодом 1-сек будет в цикле пересчитывать его контрольную сумму CRC32. Попробуйте по аналогичной схеме изменить сейчас
JZ на JNZ после ввода пароля (метка @testPass), как тут-же всплывёт мессага выше с варнингом.6. Послесловие
Под занавес приведём пример расчёта CRC32 аппаратным способом через инструкцию SSE4.2
crc32. На каждый байт она расходует всего 1-такт, что позволяет получить скорость гепарда. Вот пример:
C-подобный:
;// Проверка поддержки CRC32 инструкций
check_crc32_support:
push ebx
mov eax, 1
cpuid
test ecx, (1 << 20) ;// бит 20 - поддержка SSE4.2
jnz @supported
pop ebx
xor eax, eax ;// нет поддержки
ret
@supported:
pop ebx
mov eax, 1
ret
;//-----------------
;// Аппаратное вычисление CRC32 (только для SSE4.2)
;// На входе: ESI = адрес начала блока, ECX = длина
;//-----------------
calc_crc32_hardware:
push ebx
mov eax, 0xFFFFFFFF ;// начальное значение
or ecx, ecx
jz @done_hw
@calc_hw_loop:
movzx ebx, byte[esi]
crc32 eax, bl ;// аппаратная инструкция CRC32
inc esi
dec ecx
jnz @calc_hw_loop
@done_hw:
xor eax, 0xFFFFFFFF
pop ebx
retЛинк по теме:
Неплохой обзор алгоритма CRC32
Ссылка скрыта от гостей
