Хитрости крипторемесла

Автор: Киви Берд
Опубликовано в журнале "Компьютерра" №46 от 26 декабря 2007 года

Как уже сообщалось в "КТ" #712, Бенни Пинкас, Цви Гуттерман и Лео Доррендорф (Benny Pinkas, Zvi Gutterman, Leo Dorrendorf), криптографы из университетов Хайфы и Иерусалима, вскрыли схему работы генератора псевдослучайных чисел, используемого Microsoft во всех криптоприложениях Windows 2000. Исследователи проанализировали стойкость подсистемы защиты и выявили в ней серьезнейшую уязвимость. В частности, они обнаружили, что из-за слабой схемы генератора злоумышленники могут всего лишь по одному внутреннему состоянию алгоритма предсказывать большое количество криптоключей, вырабатываемых в ОС. Причем не только ключей для будущих потребностей, но и уже сгенерированных.

Что такое "уязвимость"

Windows 2000 по сию пору используется многими компаниями и организациями, оставаясь, согласно общим оценкам, второй по популярности операционной системой Microsoft после XP. Но когда разнеслась весть о слабостях в PRNG (pseudo-random number generator), встал вопрос об уязвимости крипто в более новых системах, XP и Vista, - можно ли и их атаковать аналогичным образом?

Поначалу реакция Microsoft была довольно уклончивой и сводилась к заверениям, что последние версии Windows "содержат разнообразные изменения и доработки в схеме генератора случайных чисел", но затем Редмонд все же признал, что Windows XP тоже уязвима для атаки, описанной в работе Пинкаса, Гуттермана и Доррендорфа. Что же касается систем Windows Vista, Windows Server 2003 SP2 и планируемой к выпуску Windows Server 2008, то там, по словам Microsoft, схема генерации псевдослучайных чисел работает иначе и обладает иммунитетом к подобному методу взлома.

Попутно была сделана попытка интерпретировать работу израильтян не как выявление серьезной и реальной угрозы для безопасности XP (не говоря уж о Win2000), а как сугубо "теоретическую атаку". Ибо, по официальному мнению Microsoft, выявленный баг не отвечает определению "уязвимость", поскольку для эксплуатации слабостей в PRNG злоумышленник должен обладать правами администратора. Или, дословно, "поскольку администраторы по определению имеют доступ ко всем файлам и ресурсам системы, это [восстановление внутреннего состояния PRNG и вычисление ключей] не является недопустимым раскрытием информации". То, что множество известных червей и троянцев умеет повышать свои привилегии до уровня администратора, Microsoft, очевидно, сочла не относящимся к делу, но дабы публика не слишком волновалась, пообещала залатать-таки дыру в PRNG - где-нибудь в первой половине следующего года, вместе с выходом третьего сервис-пака, Windows XP SP3.

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

WEP, или Слабый эквивалент приватности

Стандарт криптозащиты WEP для беспроводных сетей WiFi порой неверно расшифровывают как Wireless Encryption Protocol, или протокол беспроводного шифрования. На самом деле аббревиатура означает Wired Equivalent Privacy (приватность, эквивалентная проводным сетям). Уже само имя дает основание предполагать, что защита, обеспечиваемая таким шифрованием, вряд ли обладает высокой стойкостью к атакам.

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

Начиная с 2001 года эффективность атак на WEP и скорость вскрытия ключей понемногу довели с нескольких часов до нескольких минут. Апофеозом же этого процесса можно считать наглядную демонстрацию в апреле 2007 года, когда трое исследователей из германского Университета Дармштадта на одной из конференций по инфобезопасности вскрывали ключи "защищенной" с помощью WEP сети менее чем за 3 секунды.

И хотя с 2003 года для защиты беспроводных сетей разработаны и применяются существенно более стойкие протоколы WPA и WPA2, изготовители сетевого оборудования по-прежнему ставят стандарт WEP первым в списках возможных опций для средств безопасности. Вследствие этого, как показали исследования, проводившиеся в текущем году в Германии, около половины всех WiFi-сетей используют для защиты откровенно слабый WEP и лишь чуть больше четверти - WPA. Остальные, впрочем, не применяют защиты вообще.

 

Чему учит история

Строго говоря, общедоступных официальных (или неофициальных) документов с хронологией развития и внятным рассказом о средствах защиты информации в программах MS не существует. Причина - в закрытости кодов Windows-платформы. Имеются, правда, заслуживающие доверия источники вроде книги "Написание безопасных кодов" [Michael Howard and David LeBlanc, Writing Secure Code. Microsoft Press, 2002], подготовленной специалистами корпорации и выпущенной издательством Microsoft Press. Но содержательные моменты в устройстве используемых криптоалгоритмов излагаются там лишь в самых общих чертах, без углубления в принципиально важные конструктивные подробности.

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

