Интернет магазин китайских планшетных компьютеров

Компьютеры - A3 (шифр) - Описание алгоритма

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

Формат входных и выходных данных для алгоритма 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 байта. 32 старших бита вычисленного значения берутся в качестве SRES, а 64 младших бита в качестве сессионного ключа Kc. Пусть X — 32байтный вход алгоритма, где X = Ki, а X = RAND. T0, T1,T2,T3 и T4 — секретные таблицы подстановки байт. Алгоритм состоит из 8 раундов, в каждом раунде 5 итераций. Каждая итерация заключается в поиске по соответствующей таблице и подстановке байт. В конце каждого раунда, за исключением последнего, происходит перестановка полученных 128 бит результата, и после перестановки эти 128 бит используется в следующем раунде. Описание одного раунда в псевдокоде:

 for i = 0 to 4 do:
 for j = 0 to 2^i - 1 do:
 for k = 0 to 2^ - 1 do:
 {
   s = k + j*2^
   t = s + 2^
   x = mod)
   y = mod)
   X=Ti
   X=Ti
 }
 

 for j = 0 to 31 do:
 for k = 0 to 7 do:
 {          
   bit = theth bit of byte j
 }

 if then
 for j = 0 to 15 do:
 for k = 0 to 7 do:
 {
   next bit = x 17 mod 128
   Bit k of X = bit
 }

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

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

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

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

COMP128-2 и COMP128-3

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

Milenage

Алгоритмы аутентификации и генерации сеансового ключа Milenage бы разработан консорциумом 3GPP объединёнными усилиями входящих в 3GPP организаций. Нет никаких дополнительных требований или разрешений, необходимых для использования этих алгоритмов. Пример использования Mileage в качестве 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 является неуязвимым к каким-либо известным атакам.