A3 (шифр)

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

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

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

В настоящее время известны следующие стандартные реализации алгоритма 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.

В 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 держатся в секрете

Алгоритмы аутентификации и генерации сеансового ключа 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 является неуязвимым к каким-либо известным атакам.[2]

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 атаку в терминах дифференциального криптоанализа).

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

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

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 подчеркивают тот факт, что несмотря на сложность и затратность такого вида атак, не следует игнорировать возможность их реализации.

В мае 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 из 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 является шифрованной. В таком случае, отследить такого рода атаку непросто.