Common Scrambling Algorithm (Common Scrambling Algorithm)

CSA (англ. Common Scrambling Algorithm — общий алгоритм скремблирования) — алгоритм шифрования, используемый для защиты цифрового телевизионного потока от несанкционированного доступа. Алгоритм был разработан организацией ETSI и принят на консорциуме DVB в мае 1994 года. На данный момент алгоритм CSA заменен на CSA3, на основе 128-битного AES. Тем не менее, CSA3 пока не получил большого распространения, так что CSA продолжает быть доминирующим шифром для защиты DVB вещания.

История

Стандарт для алгоритма CSA принимали под руководством таких организаций, как the Joint Technical Committee (JTC) of the European Broadcasting Union (EBU), Comité Européen de Normalisation ELECtrotechnique (CENELEC) и the European Telecommunications Standards Institute (ETSI).

Алгоритм CSA был полностью засекречен вплоть до 2002 года. Некоторые детали его реализации можно было определить из документов, таких как патенты. Однако наиболее существенные части алгоритма, такие как S-блоки, были засекречены. Это делало невозможным использование алгоритма сторонними разработчиками без получения соответствующей лицензии от DVB. В это время все реализации алгоритма были исключительно аппаратными, что также затрудняло обратную разработку и воспроизведение алгоритма в каком-либо виде.

В 2002 году в свет вышла программа FreeDec, в которой был программно реализован алгоритм CSA. Анализ исполняемых файлов этой программы позволил получить дизассемблированный код алгоритма со всеми недостающими деталями. После того, как алгоритм стал рассекречен, у криптоаналитиков появилась возможность искать его слабые места.

Описание алгоритма

Алгоритм CSA является комбинацией двух различных шифров: блочного шифра и поточного шифра. При работе в режиме шифрования данные сначала шифруются с использованием 64 битного блочного шифра в режиме CBC (англ. Cipher Block Chaining — режим сцепления блоков шифротекста), начиная с конца пакета. Затем применяется поточный шифр (Stream cipher) от начала пакета.

Блочный шифр

Блочный шифр обрабатывает 64 битные блоки в 56 раундов. Ключ расширяется до 448 бит и на каждом раунд используется 8 бит этого расширенного ключа.

Поточный шифр

Первые 32 раунда поточного шифра используются для инициализации, и не формирует никаких выходных данных. Первые 64 бит данных используются в качестве вектора инициализации во время этой фазы и остаются неизменными. Потоковый шифр генерирует 2 бита псевдослучайного потока на каждом раунде, которые складываются операцией XOR с данными, начиная с 64 бита пакета.

Спецификация ключа

В шифровании используется общий ключ K, и первый блок передаваемого потока специальным образом инициализирует начальное состояние. Затем общий ключ $K=\left({k_{0},\ldots ,k_{63}}\right)$ загружается в регистры сдвига $A=\left({a_{0,j},\ldots ,a_{9,j}}\right)$ и $B=\left({b_{0,j},\ldots ,b_{9,j}}\right)$, где $0\leqslant j\leqslant 3$, согласно следующему правилу:

