Често задавани въпроси

Съгласно спецификация GSM 02.09 се допускат до 7 различни алгоритъма А5 и те се специфицират от органа, дефиниращ стандартите за GSM с цел съвместимост на мрежите на различните оператори.
Имплементацията на А5 е засекретена, но през 1994 г. благодарение на изтичане на информация е оповестена общата схема на алгоритъма и той е анализиран и реконструиран в детайли от Марк Брисено през 1999 г.

Ключовият генератор на А5/1 се състои от три линейни FSR¹, наречени съответно R1, R2 и R3 с разредност съответно 19, 22 и 23 бита. Най-старшите битове на регистрите се сумират по модул 2 и образуват изхода на генератора. Обратната връзка на всеки регистър се получава от сума по модул два на няколко от битовете му, наречени tap битове. Тези битове са на позиции 13, 16,17, 18 за R1, 20, 21 за R2, и 7, 20, 21, 22 за R3. Управлението на подаване на тактов сигнал към регистрите се прави по формулите:

clock1 = clock ^ ( (C1 ^ (C2 _ C3) ) _ :(C1 _ (C2 ^ C3) ) )
clock2 = clock ^ ( (C2 ^ (C1 _ C3) ) _ :(C2 _ (C1 ^ C3) ) )
clock3 = clock ^ ( (C3 ^ (C1 _ C2) ) _ :(C3 _ (C1 ^ C2) ) )

Така на всеки такт се местят или 2 или 3 регистъра и всеки регистър се мести с вероятност ¾ и спира с вероятност ¼
Генератора се инициализира на всеки кадър с 64-битови сесиен ключ KC и 22 битов номер на кадъра. Инициализацията става като се нулират всички регистри и се тактуват 64 + 22 = 86 такта, като ключа и номера на кадъра се използват като допълнителни битове за обратна връзка. След това генератора работи още 100 такта, като изхода му не се използва. Тогава инициализацията е завършена и следващите 228 бита се използват за шифриране на изпращания кадър и за дешифриране на получения.

В следствие реконструкцията на алгоритъма той е подложен на криптоанализ от множество учени в областта и са открити слабости.
Така например Алекс Бирюков, Ади Шамир и Дейвид Вагнер² описват три типа атаки, които биха могли да се проведат с използването на обикновен компютър. Атаките описани от горните автори изискват предварителното изчислените на между 240 и 245 операции, като след това предлагат три типа атаки в зависимост от това какво количество шифрирана информация е налична. Така например Biased Birthday 1 изисква 2 минути шифрирана информация, като времето за разкодиране е 1 секунда. Random Subgraph атаката изисква само 2 секунди шифрирана информация, но разкодирането е в продължение на няколко минути. Според твърдението на самите автори тези атаки не са по силите на хора, разполагащи с ограничено количество техника, а само на големи организации със сериозен бюджет.
Други автори³ анализират хардуеренo дешифриране на А5 на базата на Xilinx XC4062 FPGA. Резултатът от анализа е, че при използването на ASIC с 0,1 микронна технология, и използването на 1000 такива чипа, разкодирането на А5 дори при наличие на само един кадър би отнело под половин минута. Според авторите разработката и реализацията на подобен апарат би струвала в границите на 1-2 милиона долара – отново не по силите на “самотен войн”.
Тези анализи са направени на базата на 64 битов сесиен ключ Kc. Скорошни анализи показват, че не се използват всички битове на сесийния ключ. Пример може да бъде следния лог-файл:

BSSMAP GSM 08.08 Rev 3.9.2 (BSSM) HaNDover REQuest (HOREQ)
——-0 Discrimination bit D BSSMAP
0000000- Filler
00101011 Message Length 43
00010000 Message Type 0×10
Channel Type
00001011 IE Name Channel type
00000011 IE Length 3
00000001 Speech/Data Indicator Speech
00001000 Channel Rate/Type Full rate TCH channel Bm
00000001 Speech encoding algorithm GSM speech algorithm
Encryption Information
00001010 IE Name Encryption information
00001001 IE Length 9
00000010 Algorithm ID GSM user data encryption V.1
******** Encryption Key C9 7F 45 7E 29 8E 08 00

Както се вижда последните 10 бита от ключа са нулирани, ограничавайки по този начин същинските битове на 54.
Причината за това трябва да потърсим при разработката на тези алгоритми: Имало е няколко предложения за алгоритъм А5, като при избора на конкретна версия са се намесили правителствата на страните, разработвали GSM, както и според слуховете няколко разузнавателни агенции. Целта е била умишлено отслабване на алгоритъма, така че да е възможно подслушването на разговори и данни от организации с бюджет, надхвърлящ определена граница. По този начин автоматично се гарантира достъп на големите разузнавателни организации, а класифицирането на алгоритъма и държането му в тайна би било достатъчна гаранция за сигурността му. За съжаление според закона на Мур изчислителната мощност на процесорите се удвоява на всяка година и половина. Това, съчетано с изтичането на информация правят А5 сравнително лесна мишена.
Всичко казано дотук се отнася за версия А5/1 – това е криптографски сигурната версия.Версия А5/2 – предназначената за страните, които не са членки на ETSI е още по-слаба. Prof. Dr. Jorg Keller предполага ключ не по-дълъг от 16 бита, което предполага дешифриране в реално време с доста скромен бюджет.
За съжаление метода “сигурност чрез секретност” продължава да се прилага – като пример може да посочим отменената изява на д-р Саймън Шепърд от университета Bradford, чието изказване на тема нова атака срещу А5, на годишния колоквиум на IEE в Лондон е било отменено в последната минута.

1. Feedback Shifting Register [обратно ↩]
2. Alex Birykov, Adi Shamir, David Wagner. Real Time Cryptanalysis of A5/1 on a PC., 2000. http://cryptome.org/a51-bsw.htm [обратно ↩]
3. Prof. Dr. Jorg Keller,A Hardware-Based Attack on the A5/1 Stream Cipher, Fern Universitat, Germany [обратно ↩]