A5 (алгоритм шифрования)

Схема поточного шифра: сложение открытого текста и последовательности бит даёт шифротекст

В этом алгоритме каждому символу открытого текста соответствует символ шифротекста. Текст не делится на блоки (как в блочном шифровании) и не изменяется в размере. Для упрощения аппаратной реализации и, следовательно, увеличения быстродействия используются только простейшие операции: сложение по модулю 2 (XOR) и сдвиг регистра.

Формирование выходной последовательности происходит путём сложения потока исходного текста с генерируемой последовательностью (гаммой). Особенность операции XOR заключается в том, что применённая чётное число раз, она приводит к начальному значению. Отсюда, декодирование сообщения происходит путём сложения шифротекста с известной последовательностью.

Таким образом, безопасность системы полностью зависит от свойств последовательности. В идеальном случае каждый бит гаммы — это независимая случайная величина, и сама последовательность является случайной. Такая схема была изобретена Вернамом в 1917 году и названа в его честь. Как доказал Клод Шеннон в 1949 году, это обеспечивает абсолютную криптостойкость. Но использование случайной последовательности означает передачу по защищённому каналу сообщения, равного по объёму открытому тексту, что значительно усложняет задачу и практически нигде не используется.

В реальных системах создаётся ключ заданного размера, который без труда передаётся по закрытому каналу. Последовательность генерируется на его основе и является псевдослучайной. Большой класс поточных шифров (в том числе A5) составляют шифры, генератор псевдослучайной последовательности которой основан на регистрах сдвига с линейной обратной связью.

Регистр сдвига с линейной обратной связью,
многочлен обратной связи х³²+х²⁹+х²⁵+х⁵+1

Регистр сдвига с линейной обратной связью состоит из собственно регистра (последовательности бит заданной длины) и обратной связи. На каждом такте происходит следующие действия: крайний левый бит (старший бит) извлекается, последовательность сдвигается влево и в опустевшую правую ячейку (младший бит) записывается значение функции обратной связи. Эта функция является суммированием по модулю два определённых битов регистра и записывается в виде многочлена, где степень указывает номер бита. Извлечённые биты формируют выходную последовательность.

Для РСЛОС основным показателем является период псевдослучайной последовательности. Он будет максимален (и равен 2ⁿ−1), если многочлен функции обратной связи примитивен по модулю 2. Выходная последовательность в таком случае называется М-последовательностью.

Система регистров в алгоритме А5/1

Сам по себе РСЛОС легко поддаётся криптоанализу и не является достаточно надёжным для использования в шифровании. Практическое применение имеют системы регистров переменного тактирования с различными длинами и функциями обратной связи.

Структура алгоритма А5 выглядит следующим образом:

• Три регистра(R1, R2, R3) имеют длины 19, 22 и 23 бита,
• Многочлены обратных связей:
  • X¹⁹ + X¹⁸ + X¹⁷ + X¹⁴ + 1 для R1,
  • X²² + X²¹ + 1 для R2 и
  • X²³ + X²² + X²¹ + X⁸ + 1 для R3,
• Управление тактированием осуществляется специальным механизмом:
  • в каждом регистре есть биты синхронизации: 8 (R1), 10 (R2), 10 (R3),
  • вычисляется функция F = x&y|x&z|y&z, где & — булево AND, | - булево OR, а x, y и z — биты синхронизации R1, R2 и R3 соответственно,
  • сдвигаются только те регистры, у которых бит синхронизации равен F,
  • фактически, сдвигаются регистры, синхробит которых принадлежит большинству,
• Выходной бит системы — результат операции XOR над выходными битами регистров.

Рассмотрим особенности функционирования алгоритма на основе известной схемы. Передача данных осуществляется в структурированном виде — с разбивкой на кадры (114 бит). Перед инициализацией регистры обнуляются, на вход алгоритма поступают сеансовый ключ (K — 64 бита), сформированный А8, и номер кадра (Fn — 22 бита). Далее последовательно выполняются следующие действия:

• Инициализация:
  • 64 такта, при которых очередной бит ключа XOR-ится с младшим битом каждого регистра, регистры при этом сдвигаются на каждом такте,
  • аналогичные 22 такта, только операция XOR производится с номером кадра,
  • 100 тактов с управлением сдвигами регистров, но без генерации последовательности,
