Алгоритм шифрования A5/3 в сетях 3G скомпрометирован // 23 Ноября 2012

Не прошло и двух недель после демонстрации практического способа по прослушке переговоров в сетях GSM, как израильские криптоаналитики опубликовали теоретические выкладки по взлому шифра A5/3 (Kasumi), который используется в более защищенных сетях 3G. Несмотря на явную непригодность открытого алгоритма для реальной прослушки переговоров, данная теоретическая работа служит грозным предупреждением о необходимости периодической модернизации механизмов шифрования.

Авторами теоретической работы по взлому ключа шифрования в алгоритме A5/3, носящем кодовое наименование Kasumi, выступили три исследователя – Орр Данкельман (Orr Dunkelman), Натан Келлер (Nathan Keller) и Ади Шамир (Adi Shamir). Ади Шамир – это буква S в знаменитом алгоритме шифрования RSA с открытым ключом. Сейчас Шамир преподает на кафедре математики и вычислительных машин в институте Вейцмана в Израиле.

Метод взлома, основанный на схеме так называемых «связанных ключей» (related keys), сами авторы назвали «методом сэндвича», поскольку он состоит из трех слоев – два тонких слоя сверху и снизу, а еще один «толстый» слой посередине. Атака с помощью связанных ключей подразумевает анализ изменений, которые происходят с зашифрованным сообщением, когда оно перешифруется с помощью одного или нескольких ключей, заведомо отличающихся от исходного.

Авторы исследования утверждают, что с помощью связанных ключей и анализа последнего остающегося результата им удалось получить полный 128-битный ключ алгоритма Kasumi, используя всего 4 связанных ключа. Дополнительно для взлома нужно 226 единиц данных, 230 байт памяти и 232 единиц времени. Требования оказались настолько малы, что в ходе эксперимента успешная эмуляция атаки на ПК заняла менее 2 часов.

Само собой, для практической атаки на сети 3G необходимо выполнение множества условий, невыполнимых на данный момент. В частности, атакующий должен сначала собрать несколько миллионов заведомо известных сообщений, зашифрованных с помощью A5/3. Тем не менее, появление теоретических работ, описывающих уязвимость самого стойкого из механизмов шифрования сотовых сетей, доказывает, что потребность в создании новых систем стала актуальной, как никогда. Интересно, что члены GSM Association пока никак не отреагировали на работу израильских ученых-криптоаналитиков.

Подробнее о теоретическом взломе алгоритма шифрования переговоров и данных в сотовых сетях 3G можно прочитать на сайтах The Register и Electronista. Оригинал статьи в формате PDF можно найти на сайте авторов.