я всіх запитів до них, залишиться приблизно двадцять два значення, на яких колізія не виникне.
На практиці повний перебір показує, що таких значень (Ki, Ki + 8), які «вільні» від колізій, а відповідно не сприйнятливі до WGB атаці існує 769. У додатку А наведені всі подібні (Ki, Ki + 8).
Звичайна WGB атака може бути проведена лише на ключ, в якому відсутні «вільні» від колізій компоненти (Ki, Ki + 8). Покращена WGB атака, розглянута в попередньому розділі, зможе працювати з ключем, в якому присутній один компонент (Ki, Ki + 8) вільний від колізій, оскільки останній один з компонентів (Ki, Ki + 8) знаходиться методом грубої сили в оффлайн режимі.
Для ключів, які включають два «вільних» від колізій компонента можна розширити атаку. У цьому випадку, якщо після перебору всіх (RANDi, RANDi + 8) зі списку залишилися не обчисленими два компоненти ключа (Ki, Ki + 8), можна провести на них атаку за методом грубої сили, яка зажадає 769? 769=591,361 пробних хешей (у випадку, якщо б нам не були відомі 769 «вільних» від колізій елементів (Ki, Ki + 8) це число дорівнювало б 232). Для більшого числа «сильних» (Ki, Ki + 8) атака стає практично марною, але на практиці такі ключі зустрічаються вкрай рідко (у вибірці з десяти тисяч випадково взятих ключів менше одного ключа матиме більше двох «сильних» (Ki, Ki + 8)).
Таким чином, для того щоб згенерувати «сильний ключ» повністю нечутливий до WGB атаці необхідно вибирати всі компоненти (Ki, Ki + 8) з наведеного в додатку А списку «сильних» компонентів. У псевдокоді алгоритм для генерації таких ключів наведено ніже.i in [0, 1, 2, 3, 4, 5, 6, 7] x=випадково обрані значення зі списку в додатку А Ki=перші два шістнадцяткових розряду x Ki + 8= останні два шістнадцяткових розряду xx
Так як відомо, що існує 769 «сильних» компонентів (Ki, Ki + 8), то «сильні» ключі, згенеровані наведеним вище методом, матимуть ефективну довжину 8? log2 769=76,7 біт. Ця довжина є прийнятною і перевищує довжину сесійного ключа, використовуваного для шифрування мови в алгоритмі A5.
.4 Атака на Ki, складені з «сильних» елементів
Дана атака передбачає, що зловмисникові відомо про те, що секретний ключ сформований лише з сильних елементів (Ki, Ki + 8). Якщо це так, то атака може бути проведена, але спершу необхідно відсіяти всі можливі слабкі ключі. Атака будуватися на очікуванні колізії на третьому рівні. Необхідно знайти чотири компоненти (Ki, Ki + 4, Ki + 8, Ki + 12). Кожен з них будується з двох компонентів обраних зі списку 769 «сильних» компонентів (Ki, Ki + 8) .Наглядно дана уразливість показана на малюнку 9.
Рис. 9 - Уразливий ділянку алгоритму COMP 128 за умови, що Ki складені з «сильних» компонентів (Ki, Ki + 8)
Для того, щоб знайти кожен компонент (Ki, Ki + 4, Ki + 8, Ki + 12) необхідно відправити запит (RANDi, RANDi + 4, RANDi + 8, RANDi + 12) за методом подібному з представленим у WGB атаці. Іншібайти RAND повинні залишатися константою. Коли пара біт запиту (RANDi, RANDi + 4, RANDi + 8, RANDi + 12), що викликає колізію, знайдена, проводиться пошук по 769? 769 можливим компонентам (Ki, Ki + 4, Ki + 8, Ki + 12) до тих пір, поки не знайдеться компонент викликає колізію для тієї ж пари запитів.
У цьому випадку побудова оптимізованих таблиць атаки неможливо. Також неможливо і визначити, чи існують «вільні» від колізій компоненти (Ki, Ki + 4, Ki + 8, Ki + 12).
У теорії, якби COMP 128 був насправді випадковою функцією, то, щоб очікувати колізію в сорока восьми бітному виході другого рівня, необхідно було б провести 2? 107 запитів. Експериментально Стюарт Рей обчислив, що для обчислення одного компонента (Ki, Ki + 4, Ki + 8, Ki + 12) необхідно провести порядку 127000 запитів. Також як і в модифікованій WGB атаці запити до різних компонентів можна виробляти паралельно, а при знаходженні трьох з них четвертий обчислювати методом грубої сили.
При симулюванні розтину 5290 сильних ключів Стюарт Рей [23] прийшов до висновку, що середня кількість звернень необхідних для розтину «сильного» ключа становить 525000 (Мал. 10).
Рис.10 - Залежність успіху атаки на Ki, складені з «сильних» елементів від кількості запитів
5. Практична ефективність застосовуваних зараз алгоритмів аутентифікації в стандарті GSM
Служба аутентифікації дійсності абонента є серцем системи безпеки стандарту GSM. Вона використовується для того, щоб задана мережа могла визначити справжність користувача і, в разі його правильної ідентифікації, згенерувати і надати ключі шифрування, необхідні для забезпечення конфіденційності основних сервісів мережі. Дана служба реалізована у всіх мережах і пристроях мобільного зв'язку. Однак, частоту запитів дійсності абонента, вибір конкретної реалізації алгоритму COMP 128, а також варіант виконання SIM - карти вибирає сам оператор.
Одним із завдань дипломної роботи було з'ясування...
