Сергей Холодилов (fat_crocodile) wrote,
Сергей Холодилов
fat_crocodile

CRC-3: как его обойти

CRC не криптографически-стойкий алгоритм, он предназначен для обнаружения ошибок, вызванных неразумными обстоятельствами, а не разумным противником. В некоторых частных случаях оказывается ну очень просто изменить сообщение, сохранив значение CRC.

Ещё немного неуверенной алгебры
Математически мы ищем многочлен вида

(ak*x^k + ... + a1*x + a0) * x^n,

дающий заданный остаток R при делении на заданный многочлен G степени n.

Для этого надо посчитать обратный элемент к x^n в кольце вычетов по модулю G, домножить на него R, так получится остаток, который должен давать искомый многочлен ak*x^k + ... + a1*x + a0. Дальше просто, берем любой, можно прямо сам остаток и взять.

Надо только, чтобы обратный элемент был. Кажется, он есть, если многочлены взаимнопросты. Кажется, из общих соображений можно сказать, что многочлены с коэффициентами из GF(2) ни чем не хуже обычных, и тоже разложимы единственным способом, и поэтому у x^n нет никаких неожиданных делителей, только x. А применяемые в CRC многочлены на x обычно не делятся, так что кажется все хорошо.

Ну в общем программа такая:
- расширенным алгоритмом Евклида находим обратный для x^n
- умножаем на него нужный остаток R, берем результат по модулю G
- полученный многочлен проверяем

Для простоты на Питоне, он нативно поддерживает длинные числа и позволяет переопределять операторы.
Вот так выглядит расширенный алгоритм Евклида:

# return x, y, d such that:
# - d is the greatest common divisor
# - a*x + b*y = d
def extended_euclid(a, b):
    if a == 0: return 0, 1, b
    if b == 0: return 1, 0, a

    x, y, d = extended_euclid(b, a % b)     # b * x  +  (a % b) * y == d
    return y, x - y * (a // b), d           # a % b = a - (a // b) * b   ==> a * y + b * (x - y * (a // b)) = d

Дальше, понятно, если a*x + b*y = 1, то x = a^-1 mod b
def invert_mod(a, n):
    x, y, d = extended_euclid(a, n)
    if d != 1:
        return None
    return x % n

Класс, реализующий сам полином не очень интересный, код можно посмотреть здесь

CRC-32Q
Для простоты начнем с этого алгоритма, так как он очень прямолинеен: начальное значение регистра 0, обращать ничего не надо, ксорить ничего не надо. Полином 0x1814141AB (в стандартной CRC-нотации старшая единица опускается).

crc-23q('hello, world') = 0xF6ADBF28
(2^32)^-1 mod 0x1814141AB = 0xc23a2112
0xF6ADBF28 * 0xc23a2112 mod 0x1814141AB = 0x384349b9

Проверяем:

crc-32q(0x384349b9) = 0xF6ADBF28

Ура!

Это был многочлен, сделанный с нуля. Теперь другая штука: пусть есть начало, которое надо продолжить так, чтобы получить заданный остаток. Это тривиально делается за 4 байта.

crc-32q('good buy, ') = 0x3342DA5E

ищем ответ в виде

'good buy, XXXX' = 'good buy, ' * 2^32 + 'XXXX'

удачно, что остаток по модулю 0x1814141AB от 'good buy, ' * 2^32 это как раз значение crc-32q
так что, переходя к остаткам получаем

'good buy, ' * 2^32 + 'XXXX' mod 0x1814141AB = 0x3342DA5E + 'XXXX'

Чтобы сошлось, остаток должен получиться такой же, как в прошлый раз, 0x384349b9. Значит

'XXXX' = 0x3342DA5E - 0x384349b9 = 0x0b0193e7

проверяем

crc-32q('good buy, ' + 0x0b0193e7) = 0xF6ADBF28

Ура!

А если надо что-то поменять в середине? Тут можно воспользоваться тем, что если A = B mod P, то Axyz = Bxyz mod P. То есть, если два текста дают одинаковые crc, при дописывании к ним одинаковых суффиксов равенство сохранится.

CRC-32
Всё сложно. Начальное значение регистра 0xffffffff, байты нужно отражать и результат тоже, и потом поксорить с 0xffffffff. Полином 0x104C11DB7.

crc-23('hello, world') = 0xFFAB723A

убираем xor

0xFF AB 72 3A --> 0x00 54 8D C5

разворачиваем

0x00 54 8D C5 --> 0xA3 B1 2A 00

считаем обратный к 2^32, домножаем на него то, что получилось из crc

(2^32)^-1 mod 0x104C11DB7 = 0xcbf1acda
0xA3B12A00 * 0xcbf1acda mod 0x104C11DB7 = 0x2ce24c70

это остаток, который искомый многочлен должен иметь, осталось учесть перевернутые байты и начальное значение регистра.

0x2c e2 4c 70 --> 0x34 47 32 0e перевернутые байты
0x34 47 32 0e --> 0xcb b8 cd f1 начальное значение

Проверяем:

crc-32(0xcbb8cdf1) = 0xFFAB723A

Ура!
Ну и понятно, что если не с нуля, а менять с того, что есть на заданный -- тоже можно, просто более запарно.

P.S. А что если совсем без алгебры
Да тоже не сложно. Напомню алгоритм:

пока в сообщении есть ещё байты
    в регистр справа задвигаем нулевой байт
    регистр ^= таблица[старший_выдвинутый_байт ^ старший_байт_сообщения]

Давайте посмотрим на последний байт CRC. Он получился из xor-а нулевого байта и значения из таблицы.

Так можно найти использовавшийся последним элемент таблицы -- может быть будет несколько вариантов, не важно, вряд ли их будет много (из проверенных мною только алгоритм crc-16/arc оказался плохим в этом смысле: у него всего 8 вариантов последних байтов, по 32 штуки каждого). Соответственно можно отменить последнее действие и найти предпоследний элемент. И т.п., нам нужно получить последние четыре элемента таблицы (для 32-разрядного алгоритма).

После чего нужно сконструировать такой вход, который будет их привлекать.

Если мы делаем многочлен с нуля, то у нас есть исходное состояние регистра, если продолжаем -- какое-то состояние регистра, на котором процесс остановился. По алгоритму

номер_элемента_таблицы = старший_выдвинутый_байт ^ старший_байт_сообщения

Из трех переменных мы знаем две: старший байт регистра и нужный нам номер. Соответственно, очередной байт сообщения находится как

старший_байт_сообщения = номер_элемента_таблицы ^ старший_выдвинутый_байт

после чего делаем этот шаг алгоритма, т.е. ксорим регистр с элементом таблицы. Повторить ещё три раза.

Всё! И на этом тему CRC закрываем.
Tags: математика, программинг
Subscribe

  • (no subject)

    Очень простую штуку объяснили, как-то мимо проходила. В книжках про ассемблер и прочее такое пишут про "представление отрицательных чисел в…

  • (no subject)

    Наконец вроде осознал, когда и зачем аксиома выбора нужна, а когда она не нужна. Если у нас есть одно непустое множество X и нам нужно взять…

  • CRC-2: немного алгебры

    Благодаря разговору с kodt_rsdn в прошлом посте, удалось переформулировать происходящее, добавив туда немного математического смысла.…

  • Post a new comment

    Error

    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments