них у цьому осіб) ставав би справою часу. Так і сталося у 1998 році, коли деякі документи, що стосуються технічних рішень, реалізованих в COMP 128 потрапили в мережу Інтернет. Незважаючи на неповне і частково помилкове опис, було встановлено, які саме криптографічні методи використовуються в GSM. На підставі даних документів Девід Вагнер, Аян Голдберг і Марк Бріц менш ніж за два дні зламали алгоритм COMP 128, оскільки його ключ виявився занадто коротким.
На даний момент практично всі атаки, спрямовані на отримання ключів Ki будуються саме на базі атаки WGB.
.1 Атака WGB
У 1998 році Вагнер, Голдберг і Бріц опублікували метод атаки, за допомогою якого секретний ключ Ki може бути обчислений шляхом відправки на SIM - карту спеціально підібраних певних значень RAND, які дозволять отримати частину інформації про секретному ключі Кi.
Алгоритм криптоаналізу заснований на тому, що після другого раунду роботи хеш-функції вихідні байти i, i + 8, i + 16, i + 24 залежать тільки від відповідних їм вхідних байт i, i + 8, i + 16, i + 24. Наочно дана уразливість показана на малюнку 7 [21].
Рис. 7 - Уразливий ділянку алгоритму COMP 128
Так як стиснення інформації проводиться після останнього раунду роботи функції, у всіх попередніх раундах розмір вихідної послідовності збігається з розміром вхідний. Байти i, i + 8 представляють секретний ключ, а байти i + 16, i + 18, - відкрите число RAND. Криптоаналіз грунтується на пошуку всіх можливих колізій у роботі хеш-функції при переборі тільки двох вхідних байт для кожної пари байт-ключа. Колізія в роботі хеш-функції відбувається, коли різні вхідні значення функції призводять до однакового значенню. Ефективність алгоритму забезпечується тим, що для пошуку колізії необхідно перебрати невелике число варіантів, а саме два байти для кожної пари байт ключа: 28 * 28=216. Для порівняння складність повного перебору становить 2 128.
.2 Покращення для WGB атаки
Оригінальна версія WGB атаки вимагала приблизно 150000 запитів для знаходження ключа. У звіті про проведення цієї атаки було зазначено, що «розроблено декілька оптимізацій для зменшення кількості запитів», але що це за оптимізації не було сказано ні слова [21].
Структура перших двох рівнів COMP 128 не є рівномірно розподіленою випадковою функцією. Деякі запити (RANDi, RANDi + 8) є більш продуктивними ніж інші так як потенційно вони можуть викликати колізію в декількох різних парах (Ki, Ki + 8). Тому цілком логічно використовувати такі запити в першу чергу. Це може бути реалізовано шляхом повного перебору всіх (Ki, Ki + 8) і для кожного з таких значень повного перебору всіх (RANDi, RANDi + 8). Таким чином, для кожного (Ki, Ki + 8) ми знайдемо всі пари (RANDi, RANDi + 8) призводять до колізій. Після цього всі подібні (RANDi, RANDi + 8) можуть бути впорядковані в новому, покращеному розкладі запитів. Таким чином, (RANDi, RANDi + 8), що показали себе найбільш продуктивними будуть використовуватися в першу чергу [22].
Подальші поліпшення можуть бути досягнуті шляхом проходження розкладом запитів паралельно для всіх восьми (Ki, Ki + 8). Коли ж знаходяться перші 7 значень (Ki, Ki + 8) зловмисник може припинити посилку запитів до SIM - карті, так як останнє значення (Ki, Ki + 8) може бути обчислено шляхом звичайної оффлайн атаки методом грубої сили. Дані по необхідній кількості запитів для успішного завершення атаки даним методом можна відобразити на графіку, представленому на малюнку 8.
Рис.8 - Залежність успіху поліпшеною WGB атаки від кількості запитів
Використовуючи цю техніку, середнє число запитів необхідних для компрометації ключа становить приблизно 60000.
.3 Слабкості WGB атаки
Слабкості WGB атаки стають очевидні при проведенні повного пошуку «успішних» запитів (RANDi, RANDi + 8). Як уже згадувалося вище, структура перших двох рівнів COMP 128 не є рівномірно розподіленої випадкової функцією. Відповідно, так само як існують найбільш продуктивні запити (RANDi, RANDi + 8) існують і значення (Ki, Ki + 8), які найбільш сприйнятливі до атаки. Ці сприйнятливі значення (Ki, Ki + 8) мають кілька пар (RANDi, RANDi + 8) які викликають колізію.
Інші значення (Ki, Ki + 8) менш сприйнятливі до атаки (т.е більш стійкі), а деякі взагалі не мають пар (RANDi, RANDi + 8), що викликають колізію.
Всупереч твердженням, висунутому Вагнером, Голдбергом і Бріц про те, що «парадокс днів народжень гарантує досить-таки швидке виникнення колізії» такої гарантії насправді не існує. Все, що пропонується - висока ймовірність за умови, що хеш функція є дійсно випадковою. Грунтуючись на цьому, для кожного значення (Ki, Ki + 8) ймовірність не виникнення колізії після всіх 216 запитів (RANDi, RANDi + 8) становить приблизно 3,35? 10-4. Так як існує 216 можливих значень (Ki, Ki + 8), можна очікувати, що після проведенн...
