yeti
07.06.2007, 15:34
Само слово коллизия - это столкновение противоположных сил, интересов, взглядов. Так написано в словаре. ну а я хочу рассмотреть коллизию в crc32.
Коллизия контрольных сумм в crc32 - отличный пример того, что нет ничего невозможного
Допустим, вы протрянили форум.. Или же архив... Отлично, но вот в чем беда - контрольные суммы не совпадают.. И в этой статье я хочу написать о том, что такое и как подделать контрольные суммы..
Собственно, для начала нужен сам пример вычисления контрольной суммы..
Как подсчитывается CRC32?
Ниже приведены тексты программы для подсчета CRC32 заданного файла.
----------------------------------------------- crc.h
typedef unsigned char uchar; /* 8 bits or more */
typedef unsigned int uint; /* 16 - 32 bits or more */
typedef unsigned short ushort; /* 16 bits or more */
typedef unsigned long ulong; /* 32 bits or more */
typedef ulong UCRC; /* CRC-32 */
#define CRC_MASK 0xFFFFFFFFUL
extern UCRC crc;
----------------------------------------------- crc.c
#include <stdio.h>
#include "crc.h"
#include <stdlib.h>
/* Global variables */
UCRC crc;
FILE *fp;
#define BUFFERSIZE 32768U
#define CRCPOLY 0xEDB88320UL
/* 1110 1101 1001 1000 1000 0011 0010 0000 */
#define UPDATE_CRC(crc, c) \
crc = crctable[(uchar)crc ^ (uchar)(c)] ^ (crc >> 8)
static UCRC crctable[256];
static void make_crctable( void ) {
uint i, j;
UCRC r;
for (i = 0; i <= 255; i++) {
r = i;
for (j = 8; j > 0; j--) {
if (r & 1)
r = (r >> 1) ^ CRCPOLY;
else
r >>= 1;
}
crctable[i] = r;
/*
printf( "%08lx ", crctable[i] );
if( i % 8 == 7 )
printf( "\n" );
*/
}
}
int main( int argc, char *argv[] ) {
size_t len;
char *buffer, *sav;
if ( argc != 2 ) {
printf("Usage: CRC32 <File_Name>\n" );
return 1;
}
if ( ( fp = fopen( argv[1], "rb" ) ) == NULL ) exit(1);
make_crctable();
crc = CRC_MASK;
buffer = (char *) calloc( BUFFERSIZE,1 );
sav = buffer;
while ( ( len = fread(buffer,1,BUFFERSIZE,fp) ) > 0 ) {
while ( len-- ) UPDATE_CRC( crc, *buffer++ );
buffer = sav;
}
free(buffer);
len = (unsigned int)(crc>>16);
printf( "File = %13s CRC32 = %04x%04x\n", argv[1], (int)~len, (int)~crc );
fclose( fp );
flushall();
return 0;
}
А вот более подробное описание вычисления контрольной суммы:
CRC-32 инициализируется значением $FFFFFFFF. Потом для каждо-
го байта B входной последовательности CRC-32 сдвигается вправо на
1 байт. Если байты CRC-32 были {C1,C2,C3,C4} (C1 - старший, C4 -
младший), сдвиг дает {0,C1,C2,C3}. Младший байт C4 побитно склады-
вается с B по модулю 2 (C4 xor B). Новым значением CRC-32 будет
его сдвинутое значение, сложенное побитно по модулю 2 (xor) с
4-байтовой величиной из "магической" таблицы с использованием
[B xor C4] в качестве индекса.
Было: CRC-32 = {C1,C2,C3,C4} и получили очередной байт B.
Стало:
CRC-32 = { 0,C1,C2,C3} xor Magic[B xor C4].
На Паскале:
CRC := (CRC shr 8) xor Magic[B xor byte(CRC and $FF)];
(здесь CRC - longint, Magic - array[byte] of longint).
Последний этап вычисления CRC-32 - инвертировать все биты:
CRC := not CRC;
взято описание тут (http://pascal.sources.ru/crc/crc-32.htm)
Но пожалуй, надо перейти от теоризации к более практической части!
рассмотрим:
По сути, в самой прошивке не хранится CRC, а там хранятся лишь корректирующие байты. Но походу, если все структуры выверены на границу 4-х байт, то можно взять блок, стандартным алгоритмом подсчитать контрольную сумму. если же она не будет равняться нулю, то ищет тот блок, который подходит под нужные нам условия. В утилите: PEiD аже плагин есть специально для подделки CRC (http://slil.ru/24480346 - ссыль посеяла. поэтому залила), а также вот(http://www.secretashell.com/codomain/peid/plugins/ ) ссылка на подборку плагинов для нее..
По сути надо знать что вычислять и по каким параметрам.. Нашла таблицу - приведу ее:
http://img507.imageshack.us/my.php?image=20062693de8.jpg
По сути, в Crc32 нам надо подогнать блок байт к контролируемому блоку, подогнав контрольную сумму к нужному значению. Блок равен разрядности.. То есть для CRC32 блок будет равняться 4-ем байтам.. расчитанными, или полученными с помощью брута. чтобы рассчитать эту сумму, нужен не только aлгоритм, данные из вышепредставленной
таблицы, но также сведения(также необходимые) откуда и докуда защита считает контрольную сумму. Затем нам надо решить внедрять ли нам внутрь кода корректирующие байты, или же просто дописать их. И если целостность всего блока проверяется, то тогда, конечно же легче, лучше и проще нам будет дописать необходимые данные. но тогда длина контролируемого блока изменится.. Но защитные системы часто не обращают внимания на дописывание - они контролируют целостность определенного блока байтов.
Я приведу исходник плагина для 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);
}
метод внедрения кода:
Этот метод намного более действенен.. у него больше перспектив... При желании, можно выбить себе место для 4х байт.
Можно переписать машинные команды. для начала надо найти наименее значимые биты..
Да и если учесть, что компиляторы тоже не всухую работают.. То есть они тоже вставляют куски кода.. А если это сертификат, то высвободить себе места намного проще.
Но всеже, лучше мы рассмотрим пример:
Например байтовое расположние у нас выглядит так:
A:::::::::::::::::::::::::::::::::D
контрольная сумма равняется CRC_OK
теперь мы изменим некоторые байты:
A:::::x:::::::::::::::::::::::::xxx::::x:x:D
Но в чем беда - контрольная сумма отличается..
Давайте найдем себе кусочек байтов, которые можно изменить без зазрения совести?
Походу, байты лучше всего вставлять посередине. Это мы и продемонстрируем:
A:::::x::::::B_12_3_4_C::::::xxx:::x:x:D
Это шаблон, ткак сказать. а теперь нам надо просто подсчитать контрольные суммы этих 4-х байтов и подобрать те, что нам подходят.
И в конце посчитать контрольную сумму данного блока.
Так.. а теперь посмотрим поближе. Выше я разместила ссылку на PEiD и на плагины! Нам нужен плагин FixCRC(еще ссыль на плагины (http://www.wasm.ru/baixado.php?mode=tool&id=318), вот еще на пейд ссыль (http://www.wasm.ru/baixado.php?mode=tool&id=67) ). Потом мы запускаем что-либо, жмем стрелочку. и выбираем crc32 в plugins. Затем выходим, и в хекс-редакторе, к примеру, правим файл. hex_редактор можно найти тут (http://www.handshake.de/user/chmaas/delphi/download/xvi32.zip - спасибо Дикс'у с его темой про авик)) Затем опять откурываем файл в PEiD опять смотрим контрольную сумму. Не совпадает, не так ли?Затем плагин САМ пишет нам - 4 bytes written! да, и мы можем заметить, что в конец действительно было дописано 4 корректирующих байта. Потом мы может вставлять эти волшебные 4 байта в файл, предварительно отступив 4 байта назад в хекс-редакторе. таким образом, можно корректировать не только целые файлы, но и отдельные куски кода!
Чтож, мы подделали crc32 - что дальше? Никто не стоит на месте.. Завтра кто-то сможет подделать MD5, потом кто-то придумает MD6.. Посмотрим..
Коллизия контрольных сумм в crc32 - отличный пример того, что нет ничего невозможного
Допустим, вы протрянили форум.. Или же архив... Отлично, но вот в чем беда - контрольные суммы не совпадают.. И в этой статье я хочу написать о том, что такое и как подделать контрольные суммы..
Собственно, для начала нужен сам пример вычисления контрольной суммы..
Как подсчитывается CRC32?
Ниже приведены тексты программы для подсчета CRC32 заданного файла.
----------------------------------------------- crc.h
typedef unsigned char uchar; /* 8 bits or more */
typedef unsigned int uint; /* 16 - 32 bits or more */
typedef unsigned short ushort; /* 16 bits or more */
typedef unsigned long ulong; /* 32 bits or more */
typedef ulong UCRC; /* CRC-32 */
#define CRC_MASK 0xFFFFFFFFUL
extern UCRC crc;
----------------------------------------------- crc.c
#include <stdio.h>
#include "crc.h"
#include <stdlib.h>
/* Global variables */
UCRC crc;
FILE *fp;
#define BUFFERSIZE 32768U
#define CRCPOLY 0xEDB88320UL
/* 1110 1101 1001 1000 1000 0011 0010 0000 */
#define UPDATE_CRC(crc, c) \
crc = crctable[(uchar)crc ^ (uchar)(c)] ^ (crc >> 8)
static UCRC crctable[256];
static void make_crctable( void ) {
uint i, j;
UCRC r;
for (i = 0; i <= 255; i++) {
r = i;
for (j = 8; j > 0; j--) {
if (r & 1)
r = (r >> 1) ^ CRCPOLY;
else
r >>= 1;
}
crctable[i] = r;
/*
printf( "%08lx ", crctable[i] );
if( i % 8 == 7 )
printf( "\n" );
*/
}
}
int main( int argc, char *argv[] ) {
size_t len;
char *buffer, *sav;
if ( argc != 2 ) {
printf("Usage: CRC32 <File_Name>\n" );
return 1;
}
if ( ( fp = fopen( argv[1], "rb" ) ) == NULL ) exit(1);
make_crctable();
crc = CRC_MASK;
buffer = (char *) calloc( BUFFERSIZE,1 );
sav = buffer;
while ( ( len = fread(buffer,1,BUFFERSIZE,fp) ) > 0 ) {
while ( len-- ) UPDATE_CRC( crc, *buffer++ );
buffer = sav;
}
free(buffer);
len = (unsigned int)(crc>>16);
printf( "File = %13s CRC32 = %04x%04x\n", argv[1], (int)~len, (int)~crc );
fclose( fp );
flushall();
return 0;
}
А вот более подробное описание вычисления контрольной суммы:
CRC-32 инициализируется значением $FFFFFFFF. Потом для каждо-
го байта B входной последовательности CRC-32 сдвигается вправо на
1 байт. Если байты CRC-32 были {C1,C2,C3,C4} (C1 - старший, C4 -
младший), сдвиг дает {0,C1,C2,C3}. Младший байт C4 побитно склады-
вается с B по модулю 2 (C4 xor B). Новым значением CRC-32 будет
его сдвинутое значение, сложенное побитно по модулю 2 (xor) с
4-байтовой величиной из "магической" таблицы с использованием
[B xor C4] в качестве индекса.
Было: CRC-32 = {C1,C2,C3,C4} и получили очередной байт B.
Стало:
CRC-32 = { 0,C1,C2,C3} xor Magic[B xor C4].
На Паскале:
CRC := (CRC shr 8) xor Magic[B xor byte(CRC and $FF)];
(здесь CRC - longint, Magic - array[byte] of longint).
Последний этап вычисления CRC-32 - инвертировать все биты:
CRC := not CRC;
взято описание тут (http://pascal.sources.ru/crc/crc-32.htm)
Но пожалуй, надо перейти от теоризации к более практической части!
рассмотрим:
По сути, в самой прошивке не хранится CRC, а там хранятся лишь корректирующие байты. Но походу, если все структуры выверены на границу 4-х байт, то можно взять блок, стандартным алгоритмом подсчитать контрольную сумму. если же она не будет равняться нулю, то ищет тот блок, который подходит под нужные нам условия. В утилите: PEiD аже плагин есть специально для подделки CRC (http://slil.ru/24480346 - ссыль посеяла. поэтому залила), а также вот(http://www.secretashell.com/codomain/peid/plugins/ ) ссылка на подборку плагинов для нее..
По сути надо знать что вычислять и по каким параметрам.. Нашла таблицу - приведу ее:
http://img507.imageshack.us/my.php?image=20062693de8.jpg
По сути, в Crc32 нам надо подогнать блок байт к контролируемому блоку, подогнав контрольную сумму к нужному значению. Блок равен разрядности.. То есть для CRC32 блок будет равняться 4-ем байтам.. расчитанными, или полученными с помощью брута. чтобы рассчитать эту сумму, нужен не только aлгоритм, данные из вышепредставленной
таблицы, но также сведения(также необходимые) откуда и докуда защита считает контрольную сумму. Затем нам надо решить внедрять ли нам внутрь кода корректирующие байты, или же просто дописать их. И если целостность всего блока проверяется, то тогда, конечно же легче, лучше и проще нам будет дописать необходимые данные. но тогда длина контролируемого блока изменится.. Но защитные системы часто не обращают внимания на дописывание - они контролируют целостность определенного блока байтов.
Я приведу исходник плагина для 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);
}
метод внедрения кода:
Этот метод намного более действенен.. у него больше перспектив... При желании, можно выбить себе место для 4х байт.
Можно переписать машинные команды. для начала надо найти наименее значимые биты..
Да и если учесть, что компиляторы тоже не всухую работают.. То есть они тоже вставляют куски кода.. А если это сертификат, то высвободить себе места намного проще.
Но всеже, лучше мы рассмотрим пример:
Например байтовое расположние у нас выглядит так:
A:::::::::::::::::::::::::::::::::D
контрольная сумма равняется CRC_OK
теперь мы изменим некоторые байты:
A:::::x:::::::::::::::::::::::::xxx::::x:x:D
Но в чем беда - контрольная сумма отличается..
Давайте найдем себе кусочек байтов, которые можно изменить без зазрения совести?
Походу, байты лучше всего вставлять посередине. Это мы и продемонстрируем:
A:::::x::::::B_12_3_4_C::::::xxx:::x:x:D
Это шаблон, ткак сказать. а теперь нам надо просто подсчитать контрольные суммы этих 4-х байтов и подобрать те, что нам подходят.
И в конце посчитать контрольную сумму данного блока.
Так.. а теперь посмотрим поближе. Выше я разместила ссылку на PEiD и на плагины! Нам нужен плагин FixCRC(еще ссыль на плагины (http://www.wasm.ru/baixado.php?mode=tool&id=318), вот еще на пейд ссыль (http://www.wasm.ru/baixado.php?mode=tool&id=67) ). Потом мы запускаем что-либо, жмем стрелочку. и выбираем crc32 в plugins. Затем выходим, и в хекс-редакторе, к примеру, правим файл. hex_редактор можно найти тут (http://www.handshake.de/user/chmaas/delphi/download/xvi32.zip - спасибо Дикс'у с его темой про авик)) Затем опять откурываем файл в PEiD опять смотрим контрольную сумму. Не совпадает, не так ли?Затем плагин САМ пишет нам - 4 bytes written! да, и мы можем заметить, что в конец действительно было дописано 4 корректирующих байта. Потом мы может вставлять эти волшебные 4 байта в файл, предварительно отступив 4 байта назад в хекс-редакторе. таким образом, можно корректировать не только целые файлы, но и отдельные куски кода!
Чтож, мы подделали crc32 - что дальше? Никто не стоит на месте.. Завтра кто-то сможет подделать MD5, потом кто-то придумает MD6.. Посмотрим..