A3 (шифр)

A3 — алгоритм, используемый в процессе аутентификации в глобальном цифровом стандарте для мобильной сотовой связи GSM. A3 является, таким образом, элементом системы обеспечения конфиденциальности разговора в GSM наряду с алгоритмами A5 и A8. Задача алгоритма — генерация отзыва (SRES — Signed Response) на случайный пароль (RAND — Random), получаемый сотовым телефоном (MS — Mobile Station) от центра коммутации MSC (MSC — Mobile Switching Centre) в процедуре аутентификации. А3 реализуется в SIM-карте абонента.

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

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

Когда MS запрашивает доступ к сети GSM (например при включении), MSC должен проверить подлинность MS. Для этого MSC отправляет в 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 вычисляет ответ на запрос SRES при помощи алгоритма A3 и секретного ключа Ki: SRES = A3(RAND, Ki), и посылает его в MSC. Если принятый SRES совпадает с SRES, хранящимся в MSC, то аутентификация считается пройденной успешно.

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

Описание алгоритма

Общие положения

Формат входных и выходных данных для алгоритма A3, а также весь процесс аутентификации строго определены консорциумом 3GPP. Стоит отметить, что каждый отдельный оператор выбирает принцип действия алгоритма A3. Таким образом, A3 не является стандартизованным, а определяется оператором. Однако если оператор не хочет придумывать свой алгоритм A3, он может воспользоваться стандартной реализацией алгоритма.

В настоящее время принят следующий формат входных и выходных данных RAND, Ki, SRES алгоритма A3: длина Ki — 128 бит длина RAND — 128 бит длина SRES — 32 бита

Время выполнения алгоритма A3 должно быть меньше 500 миллисекунд.

В настоящее время известны следующие стандартные реализации алгоритма A3:

• COMP128
• COMP128-2
• COMP128-3
• MILENAGE

COMP128 является самой первой версией алгоритма A3. Изначально алгоритм COMP128 держался в секрете. Разработчики первой версии A3 полагались на безопасность за счёт неизвестности, то есть алгоритмы труднее взломать, если они не доступны публично. Однако COMP-128 был скомпрометирован криптоаналитиками Marc Briceno, David Wagner и Ian Goldberg исследовательской группы ISAAC security research group После публикации уязвимостей COMP128 были разработаны исправленные версии COMP128-2 и COMP128-3.

COMP128

В 1998 году произошла утечка описания алгоритма COMP128 в Интернет. Хотя описание было не полным, посредством обратной разработки код был полностью восстановлен и теперь он доступен публично

По сути, COMP128 является хеш-функцией разрядности 128 бит. Разрядность аргумента 256 бит или 32 байта (128 бит Ki + 128 бит RAND). 32 старших бита вычисленного значения берутся в качестве SRES, а 64 младших бита в качестве сессионного ключа Kc. Пусть X [0..32] — 32байтный вход алгоритма, где X [0..15] = Ki, а X [16..31] = RAND. T0 [0..511], T1 [0..255],T2 [0..127],T3 [0..63] и T4 [0..31] — секретные таблицы подстановки байт. Алгоритм состоит из 8 раундов, в каждом раунде 5 итераций. Каждая итерация заключается в поиске по соответствующей таблице (T0 для первой итерации, T1 — для второй, и т. д.) и подстановке байт. В конце каждого раунда, за исключением последнего, происходит перестановка полученных 128 бит результата, и после перестановки эти 128 бит используется в следующем раунде. Описание одного раунда в псевдокоде:

 (подстановки)
 for i = 0 to 4 do:
 for j = 0 to 2^i - 1 do:
 for k = 0 to 2^(4-i) - 1 do:
 {
   s = k + j*2^(5 - i)
   t = s + 2^(4-i)
   x = (X[s] + 2X[t]) mod (2^(9 - i))
   y = (2X[s] + X[t]) mod (2^(9 - i))
   X[s]=Ti[x]
   X[t]=Ti[y]
 }
 
 (образование бит из байт)
 for j = 0 to 31 do:
 for k = 0 to 7 do:
 {          
   bit [4*j+k] = the (8-k)th bit of byte j
 }
 (перестановка)
 if (i < 8) then
 for j = 0 to 15 do:
 for k = 0 to 7 do:
 {
   next bit = (8 x j + k) x 17 mod 128
   Bit k of X[j + 16] = bit[next_bit]
 }

На каждой итерации выходной байт зависит от двух входных байт. Два входных байта используются для определения элемента в таблице подстановки. Этот элемент обновит выходной байт. Таблица подстановки для i-ой итерации содержит 2^(9 — i) элементов размером в (8 — i) бит. То есть

