A5 (шифр)

А5 — це потоковий алгоритм шифрування, який використовують для забезпечення конфіденційності даних, що передаються між телефоном і базовою станцією в європейській системі мобільного цифрового зв'язку GSM (Group Special Mobile).

Шифр заснований на побітовому додаванні за модулем два (булева операція XOR) згенерованої псевдовипадкової послідовності і відкритого тексту (голосові дані, смс, і т. д.). В A5 псевдовипадкова послідовність реалізується на основі трьох лінійних регістрів зсуву зі зворотним зв'язком. Регістри мають довжини 19, 22 і 23 біти відповідно. Зсувами керує спеціальна схема, яка організовує на кожному кроці зміщення як мінімум двох регістрів, що призводить до їх нерівномірного руху. Послідовність формується операцією XOR над вихідними бітами регістрів.

Історія створення і розвитку

Спочатку французькими військовими фахівцями-криптографами був розроблений потоковий шифр для використання виключно у військових цілях. В кінці 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) складають шифри, генератором псевдовипадкової послідовності яких заснований на регістрах зсуву з лінійної зворотним зв'язком.

РСЛОС

Регістр зсуву з лінійної зворотнім зв'язком складається з власне регістра (послідовності біт заданої довжини) і зворотного зв'язку. На кожному такті відбуваються такі дії: крайній лівий біт (старший біт) витягується, послідовність зсувається вліво і в спорожнілу праву клітинку (молодший біт) записується значення функції зворотного зв'язку. Ця функція є підсумовуванням по модулю два певних бітів регістра і записується у вигляді многочлена, де ступінь вказує номер біта. Витягнуті біти формують вихідну послідовність.

Для РСЛОС основним показником є період псевдовипадкової послідовності. Він буде максимальний (і дорівнює 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' доданий ще один регістр на 17 біт (R4), що керує рухом інших. Зміни структури такі:

• Доданий регістр R4 довжиною 17 біт,
• Многочлен зворотного зв'язку для R4: $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 було зниження криптостійкості шифрування, однак у офіційних результатах тестування кажуть, що невідомо про якісь недоліки алгоритму.

СОРМ СПРС повинна забезпечувати:

• Контроль вихідних і вхідних викликів контрольованих рухомих абонентів у СПРС;
• Контроль вихідних дзвінків (місцевих, внутрішньозонових, міжміських та міжнародних) від усіх абонентів СПРС до певних абонентам (аналіз за номером В);
• Надання даних про місцезнаходження контрольованих ПА, ПС при їх переміщенні по СПРС;
• Збереження контролю за встановленим з'єднанням при процедурах передачі керування викликом (handover) як між БС в межах одного ЦКП, так і різних ЦКП;
• Контроль викликів при наданні ПА додаткових послуг зв'язку, зокрема, що змінюють напрям виклику (Call Forwarding). При наданні ПА такої послуги, в процесі встановлення з'єднання повинні контролюватися номера, на які виклик перенаправляється (можливо неодноразове перенаправлення виклику до встановлення розмовного стану);
• Контроль за сполуками, що забезпечують передачу телефонного та нетелефонні інформації (передача даних, факсимільний зв'язок, короткі повідомлення);
• При наданні контрольованому ПА додаткової послуги «конференцзв'язок», що забезпечує можливість ПА одночасного розмови з кількома абонентами, повинні контролюватися номери всіх учасників конференцзв'язку;
• Можливість отримання за запитом з ПУ інформації про ПА за його ідентифікатором або присвоєному номеру ТфОП, ЦСІС, а саме, що надаються даним ПА послуги зв'язку.

Відомі уразливості

З появою даних про стандарт A5, почалися спроби злому алгоритму, а також пошуку вразливостей. Величезну роль надали особливості стандарту, різко ослабляють захист, а саме:

• 10 біт ключа примусово занулені,
• Відсутність перехресних зв'язків між регістрами (крім управління зрушеннями),
• Зайва надмірність шифрованої службової інформації, відомої криптоаналітику,
• Понад 40 % ключів призводить до мінімальної довжині періоду генерується послідовності, а саме ${\frac {4}{3}}\left({2^{23}-1}\right)$

• Спочатку сеансу здійснюється обмін нульовими повідомленнями (по одному кадру),
• В A5/2 рух здійснюється окремим регістром довжиною 17 біт.

На основі цих «дір» в алгоритмі, побудовані схеми злому.

Відомі атаки

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

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

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

У 1999 році Вагнеру і Голдберг без зусиль вдалося продемонструвати, що для розкриття системи, досить перебором визначити початкове заповнення R4. Перевірка здійснюється за рахунок нульових кадрів. Складність цієї атаки дорівнює 2 ¹⁷ , таким чином, на сучасному комп'ютері розтин шифру займає кілька секунд.

У грудні 1999 року група ізраїльських вчених (Аді Шамір, Алекс Бірюков, а пізніше і американець {{en: David A. Wagner | Вагнер, Девід (дослідник) | Девід Вагнер}}) опублікували вельми нетривіальний, але теоретично дуже ефективний метод розтину A5/1:

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

Посилання

• https://web.archive.org/web/20051216201851/http://cryptome.org/gsm-crack-bbk.pdf
• http://www.gsm-security.net [Архівовано 23 листопада 2009 у Wayback Machine.]