2 АНАЛІЗ СТІЙКОСТІ АЛГОРИТМІВ КРИПТОЗАХИСТУ СТАНДАРТУ GSM

2.1 АЛГОРИТМИ А3 і А8.

На практиці ці алгоритми реалізовані як єдиний алгоритм за назвою А3А8. Принцип роботи алгоритму А3А8 представлений на рис. 2.1.

Більшість відомих публікацій про А3А8 вказують, що він піддається злому тільки за умови фізичного доступу до SIM-карти. У термінах сучасного криптоаналіза дана атака називається “атакою з обраним викликом”. Розглянемо її суть.

Формується ряд спеціальних викликів RAND, які посилають в SIM-карту. Використовуючи даний виклик і записаний ключ аутентифікації Кi, SIM-карта обчислює по алгоритму А3А8 значення відгуку SRES і повертає його. Аналізуючи запити й відповідні їм відгуки на персональному комп'ютері можливо визначити секретний ключ Кi. Для цього потрібно сформувати порядку 1,5105 запитів на SIM-карту. Технічна швидкість обробки й обчислення відгуку для SIM-карти становить порядку 6,25 запитів у секунду, так що атака займе біля восьми годин.

Атака використає слабість алгоритму А3А8, що полягає в тім, що є якийсь “вузький канал” у його структурі. Зокрема, вихідні байти i, i+8, i+16, i+24 масиву Х (див. рисунок 2.1) наприкінці другого загального циклу перетворення залежать тільки від байтів i і i+8 запиту (усього в алгоритмі А3А8 виробляється 58 загальних циклів). Отже, міняючи байти i і i+8 запиту й залишаючи постійними всю частину запиту, що залишилася, аналізується зміна відповідних відгуків на ці запити.

Так як відображення, одержувані в результаті перетворення загальних циклів, не бієктивні, то можна сподіватися на збіг байтів i, i+8, i+16, i+24 масиву Х після двох загальних циклів перетворень.

Відповідно до відомого “парадоксу днів народжень” ці збіги відбудуться відносно швидко, тому що ширина каналу тільки 4 байти. Кожний такий збіг використається, щоб одержати два байти i і i+8 ключа Кi (тобто побудувати “2-R атаку” – у термінології диференціального аналізу).

Таким чином, для одержання двох ключових байтів потрібно сформувати 2(4*7/2 + 0,5) = 214,5 запитів до алгоритму А3А8. Але тому що довжина ключа становить 16 байт, то для його повного відновлення буде потрібно 8214,5 запитів.

Схема роботи алгоритму А3А8

Рис. 2.1

2.2 АЛГОРИТМ А5

Даний алгоритм реалізований на основі трьох регістрів зрушення з лінійним зворотним зв'язком довжиною 19, 22 і 23 біта (рис. 2.2). Регістри зрушуються не регулярно. Закон руху схеми такий, що в кожному такті принаймні два регістри будуть зрушуватися. Середні осередки кожного з регістрів з номерами 8, 10 і 10, відповідно, використаються для визначення регістрів, що зрушуються, у наступному такті (при цьому зрушуватися будуть тільки ті регістри, у яких вміст даних осередків збігається). Законом руху регістрів керує схема керування синхронізацією (СКС).

Структурна схема алгоритму А5

Рис. 2.2

Виходом алгоритму А5 є побітова сума вихідних послідовностей трьох регістрів. Далі ця сумарна послідовність складається по модулю два з відкритим текстом.

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

Аналізуючи алгоритм, можна помітити, що кожний з регістрів буде простоювати 1/4 періоду своєї роботи (під періодом варто розуміти період даного регістра при його регулярній роботі). Період самого довгого регістра становить Тmax= (223–1). Якщо представити А5 як кінцевий автомат, то видно, що він має 2(19+22+23)=264 станів і функція переходів є не оборотною.

Однак знайдено 237 початкових заповнень, які мають періоди, близькі до малих множників найбільшого періоду Тmax. Крім того, більше 40% із цих початкових заповнень мають період, дуже близький до Тmax безпосередньо. Ця слабість зберігається при виборі інших поліномів зворотного зв'язку й навіть коли послідовності керування синхронізацією являють собою псевдовипадкові послідовності, не пов'язані з даними регістрами.

Таким чином, період вихідної послідовності алгоритму А5 в 57% початкових заповнень не набагато більше періоду Тmax самого довгого регістра.

Необхідно розглянути можливі атаки на алгоритм А5. Дані атаки представлені у вигляді стратегії з відомим відкритим текстом. Будемо також вважати, що номер кадру Nk (називаний також відкритим ключем А5) відомий. Завданням криптоаналіза є одержання секретного ключа Кс, використовуваного як початкове заповнення регістрів алгоритму.

Перша атака на алгоритм А5 полягає в переборі всіх можливих початкових заповнень двох найменших регістрів довжиною 19 і 22 біта, і відновлення початкового заповнення найбільшого, використовуючи вихідну послідовність А5, – так називана атака “грубою силою”. Але трудомісткість даної атаки буде становити величину не 2(19+22)=241, а порядку 245, тому що послідовність керування синхронізацією залежить також і від найбільшого регістра, що вимагає додаткових обчислень.

Друга атака на алгоритм А5 належить до класу атак із загальною назвою “балансування час-пам'ять”. Стосовно до А5 вона вперше була запропонована югославським математиком Голичем. Атака заснована на вже згаданому раніше парадоксі