Безпека GSM мереж шифрування даних

даних

Частина 1: основні моменти безпеки GSM

Перш ніж приступити до опису алгоритму шифрування використовуваного в мережах GSM розглянемо яким чином відбувається аутентифікація користувача і формування ключа шифрування. Для цього скористаємося картинкою, запозиченою з вікіпедії (за якість перепрошую, не знайшов нічого кращого).

мереж

Частина 2: алгоритм шифрування A5/1

Перед роботою алгоритму виконується ініціалізація регістрів. Відбувається це так:

  1. R1=R2=R3=0
  2. For i=0 to 63 do R1[0]=R1[0]⊕Kc[i] R2[0]=R2[0]⊕Kc[i] R2[0]=R2 [0]⊕Kc[i] Зрушити всі регістри на одну позицію, ігноруючи біти синхронізації.
  3. For i=0 to 22 do R1[0]=R1[0]⊕FrameCount[[i] R2[0]=R2[0]⊕FrameCount[[i] R2[0] =R2[0]⊕FrameCount[[i] Зрушити всі регістри на одну позицію, ігноруючи біти синхронізації.
  4. For i=0 to 99 do Зрушити регістри однією позицію, з урахуванням бітів синхронізації.
Де FrameCount 32-бітний запис номера поточного кадру.

Скористаємося наведеним вище описом і реалізуємо шифрування A5/1 С#.

Перевірити правильність коду можна, запустивши програму з ключем та номером кадру 0x134. Дві згенеровані послідовності по 114 біт кожна, повинні дорівнювати відповідно < 0x53, 0x4E, 0xAA, 0x58, 0x2F, 0xE8, 0x15, 0x1A, 0xB6, 0xE1, 0x85, 0x5A, 0x72, 0x8C, 0x00 >і < 0x24, 0xFD, 0x35, 0xA3, 0x5D, 0x5F, 0xB6, 0x52, 0x6D, 0x32, 0xF9, 0x06, 0xDF, 0x1A, 0xC0 >. Саме такі тестові дані використовували Marc Briceno, Ian Goldberg і David Wagner у своїй першій реалізації алгоритму, написаної на С.

Функція шифрування/розшифрування, яка використовує цей клас, будевиглядати так:

Тепер коли ми маємо функцію, що дозволяє шифрувати і розшифровувати дані, давайте поговоримо про вразливість алгоритму A5/1. На сьогоднішній день відома велика кількість успішних атак на GSM шифрування і всі вони відносяться до атак типу known-plaintext, тобто. Для відновлення ключа атакуючому крім зашифрованих кадрів необхідно знати також незашифровані дані, які відповідають цим кадрам. На перший погляд така вимога може здатися фантастичною, проте через специфіку стандарту GSM, в якому крім голосового трафіку передаються різні системні повідомлення, такі атаки з теоретичних розрядів переходять у розряд практичних. Системні повідомлення GSM містять дані, що повторюються, і можуть використовуватися зловмисником. Зокрема метод, запропонований Karsten Nohl у 2010 році заснований саме на пошуку такого роду даних у шифротексті та простому переборі різних варіантів ключів, що зберігаються в райдужних таблицях, до тих пір, поки не буде знайдений ключ, що породжує потрібний шифротекст для відомого заздалегідь системного повідомлення .

Частина 3: атака на алгоритм A5/1

Однак у нас немає величезних ресурсів, необхідні обчислення райдужних таблиць, тому ми реалізуємо атаку простіше, що стосується т.зв. "кореляційним атакам". Наведена нами атака була вперше описана в 2002 році двома дослідниками: Patrik Ekdahl і Thomas Johansson. З визначення процедури ініціалізації можна зробити висновок, що початковий стан регістрів є лінійною функцією від сесійного ключа K і номера кадру Fn. Знаючи так само, що вихідний біт генератора є XOR-ом вихідних біт всіх трьох регістрів ми можемо записати наступну рівність:

(1),

де si-послідовність генерується регістрами після завантаження в них тільки бітів ключа K. fi-послідовність, після завантаження тільки бітів номера кадру, а x-вихідний біт регістра.

Також із визначення ініціалізації ми знаємо, що перші 100 циклів алгоритм працює «в холосту», тобто. не виробляє жодних вихідних бітів, і перший біт вихідної послідовності насправді є 101 згенерованим бітом. Таким чином, якщо врахувати, що на кожному кроці ймовірність зсуву для кожного регістру дорівнює 3/4, можна припустити, що після 101 кроку, кожен регістр зрушувався рівно 76 разів. Отже, формула (1) перетворюється на:

(2)

Позначивши праву частину (2) як перепишемо формулу:

(3)

Т.к. вираз у правій частині (3) нам відомо, ми отримуємо 1 біт інформації про ключову послідовність S, а саме про стан 76 позиції кожного регістра після ініціалізації. Діючи подібним чином, ми можемо припустити, що на 102 позиції R1 залишився також на позиції 76, а регістри R2 і R3 зрушили на позицію 77, таким чином ми отримуємо інформацію про 77 позиції регістра, і т.д. Усього нам необхідно розкрити 64 біти, для успішного відновлення початкового стану.

Зрозуміло ситуація (76,76,76) виникає саме на 101 кроці з вкрай низькою ймовірністю, і якби ми вирішили діяти подібним чином, то нам знадобилося б перебрати величезну кількість фреймів, поки нарешті не потрапить саме той, у якому після 101 зсуву кожен регістр прокрутився на 76 позицій Для того, щоб зменшити необхідну кількість кадрів Ekdahl та Johansson запропонували наступний метод.

Немає потреби вгадувати конкретну позицію в якій регістри провертаються (cl1, cl2, cl3) раз. Досить просто знати, щоз великою часткою ймовірності кожен регістр прогорнеться від 76 до 102 на відрізку I=[100,140] вихідних біт кожного кадру. Таким чином, для кожного кадру ми можемо визначити ймовірність: як

(4),

і означає можливість, що t-й біт був породжений позиціями регістрів (cl1, cl2, cl3).

Обчисливши (4) для кожного доступного кадру середнім отримані ймовірності за допомогою логарифму:

(5).

Опишемо атаку повністю у вигляді алгоритму:

  1. Вибираємо інтервал C. Наприклад, С=[79,86]
  2. Нехай змінні cl1,cl2,cl3 пробігають усі значення з інтервалу C, для кожного кадру обчислюємо (4)
  3. Для всіх отриманих значень обчислюємо (5)
  4. На підставі значення Δ вибираємо значення s1(cl1)⊕s2(cl2)⊕s3(cl3)
Результатом виконання даного алгоритму будуть 512 рівнянь виду s1(79)⊕s2(79)⊕s3(79)=0, що складаються з 8 невідомих. Розв'язавши цю систему рівнянь простим перебором, отримаємо по 8 біт початкового значення кожного регістру. Повторивши алгоритм ще двічі для інтервалів [87, 94] та [95, 102] ми отримаємо по 24 біти початкового стану кожного з регістрів. Цього нам більш ніж достатньо. Прокрутимо кожен із регістрів 101 разів тому ми отримаємо саме той стан регістрів, який був після другого кроку ініціалізації, тобто. після завантаження в регістри ключових бітів. І тепер ми можемо згенерувати всю ключову послідовність цілком.

Використовуючи функціюFindKeyBitнаступним чином:

ми отримаємо масив з 512 значень, в якому записані XOR ключових біт починаючи з позиції 79 за позицією 86.

Отримавши всі 24 біти з кожного регістру, і перевівши їх у байтові масиви, перевіряємо наше рішення:

Якщо отриманий кадр збігається з першим кадром відомого ключовогопотоку, отже, атака була реалізована успішно і ми розкрили сеансовий ключ алгоритму A5/1.

Частина 4: заключна

Підсумовуючи, хочу відзначити, що описана атака є однією з перших подібних атак. Найбільш досконала з них дозволяє з 90% ймовірністю розкрити сеансовий ключ із всього 2000 кадрів (9 секунд розмови). Отже, кореляційні атаки — дуже серйозна загроза у теорії, а й у практиці.

Література та посилання

  • Marcin Olawski. "Security in the GSM network".
  • Patrik Ekdahl та Thomas Johansson. "Another Attack on A5/1".
  • Karsten Nohl. "Attacking phone privacy".
  • Marc Briceno, Ian Goldberg та David Wagner. A pedagogical implementation of A5/1.

А у нас тут можна отримати грант на тестовий період Яндекс.Хмари. Варто лише у полі «секретний пароль» запровадити «Хабр»