Просмотр кода страницы A5 (алгоритм шифрования)

{{другие значения|A5 (значения)}}

[[Файл:Ciphering NotProvidedRu.JPG|right|thumb|200 px|Предупреждение на экране [[сотовый телефон|сотового телефона]] об отсутствии шифрования в сети]]

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

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

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

== Появление в широком доступе ==
Официально данная криптосхема не публиковалась и её структура не предавалась гласности. Это было связано с тем, что разработчики полагались на [[Безопасность через неясность|безопасность за счёт неизвестности]], то есть алгоритмы труднее взломать, если их описания не доступны публично. Данные предоставлялись операторам GSM только по необходимости. Тем не менее, к 1994 году детали алгоритма А5 были известны: британская телефонная компания ''British Telecom'' передала всю документацию, касающуюся стандарта, Брэдфордскому университету для анализа, не заключив [[соглашение о неразглашении|соглашения о неразглашении]] информации. Кроме того, материалы о стандарте появились на одной из конференций в Китае. В результате его схема постепенно просочилась в широкие круги. В этом же году кембриджские учёные Росс Андерсон (Ross Anderson) и Майкл Роу (Michael Roe) опубликовали восстановленную по этим данным криптосхему и дали оценку её криптостойкости<ref>{{cite web
 | last          = Anderson
 | first          = Ross
 | datepublished          = 1994-06-07
 | url          = http://www.ussrback.com/crypto/source/algorithms/A5-GSM-Algorithm.txt
 | title          = A5 - The GSM Encryption Algorithm
 | format          = txt
 | publisher          = sci.crypt
 | accessdate          = 2009-11-24
 | lang          = en
 | archiveurl          = https://web.archive.org/web/20110921194608/http://www.ussrback.com/crypto/source/algorithms/A5-GSM-Algorithm.txt
 | archivedate          = 2011-09-21
 | deadlink          = yes
 }}</ref>. Окончательно алгоритм был представлен в работе Йована Голича на конференции Eurocrypt’97.

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

=== Потоковое шифрование ===
{{main|Поточный шифр}}
[[Файл:Поточный шифр.PNG|right|thumb|400px|Схема поточного шифра: сложение открытого текста и последовательности бит даёт шифротекст]]
В этом алгоритме каждому символу открытого текста соответствует символ шифротекста. Текст не делится на блоки (как в [[Блочный шифр|блочном шифровании]]) и не изменяется в размере. Для упрощения аппаратной реализации и, следовательно, увеличения быстродействия используются только простейшие операции: [[Сложение по модулю 2|сложение по модулю 2 (XOR)]] и сдвиг регистра.

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

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

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

=== РСЛОС ===
{{main|Линейный регистр сдвига с обратной связью}}
[[Файл:РСЛОС.png|right|thumb|400px|Регистр сдвига с линейной обратной связью,<br> многочлен обратной связи х<sup>32</sup>+х<sup>29</sup>+х<sup>25</sup>+х<sup>5</sup>+1]]
Регистр сдвига с линейной обратной связью состоит из собственно регистра (последовательности бит заданной длины) и обратной связи. На каждом такте происходит следующие действия: крайний левый бит (старший бит) извлекается, последовательность сдвигается влево и в опустевшую правую ячейку (младший бит) записывается значение функции обратной связи. Эта функция является суммированием по модулю два определённых битов регистра и записывается в виде многочлена, где степень указывает номер бита. Извлечённые биты формируют выходную последовательность.

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

==== Система РСЛОС в А5 ====
[[Файл:РСЛОС в A5.png|right|thumb|400px|Система регистров в алгоритме А5/1]]
Сам по себе РСЛОС легко поддаётся криптоанализу и не является достаточно надёжным для использования в шифровании. Практическое применение имеют системы регистров переменного тактирования с различными длинами и функциями обратной связи.