таблица    число элементов    размер одного элемента
T0         512                8 бит
T1         256                7 бит
T2         128                6 бит
T3         64                 5 бит 
T4         32                 4 бита

По сути, каждый из 32 выходных байт последней итерации раунда имеет лишь 4 значимых бита. Поэтому в конце итерации происходит преобразование этих 32 байт перестановкой в 16 байт, все биты которых значимые. Эти 16 байт записываются в X [16 .. 31], и запускается следующий раунд алгоритма (в X [0 .. 15] значение Ki никак не меняется).

Такую структуру алгоритма David Wagner назвал butterfly structure, что означает «в форме бабочки»

COMP128-2 и COMP128-3

Хотя сейчас ясно, что принцип «безопасность за счёт неизвестности» не работает, версии COMP128-2 и COMP128-3 держатся в секрете

Milenage

Алгоритмы аутентификации и генерации сеансового ключа Milenage были разработаны консорциумом 3GPP объединёнными усилиями входящих в 3GPP организаций. Нет никаких дополнительных требований или разрешений, необходимых для использования этих алгоритмов. Пример использования Milenage в качестве A3 показан в документе 3GPP TS 55.205 «Specification of the GSM-MILENAGE Algorithms: An example algorithm set for the GSM Authentication and Key Generation functions A3 and A8». Полная спецификация Milenage представлена на сайте консорциума 3GPP

Milenage является неуязвимым к каким-либо известным атакам.

Возможные атаки

Атаки на COMP128

Атака BGW

13 апреля 1998 года Marc Briceno, Ian Goldberg и David Wagner опубликовали статью, в которой описали способ получения секретного ключа Ki путём посылания SIM карте около 150000 запросов. Атака использует узкое место алгоритма.

После второй итерации первого раунда байты X[i], X[i+8], X[i+16], X[i+24] зависят только от входных байт с такими же индексами. Байты X[i] и X[i+8] являются байтами ключа, то есть X[i] = Ki[i] и X[i+8] = Ki[i+8] (для каждого i от 0 до 7), а байты X[i+16] и X[i+24] являются байтами запроса RAND от базовой станции, т.е X[i+16] = RAND[i+16] и X[i+24] = RAND[i+24] (для каждого i от 0 до 7).

Теперь мы меняем байты i+16, i+24 входа алгоритма COMP128 (то есть байты i, i+8 запроса RAND), оставляя оставшиеся входные байты постоянными. Так как одна итерация не является взаимно-однозначной, можно ожидать коллизию байтах выхода с номерами i, i+8,i+16,i+24 после второй итерации. „Парадокс дней рождений“ гарантирует, что коллизия произойдёт довольно быстро (так как узкое место ограничено 4 байтами). Коллизии в узком месте может быть обнаружены, ибо они вызовут коллизию выходов алгоритма COMP128 (то есть мы получим два одинаковых отзыва SRES), причём каждая коллизия может быть использована для получения двух байт ключа i, i+8 (с учётом небольшой обработки первых двух итераций — то есть применяя 2R атаку в терминах дифференциального криптоанализа).

На это потребуется $2^{4*7/2+0.5}=2^{14.5}$ определённых входных запросов COMP128 для нахождения двух байтов ключа (так как каждый из четырёх байт выхода после второй итерации по сути имеет 7 значимых бит). Теперь проводим 2R атаку для каждой пары байт ключа (для каждого i от 0 до 7). Таким образом, для получения всего 128 битного ключа Ki потребуется $8*2^{14.5}=2^{17.5}$ запросов.

Стоит отметить, что для проведения атаки требуется физический доступ к SIM карте, кардридер и компьютер. Для проведения атаки потребуется послать около 150000 запросов к SIM карте. Кардридер, который был использован группой учёных из ISAAC, выполнял 6,25 запросов в секунду, а вся атака заняла, таким образом, 8 часов. Для анализа ответов от SIM карты требуется значительно меньше времени, чем для отправки запросов.

Атака BGW over-the-air

Marc Briceno, Ian Goldberg и David Wagner также уверены в том, что атаку BGW можно провести дистанционно, не имея физического доступа к SIM-карте. К сожалению, они не стали проводить эксперимент, так как это было бы нарушением законов США. Однако эксперты в области GSM, к которым обратились исследователи из ISAAC, подтвердили возможность практической реализации атаки. Свойства протоколов GSM позволяют выполнять атаку BGW, если удастся создать фейковую базовую станцию BS. Фейковой BS не требуется поддерживать весь протокол GSM, а лишь часть его функций. Атака BGW over-the-air основана на том, что мобильной станции MS требуется ответить на каждый запрос, сделанный сетью GSM. Если сигнал от фейковой BS перекроет сигнал от легальной BS, атакующий сможет посылать запросы целевой MS и воссоздать Ki из ответов, полученных от MS. Стоит отметить, что MS должна быть доступна атакующему на всё время, в течение которого будет проводиться атака. Неизвестно, как много времени занимает атака BGW over-the-air. По оценкам, от восьми до тринадцати часов.

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

