Лобовая атака A5

Как было указано выше, лобовая атака системы безопасности в реальном времени невозможна. Сложность атаки составляет 2⁵⁴ (2⁶⁴ если 10 битов не были 0). Потребуется слишком много времени, чтобы прослушивание GSM звонков в реальном времени стало возможным. Можно было бы записать кадры между MS и BTS и после этого начать атаку.

Если имеется чип класса Pentium III, который содержит примерно 20 миллионов чипов, а для реализации одного набора LSFR схемы шифрования алгоритма А5 требуется 2000, то в одном чипе можно организовать примерно 10000 реализаций А5/1. При тактовой частоте 600 МГц, и если каждая реализация А5 выдает 1 бит за такт, и необходимо сгенерировать 100+114+114 бит, в реализации А5/1 можно проверять 2 миллиона ключей в секунду. Пространство ключей в 2⁵⁴ требует для перебора 900000 секунд или приблизительно 2⁵⁰ часов при одном чипе. Атака может быть оптимизирована отбрасыванием целых классов ключей после первого плохого бита ключевой последовательности. Это сократит требуемое время на одну треть. Атаку можно распределить между несколькими чипами, и таким образом значительно сократить время.

Атака A5 «Разделяй и Властвуй»

Атака «Разделяй и Властвуй» позволяет уменьшить стойкость алгоритма с 2⁵⁴ при лобовой атаке до 2⁴⁵, и это уже является относительно значительным изменением (2⁹ - это в 512 раз быстрее). Атака «Разделяй и Властвуй» основана на известной атаке открытого текста. Атакующийпытается определить начальные состояния регистров LSFR из известной последовательности гаммы. Атакующий должен знать 64 последовательные бита гаммы, которые можно извлечь, если атакующий знает какой-либо текст шифра и соответствующий открытый текст. Это в большой степени зависит от формата GSM кадров, посылаемых туда и обратно. Кадры GSM содержат большое количество постоянной информации, например, заголовки кадров. Требуемые 64 бита не всегда могут быть получены, но 32 или 48 бит, иногда и больше, обычно известны. Атакующему необходим только сегмент из 64 битов открытого текста.

Одним словом, атака «Разделяй и властвуй» реализуется путем угадывания содержания двух более коротких LSFR, а затем вычисления третьего LSFR из известной гаммы. Это была бы атака 2⁴⁰, если бы синхронизация первых двух регистров не зависела от третьего регистра. Вследствие того, что центральный бит третьего регистра используется для синхронизации, необходимо также угадать почти половину битов третьего регистра между битом синхронизации и LSB. Этот факт увеличивает сложность атаки с 2⁴⁰ до 2⁴⁵.

Однако Дж. Голик[]предложил другую атаку «Разделяй и Властвуй», основанную на этих же предположениях, приблизительная сложность атаки 2⁴⁰. Он описывает, как получить линейное равенство, угадывая n биты в регистрах LSFR. Решив эти линейные уравнения, можно восстановить начальные состояния трех LSFR. Сложность решения линейных уравнений составляет 2⁴⁰. Существует только 50-процентная вероятность решения.

В этой же работе Голик предложил атаку, основанную на Парадоксе дней рождений. Целью этой атаки было восстановление начальных состояний трех LSFR в известный промежуток времени для известной гаммы, соответствующей известному номеру кадра, и, таким образом, восстановление сеансового ключа, K_c.