Курс Молодого Бойца. Циклические Контрольные Суммы
by Sassa
Реферат
Некоторые вирусы производят поиск двоичных объектов по контрольным
суммам. Например, вирусы типа W32.CTX, I-Worm.Hybris, и другие,
обнаружив функции API, находят по контрольной сумме их имен нужные.
Вирусы также используют контрольные суммы и для других целей. Нужно
учесть, что эти вопросы не вполне изучены авторами вирусов и алгоритмы
расчета сумм содержат ошибки. Использование огромных таблиц расчета
контрольных сумм вместо элегантных битовых алгоритмов также наводит на
мысль, что авторы не владеют материалом. Не будем же уподобляться
троечникам курсов информатики и автоматизации, а сиюминутно прослушаем
лекцию о циклических контрольных суммах.
Статья расчитана на широкий круг читателей и не требует специально-
математических знаний для понимания сути проблемы и алгоритмов.
Приведенные ссылки содержат текст, который может потребовать хороших
знаний в теории групп и теории чисел.
К статье прилагаются примеры программ на Java для расчета таблицы
CRC-32, включающий также возможность расчета 4 байт, которыми нужно
маскировать остаток сообщения, чтобы контрольная сумма измененного
сообщения оставалась такой же, как и исходного сообщения. Другая
программа позволяет реверсировать функцию CRC-32 для расчета ASCII
строк, имеющих одинаковые контрольные суммы.
1. Общие термины и применение технологии
Вопреки распространенному заблуждению, циклические контрольные
суммы - это вполне определенный вид контрольных сумм, и говорить, а уж
тем более подписываться "сейчас подсчитаем CRC" (CRC, cyclic redundancy
checksum) - это иметь в виду как раз расчет такой суммы, а вовсе не
подсчитывать КАКУЮ-ТО сумму. Поэтому сейчас самое время принять
терминологический душ.
* Сумма - это результат сложения последовательности чисел (битов,
байт и т.д.). При этом не обязательно используется знакомая нам с
первых классов арифметическая операция сложения - может, например,
использоваться операция сложения по модулю 2 (известная также под
псевдонимом XOR).
* Контрольная сумма - это сумма, которая используется для контроля
целостности данных. То есть, представив блок данных в виде цепочки
чисел, складывают эти числа. В дальнейшем можно проверить произошли ли
спонтанные изменения в блоке данных - это можно сделать путем сравнения
контрольной суммы с суммой, расчитанной заново по тому же блоку данных:
если суммы не совпали, значит, произошли изменения.
Контрольные суммы используются на носителях информации (магнитные и
оптические диски, магнитные ленты и т.п.), в протоколах передачи
данных, да и просто в архивных файлах.
Простейшей такой суммой является бит четности - паритет. Эта сумма
имеет длину всего 1 бит и является суммой по модулю 2 всех битов блока
данных. Если в результате хранения или передачи данных какой-то бит
будет искажен, этот факт может быть обнаружен, поскольку бит четности
будет другой.
Другая область применения контрольных сумм - криптография, в
частности - создание электронных подписей. Электронная подпись сама по
себе является криптографически защищенной контрольной суммой (например,
зашифрованная секретным ключом подписавшего). Тогда если сообщение было
(не)преднамеренно искажено, то контрольная сумма не совпадет и можно
говорить не только об искаженности информации, но и о непричастности
подписавшего к содержимому сообщения: после модификации электронного
документа можно сразу сказать, что подпись взята от другого документа и
потому недействительна. (Юридические вопросы, связанные с
использованием электронных подписей - тема совершенно ортогональная.)
Такое применение контрольных сумм - детекция ошибок и изменений.
Заметим, что сама сумма при этом хранится или передается вместе с
данными, а потому подвержена искажению не менее самих данных. Заметим
также, что сами данные могут получить не одну, а несколько ошибок,
причем, ошибки могут быть таковы, что контрольная сумма не изменится из
-за наличия всех ошибок, что накладывает ограничения на количество
ошибок, которые можно зафиксировать такой контрольной суммой.
Как правило, чем длиннее сообщение, тем менее значительна
вероятность того, что ошибка возникнет именно в контрольной сумме (по
сравнению с вероятностью возникновения ошибки в сообщении - контрольные
суммы значительно короче самих сообщений), но зато выше и вероятность
того, что возникнет более одной ошибки в сообщении.
Эти факты налагают ограничения на достоверность детекции ошибок.
Даже криптографические котрольные суммы, вроде SHA-1 и MD5 не лишены
этого свойства: существует отличная от ноля вероятность того, что
совокупность ошибок не изменит контрольной суммы; правда, вероятность
этого события настолько мала, что ею пренебрегают, даже применяя
функцию в военных целях.
* Коды Хэмминга - это специальным образом расчитанные контрольные
суммы, позволяющие не только выяснить наличие ошибки, но и _исправить_
ее. Так если переданное сообщение содержит ошибку в одном бите,
сообщение не нужно пересылать заново: его можно исправить при
получении. Тем не менее, как уже было замечено, ошибок может возникнуть
несколько и ошибки могут возникнуть при передаче именно контрольной
суммы, поэтому нет 100% гарантии того, что исправленное сообщение - это
действительно то, что было передано.
Коды Хэмминга относительно сложно вычисляются. Кроме того,
отсоединение кодов Хэмминга от данных - процесс трудоемкий и требует
блоковой обработки данных (невозможно отправить сообщение до того, как
расчитаны все биты его контрольной суммы), в то время как в
коммуникационных технологиях более интересны алгоритмы, обрабатывающие
потоки бит. Именно по этим причинам чаще используются Циклические
контрольные суммы, которые, кроме того, относительно легко
протабулировать для ускорения программного расчета контрольных сумм.
Именно табличная форма таких функций наиболее широко известна среди
практиков разработки программ, и именно такие реализации и встречаются
в вирусах, раздувая их размеры.
2. Как правильно расчитывать контрольные суммы
2.1 Коды Хэмминга
Хэмминг показал, что для коррекции единичной ошибки достаточно
хранить не менее log(n+1) контрольных бит (log - логарифм по основанию
2, n - длина сообщения). Он также предложил алгоритм расчета этих
контрольных бит. Суть этого алгоритма и пример расчета излагается ниже.
Пример исправления ошибки приведен в разделе 3.
Предположим, нужно передать n бит. Запишем числа от 1 до n. В
позициях с номером, являющимся степенью числа 2, расположим контрольные
биты, а биты данных - в оставшихся позициях. Значения этих бит -
паритет всех битов сообщения в позициях, в которых есть единица в том
же месте, что и в номере позиции контрольного бита.
Так, C0, первый контрольный бит, располагается в позиции 1 (2^0,
единица в самом младшем бите номера позиции) и его значение - паритет
всех нечетных бит сообщения (всех бит, в номере позиции которых самый
младший бит установлен в 1).
Соответственно, C1, второй бит, располагается в позиции 2 (2^1,
единица во втором бите номера позиции) и его значение - паритет всех
бит сообщения, у которых в номере позиии установлен второй бит.
Третий контрольный бит располагается в позиции 4, а в позиции 3,
стало быть, бит данных. И так далее.
Пример:
В первой колонке этой таблицы - двоичная запись номера позиции в
сообщении. Вторая колонка - пометки, какие биты сообщения используются
для расчета соответствующего контрольного бита. Третья колонка -
расположение содержимого сообщения. Четвертая колонка - результат
сложения сообщения и контрольных бит - собственно, что должно
передаваться.
| C3 C2 C1 C0 | K | M .
0001 | . . . * | . | 1 = 1+0+0:складываем биты,
0010 | . . * . | . | 0 = 1+1+0:помеченные звездочкой
0011 | . . * * | 1 | 1 :в соответствующей
0100 | . * . . | . | 1 = 0+1+0:колонке
0101 | . * . * | 0 | 0 '
0110 | . * * . | 1 | 1
0111 | . * * * | 0 | 0
1000 | * . . . | . |
1001 | * ...... и так далее
Итак (старшие биты справа)
Сообщение: 1010 = ..1.010 = 5
Код: 101 = 10.1... = 5
Передано: 1011010 = 0x2d
Естественно, контрольные биты не контролируют друг-друга: в тех
позициях, где находятся контрольные биты, в 1 установлен только один
бит. То есть, если ошибка происходит при передаче контрольного бита, ее
невозможно будет обнаружить.
Если происходит ошибка при передаче одного бита, контрольные биты
будут иметь другое значение. Хэмминг показал как можно вычислить
позицию ошибочного бита в таком случае. Описание способа приведено в
разделе 3.
2.2 Циклические контрольные суммы
Для расчета циклических контрольных сумм сообщение условно
представляют в виде полинома, коэффициенты которого - это
соответствующие биты сообщения. Тогда контрольной суммой является
остаток на GF(2) от деления полинома-сообщения на специально
подобранный полином, называемый полиномом-генератором. В этой статье мы
не будем касаться способов расчета полинома-генератора.
Сообщение K: 1010
Полином сообщения: 1*x^3 + 0*x^2 + 1*x^1 + 0*x^0 = x^3+x
Степень этого полинома: 3.
GF(2) - Galois Field, Поле Галуа (в данном случае - по модулю 2).
Это такое поле чисел, в котором результаты арифметических операций
сравниваются по модулю 2; например, на GF(10): 3*7=21=1 mod 10 (остатки
от деления 1 и 21 на 10 равны, поэтому полагают оба числа равны по
модулю 10).
В таких полях арифметические операции определены таким образом,
чтобы сохранялся их алгебраический смысл. Например, операция деления на
GF (p) определена таким образом: 1/a=b <=> a*b=1 mod p. То есть, b -
это число, обратное a, если произведение его на a равно 1 по модулю p.
Заметим, что чисел, обратных данному, бесконечно много: это все n*p+b
для любых n.
Так, 1/3=7 mod 10 (поскольку 3*7=1 mod 10). Проверим: 6/3=2 -
должно быть так? Тогда 6/3 = 6*7 = 42 = 2 mod 10 (42 и 2 имеют
одинаковые остатки от деления на 10).
По такому же принципу определяются операции на GF(2). В частности,
нам понадобятся операции сложения и вычитания.
Вычитание - это процесс сложения числа с противоположным ему: b-a=b
+ (-a). Считают, что -a=c <=> a+c=0 mod p. Таких чисел очень много: это
все n*p+c.
Так, на GF(2) имеем, что -1=1, поскольку 1+1=2=0 mod 2 (остатки от
деления 0 и 2 на 2 равны), а это есть операция XOR.
Теперь мы сможем производить деление полинома на полином. Нас
интересует только остаток от деления, поэтому не будем обращать
внимания на частное.
Расчет контрольной суммы производится следующим образом. Сообщение
представляют в виде полинома S(x), умножают на x^M, и ищут остаток от
деления на полином-генератор G(x), где M - это степень
полиномагенератора.
Так, пусть имеем сообщение 1010. Ему соответствует полином S(x)=x^3
+x. Имеем полином-генератор G(x)=x^3+x+1, что соотвествует двоичной
записи 1011, M=3 (степень полинома и количество бит контрольной суммы:
это CRC-3). Расчет циклической контрольной суммы производится вот так:
S(x)*x^M - дописываем в конец сообщения M нолей: 1010*1000=1010000.
S(x)*x^M = Q(x)*G(x) + C(x) - делим полученный полином на G(x), в
результате чего получаем частное Q(x) и остаток от деления C(x) (здесь
представлено разложение сообщения на сумму полинома, делящегося нацело
на G(x), и полинома, который уже не делится на G (x)). C(x) и есть
искомая контрольная сумма. Ниже показано деление в столбик. Слева -
привычное деление многочленов, справа - бинарная форма записи того же
процесса.
S(x)*x^M G(x) K shl M G
------------------------------------------------
x^6+x^4 | x^3+x+1 1010000 | 1011
- `-------- - `------
x^6+x^4+x^3 Q(x)=x^3+1 1011 101
--- ----
-x^3=x^3 (-1=1 mod 2) 1000
- -
x^3+x+1 1011
--- ---
-x-1=x+1=C(x) 011=CRC-3
Легко заметить, что расчет контрольной суммы можно производить
путем циклического сдвига битов сообщения, последовательно вдвигая биты
сообщения в некий регистр, и как только самый старший бит в регистре
cтановится равен 1, нужно вычесть из него (читай: побитно сложить по
модулю два) двоичный образ полинома-генератора. Необходимо повторять
эту операцию до тех пор, пока не будет выдвинут из регистра последний
бит данных.
2.2.2 Свойства.
Циклические контрольные суммы обладают следующими свойствами:
1. позволяют исправить единичную ошибку в сообщениях, которые
короче, чем 2^c (c - степень полинома)
2. позволяют обнаружить вспышки ошибок длиной менее c (то есть,
последовательности бит, начинающиеся с ошибки и заканчивающиеся
ошибкой)
3. специальные виды полиномов позволяют также детектировать любое
нечетное количество ошибок
4. CRC(a+CRC(a))=0: если за сообщением дописать его контрольную
сумму, то контрольная сумма от результирующего потока бит равна нулю
2.2.3 Пример кода побитного расчета CRC-16 и тонкости реализации
Несложная модификация этого кода может расчитывать CRC-32.
; (с) Sassa
mov cx, chunksizeToCRC ; количество байт
; не забудьте в конце блока приписать нулевое слово:
; правильное CRC будет соответствовать s*x^M - в конец
; сообщения нужно приписать M нулей.
; хотя для получения просто некоторого уникального
; числа можно этого не делать.
mov si, offset chunk
xor bx, bx ; некоторые стандарты расчета CRC требуют
; начинать с ненулевого значения(см. ниже)
; в таком случае здесь должно быть
; mov bx, CRC_INIT
; конечно, при CX==0 не нужно начинать цикл, но
; как минимум CX==2 - в конце даже нулевого сообщения
; приписано 16 бит = 2 байта (нулей)
read_next_word:
loadsb
; xor bl, al ; дописав такую строку, нужно заменить
; RCR BX,1 на SHR BX,1, и избавиться
; от нулевых бит в конце сообщения.
stc ; за счет последующего RCR в AL
; задвинется 1, так что, AL!=0, пока
; не выдвинутся все биты данных,
; включая нулевые биты (избавляемся
; от дополнительного счетчика циклов)
shift_next_bit:
rcr al, 1 ; выдвигаем биты от младших к старшим
; задвигаем CF: 1 на первой итерации,
; 0 во всех остальных случаях
jz _loop_again ; AL==0 => выдвинут последний бит
; (см. Комментарии выше)
rcr bx, 1
jnc shift_next_bit
; CY означает, что 1 в самом старшем бите полинома
; и пора вычитать из него полином-генератор:
; вычитание на GF(2) равно xor
xor bx, 0a001h ; CRC-16, младшие 16 бит полинома
; записанные в обратном порядке -
; наиболее знакомая форма записи
; этого полинома.
; CF==0 после последнего XOR: RCR AL,1 задвинет в AL 0
jmp shift_next_bit
_loop_again:
loop read_next_word
Обращаем внимание на направление циклических сдвигов контрольной
суммы и регистра с данными. Если сдвиги контрольной суммы делать в
обратном направлении, тоже получится уникальное число, характерное для
именно этих исходных данных, но это более не будет циклическая
контрольная сумма, расчитанная по полиному-генератору, и другие
программы не смогут получить тот же код.
Если сдвиги регистра данных делать в обратном направлении, то
просто поток бит будет перемешан.
Обращаем также внимание на то, что в CRC-16 используется полином
_16 _-й степени! 17-й бит полинома не влазит в 16-разрядный регистр, но
ведь этот бит всегда будет обнулен. Таким образом, CRC-16 всегда 16
бит, хотя полином-генератор 16-й степени; аналогично для других
степеней!
Возможно оптимизировать программу расчета контрольной суммы, если
раскомментировать строку XOR BL,AL и заменить RCR BX,1 на SHR BX,1:
тогда не нужно помещать в конце сообщения два нулевых байта для CRC16
(выполняющие роль умножения на x^M). Такой алгоритм на каждой итерации
содержит в BX контрольную сумму всех байт, которые были обработаны
(считая последний обработанный байт действительно последним в
сообщении). Тогда чтобы добавить еще один байт в сообщение, нужно
переписать самые старшие биты контрольной суммы битами новых данных
(XOR BL,AL), и продолжить деление на полиномгенератор.
Математически такая операция выглядит вот так:
S(x)=A(x)*x^N+B(x) - сообщение представляем в виде суммы двух
сообщений, где N - степень полинома B(x) (N<M, M - степень полинома G
(x)). Тогда:
S(x)*x^M=(A(x)*x^N+B(x))*x^M
=(AQ(x)*G(x)+AR(x)+B(x)*x^(M-N))*x^N,
где AR(x) - остаток от деления A(x)*x^M на G(x), контрольная сумма
сообщения A, B(x)*x^(M-N) - сдвиг сообщения B(x) влево так, чтобы самая
старшая степень B(x) была M, а умножение на x^N - дописывание в конце N
нулей. То есть, AR(x)+B(x)*x^(M-N) - это и есть CRC(A) XOR (B SHL
(M-N)). (Обратите внимание, что программа сдвигает биты в обратном
направлении, поэтому сдвиг влево не нужен).
Некоторые программы (например, PKZIP) начинают расчет контрольной
суммы не с 0, а с -1, а потом еще инвертируют результат. Сходные
операции производят и коммуникационные устройства. Смысл таких операций
- начинать расчет суммы не с нуля, чтобы можно было обнаружить потерю
начальных битов в сообщениях, начинающихся с нулевых битов. Если же
начинать с нулевого значения, при передаче нулевых бит значение
контрольной суммы не будет меняться, так что, нельзя узнать, утеряны ли
нулевые биты и сколько. Инвертирование результата является защитой от
потери начальной единицы [CORNELL].
(Стоит заметить, что существуют такие цепочки бит, CRC которых
будет равно нулю - это цепочки бит, за которыми приписана их
контрольная сумма. После такой цепочки бит может идти сколько угодно
нулей, которые не будут отражены в контрольной сумме - CRC будет
оставаться "правильной", даже если будут утеряны несколько нулевых
бит.)
2.2.4 Как расчитать таблицу CRC.
В этой статье мы рассматриваем расчет циклических контрольных сумм
с использованием программ. В этом случае не всегда удобно пользоваться
побитным представлением данных (и чаще всего такой способ несколько
медленнее побайтной обработки данных). Поэтому в большинстве случаев
программисты пользуются таблицами расчета CRC, по которым можно
выяснить значение циклической контрольной суммы, обрабатывая сообщение
побайтно.
По построению в циклической контрольной сумме в зависимости от
старших бит накопленной контрольной суммы изменяется фиксированный
набор бит: для изменения суммы используется одно и то же число. Поэтому
если выдвинуть из контрольной суммы 8 бит, а не 1, в сумме всегда
изменится некоторый фиксированный набор бит.
Одновременно младшие биты накопленной контрольной суммы изменятся в
зависимости от вдвигаемых битов данных. Последовательность применения
полинома-генератора и вдвижения битов данных не имеет значения,
поскольку в обоих случаях выполняется операция XOR. Такие свойства
циклических сумм позволяют построить простую таблицу из 256 строк, в
каждой строке которой записана XOR-маска, на которую должна измениться
накопленная контрольная сумма при циклическом сдвиге суммы на 8 бит.
Для построения такой таблицы необходимо расчитать CRC каждого
возможного байта (0..255), взятого поотдельности. Эти значения и нужно
занести в таблицу.
Пользоваться этой таблицей нужно так:
- запомнить 8 старших бит накопленной контрольной суммы
- сдвинуть контрольную сумму на 8 бит
- скопировать следующий байт данных в младшие 8 бит контрольной
суммы
- сложить по модулю 2 контрольную сумму с маской XOR, взятую из
строки таблицы, соответствующей запомненному байту контрольной суммы
То есть:
data - следующий байт данных
crc[] - таблица
crc(int) - функция побитного расчета CRC
b - текущее значение CRC
CRC_BITS - количество бит в CRC
Инициализация таблицы:
for (i=0; i<0x100; i++) crc[i]=crc(i);
Использование таблицы (классическое деление на полином - не
забудьте, что биты данных нужно дополнить M нулями):
c=b>>(CRC_BITS-8);
b=b<<8 + data;
b=b ^ crc[c];
Что можно записать одной строкой:
b = (data + b<<8) ^ crc[b>>(CRC_BITS-8)];
Использовать таблицу можно и по-другому (оптимизация деления, как
описано в 2.2.3):
c=data ^ (b>>(CRC_BITS-8));
b=b<<8;
b=b ^ crc[c];
Одной строкой такой расчет выглядит так:
b=(b<<8) ^ crc[data ^ (b>>(CRC_BITS-8))];
3. Как исправить ошибку
3.1 По кодам Хэмминга
Чтобы исправить ошибку, необходимо расчитать синдром, а он равен
расстоянию между кодами Хэмминга: сложить по модулю 2 полученный код и
код, расчитанный по искаженному сообщению.
Расстояние между кодами Хэмминга указывает номер бита с ошибкой (по
построению). Если исправимых ошибок не было, расстояние между кодами
Хэмминга равно нулю. Если была одна ошибка, расстояние между кодами
Хэмминга укажет на позицию бита с ошибкой. Исправление заключается в
инвертировании идентифицированного бита.
Пример:
Сообщение: ..1.010 = 1010 = 5
Код: 10.1... = 101 = 5 (1)
Передано: 1011010 = 0x2d
Ошибка: .....1. (искажаем бит 6)
Получено: 1011000 = 0x0d
Код: 11.0... = 110 = 3 (2)
Синдром (1) xor (2): 101 xor 110 = 011 = 6.
Исправляем ошибку в 6-м бите, извлекаем полезные данные (выбросить
биты кода Хэмминга).
3.2 По Циклическим Контрольным Суммам
Продемонстрируем проверку CRC сообщения K=1010, в котором искажен
третий бит: E=0010, пришло сообщение K+E.
S(x)+E(x)=x^3+x+x=x^3
S(x)+E(x)*x^M G(x) K+E shl M G
x^6 | x^3+x+1 1000000 | 1011
- `-------- - `------
x^6+x^4+x^3 Q(x)=x^3+x+1 1011 1011
--- ----
-x^4-x^3=x^4+x^3 (-1=1 mod 2) 1100
- -
x^4+x^2+x 1011
--- ---
x^3-x^2-x=x^3+x^2+x 1110
- -
x^3+x+1 1011
--- ---
x^2-1=x^2+1=C(x) 101=CRC-3
101!=011, то есть, расчетная контрольная сумма не совпала с
переданной вместе с сообщением, а значит, при передаче произошло
искажение данных.
Исправить ошибку по циклическим контрольным суммам не так просто,
как по кодам Хэмминга: для исправления ошибки нужно пользоваться
таблицами. Заметим, что для длинных сумм (скажем, 32-бит) эти таблицы
будут просто огромными, а их применение - непрактично.
3.3 Целевое искажение сообщений (Как внести незаметную ошибку в
сообщение)
Представим сообщение в виде полинома
S(x)=F(x)*x^(M+n-1)+A(x)*x^(M-1)+D(x)
Пусть S(x)*x^M=Q(x)*G(x)+C(x)
где F(x) - неизменная часть полинома, A(x) - целевой полином
степени n, D(x) - полином степени (M-1), как и полином C(x), C(x) -
остаток от деления на полином-генератор G(x), контрольная сумма
сообщения S (x). Q(x) - некое частное (мы его игнорируем).
Тогда контрольная сумма части сообщения будет вычисляться таким
образом:
(F(x)*x^(M+n-1)+A(x))*x^M=R(x)*G(x)+C_0(x),
а контрольную сумму всего сообщения можно расчитать по
эквивалентной формуле:
S(x)*x^M=(R(x)*G(x)+C_0(x)+D(x))*x^M=Q(x)*G(x)+C(x)
Если задаться целью изменить часть сообщения - заменить полином
A(x) на B(x) той же степени - и чтобы при этом контрольная сумма общего
сообщения осталась неизменной, нужно вычислить значение полинома P (x):
S_1(x)= F(x)*x^(M+n)+B(x)*x^M+P(x)
Пусть (F(x)*x^(M+n)+B(x))*x^M=R_1(x)*G(x)+C_1(x),
тогда чтобы контрольная сумма всего сообщения S_1(x) была тоже
C(x), как и у сообщения S(x):
S(x)*x^M=(R(x)*G(x)+C_0(x)+D(x))*x^M=Q(x)*G(x)+C(x)
=S_1(x)*x^M=(R_1(x)*G(x)+C_1(x)+P(x))*x^M
полином P(x) должен удовлетворять такому условию:
C_1(x)+P(x)=C_0(x)+D(x).
Отсюда легко видеть, что P(x)=C_0(x)-C_1(x)+D(x)=C_0(x)+C_1(x)+D(x)
поскольку на поле GF(2) операции сложения и вычитания равны.
Если говорить о битовых операциях, то по сути изменяя некоторое
слово внутри сообщения, нужно изменить и какие-нибудь последующие M
бит. Причем, изменение заключается в том, что нужно сложить с помощью
XOR существующие биты с контрольной суммой части неизмененного
сообщения и с контрольной суммой соответствующей части измененного
сообщения:
S=FAD
S1=FB(D xor CRC(FA) xor CRC(FB))
CRC(S)=CRC(S1),
где F - неизменная часть сообщения, A - изменяемое слово, B -
целевым образом измененное слово A, D - подбираемое слово.
Нужно учесть, что целевым образом возможно изменить лишь
ограниченную часть сообщения, и что необходимо иметь в конце сообщения
как минимум M бит, которые можно менять произвольно (это D).
Рассмотрим же случай, когда после A нет M бит, которые можно менять
произвольно, но есть такие биты до A: S=FDA. Тогда пусть измененное
сообщение S1=FPB. Найдем условие, которому должен удовлетворять полином
P, чтобы контрольные суммы обоих сообщений были одинаковы.
Пусть C0=CRC(FD), C1=CRC(FP).
Тогда CRC(S)=CRC(FDA)=CRC(C0+A)=CRC(FPB)=CRC(C1+B).
Итак, из условия C0+A=C1+B имеем, что C1=C0+A+B. Расчет полинома P
производится способом, описанным ниже.
(F*x^M+P)*x^M=R*G+C1=F*x^(2*M)+P*x^M=T*G+CF+P*x^M, CF=CRC(FO), где
O - цепочка из M нулевых бит.
Пусть CT=C1+CF.
P*x^M+CT=R*G - левая часть делится нацело на G(x).
Пусть p_i - коэффициенты при соответствующих степенях x в полиноме
P (x), а c_i, r_i и g_i - в полиномах CT(x), R(x) и G(x)
соответственно.
Тогда необходимо решить такую систему уравнений (0<=i<=M):
.--
c_i= > {r_j*g_(i-j)}
`--
0<=j<=i
.--
p_i= > {r_j*g_(M-j)}
`--
0<=j<=i
.--
где > - суммирование ряда чисел, в котором индекс j
`--
0<=j<=i
пробегает значения от 0 до i включительно, r_j - j-й коэффициент
полинома R(x), а g_(i-j) - i-j-й коэффициент полинома G(x).
Учитывая, что сложение делается по модулю 2, решаем эту систему.
Первая половина уравнений (c_i=...) даст нам значения r_j, а вторая
половина уравнений (p_i=...) даст нам коэффициенты полинома P(x).
Битовое представление этих расчетов выглядит намного проще и не
требует решения системы уравнений. Для этого необходимо записать биты
полинома CT сразу за битами полинома P, и производить операции,
обратные делению в столбик на G. А именно:
0... 0 0 c_M...c_2 c_1 c_0 = P(x)*x^M+CT(x)
+ : : : : : : :
: : 1 g_M...g_2 g_1 g_0 = r_0*G(x)
+ : : : : : : :
: 1 g_M.......g_1 g_0 : = r_1*x*G(x)
+ : : : : : : :
: 1 g_M ..........g_0 : : = r_2*(x^2)*G(x)
+ : : : : : : :
..:.....:...: : : : :
+ : : : : : : :
1 g_M...g_1 g_0 : : : = r_(M-1)*(x^M)*G(x)
-------------------------------
p_M...p_1 p_0 0... 0 0 0
То есть, необходимо сдвигать G(x) влево и складывать по модулю 2 с
CT (x) так, чтобы самый младший значащий бит G(x) обнулял самый младший
значащий бит CT(x). Когда обнулены все биты CT(x), получен полином P
(x)*x^M.
Этот процесс можно представить в виде расчета контрольной суммы
обратной цепочки бит с помощью "полинома-генератора", состоящего из бит
исходного полинома-генератора, но записанные в обратном порядке. (Такое
представление возможно по той причине, что сложение и вычитание
эквивалентны на GF(2). Следует также заметить, что прилагаемая
программа не делает этой оптимизации, чтобы виднее было, как происходит
процесс обращения результата функции в исходную цепочку бит данных.)
Итак, можно расчитать такой полином P(x), который в совокупности с
целевым изменением B(x) полинома A(x), даст ту же контрольную сумму,
что и исходное сообщение.
Возможно также обобщить способ расчета полинома P(x) таким образом,
чтобы можно было зафиксировать значения некоторых битов полинома. В
таком случае искомые биты могут быть разбросаны более широко, чем
просто M подряд идущих бит, но и решения может не быть: может
потребоваться изменить как раз те биты, значение которых зафиксировано.
4. Использование контрольных сумм в других целях
Контрольные суммы сейчас используются не только для проверки
целостности сообщения. Довольно часто контрольные суммы используются
как идентификаторы длинных цепочек байт.
Такие цепочки байт - это и совокупность информации,
аутентифицирующей конкретного пользователя, и формула молекулы ДНК в
банке данных, и сигнатура вируса, и даже идентификатор программы,
расчитанный по ее имени.
Более подробно использование контрольных сумм при аутентификации
обсуждается в Приложении Б, а критика использования контрольных сумм
для идентификации программ вирусами - в Приложении В. Здесь же
остановимся на проблемах, связанных с использованием контрольных сумм
как хэширующих функций.
Во всех этих случаях контрольные суммы используются для
идентифицирования отнюдь не случайных цепочек бит. Так, пароль как
правило состоит из печатных символов ASCII таблицы. Формулы ДНК во
многих системах записываются в виде текстовых строк. Тела вирусов
состоят из процессорных инструкций вполне определенного формата.
Контрольные суммы во всех этих случаях используются как хэширующие
функции, а потому не всегда дают хорошее рассеивание результатов на
каждой отдельной области определения. Например, CRC-32 слова `begin'
равно CRC-32 цепочки символов `?,J|{' и равно 0x7a859515 (контрольные
суммы расчитаны по алгоритму, используемому в архивах ZIP). (Такой
результат можно получить, запустив прилагаемую к статье программу:
"revCRC begin .....")
Исследование качества хэширования формул ДНК с помощью CRC-64
[CRC64] также ярко демонстрирует недостатки выбранной функции. Таким
образом, перед тем, как использовать контрольные суммы как хэширующие
функции, необходимо исследовать рассеивание результатов и, возможно,
подобрать более подходящую функцию.
Приложение А. Стандартные полиномы
(Значения взяты из [BERKLEY, ATT])
CRC-8: x^8+x^2+x+1
100000111
CRC-10: x^10+x^9+x^5+x^4+x+1
11000110011
CRC-12: x^12+x^11+x^3+x^2+x+1
110000001111
CRC-16 (bisynch): x^16+x^15+x^2+1
11000000000000101
CRC-16 (CCITT, XMODEM): x^16+x^12+x^5+1
10001000000100001
CCITT использует обратную последовательность вдвижения бит, а
XMODEM - прямую.
CRC-24: x^24+x^23+x^18+x^14+x^11+x^10+x^7+x^6+x^5+x^4+x^3+x+1
1100001000100110011111011
CRC-32 (Ethernet):
x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4
+x^2+x+1
100000100110000010001110110110111
Обратите внимание, что реальные значения, которые используются для
маскирования контрольной суммы, не содержат самого старшего бита, а
иногда все биты записаны в обратной последовательности (что означает
что биты данных должны вдвигаться с другого конца и сдвиг регистра
должен происходить в другую сторону; так CRC-16 лучше знакомо как
0xa001 - младшие 16 бит полинома записанные в обратном порядке).
Однако, соблюдение этих правил необходимо лишь для совместимости. Для
расчета "уникального идентификатора" в личных целях это не так важно.
Приложение Б. Использование контрольных сумм при аутентификации
Аутентификация - это процесс ассоциации участника общения с
уникальным идентификатором. Таким идентификатором может выступать,
например, имя пользователя в системе (login).
В процессе аутентификации участник должен доказать каким-то
образом, что ему соответствует именно тот уникальный идентификатор. В
простейшем случае участник должен передать некоторый секрет, известный
ему и проверяющему; скажем, ввести пароль (проверяющий - операционная
система или сайт веб-почты). Чтобы секрет не стал доступен на этапах
передачи от участника к проверяющему, его не передают в открытом виде,
а хэшируют или расчитывают контрольную сумму. (При этом пароль
дополняется случайными данными для борьбы с replay-атаками.)
Проверяющий всегда может удостовериться, что участник использовал
правильный секрет, если полученная контрольная сумма совпадает с
контрольной суммой секрета (это всегда можно сделать, ведь секрет
известен им обоим).
Более сильный способ аутентификации - использование криптографии с
открытым ключом. Во многих государствах Западной Европы серьезно
подумывают о введении общенациональных инфраструктур поддержки такой
аутентификации граждан, а в США уже многие штаты разрешают использовать
электронную подпись на документах как юридически обязующую.
При такой аутентификации участник создает электронную подпись
документа дополненного некоторым блокам случайных данных (используемого
с целью борьбы с replay-атаками) с использованием личного секретного
ключа. Для проверки достоверности подписи используется открытый ключ,
доступный всем и соответствующий секретному ключу участника.
Как уже было сказано ранее, электронная подпись является
зашифрованной контрольной суммой сообщения. Для проверки целостности и
аутентичности сообщения (то есть, проверки того, что сообщение было
подписано именно тем, кем мы думаем) достаточно заново расчитать
контрольную сумму сообщения и сравнить с суммой, расшифрованной из
электронной подписи с помощью открытого ключа. Если обе суммы совпали,
значит сообщение не претерпело изменений и аутентично.
Кстати ли будет сказать, что оперативная информация для выполнения
военных миссий защищается симметричными ключами и криптография с
открытым ключом не используется, несмотря на кажущееся важным
требование аутентичности и безопасности: симметричными ключами проще
управлять, проще передать другому - а это и есть преимущество перед
системами асимметричного шифрования в высокодинамичных условиях.
(Да, а вот при создании документов для длительного хранения
используются все-таки системы асимметричного шифрования.)
---------------------------------------------------------------------
Приложение В. Расчет контрольных сумм имен функций.
Помимо проблемы с выбором хорошей хэш-функции (см. Раздел 4),
которая может не волновать создателя вируса (подумаешь - находит нужные
функции, плюс еще какие-то), существуют другие объективные причины, по
которым использование контрольных сумм не является удачным решением.
Предположим, вирус хранит контрольные суммы 30 функций, которые он
хочет найти. Пусть он использует таблицу CRC-16 для расчета контрольных
сумм имен файлов. Тогда размер памяти, используемой для хранения всех
данных, сопряженных с поиском имен полезных функций, равняется
30*2+2*256=572 байта. Этого хватило бы для хранения 30 имен функций
средней длиной 19.06 символов. Пусть один байт тратится на длину строки
или на нуль. Тогда имеем 18-символьные имена. Этого кажется более чем
достаточно для записи имен большинства функций: слишком длинные имена
функций не смогут распознаваться компиляторами (ANSI C различает
идентификаторы по первым 32 символам).
Таким образом, использование вирусами контрольных сумм для поиска
подозрительных программ является неоптимальным решением.
Ссылки на учебный материал и интересные статьи
[ATT] http://home.att.net/~cbwatson/CRC_info.doc - [9 Марта] еще
объяснения, стандартные полиномы, пример программы и таблица справочных
CRC.
[BERKLEY] http://www.cs.berkeley.edu/~kfall/EE122/lec06/lec06-outline.pdf
[9 Марта] слайды по лекции по контрольным суммам
[CORNELL] http://www.library.cornell.edu/nr/bookcpdf/c20-3.pdf -
[9 Марта] глава из книги Less-Numerical Algorithms.
[CRC64] http://www.cs.ucl.ac.uk/staff/D.Jones/crcnote.pdf -
[9 Марта] замечания по качеству хэширования ASCII строк с помощью CRC-64
[MAN1] http://www.cs.man.ac.uk/Study_subweb/Ugrad/coursenotes/CS2272/skb/
[9 Марта] лекции по контрольным суммам
[MAN2] http://www.cs.man.ac.uk/Study_subweb/Ugrad/coursenotes/CS2272/skb/
SKB_Lecture_11.pdf -
[9 Марта] лекция по CRC
----------------------------------------------------------------
Приложение Г
/*
* This program gets two strings on input: the initial ASCII string, and
* the target ASCII string. The target ASCII string may contain wildcards,
* which means that those characters will be calculated. The program will
* output the resulting ASCII string that will have the same CRC-32, as the
* initial ASCII string, and will have the same characters, as the target
* string, except for wildcards.
*
* Wildcard is '.' (dot).
*
* The program produces an example of how the CRC-32 is calculated bit by bit
* (and outputs the process on the screen). Then it shows how CRC-32 can be
* reversed to get the target CRC-32. Note that ZIP and Java use the reverse
* form of the polynomial, so bear in mind that the bits in the result are
* in the reverse order.
*
* Note also that the first 4 bytes may not be achieved in a-zA-Z range -
* that's because CRC-32 may not be reversible in such way, it may HAVE to have
* the bits that are forbidden by usage mask.
*
* (c) 2004 Sassa
*/
public class revCRC {
public static final int POLYNOMIAL = 0x04c11db7;
public static void main(String [] args) throws Exception {
if (args.length!=2){
System.out.println("usage: revCRC <initial string>
<target string> \n\n\tinitial string - may only contain
characters a-z, A-Z\n\ttarget string - may contain '.', wildcards\n\n");
return;
}
byte [] original = args[0].getBytes();
byte [] achieve = args[1].getBytes();
byte [] usageMask = new byte[achieve.length];
int firstBit=achieve.length*8;
for (int i=0; i<usageMask.length; i++){
if (achieve[i]=='.'){
if (firstBit>i*8){
firstBit=i*8;
}
achieve[i]=(byte)0x40;
usageMask[i]=(byte)0xc0;
}else{
usageMask[i]=(byte)0xff;
}
}
java.util.zip.CRC32 javacrc32 = new java.util.zip.CRC32();
javacrc32.reset();
javacrc32.update(original);
long crcOriginal=javacrc32.getValue();
javacrc32.reset();
javacrc32.update(achieve);
long crcAchieve=javacrc32.getValue();
System.out.println("CRC-32 for `"+args[0]+"':
"+Long.toHexString(crcOriginal)+
"\nInitial CRC-32
for `"+new String(achieve)+"':
"+Long.toHexString(crcAchieve));
byte [] a = new byte[achieve.length+4];
byte [] u = new byte[a.length];
byte [] r = new byte[a.length]; // this array will hold the resulting string;
// it is initiated with achieve string
// of bytes, with crc
// Original XOR crcAchieve at the end
System.arraycopy(achieve, 0, a, 0, achieve.length);
a[0] ^= 0xff; // invert the first 4 bytes - that's "
// start with CRC_INIT=0xffffffff"
a[1] ^= 0xff;
a[2] ^= 0xff;
a[3] ^= 0xff;
System.arraycopy(usageMask, 0, u, 0, usageMask.length);
System.arraycopy(a, 0, r, 0, a.length);
crcAchieve ^= crcOriginal; // XOR both - we will show how CRC is calculated first
//crcAchieve=~crcOriginal; // invert the CRC-32 value - get the actual
// CRC of the original message
for (int i=usageMask.length; i<u.length; i++){
a[i]=0;
u[i]=(byte)0xff;
r[i] ^=(byte)(crcAchieve & 0xff); // put 0 here to see the real
// CRC-32 of the message
crcAchieve >>>= 8;
}
usageMask=u;
achieve=a;
byte [][] polynomial = new byte[8][];
int p=POLYNOMIAL;
for (int i=0; i<8; i++){
polynomial[i]=new byte[4];
int p1=p;
for (int j=0; j<polynomial[i].length; j++){
polynomial[i][j]=(byte)(p1 & 0xff);
p1 >>= 8;
}
p=rol(p); // cyclic rotation
}
// now we are ready to reverse the CRC-32 to get the answer
int bit=0; // the rightmost bit
int bitNum=7; // what polynomial to use
int bitpos=0;
// note also that -1 is to account for the 33-d bit of the generator polynomial
int pos=0;
int mask=0xff;
// have to reverse the bits in bytes, so they will be XORed in the right order
reverse_bits(achieve);
reverse_bits(usageMask);
reverse_bits(r);
printBits(achieve);
printBits(r);
System.out.println("-------------");
System.out.println("\n\n*** Calculate CRC-32 now ***\n");
while(bitpos<8*(achieve.length-4)){
mask >>>=1;
if (bit==0) bit=0x80;
printBits(r);
if ((r[pos] & bit) != 0){
// i.e. in the next position there is 1
for (int i=1; i<polynomial[bitNum].length; i++){
r[pos+polynomial[bitNum].length-i] ^= polynomial[bitNum][i];
}
r[pos] ^= (polynomial[bitNum][0] & mask) | bit; // invert the
// highest bit, too
r[pos+polynomial[bitNum].length] ^= polynomial[bitNum][0] & ~mask;
}
printPolynomial(bitpos);
printBits(r);
System.out.println("-------------");
bit>>>=1;
if (bit==0){ // full rotation occured
pos++;
mask=0xff;
}
bitpos++;
bitNum = (bitNum-1) & 7;
}
System.out.println("\n\n*** CRC calculated now ***\n");
printBits(achieve);
printBits(usageMask);
printBits(r);
System.out.println("-------------");
pos=achieve.length-1;
mask=0;
bitpos=8*(achieve.length-4)-1; // this is the position of the
// major bit that will change
bit=1;
bitNum=0;
while(bitpos>=0){
if ((usageMask[pos] & bit)!=0 &&
((achieve[pos] & bit) != (r[pos] & bit))){
// i.e. the usage Mask tells that this bit must have a specific value
// and the bit in r (result) and achieve mask is different,
// need to XOR the lot with the polynomial
for (int i=1; i<polynomial[bitNum].length; i++){
r[pos-i] ^= polynomial[bitNum][i];
}
r[pos] ^= polynomial[bitNum][0] & ~mask;
r[pos-polynomial[bitNum].length] ^= (polynomial[bitNum][0]
& mask) | bit;
// invert the highest bit, too
}
printBits(achieve);
printBits(usageMask);
printPolynomial(bitpos);
printBits(r);
System.out.println("-------------");
bit=(byte)rol(bit, 8);
if (bit==1){ // full rotation occured
pos--;
mask=0;
}else{
mask = (byte)(1 | (mask << 1));
}
bitpos--;
bitNum = (bitNum+1) & 7;
}
reverse_bits(r);
r[0] ^= 0xff; // inverse the first 4 bytes of the result back
r[1] ^= 0xff;
r[2] ^= 0xff;
r[3] ^= 0xff;
byte [] result = new byte[r.length-4];
System.arraycopy(r, 0, result, 0, result.length);
javacrc32.reset();
javacrc32.update(result);
long crcR = javacrc32.getValue();
System.out.println("CRC-32 for `"+new String(result)+
"': "+Long.toHexString(crcR));
}
public static int rol(int p){
return rol(p, 32);
}
public static int rol(int p, int b){
return ((p << 1) | ((p >> (b-1)) & 1)) &
(0xffffffff >>> (32-b));
}
/**
* This method reverses the bits in the bytes of the array.
*/
public static void reverse_bits(byte [] a){
for (int i=0; i<a.length; i++){
int b=0;
for (int j=0; j<8; j++){
b = (b << 1) | (a[i] & 1);
a[i] >>>= 1;
}
a[i]=(byte)b;
}
}
/**
* Debugging method.
*/
public static void printBits(byte [] a){
for (int i=0; i<a.length; i++){
for (int j=0x80; j!=0; j>>=1){
System.out.print((a[i] & j)!=0?"1":"0");
}
System.out.print(" ");
}
System.out.println();
}
public static void printPolynomial(int bitpos){
for (int i=0; i<bitpos; i++) System.out.print(((i+1)& 7)==0?"
":" ");
System.out.print("1");
bitpos++;
for (int j=0x80000000; j!=0; j>>>=1, bitpos++){
System.out.print(
((bitpos & 7)==0?" ":"")+
((POLYNOMIAL & j)!=0?"1":"0")
);
}
System.out.println();
}
}
---------------------------------------------------------------------
Приложение Д
/*
* This code calculates CRC-32 of a given file.
* Then you can specify a CRC to reach, and it will give you 4 bytes to append
* to the file. You will need to xor the bytes with the actual value residing
* in the original file.
* cksum from UNIX does almost the same, but in a less efficient way (see comment
* on RICRC table); besides, they also use file length in the CRC output, and
* they use 0 as initial value, not FFFFFFFF, as specified by the standard.
* prepend your file with FF FF FF FF to obtain 0 CRC at the start
* of the actual file.
* append file length (truncate zero major bytes of the length) - now RICRC will
* give you the same value as the cksum utility.
* (c) 24 August 2001, Sassa
*/
public class CRC32 {
private static final int [] CRC = new int[256]; // the table
private static final int [] RICRC = new int[256];
// the table for reverse input CRC (bytes input msb->lsb, not usual lsb->msb)
public static final int POLYNOMIAL = reverse(0x04c11db7, 32);
// this is a reverse of what Kris Kaspersky used to tell,
// but this is what actually is used by Ethernet, PKZIP,
// etc; if you notice, PKZIP etc have a different way
// of applying it, while most people simply fail to
// calculate the CRC32 properly at all (see all those free
// code on-line). I think, my "RICRC", standing for
// Reverse Input CRC table, is more efficient, than
// the published code, since it does not need to do
// those additional {crc >>> 24} all the time.
// i simply have to output the bytes of the checksum in
// the reverse order - that's all
public static final int INITIAL_VALUE = 0xffffffff;
public static final String HELP_SCREEN = "usage: CRC32 filename
[[-r]crc to achieve]\n\n the utility will calculate crc32 and will tell
you the four bytes to append to the file, to get the given crc32
value\nif -r option is specified, it calculates the bytes for the
Reverse Input CRC (ZIP-like)\n\n";
public static void main(String [] args){
if (args.length<1 || args.length>3){
System.out.println(HELP_SCREEN);
System.exit(0);
}
try{
java.io.FileInputStream fis = new java.io.FileInputStream(args[0]);
init_table();
int crc=INITIAL_VALUE;
int ricrc = reverse(INITIAL_VALUE); // a bit silly thing - just in
// case you will need to use a different
// INITIAL_VALUE
java.util.zip.CRC32 javacrc32=new java.util.zip.CRC32(); // reference implementation
javacrc32.reset();
while(fis.available()!=0){ // I've just checked that my code is
// correct: "resume" = 60C1D0A0 (CRC table),
// as advertised. RICRC gives
// something different, as it is supposed to do,
// either
int c=fis.read();
javacrc32.update(c);
crc = (crc >>> 8) ^ CRC[(crc ^ c) & 0xff];
ricrc = (ricrc >>> 8) ^ RICRC[(ricrc ^ c) & 0xff];
}
fis.close();
System.out.println("Java CRC32: "+Long.toHexString(javacrc32.getValue())+
"\nCRC32: "+Integer.toHexString(crc ^ INITIAL_VALUE)+
"\nReverse input CRC32: "+
Integer.toHexString(reverse_bytes(ricrc) ^ INITIAL_VALUE)
);
if (args.length>1){
int achieve = (int)(Long.parseLong(args[args.length-1], 16) ^ INITIAL_VALUE);
int ri=0;
if (args.length==2){ // no -r option
ri = achieve(achieve, crc);
}else{
ri = achieve(reverse_bytes(achieve), ricrc);
}
System.out.println("\n\nxor the original bytes with such 4 bytes:
"+Integer.toHexString(reverse_bytes(ri)));
}
}catch (Exception ex){
System.out.println("oops...");
ex.printStackTrace();
}
}
public static void init_table(){
for (int i=0; i>> 1) ^ ((CRC[i] & 1)!=0 ? POLYNOMIAL : 0);
}
RICRC[reverse(i, 8)] = reverse(CRC[i]);
}
}
private static int reverse(int what, int bits){
int result = 0;
for (; bits-->0; what >>=1){
result |= (what & 1) << bits;
}
return result;
}
private static int reverse(int what){ // reverses bits in bytes
return reverse_bytes(reverse(what, 32));
}
private static int reverse_bytes(int c){ // reverse bytes
return (c << 24) | ((c & 0xff00) << 8) |
((c >> 8) & 0xff00) | (c >>> 24);
}
private static int achieve(int achieve, int crc){
return achieve ^ crc;
}
}
|