Marc Briceno, Ian Goldberg и David Wagner подчеркивают тот факт, что несмотря на сложность и затратность такого вида атак, не следует игнорировать возможность их реализации.

Распределённая атака (Partitioning Attack)

В мае 2002 группа исследователей из IBM Watson Research Center совместно с исследователями из Swiss Federal Institute of Technology Zurich опубликовали распределённую атаку на COMP128. Она основана на простом анализе потребляемого тока (Simple Power Analysis (SPA)) и позволяет получить ключ за несколько минут. Атака использует малую производительность процессора SIM карты. Так, первая подстановка с помощью таблицы T0 выбирает одно из 512 значений, для выбора одного значения требуется 9 бит. Однако процессор SIM может обратиться только по 8-битному адресу. Для этого таблица должна быть разбита на две части. Исследователи IBM Watson Research Center предположили, что таблица разбита на две равные части. Анализируя энергопотребление SIM карты при различных запросах (а также электромагнитное излучение), исследователи определяли, к какой части таблицы T0 был адресован запрос. Анализируя адресацию и энергопотребление запросов при изменении первого байта RAND[0] им удалось найти K[0]. Проводя похожий анализ для других байт RAND, ключ Ki восстанавливается полностью.

В итоге, атака может быть проведена путём посылки 1000 случайных или 255 определённых запросов. В конце концов атаку свели до 8 самоприспосабливающихся запросов, что позволяет получить Ki за 2 секунды. Однако атака возможна лишь при физическом доступе к SIM карте.

Получение Ki из AuC

Точно такая же атака с целью получения Ki из SIM может быть проведена по отношению к AuC. AuC должен отвечать на все запросы сети GSM и выдавать триплеты, используемые для аутентификации MS. По сути процедура аналогична атаке BGW на SIM. Отличие лишь в том, что AuC намного быстрее SIM обрабатывает запросы, потому что ему нужно обрабатывать во много раз большее количество запросов. Безопасность AuC играет большую роль, независимо от того, возможен ли этот тип атак.

Фейковая базовая станция

Важно отметить, что аутентификация в GSM — односторонняя: телефон (MS) аутентифицируется базовой станцией (BS), но базовая станция (BS) телефоном (MS) не аутентифицируется. Этот факт делает возможными атаки, когда третья сторона притворяется легальной BS для одной или нескольких MS. Одним из предположений при разработке GSM заключалось в том, что такого рода атаки будут очень дорогими по сравнению с другими типами атак. Однако стоимость BS быстро упала и в настоящее время нетрудно найти эмуляторы BS. Более того, использование шифрования для текущего вызова происходит не автоматически — сеанс связи устанавливается нешифрованным и лишь потом MS высылается команда, шифровать сеанс или нет. Команда начала шифрования посылается нешифрованной и никак не проверяется внутри сети GSM. Таким образом, используя фейковую BS, можно создать ситуацию, когда сеанс связи MS с фейковой BS не является шифрованным, и легко прослушивается; а связь между фейковой BS (выдающей себя за легальную MS) и легальной BS является шифрованной. В таком случае, отследить такого рода атаку непросто.

См. также

• A5 (алгоритм шифрования)
• A8 (шифр)
• GSM
• Поточный шифр
• Безопасность GSM
• Клонирование SIM-карты

Ссылки

• Положения Ассоциации GSMA (The GSM Association) о алгоритмах обеспечения конфиденциальности в GSM (GSM Security Algorithms) (англ.)
• Результаты исследовательской группы ISAAC security research group (англ.)
• Marc Briceno, Ian Goldberg and David Wagner GSM cloning (англ.)
• Lauri Pesonen, GSM Interception (англ.)
• H. Haverinen, J. Salowey Extensible Authentication Protocol Method for Global System for Mobile Communications (GSM) and Subscriber Identity Modules (EAP-SIM) (англ.)
• 3GPP — Текущий уровень стандартизации GSM, свободные стандарты (англ.)
• Подробное описание COMP128 с оценками требуемой памяти и времени выполнения (англ.)
• Handschuh, Pascal Paillier Reducing the Collision Probability of Alleged Comp128 (недоступная ссылка) (англ.)
• Paulo S. Pagliusi A Contemporary Foreword on GSM Security (англ.)
• Клонирование SIM-карт — миф или реальность?