$a_{i,j}=\left\{{\begin{matrix}k_{4\cdot i+j},i\leqslant 7\\0,i\leqslant 7\end{matrix}}\right.$

$b_{i,j}=\left\{{\begin{matrix}k_{32+4\cdot i+j},i\leqslant 7\\0,i\leqslant 7\end{matrix}}\right.$

Далее шифр находится в режиме инициализации. Он использует первый блок потока и регистр обратной связи D в качестве входных данных и выполняет 32 тактовых цикла для расчёта начального состояния.

Использование алгоритма

В соответствии с документами, опубликованными организацией DVB, все технические детали алгоритма CSA являются секретными. Любая организация, желающая использовать этот алгоритм шифрования при создании собственной системы условного доступа, должна получить соответствующую лицензию и подписать соглашение о неразглашении полученной информации. Эти требования остаются в силе несмотря на то, что в настоящее время детали алгоритма повсеместно известны и проведен его тщательный криптоанализ.

Слабые стороны алгоритма

После выявления слабостей алгоритма CSA, стало возможным получить доступ к любым видео данным, зашифрованным с его использованием, что создает определённые трудности для многочисленных вещателей цифрового телевидения в Европе и других местах, использующих системы условного доступа на основе алгоритма CSA. Несмотря на то, что криптографические атаки на алгоритм в настоящее время опубликованы, он продолжает широко использоваться.

Большинство нападений на системы платного ТВ не были направлены на сам CSA, а вместо этого были направлены на различные ключевые системы обмена ответственные за генерацию ключей CSA (Conax, Irdeto, VideoGuard и т. д.);

Криптоанализ

Криптоанализ затрудняется тем, что большинство данных защищены как блочным, так и поточным шифрами. Тем не менее, есть части, защищенные всего лишь одним из шифров. Только первые 64-бита зашифрованы блочным шифром, и любые избыточные биты после последнего 64-битного блока (от нуля до семи байт) защищены только потоковым шифром. Тем не менее, блочный шифр применяется от конца пакета к началу в режиме CBC, что означает, что, в конце концов, каждый бит выходного сигнала зависит от каждого бита на входе, и каждая ячейка в 183 байт должна быть декодирована целиком.

Однако, у алгоритма CSA существует ряд слабых мест, которые позволяют вскрывать зашифрованные сообщения методами современного криптоанализа. Поскольку алгоритм был разработан исключительно для применения в области передачи цифрового телевизионного потока, становятся заранее известны некоторые участки открытых сообщений. К ним относятся заголовки MPEG-пакетов, некоторые фрагменты которых имеют предсказуемую структуру. С точки зрения криптоанализа такая особенность является существенной слабостью криптографического алгоритма, которая в данном случае неизбежна.

Метод грубой силы

Длина ключа в CSA составляет всего 64 бита (8 байт) и по современным криптографическим меркам является очень малой. Такая длина вполне допускает взлом ключа методом грубой силы за конечное время, который ещё более облегчается с учётом первой описанной слабости. Более того, фактическая длина секретного ключа составляет всего 48 бит, поскольку два байта из восьми используются в качестве контрольной суммы (байты с номерами 3 и 7, если занумеровать байты ключа от 0 до 7). Эти байты вычисляются путём сложения по модулю 2 трёх предыдущих байт. Ещё 16 бит можно определить с помощью таблиц памяти, построенных на основе шифротекста. Таким образом, прямой перебор нужно применять только к 32 битам из 64, а вторую половину ключа вычислять на основе первой. При реализации такого подхода на основе ПЛИС или с использованием Cell-процессора подбор ключа должен занимать не более 1 секунды. Однако чтобы проверить, является ли подобранный ключ верным, необходимо проанализировать заголовки полученных MPEG-пакетов. Это создает определённые вычислительные трудности при реализации методов взлома.

Программная реализация и фрагментирование

Потоковое шифрование в CSA подвержено фрагментированию, которое является программной реализацией, позволяющей расшифровать множество блоков или один блок с множеством различных ключей. Это значительно ускоряет поиск методом грубой силы, но в то же время является недостаточным для совершения атак в реальном масштабе времени.

Блочный шифр сложнее фрагментировать, поскольку соответствующие S-блоки являются слишком большими (8x8) для того, чтобы быть эффективно реализованными при помощи логических операций. Это является необходимым условием для того, чтобы фрагментация была эффективнее обычной реализации. Однако из-за того, что все операции происходят в 8-битных подблоках, алгоритм может быть реализован с использованием обычных команд SIMD или «среза байтов». Поскольку большинство наборов команд SIMD, за исключением AVX2, не поддерживают параллельные поисковые таблицы, подстановки S-блоков выполняется без среза байтов, однако, интеграция данных блоков в оставшуюся часть алгоритма этому не препятствует.

Оба метода используются в libdvbcsa, что является свободной реализацией CSA.

Атака на основе известного открытого текста

В 2011 году группа немецких исследователей реализовала атаку на алгоритм CSA, используемый в DVB системе. Этой группой было замечено, что в H. 262 (ISO 13818-2) кодек сжатия видео, используемый в формате DVB-S, так называемый вброс байт, используется для обеспечения минимальной скорости потока. Стандарт ISO 13818-2 позволяет вставлять только нулевые байты между элементами битового потока. Поскольку DVB-CSA является полностью детерминированным, все зашифрованные нулевые ячейки в формате MPEG-TS (транспортный поток) обнаруживаются как совпадающие в зашифрованном тексте, если в течение всего времени существования ключа происходит два нулевых кадра. Все нули в основном соблюдаются при кодировании серии кадров, не имеющих или только маленькие отличия. Например, в телеторговом шоу, отображающем статическое изображение продукта, будет генерироваться множество ячеек с нулевым значением. Хорошим примером может быть видеозапись со старой плёночной камерой, содержащей множество царапин или других артефактов. Некоторые программы всегда содержат некоторое число ячеек с нулевым значением, чтобы можно было восстановить известный неформатированный текст. Это приводит к тому, что целые ячейки 183-байтов шифруются только нулями. Таким образом, можно построить радужную таблицу различных сценариев атаки.

При условии, что жёсткий диск способен выполнять 100 случайных обращений в секунду, а противник может зашифровать около 4 000 000 элементов графического процессора и около 500 000 элементов на одном ядре ЦП. Противник может интересоваться восстановлением передачи в режиме DVB-CSA в реальном времени. Ему необходимо восстановить единый ключ DVB-CSA менее чем за 7 секунд. При использовании графического процессора в предвычислениях требуется 4 жёстких диска и 7,9 ТБ памяти. Такая таблица может быть предварительно рассчитана на одной графической карте менее чем за 13 лет. Использование нескольких графических плат или более быстрых графических карт уменьшает необходимое время. Кроме того, противник может не интересоваться декодированием передачи в реальном времени, или он хотел бы восстановить статический ключ от станции, который только изменяет ключ вручную. Если ключ должен быть восстановлен в течение 30 минут, это может быть сделано с 120 ГБ на графической карте (менее 8 лет предрасчетов на одной графической карте) или 525гб предрасчетов на ЦП (менее 5 лет предрасчетов на графической карте).

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

Литература

• Erik Tews, Julian Wälde, and Michael Weiner. "Breaking DVB-CSA". — West European Workshop on Research in Cryptography, 2011.
• Kai Wirt. "Fault attack on the DVB Common Scrambling Algorithm". — Cryptology ePrint Archive, 2004.
• Ralf-Philipp Weinmann, Kai Wirt. "Analysis of the DVB Common Scrambling Algorithm". — Springer, 2004.