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

А5 — это поточный алгоритм шифрования, используемый для обеспечения конфиденциальности передаваемых данных между телефоном и базовой станцией в европейской системе мобильной цифровой связи GSM (Groupe Spécial Mobile).

Предупреждение на экране сотового телефона об отсутствии шифрования в сети

Шифр основан на побитовом сложении по модулю два (булева операция «исключающее или») генерируемой псевдослучайной последовательности и шифруемой информации. В A5 псевдослучайная последовательность реализуется на основе трёх линейных регистров сдвига с обратной связью. Регистры имеют длины 19, 22 и 23 бита соответственно. Сдвигами управляет специальная схема, организующая на каждом шаге смещение как минимум двух регистров, что приводит к их неравномерному движению. Последовательность формируется путём операции «исключающее или» над выходными битами регистров.

История создания и развитияПравить

Изначально французскими военными специалистами-криптографами был разработан поточный шифр для использования исключительно в военных целях. В конце 80-х для стандарта GSM потребовалось создание новой, современной системы безопасности. В её основу легли три секретных алгоритма: аутентификации — A3, шифрования потока — A5, генерации сеансового ключа — А8. В качестве алгоритма A5 была использована французская разработка. Этот шифр обеспечивал достаточно хорошую защищённость потока и, следовательно, конфиденциальность разговора. Изначально экспорт стандарта из Европы не предполагался, но вскоре в этом появилась необходимость. Именно поэтому А5 переименовали в А5/1 и стали распространять как в Европе, так и в США. Для остальных стран (в том числе и России) алгоритм модифицировали, значительно понизив криптостойкость шифра. А5/2 был специально разработан как экспортный вариант для стран, не входивших в Евросоюз. Криптостойкость А5/2 была понижена добавлением ещё одного регистра (17 бит), управляющего сдвигами остальных. В А5/0 шифрование отсутствует совсем. В настоящее время разработан также алгоритм А5/3, основанный на алгоритме Касуми и утверждённый для использования в сетях 3G. Эти модификации обозначают как A5/x.

Появление в широком доступеПравить

Официально данная криптосхема не публиковалась и её структура не предавалась гласности. Это было связано с тем, что разработчики полагались на безопасность за счёт неизвестности, то есть алгоритмы труднее взломать, если их описания не доступны публично. Данные предоставлялись операторам GSM только по необходимости. Тем не менее, к 1994 году детали алгоритма А5 были известны: британская телефонная компания British Telecom передала всю документацию, касающуюся стандарта, Брэдфордскому университету для анализа, не заключив соглашения о неразглашении информации. Кроме того, материалы о стандарте появились на одной из конференций в Китае. В результате его схема постепенно просочилась в широкие круги. В этом же году кембриджские учёные Росс Андерсон (Ross Anderson) и Майкл Роу (Michael Roe) опубликовали восстановленную по этим данным криптосхему и дали оценку её криптостойкости. Окончательно алгоритм был представлен в работе Йована Голича на конференции Eurocrypt’97.

Структура А5Править

Алгоритм A5 в настоящее время — это целое семейство шифров. Для описания возьмем А5/1 как родоначальника этого семейства. Изменения в производных алгоритмах опишем отдельно.

Потоковое шифрованиеПравить

Основная статья: Поточный шифр

 

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

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

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

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

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

РСЛОСПравить

Основная статья: Линейный регистр сдвига с обратной связью

 

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

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

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

Система РСЛОС в А5Править

 

Система регистров в алгоритме А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 над выходными битами регистров.

Функционирование алгоритма А5Править

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

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

Отличия производных алгоритмов A5/xПравить

 

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

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

• добавлен регистр R4 длиной 17 бит,
• многочлен обратной связи для R4: $X^{17}+X^{12}+1$$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 не содержит шифрования.

КриптостойкостьПравить

Разработка стандарта GSM подразумевала мощный аппарат шифрования, не поддающийся взлому (особенно в реальном времени). Используемые разработки при надлежащей реализации обеспечивали качественное шифрование передаваемых данных. Именно такую информацию можно получить от компаний, распространяющих этот стандарт. Но стоит отметить важный нюанс: прослушивание разговоров — неотъемлемый атрибут, используемый спецслужбами. Они были заинтересованы в возможности прослушивания телефонных разговоров для своих целей. Таким образом, в алгоритм были внесены изменения, дающие возможность взлома за приемлемое время. Помимо этого, для экспорта A5 модифицировали в A5/2. В MoU (Memorandum of Understand Group Special Mobile standard) признают, что целью разработки A5/2 было понижение криптостойкости шифрования, однако в официальных результатах тестирования говорится, что неизвестно о каких-либо недостатках алгоритма.

Известные уязвимостиПравить

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

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

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

Известные атакиПравить

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

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

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

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

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

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

СсылкиПравить

• instant ciphertext-only cryptanalysis of GSM encrypted communication (англ.) (pdf). Дата обращения: 24 ноября 2009. Архивировано из оригинала 25 июля 2009 года.
• GSM security (англ.). Дата обращения: 24 ноября 2009. Архивировано из оригинала 23 ноября 2009 года.