Вскрытие A5/1. Пока только теоретическое, но впечатляющее
Наконец, в декабре нынешнего года пришло еще одно известие. Израильские криптографы Ади Шамир и Алекс Бирюков опубликовали статью [12], в которой описан разработанный ими весьма нетривиальный, но по теоретическим расчетам очень эффективный метод вскрытия алгоритма A5/1.
Ади Шамира называют "патриархом израильской криптографии". Еще в 1977 году совместно с американцами Райвестом и Адлеманом Шамир разработал знаменитую криптосхему с открытым ключом RSA (здесь "S" - это Shamir). В 80-е годы, помимо сильных криптоаналитических работ, им разработано несколько криптографических протоколов и криптосхем. В начале 90-х совместно с Эли Бихамом Шамиром разработан метод дифференциального криптоанализа, ставший основой практически всех современных методов исследования и вскрытия блочных шифров. Его новая совместная с Бирюковым работа - это, возможно, первое обращение Шамира к анализу поточных шифров на основе регистров сдвига. Сам он говорит о разработанном методе вскрытия А5 следующее: "Это весьма сложная идея, реализуя которую мы наступаем на многих фронтах, чтобы накопить несколько небольших преимуществ, но сложенные все вместе они дают большой выигрыш. Но статью нашу было нелегко написать. Нелегко ее и читать".
Изложим суть работы в нескольких фразах. Новый метод атаки использует тонкие слабости в структуре регистров сдвига, необратимый механизм их движения, а также частые перезагрузки регистров, применяемые в GSM. В итоге такая атака позволяет отыскивать ключ менее чем за секунду на персональном компьютере, имеющем 128 Мб RAM и два жестких диска по 73 Гб, путем анализа выхода алгоритма в течение первых двух минут телефонного разговора (сразу отметим, что это весьма щедрое теоретическое допущение, поскольку две минуты открытого текста в реальных условиях получить не так просто). Для успеха атаки требуется предварительная и поддающаяся распараллеливанию подготовка данных, сложность которой может варьироваться от 238 до 248 шагов. Для подтверждения теоретических расчетов авторы действительно менее чем за секунду нашли 64-битный ключ шифрпоследовательности, порожденной алгоритмом A5/1 в версии SDA (отметим, что факт реальной длины ключа в 54 бита ими не использовался).
Сейчас полученные израильскими математиками результаты тщательно изучаются криптографами, но выводы из всей этой истории практически очевидны.
