Подделка CRC32, не преследуемая по закону
В общих чертах, идея "взлома" CRC заключается в добавлении к контролируемому блоку нескольких байт, подгоняющих конечную контрольную сумму под прежнее значение. Как легко показать, количество корректирующий равно разрядности контрольной суммы, то есть CRC16 требует двух, CRC32 – четырех, а CR-64 восьми байт, рассчитанных специальным образом (или полученных методом перебора, см. врезку "неизвестные алгоритмы и борьба с ними").
Как же их рассчитать? Помимо используемого алгоритма (включая такие интимные подробности как значение полинома, начальное значение и xor-out), необходимо знать откуда и докуда защита считает контрольную сумму. Выяснив это, необходимо решить другой, гораздо более щекотливый вопрос: собираемся ли мы внедрять корректирующие байты внутрь контролируемого блока или ограничимся их дописыванием. Если защитный механизм проверяет целостность всего блока, то лучше и проще всего будет дописать, как это подробно описано в руководстве "CRC and how to Reverse it" с приложенными к нему исходными текстами. Однако, длина контролируемого блока (в роли которого чаще всего выступает исполняемый файл) в этом случае заметно изменится! К тому же многие защитные механизмы контролируют целостность фиксированного участка и хоть дописывай байты, хоть не дописывай — защита не обратит на них никакого внимания, и CRC контролируемого блока после его модификации необратимо изменится!
Ниже приведен фрагмент исходного кода плагина "CRC" к утилите PEiD, которая как раз и дописывает 4'е корректирующих байта к модифицированному файлу. Пользуйтесь им на здоровье, только не спрашивайте, где взял.
#include<stdio.h>
unsigned long c,c2,p2,pol=0xEDB88320;
long n,k;
main()
{
printf("CRC32 Adjuster (c) 2001 by RElf @ HHT/2\n");
printf("Length of data: "); scanf("%ld",&n);
printf("Offset to patch: "); scanf("%ld",&k);
n = (n-k)<<3;
printf("Current CRC32: 0x"); scanf("%x",&c);
printf("Desired CRC32: 0x"); scanf("%x",&c2);
c ^= c2;
p2 = (pol << 1) | 1;
while(n--) if(c&0x80000000) c = (c<<1)^p2; else c<<=1;
printf("XOR masks:%02X%02X%02X%02X\n",c&0xff,(c>>8)&0xff,(c>>16)&0xff, c>>24);
}
Листинг 2 вот код от RElf' а для нахождения корректирующих байт ;)
Методика внедрения байт внутрь контролируемого блока гораздо более перспективна. Если это машинный код (где нужно исправить один условный переход на другой), нам наверняка удастся переписать несколько машинных команд так, чтобы высвободить место для 4х байт, не говоря уже о том, что компиляторы всюду вставляют NOP'ы для выравнивания. Если же это ключевой файл типа сертификата, что ж… втиснуться туда еще проще (хотя бы оттяпать от своего имени четыре символа, при условии, что там содержится имя).
Рассмотрим практический пример подделки CRC32 с little-endian порядком бит в потоке (наименее значимый бит располагается по меньшему адресу, то есть поток движется справа налево). Остальные алгоритмы взламываются аналогичным образом, с поправкой на специфику разрядности и направления потока.
Возьмем последовательность байт "A::::::::::::::::::::::::::::::::::D", контрольная сумма которой известна и равна CRC_OK, модифицируем ее некоторым образом, изменив один или несколько произвольно расположенных байт (они обозначены символом "x"): "A:::::x::::::::::::::::::::::::::xxx::::x:x:D", после чего контрольная сумма модифицированной последовательности будет CRC_NOT_OK, что очень нехорошо со всех точек зрения с какой только ни посмотри.
Подделка CRC начинается в выбора позиции "врезки" 4х корректирующих байт. С точки зрения алгоритма CRC их положение непринципиально и главным образом оно определяется внутренней структурой модифицируемого блока. Для наглядности, разместим корректирующие байты в середине "A:::::x::::::B_12_3_4_C:::::::xxx:::x:x:D".
Остается только рассчитать корректирующие байты _1_2_3_4_ и восстановить (в смысле "подделать") CRC. Будем действовать по шагам.
1) в точке "A" СRC равно начальному значению полинома (для CRC32 с отраженным полиномом EDB88320h это FFFFFFFFh). В точке "D" оно известно из условия задачи и равно CRC_OK;
2) если участок A-B не пуст — считаем CRC от точки "A" до точки "B", используя обычную процедуру update_CRC32(), исходный код которой приведен в листинге 3;
3) если участок C-D не пуст — считаем CRC от точки "C" до точки "D", используя инверсную процедуру reverse_crc32(), исходный код которой приведен в листинге 4;
4) двигаясь в обратном направлении от точки "C" к точке "B", вычисляем элементы CRC-таблицы, преобразующие CRC(C) в CRC(B), и запоминаем индексы этих элементов в массиве i (см. листинг 7).
5) двигаясь в прямом направлении от точки "B" к точке "C", по индексам, рассчитанным на шаге 4, вычисляем корректирующие байта _1_2_3_4_, записывания их в массив x (см. листинг 8).
Остается только переместить массив x на отрезок B-C, удостовериться, что контрольная сумма блока не изменилась, и бежать в ближайший ларек за свежим пивом (травой или грибами — это уже по вкусу).
Все необходимые для взлома листинги приводятся ниже. Обратите внимание на копирайт. За исключением первого и третьего из них, мыщъх не имеет к ним никакого отношения! Так что за хвост не дергать и ногами не пинать.
update_CRC32(unsigned long crc, unsigned char byte)
{
return crc32nornal[(unsigned char)crc ^ byte] ^ (crc >> 8);
}
Листинг 3 функция вычисления "прямого" CRC (см. шаг 2)
// (c)Dmitry Tomashpolski
reverse_crc32(unsigned long crc, unsigned char byte)
{
return ((crc<<8) ^ crc32inv[(unsigned char)(crc>>24)] ^ (byte));
}
Листинг 4 функция вычисления обратного CRC (см.
шаг 3)
gen_crc32()
{
unsigned int i, j, r;
for (i = 0; i < 256; i++)
{
for(j = 8,r=i; j > 0; j--) if(r&1)r = (r >> 1) ^ CRCPOLY; else r >>= 1;
crc32normal[i] = r;
}
}
Листинг 5 функция построение прямой CRC-таблицы, на которую опирается процедура update_CRC32 (см. листинг 3)
// (c)Dmitry Tomashpolski
gen_crc32inv(void)
{
int i; for(i = 0; i < 256; i++)
unsigned long tmp = crc32(0, i),
crc32dir[i] = tmp,
crc32inv[(unsigned char)(tmp>>24)] = (tmp<<8) ^ i;
}
Листинг 6 функция для расчета инверсной CRC-таблицы, на которую опирается процедура reverse_CRC32 (см. листинг 4)
// (c)Dmitry Tomashpolski
k = 4;
y = CRC_D;
if((i[--k] = sr(crc32dir, y, 0xFF000000ul)) < 0) goto err;
t = crc32dir[i[k]]; y = (y ^ t)<<8 | i[k];
if((i[--k] = sr(crc32dir, y, 0xFF000000ul)) < 0) goto err;
t = crc32dir[i[k]]; y = (y ^ t)<<8 | i[k];
if((i[--k] = sr(crc32dir, y, 0xFF000000ul)) < 0) goto err;
t = crc32dir[i[k]]; y = (y ^ t)<<8 | i[k];
if((i[--k] = sr(crc32dir, y, 0xFF000000ul)) < 0) goto err;
t = crc32dir[i[k]]; y = (y ^ t)<<8 | i[k];
Листинг 7 код, занимающийся построением массива индексов (см. шаг 4)
// (c)Dmitry Tomashpolski
y = CRC_B;
x[k] = (unsigned char) y ^ i[k];
z = crc32f(z, x[k]); k++;
y = z; x[k] = (unsigned char) y ^ i[k];
z = crc32f(z, x[k]); k++;
y = z; x[k] = (unsigned char) y ^ i[k];
z = crc32f(z, x[k]); k++;
y = z; x[k] = (unsigned char) y ^ i[k];
z = crc32f(z, x[k]); k++;
Листинг 8 код, вычисляющий корректирующие байты (см. шаг 5), и помещающий их в массив x.
// (c)Dmitry Tomashpolski
int sr(unsigned long *a, unsigned long v, unsigned long m)
{
int d;
for(d = 256; --d >= 0;)
if(((a[d]^v)&m) == 0)
break;
return d;
}
Листинг 9 служебная функция, занимающаяся поиском элементов в таблице t, которые по маске m, совпадают со значением v (см. листинг 7);
