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