Структура алгоритма А5 выглядит следующим образом:
* Три регистра(R1, R2, R3) имеют длины 19, 22 и 23 бита,
* Многочлены обратных связей:
** X<sup>19</sup> + X<sup>18</sup> + X<sup>17</sup> + X<sup>14</sup> + 1 для R1,
** X<sup>22</sup> + X<sup>21</sup> + 1 для R2 и
** X<sup>23</sup> + X<sup>22</sup> + X<sup>21</sup> + X<sup>8</sup> + 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 ===
[[Файл:РСЛОСвA52.png|right|thumb|400px|Система регистров в алгоритме А5/2]]
'''В алгоритм А5/2''' добавлен ещё один регистр на 17 бит (R4), управляющий движением остальных. Изменения структуры следующие:
* добавлен регистр R4 длиной 17 бит,
* многочлен обратной связи для R4: <math>X^{17} + X^{12} + 1</math>,
* управление тактированием осуществляет 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 в третьем поколении мобильных систем. Также он называется алгоритм [[KASUMI|Касуми]]. При его создании за основы взят шифр [[MISTY1|MISTY]] корпорации Mitsubishi. В настоящее время считается, что A5/3 обеспечивает требуемую стойкость.

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

== Криптостойкость ==
Разработка стандарта GSM подразумевала мощный аппарат шифрования, не поддающийся взлому (особенно в реальном времени). Используемые разработки при надлежащей реализации обеспечивали качественное шифрование передаваемых данных. Именно такую информацию можно получить от компаний, распространяющих этот стандарт. Но стоит отметить важный нюанс: прослушивание разговоров — неотъемлемый атрибут, используемый спецслужбами. Они были заинтересованы в возможности прослушивания телефонных разговоров для своих целей. Таким образом, в алгоритм были внесены изменения, дающие возможность взлома за приемлемое время. Помимо этого, для экспорта A5 модифицировали в A5/2. В MoU (Memorandum of Understand Group Special Mobile standard) признают, что целью разработки A5/2 было понижение криптостойкости шифрования, однако в официальных результатах тестирования говорится, что неизвестно о каких-либо недостатках алгоритма<ref>{{cite web | archiveurl = https://web.archive.org/web/20040712061808/http://www.ausmobile.com/downloads/technical/Security+in+the+GSM+system+01052004.pdf | first = Jeremy | last = Quirke | archivedate = 2004-07-12 | title = Security in the GSM system | publisher = AusMobile | date = 2004-05-01 | url = http://www.ausmobile.com/downloads/technical/Security+in+the+GSM+system+01052004.pdf | deadurl = yes }}</ref>.

<!-- Интересны цитаты из приказа министерства связи российской федерации от 31 января 1996 года N 9
''(СОРМ — система оперативно-розыскных мероприятий, СПРС — сети подвижной радиотелефонной связи)''<ref>http://web.ku.edu/~herron/info_policy/russia/sorm_7_mindec_96.pdf</ref>
<ref>{{cite web
 | url           = http://www.libertarium.ru/l_sormlaw_9
 | title         = Министерство связи РФ, приказ №9 от 31 января 1996 года
 | accessdate    = 2009-11-24
 | lang          = ru
}}</ref>
{{начало цитаты}}
СОРМ СПРС должна обеспечивать:
* контроль исходящих и входящих вызовов контролируемых подвижных абонентов в СПРС;
* контроль исходящих вызовов (местных, внутризоновых, междугородных и международных) от всех абонентов СПРС к определенным абонентам (анализ по номеру В);
* предоставление данных о местоположении контролируемых ПА, ПС при их перемещении по СПРС;
* сохранение контроля за установленным соединением при процедурах передачи управления вызовом (handover) как между БС в пределах одного ЦКП, так и разных ЦКП;
* контроль вызовов при предоставлении ПА дополнительных услуг связи, в частности, изменяющих направление вызова (Call Forwarding). При предоставлении ПА такой услуги, в процессе установления соединения должны контролироваться номера, на которые вызов перенаправляется (возможно неоднократное перенаправление вызова до установления разговорного состояния);
* контроль за соединениями, обеспечивающими передачу телефонной и нетелефонной информации (передача данных, факсимильная связь, короткие сообщения);
* при предоставлении контролируемому ПА дополнительной услуги «конференцсвязь», обеспечивающей возможность ПА одновременного разговора с несколькими абонентами, должны контролироваться номера всех участников конференцсвязи;
* возможность получения по запросу с ПУ информации о ПА по его идентификатору или присвоенному номеру ТфОП, ЦСИС, а именно, предоставляемые данному ПА услуги связи.
{{конец цитаты}}-->

=== Известные уязвимости ===
С появлением данных о стандарте A5 начались попытки взлома алгоритма, а также поиска уязвимостей. Огромную роль оказали особенности стандарта, резко ослабляющие защиту, а именно:
* 10 бит ключа принудительно занулены,
* отсутствие перекрестных связей между регистрами (кроме управления сдвигами),
* шифрование служебной информации, известной криптоаналитику,
* свыше 40 % ключей приводит к минимальной длине периода генерируемой последовательности, а именно <math>\frac{4}{3}\left( {2^{23}  - 1} \right)</math><ref>{{cite web
 | last          = Preneel
 | first         = Bart
 | datepublished = 1994-12
 | url           = https://books.google.ru/books?id=kCt91nGHR_MC&dq=Fast+Software+Encryption+-+Second+International+Workshop&printsec=frontcover&source=bl&ots=FXMr7Wp3jj&sig=jOvxS-drWxyyloVVMyAzM5cSbDg&hl=ru&ei=y2oES-GGOJqCnQO7m6h1&sa=X&oi=book_result&ct=result&resnum=1&ved=0CAgQ6AEwAA#v=onepage&q=&f=false
 | title         = Fast software encryption
 | format        = google book
 | accessdate    = 2009-11-24
 | lang          = en
 | description   = (стр. 26)
}}</ref>
* в начале сеанса осуществляется обмен нулевыми сообщениями (по одному кадру),
*одинаковое дополнение (padding) для всех пакетов,
* в A5/2 движение осуществляется отдельным регистром длиной 17 бит.
На основе этих «дыр» в алгоритме построены схемы взлома.

=== Известные атаки ===
Ключом является сеансовый ключ длиной 64 бита, номер кадра считается известным. Таким образом, сложность атаки, основанной на прямом переборе, равна 2<sup>64</sup>.

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

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

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

В декабре 1999 года группа израильских учёных ([[Шамир, Ади|Ади Шамир]], [[Бирюков, Алекс|Алекс Бирюков]], а позже и американец {{Не переведено|Вагнер, Девид (исследователь)|Дэвид Вагнер|en|David A. Wagner}}) опубликовали весьма нетривиальный, но теоретически очень эффективный метод вскрытия A5/1:
{{цитата|автор=[[Шамир, Ади|Ади Шамир]]|Это весьма сложная идея, реализуя которую мы наступаем на многих фронтах, чтобы накопить несколько небольших преимуществ, но сложенные все вместе, они дают большой выигрыш.}}

== Примечания ==
{{примечания}}

== Ссылки ==
* {{cite web
 | url  = http://cryptome.org/gsm-crack-bbk.pdf
 | title  = instant ciphertext-only cryptanalysis of GSM encrypted communication
 | format  = pdf
 | accessdate  = 2009-11-24
 | lang  = en
 | archiveurl  = https://web.archive.org/web/20090725012506/http://cryptome.org/gsm-crack-bbk.pdf
 | archivedate  = 2009-07-25
 | deadlink  = yes
 }}
* {{cite web
 | url  = http://www.gsm-security.net/
 | title  = GSM security
 | accessdate  = 2009-11-24
 | lang  = en
 | archiveurl  = https://web.archive.org/web/20091123214950/http://www.gsm-security.net/
 | archivedate  = 2009-11-23
 | deadlink  = yes
 }}

<!-- В англовики описываются также атаки 2000 и 2004 годов -->

{{rq|wikify|sources}}

{{Симметричные криптоалгоритмы}}

[[Категория:GSM]]
[[Категория:Потоковые шифры]]