5.6. Анализ стойкости криптографических примитивов

Несмотря на многовековую историю криптографии и криптоанализа, до сих пор не существует математического аппарата, позволяющего доказать, что ключ шифрования определенного алгоритма невозможно найти более эффективно, чем полным перебором ключевого пространства. Скорее всего, такой математический аппарат не будет разработан и в обозримом будущем. Однако прежде чем использовать любой криптографический алгоритм, необходимо получить подтверждение его надежности.

Алгоритмы шифрования с открытым ключом, как правило, позволяют свести задачу взлома шифра к хорошо известной математической проблеме, такой как разложение большого числа на простые сомножители или вычисление дискретного логарифма в конечном поле. Пока математическая проблема не имеет эффективного решения, алгоритм будет оставаться стойким. Как только эффективное решение будет найдено, стойкость всех криптографических алгоритмов и протоколов, использующих данную математическую проблему, резко снизится. Так что разработчикам и пользователям криптосистем, основанных на математической проблеме, остается лишь надеяться, что эффективное решение не существует или никогда не будет найдено. К их счастью, значительных предпосылок к близкому прорыву в этих областях математики пока нет.

Для симметричной криптографии автор алгоритма может привести соображения, которыми он руководствоваться при разработке шифра, но этого явно недостаточно. Требуется некая процедура, если не гарантирующая стойкость, то хотя бы дающая высокую степень уверенности, что алгоритм не будет взломан злоумышленником.

На настоящий момент основным методом проверки криптографической стойкости алгоритмов является экспертная оценка. Новый алгоритм открыто публикуется, и все желающие получают возможность попытаться найти в нем слабые места. Если кому-то из криптоаналитиков удается обнаружить серьезные недостатки, алгоритм отправляется в мусорную корзину. Если же на протяжении значительного периода времени (обычно нескольких лет) никому не удалось отыскать уязвимости в алгоритме, то он может занять почетное место среди других алгоритмов, рекомендуемых к применению на практике. Именно так проводятся сейчас конкурсы на выбор алгоритма для национального стандарта шифрования.

Проверить надежность нового алгоритма без привлечения криптографической общественности под силу разве что таким организациям, как АНБ. А любой другой разработчик, желающий сохранить алгоритм в тайне, может оказаться в ситуации, когда через некоторое время используемый алгоритм перестает быть секретным и вскоре появляется эффективный метод его вскрытия. Именно поэтому современная криптография, в большинстве случаев, является открытой — вероятность взлома хорошо исследованного алгоритма значительно ниже, чем алгоритма, державшегося долгое время в секрете.

Алгоритм шифрования А5
В качестве наглядного примера опасности, связанной с засекречиванием деталей реализации алгоритмов шифрования, можно привести историю поточного шифра А5, применяемого для шифрования сеансов телефонной связи между трубкой абонента и базовой станцией в европейской системе мобильной цифровой связи GSM (Group Special Mobile).
Шифр А5 был разработан в 1989 году и существует в двух версиях: А5/1 — "сильная" версия шифра, разрешенная к применению только в некоторых странах, и А5/2 — "ослабленная" версия, разрешенная к свободному применению. В 1989 году широкая публикация алгоритмов не была распространенным подходом, и детали построения А5 оказались засекречены.
Но как бы строго ни контролировались коммерческие секреты, широкое распространение продукции рано или поздно приводит к утечкам информации. В случае с GSM утечки начались в начале 90-х годов. Британская телефонная компания передала всю документацию Брэдфордскому университету, не потребовав от него подписать соглашение о неразглашении. Часть информации попала в Интернет, а к 1994 году основные детали алгоритма А5 стали общедоступны. В конце концов, кембриджские ученые Майк Роэ (Mike Roe) и Росс Андерсон (Ross Anderson) опубликовали в Интернете примерную схему алгоритма.
В начале 1999 года в ассоциации разработчиков смарт-карт (Smart-Card Developer Association, SDA) были полностью восстановлены и проверены на реальных тестовых векторах схемы алгоритмов А5/1 и А5/2. Почти сразу после этого была предложена атака, позволяющая вскрывать шифр А5/2 на персональном компьютере всего за 15 миллисекунд.
В декабре 1999 года израильскими математиками Ади Шамиром (Adi Shamir) и Алексом Бирюковым (Alex Biryukov) была опубликована еще одна работа, в которой описан нетривиальный, но по теоретическим расчетам очень эффективный метод вскрытия алгоритма А5/1. Этот метод требует 24В предварительных вычислений и позволяет находить ключ за 1 секунду на персональном компьютере, имеющем 128 Мбайт оперативной памяти и 150 Гбайт дискового пространства, путем анализа выхода алгоритма в течение первых двух минут телефонного разговора.

Однако интуитивно понятно, что отсутствие успешных результатов криптоанализа конкретного алгоритма еще не гарантирует, что эти результаты не появятся в будущем. Работы по усовершенствованию методов криптоанализа ведутся постоянно, и нет никакой гарантии, что не удастся найти эффективные методы взлома существующих шифров.

Экспертная оценка применяется аналогичным образом и для проверки криптографической стойкости хэш-функций и генераторов псевдослучайных чисел.