Элемент композиции скульптора Джеймса Сэнборна (James Sanborn) «ДвоиЧные системы» («Binary systems»). Десятифутовый гранитный диск, содержащий номера социального страхованияПо словам авторов книги Майка Ховарда (Michael Howard) и Дэвида Леблана (David Le-Blanc), генератор псевдослучайных чисел, вызываемый функцией CryptGen-Random, впервые появился в Windows 95, то есть в середине 1990-х годов. С той поры его стали включать во все базовые версии операционных систем Microsoft и их вариации. По свидетельству тех же авторов, конструкция алгоритма PRNG оставалась неизменной вплоть до Windows XP. Правда, при вскрытии схемы генератора в Win2000 израильтяне установили, что это не совсем так - некоторые модификации были, причем далеко не в лучшую сторону. Но в любом случае трудно не поражаться, что алгоритм Windows PRNG - несомненно, самого распространенного в мире криптогенератора - оставался невскрытым и никем не проанализированным на протяжении почти полутора десятков лет.

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

В самом первом продукте, MS Office 95, уже имелись средства шифрования документов. Но реально шифрование сводилось к применению побитовой операции XOR к паролю пользователя и тексту документа. С точки зрения криптоанализа защиты это не обеспечивало. Создавалась лишь ее видимость - превращение читаемого текста в нечитаемый.

Применение шифров из арсенала бойскаутов в тот период, когда миру уже была прекрасно известна программа PGP - символ общедоступного и очень сильного крипто, конечно, не злой умысел (или невежество) Microsoft. Просто все предыдущие десятилетия американские законы считали стойкие криптосредства столь же опасным военным товаром, как наступательные виды оружия, и они подлежали строжайшим экспортным ограничениям. В течение 1990-х годов, впрочем, эти драконовские законы были заметно ослаблены, а вместе с ними менялась и стойкость криптографии в Windows и MS Office.

В частности, в последующих версиях программ начали применять вполне качественный поточный шифр RC4. Правда, в ранних экспортных версиях ПО длина ключа ограничивалась всего лишь 40 битами. При такой длине шифры, как известно, без проблем вскрываются на ПК лобовым (тотальным) перебором всех возможных ключевых комбинаций. Но после коррекции экспортных законов к концу 1990-х пользователям новых версий Microsoft Office, в принципе, стали доступны теоретически стойкие шифрсредства - в частности, RC4 с длиной ключа 128 бит. Вот только на практике шифр оказался реализован так, что надежной защиты данных с его помощью все равно не получалось.

Среди фундаментальных основ криптографии имеется очень важное правило: если для засекречивания используется поточный шифр (наложение на открытый текст постоянно изменяющейся шифрпоследовательности), то никогда одну и ту же шифрпоследовательность не накладывают на два разных документа (разными в данном случае считаются любые модификации файла, включая вставку или изъятие единственного знака). Если же это сделано, то всего по двум одноключевым документам шифрование можно развалить и прочитать оба текста - причем сам ключ и его длина никакой роли не играют. В годы Второй мировой войны английские криптоаналитики из-за такого рода ошибок германских шифровальщиков смогли полностью вскрыть криптосхему шифратора "Шлюссельцузатц". Позже это позволило им с помощью "суперкомпьютера" Colossus вскрывать ключи и читать всю переписку противника.

В программных же продуктах Microsoft шифр RC4 был реализован таким образом, чтобы одноключевые комплекты порождались ВСЕГДА. Ключ без затей генерировался на основе пароля доступа к документу, поэтому разные версии документа шифровались одним и тем же ключом. Как известно, разные версии одних и тех же файлов присутствуют в системе очень часто - в резервных кэшах, как архивные копии, как совместно подготавливаемые документы и т. д. Для таких случаев в криптографии есть элементарнейший способ недопущения одноключевых комплектов - подмешивание в ключ наряду с паролем уникального, одноразового "вектора инициализации" (IV, initialization vector), который не является секретом, но всякий раз делает шифрпоследовательность иной.

То, что в Microsoft почему-то уклоняются от использования IV в поточном шифре, впервые стало известно в 1999 году еще для Windows NT - когда хакеры обнаружили слабости в системе защиты криптоключей Syskey. Серьезные оплошности в реализации криптографии допускаются регулярно и почти всеми разработчиками (см. врезку о WEP), однако в Microsoft не только проигнорировали тревожные сигналы, но и перенесли ту же самую слабость в последующие версии системы. В частности, в 2005 году, когда уже вышли Windows XP и Office 2003, стало известно, что все та же по сути уязвимость - отсутствие IV и систематическое порождение одноключевых комплектов - выявлена в документах, подготовленных и зашифрованных программами MS Word и MS Excel с помощью RC4.

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

Впрочем, и в тех ситуациях, когда PRNG используется для генерации секретных ключей или других криптопоследовательностей, делается это весьма небезопасным образом.

Слабость спереди и сзади

Качественный с точки зрения криптографии генератор псевдослучайных чисел должен отвечать трем главным требованиям: (1) выдавать последовательность, статистически неотличимую от случайной равновероятной; (2) противостоять восстановлению прошлых состояний по известному текущему; (3) противостоять восстановлению будущих состояний по текущему состоянию алгоритма.

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

