Главная | Обратная связь

Процесс аутентификации

Суть аутентификации в GSM — избежание клонирования мобильного телефона пользователя. Секретным ключом является 128-битный ключ Ki, которым обладает как абонент, так и Центр Аутентификации (AuC — Authentication Centre). Ki хранится в SIM-карте, также как и алгоритм A3. Также в аутентификации принимают участие Домашний реестр местоположения (HLR — Home Location Registry) и Центр коммутации (MSC — Mobile Switching Centre)

Когда MS запрашивает доступ к сети GSM (например при включении), MSC должен проверить подлинность MS. Для этого MS отправляет в HLR уникальный международный идентификатор абонента (IMSI — International Mobile Subscriber Identity) и запрос на получение набора специальных триплетов. Когда HLR получает IMSI запрос на триплеты, он сначала проверяет свою базу данных, чтобы удостовериться, что MS с таким IMSI действительно принадлежит сети. Если проверка прошла успешно, то HLR отправляет IMSI и запрос установления подлинности в АuC.

AuC использует IMSI, чтобы найти Ki соответствующий этому IMSI. Также AuC генерирует случайное 128-битное число RAND. После этого AuC вычисляет 32-битный отзыв SRES (SRES — Signed Response) при помощи алгоритма A3: SRES = A3(RAND, Ki). Кроме того, AUC вычисляет 64-битный сеансовый ключ Kc при помощи алгоритма A8: Kc = A8(RAND, Ki). Kc в дальнейшем используется в алгоритме A5 для шифрования и расшифрования данных.

RAND, SRES, и Kc как раз образуют триплеты, которые MSC запросил у HLR. AuC генерирует пять таких триплетов и посылает их в HLR, затем HLR пересылает этот набор в MSC. Генерируется именно набор триплетов, чтобы уменьшить передачу сигналов в GSM core network, которая происходила бы каждый раз, когда MS запрашивала бы доступ к сети, а MSC должен был бы проверить подлинность MS. Следует отметить, что набор триплетов уникален для одного IMSI и не может быть использован для какого-либо другого IMSI.

MSC сохраняет Kc и SRES и посылает запрос RAND мобильной станции MS абонента. Получив запрос RAND, MS вычисляет ответ на запрос SRAND при помощи алгоритма A3 и секретного ключа Ki: SRES = A3(RAND, Ki), и посылает его в MSC. Если принятый SRES совпадает с SRES, хранящимся в MSC, то аутентификация считается пройденной успешно.

После пяти сессий аутентификации MSC запрашивает у HLR новый набор триплетов (RAND, SRES, Kc)

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

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

Структура А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: ,

· управление тактированием осуществляет 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 не содержит шифрования.

 

№ Методы получения случайных и псевдослучайных последовательностей.