Версия для печати


Почти всё, что вы хотели узнать, но боялись спросить о Crc32. Продолжение
http://www.delphikingdom.com/asp/viewitem.asp?catalogID=431

Andrew Rybin
дата публикации 12-07-2001 15:54

Почти всё, что вы хотели узнать, но боялись спросить о Crc32. Продолжение

После написания данной статьи я перебирал старые архивы и наткнулся на описание программы Locker разработанной в Институт математики АН Молдовы, Колесниковым Александром Евгеньевичем.

Самой программы и алгоритмов её функционирования представлено не было. Далее приводится оригинальный текст описания:
Традиционное использование CRC, в том числе и в области персо-нальных компьютеров - в контроллерах дисков, коммуникационных (XMODEM) и сетевых (Ethernet, Token Ring и др.) протоколах, предполагает размещение (передачу) значения CRC ПОСЛЕ блока информа-ции. Такой метод позволяет обнаружить практически все виды ЕСТЕСТВЕННЫХ ошибок в канале (физический сбой, помеха и пр.), но совершен-но не помогает в случае ошибок ИСКУССТВЕННЫХ (злонамеренные действия ПЕРЕХВАТЧИКА, например).

Действительно, применительно к безопасности данных в файловой системе персонального компьютера, можно представить себе следующую ситуацию. Пусть фирма-разработчик пакета программ сопровождает свой пакет файлом типа README, в котором приведены значения CRC для всех исполняемых файлов пакета. Такая информация позволит однозначно определить, например, факт поражения вирусом по неизбежному изменению реальной CRC файла по отношению к приведенной в README. Однако обна-ружить злонамеренные действия пионера, сажающего в тело файла шутки ради вирус или троянскую компоненту и РЕДАКТИРУЮЩЕГО соответствующее значение CRC в README, таким способом не удастся принципиально.

Если же предположить, что значение CRC блока данных находится ВНУТРИ этого блока (не рассматривая пока вопрос о том, как это сделать), то подобные действия пионера будут серьезно затруднены: при попытке редактирования блока произойдет рассогласование реальной CRC и записанного внутри блока значения, причем согласовать их снова (в случае использования достаточно мощного CRC алгоритма, например, CRC32) будет практически невозможно.

Как поместить в тело файла значение его CRC32? Пусть дан исход-ный файл. Определим его CRC32 и попытаемся добавить полученное зна-чение к исходному файлу. Это получится, однако при редактировании значение CRC файла безнадежно изменится. Из теоретических соображе-ний, приведенных в литературе, следует, что для согласования ("балансирования") в этом случае достаточно 64 бит или 8 байт (удвоенная длина используемого сдвигового регистра), однако теория ничего не говорит о том, как эти 8 байт определить. Несмотря на то, что психологически 8 байт выглядят как ерунда, найти нужное значение прямым перебором всех 2^64 возможных комбинаций в течение ближайших пятилеток не представляется возможным.

Происходило это всё в воскресный день, и я решил развлечения ради написать программу с аналогичными функциями. Рассмотрев что дано и что требуется мною была написана процедура: 
procedure Crc32UpdateDelta (CrcFrom, CrcTo: LongWord; lpData: Pointer);
где Сначала я написал процедуру генерирующую 8 байт, но немного подумав сократил количество корректирующих CRC32 байт до 4х. После этого я перепробовал её на разных файлах и разных поверяльщиках CRC32. Итоги были одинаковы - сгенерированные процедурой байты приводят CRC32 к нужному. Существенным ограничением является то, что образующий полином для процедуры Crc32UpdateDelta и поверяльщика должны (скорее всего ;-) совпадать, НО учитывая то что стандартом де-факто во всех программах считающих CRC32 (пр: RAR и pkZIP) является $EDB88320, то ограничение почти не существенно.

Исходный код (распространяется по принципу GratitudeWare - если вы имеете с этого выгоду, автор хочет получить презент ;-). 
 
function  StepBack (Crc: LongWord): LongWord;//>Index
var
    i: Integer;
Begin

    Result:=0;
    for i:=0 to 255 do
      if ((CRC32Table[i] xor Crc) shr 24)=0 then begin
        Result:=i;
        EXIT;
      end;

End;//StepBack - индекс элемента массива с HiByte=Crc

var

  Crc,A,B,C,D: LongWord;
  P: PChar;

Begin

  P:=lpData;
  CrcFrom:=Crc32Done(CrcFrom);//привести к истинному виду
  CrcTo:=Crc32Done(CrcTo);

  //1.DCBA - поиск в таблице индексов элементов со старшими байтами образующими новый CRC32
  D:=StepBack(CrcTo);
  CrcTo:=(CrcTo xor Crc32Table[D]) shl 8;
  C:=StepBack(CrcTo);
  CrcTo:=(CrcTo xor Crc32Table[C]) shl 8;
  B:=StepBack(CrcTo);
  CrcTo:=(CrcTo xor Crc32Table[B]) shl 8;
  A:=StepBack(CrcTo);
  //2. (X xor Crc) xor Crc = X - зная какие элементы таблицы формируют 
  // нужный CRC - просто подставляем их
  
  Crc:=CrcFrom;
  P^:=chr(A xor Crc);
  Crc:=(Crc shr 8) xor Crc32Table[A]; //*Crc32Table[Crc];
  
  inc(P);
  P^:=chr(B xor Crc);
  Crc:=(Crc shr 8) xor Crc32Table[B];
  
  inc(P);
  P^:=chr(C xor Crc);
  Crc:=(Crc shr 8) xor Crc32Table[C];
  
  inc(P);
  P^:=chr(D xor Crc);

End;//Crc32UpdateDelta

Andrew P.Rybin
Специально для Королевства Delphi