Криптогенератор - это непросто

Из того, что требования, предъявляемые к качественному криптографическому генератору случайных чисел, хорошо известны, вовсе не следует, что сконструировать его проще простого. В истории криптографии много случаев, когда слабости находили и в новых схемах известных авторов, и в алгоритмах, успевших получить распространение. Например, в 1996 году одна из ранних версий протокола SSL была взломана именно из-за слабостей в генераторе случайных чисел. Совсем недавно были обнаружены криптографические слабости в PRNG операционных систем Linux и FreeBSD, открытых для анализа.

По этой причине многие разработчики средств защиты благосклонно встретили инициативу NIST, американского Института стандартов и технологий, подготовившего и опубликовавшего большой, на 130 страниц документ под названием NIST Special Publication 800-90, целиком посвященный генераторам псевдослучайных чисел. В этом документе они именуются DRBG (Deterministic Random Bit Generators), и там содержатся описания четырех изученных и рекомендуемых к применению генераторов.

Все четыре генератора построены на основе уже существующих криптографических примитивов, что принято считать плюсом. Один на основе хеш-функций, другой на основе HMAC (хешированного кода аутентификации сообщения), третий на основе блочных шифров, четвертый - на эллиптических кривых. С последним, правда, вышел конфуз по целому ряду причин. В отличие от трех первых, где примитивы уже хорошо изучены и проверены криптографическим сообществом, его схема была предложена совсем недавно, около года назад, Агентством национальной безопасности США. Алгоритм, по независимым оценкам, ничем хорошим не отличается, имеет мутную и не разъясненную разработчиком конструкцию и работает гораздо медленнее остальных трех. Да еще и несет в себе, как уже установлено, явные признаки математической закладки, с помощью секретных констант позволяющей взламывать генератор на лету.

Зачем в стандарты NIST включен столь сомнительный "подарок", в общем-то, понятно. Но не факт, что хоть кто-то захочет по доброй воле им воспользоваться.


Этот генератор тоже построен на основе RC4. И коль скоро всякий приличный поточный шифр дает на выходе последовательность чисел, статистически неотличимую от равновероятной, то и генератор на его основе вполне отвечает требованию (1). Но вот дальше начинаются очень неприятные моменты конкретной реализации PRNG. Чтобы обеспечить свойство (2) - не допустить восстановление прошлых состояний, - в качестве тактов генерации принято использовать однонаправленные (хеш-)функции, легко вычисляемые только в одну сторону. В Windows же обратная функция вычисляется столь же просто, как и прямая генерация следующего состояния.

Такая же унылая картина и для свойства (3). Дабы воспрепятствовать восстановлению будущих состояний криптогенератора, используют так называемую рандомизацию - то есть обновление состояний случайно взятой последовательностью бит от какого-нибудь внешнего источника. Чем короче расстояние между такими "перезагрузками", тем выше криптостойкость генератора. Хотя общая схема PRNG в Windows не менялась, в ранних версиях OC длина между перезагрузками состояний составляла 512 байт, а в Win2000, как установили израильтяне, она выросла до 16 килобайт. Если же учесть, что PRNG здесь реализован на основе восьми потоков от работающих в параллели шифров RC4, то получается, что реально длина генерируемой криптопоследовательности между перезагрузками состояний составляет 128 килобайт.

Поэтому, определив всего одно внутреннее состояние генератора (например, с помощью известного трюка с переполнением буфера памяти), злоумышленник может вычислить огромное количество ключей - как уже использованных, так и на будущее. Хуже того, перезагрузка состояний произойдет лишь в том случае, когда все эти 128 килобайт сгенерированы между включением и выключением компьютера. В терминах защищенных SSL-соединений веб-браузера это, огрубленно, означает от 600 до 1200 сеансов шифрованной связи. Понятно, что для обычного компьютера это нереально огромное число. Иными словами, в большинстве случаев криптогенератор вообще не перезагружает свои состояния, так что всего одной "израильской атакой" можно восстановить, по сути, ВСЕ генерируемые им ключи, как вперед, так и назад.

«Кириллический проектор» (Cyrillic projector, James Sanborn,1997 г.). Cодержит ключ к шифру и зашифрованный им текст на русском,  прочитать который удалось только в 2003 году

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

Ситуация с Vista

В новой системе Windows Vista, как не раз подчеркивали разработчики по самым разным поводам, защита информации реализована существенно иначе и на основе других алгоритмов. Отчасти это сделано в угоду всемогущей индустрии контента - для надежной защиты файлов от бесконтрольного копирования пользователями. В другой же, не менее важной части - чтобы обеспечить интересы Агентства национальной безопасности США. Тесное сотрудничество Microsoft с АНБ при разработке Vista является официально известным фактом, однако в чем именно состояли здесь интересы крупнейшей в мире разведслужбы, в объявлении скромно умолчали. Хотя секрет этот является секретом Полишинеля.

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

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


<<Венчур Колумба
Все материалы номера
Большой мрак и "Маленький брат" >>