• 228 (114 + 114) тактов рабочие, происходит шифрование передаваемого кадра (первые 114 бит) и дешифрование (последние 114 бит) принимаемого,
• далее инициализация производится заново, используется новый номер кадра.

Система регистров в алгоритме А5/2

В алгоритм А5/2 добавлен ещё один регистр на 17 бит (R4), управляющий движением остальных. Изменения структуры следующие:

• добавлен регистр R4 длиной 17 бит,
• многочлен обратной связи для R4: ${\displaystyle X^{17}+X^{12}+1}$,
• управление тактированием осуществляет R4:
  • в R4 биты 3, 7, 10 есть биты синхронизации,
  • вычисляется мажоритарная функция F = x&y|x&z|y&z (равна большинству), где & — булево AND, | - булево OR, а x, y и z — биты синхронизации R4(3), R4(7) и R4(10) соответственно,
  • R1 сдвигается если R4(10) = F,
  • R2 сдвигается если R4(3) = F,
  • R3 сдвигается если R4(7) = F,
• выходной бит системы — результат операции XOR над старшими битами регистров и мажоритарных функций от определённых битов регистров:
  • R1 — 12, 14, 15,
  • R2 — 9, 13, 16,
  • R3 — 13, 16, 18.

Изменения в функционировании не такие существенные и касаются только инициализации:

• 64+22 такта заполняется сеансовым ключом и номером кадра также R4,
• 1 такт R4(3), R4(7) и R4(10) заполняются 1,
• 99 тактов с управлением сдвигами регистров, но без генерации последовательности.

Видно, что инициализация занимает такое же время (100 тактов без генерации разбиты на две части).

Алгоритм А5/3 разработан в 2001 году и должен сменить A5/1 в третьем поколении мобильных систем. Также он называется алгоритм Касуми. При его создании за основы взят шифр MISTY корпорации Mitsubishi. В настоящее время считается, что A5/3 обеспечивает требуемую стойкость.

Алгоритм A5/0 не содержит шифрования.

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

• 10 бит ключа принудительно занулены,
• отсутствие перекрестных связей между регистрами (кроме управления сдвигами),
• шифрование служебной информации, известной криптоаналитику,
• свыше 40 % ключей приводит к минимальной длине периода генерируемой последовательности, а именно ${\displaystyle {\frac {4}{3}}\left({2^{23}-1}\right)}$[3]
• в начале сеанса осуществляется обмен нулевыми сообщениями (по одному кадру),
• одинаковое дополнение (padding) для всех пакетов,
• в A5/2 движение осуществляется отдельным регистром длиной 17 бит.

На основе этих «дыр» в алгоритме построены схемы взлома.

Ключом является сеансовый ключ длиной 64 бита, номер кадра считается известным. Таким образом, сложность атаки, основанной на прямом переборе, равна 2⁶⁴.

Первые обзоры шифра (работа Росса Андерсона) сразу выявили уязвимость алгоритма — из-за уменьшения эффективной длины ключа (зануление 10 бит) сложность упала до 2⁴⁵ (сразу на 6 порядков). Атака Андерсона основана на предположении о начальном заполнении коротких регистров и по выходным данным получения заполнения третьего.

В 1997 году Йован Голич опубликовал результаты анализа А5. Он предложил способ определения первоначального заполнения регистров по известному отрезку гаммы длиной всего 64 бита. Этот отрезок получают из нулевых сообщений. Атака имеет среднюю сложность 2⁴⁰.

В 1999 году Вагнеру и Голдбергу без труда удалось продемонстрировать, что для вскрытия системы достаточно перебором определить начальное заполнение R4. Проверка осуществляется за счёт нулевых кадров. Сложность этой атаки равна 2¹⁷, таким образом, на современном компьютере вскрытие шифра занимает несколько секунд.

В декабре 1999 года группа израильских учёных (Ади Шамир, Алекс Бирюков, а позже и американец Дэвид Вагнер) опубликовали весьма нетривиальный, но теоретически очень эффективный метод вскрытия A5/1: