В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 10. Генерация случайных чисел ходных данных и всех обновлений внутреннего состояния. Из этого следует, что, если атака на генератор псевдослучайных чисел когда-нибудь окончится успехом, этот генератор никогда не сможет вернуться в безопасное состояние. Восстановить безопасность генератора, внутреннее состояние которого стало известно злоумышленнику, весьма сложно. Для этого понадобится неко- торый источник энтропии, с помощью которого можно генерировать истинно случайные числа. Для простоты будем предполагать, что у нас есть один или несколько источников, предоставляющих определенное количество энтропии (обычно в виде небольших порций, которые мы будем называть событиями) в непредсказуемые моменты времени. Даже если мы перемешаем внутреннее состояние генератора с небольши- ми количествами энтропии, полученными в результате возникновения собы- тия, у злоумышленника все еще останутся пути нападения. Он может посы- лать генератору частые запросы на получение случайных данных. Посколь- ку общее количество энтропии, добавляемое к внутреннему состоянию ге- нератора в промежуток времени между двумя подобными запросами, будет ограничено, скажем, 30 битами, злоумышленник сможет просто перебрать все возможные варианты случайных входных данных и определить новое внутреннее состояние, полученное после перемешивания. Это потребует око- ло 2 30 шагов, что вполне достижимо с помощью современных технологий 1 . Обнаружив правильное решение, злоумышленник сможет легко проверить его с помощью все тех же случайных данных, выдаваемых генератором. Лучшее, что можно сделать для борьбы с описанным типом атак, — это ор- ганизовать пул входящих событий, которые несут в себе энтропию. Мы будем собирать энтропию до тех пор, пока ее не окажется достаточно для того, что- бы при перемешивании энтропии с внутренним состоянием генератора зло- умышленник не мог угадать собранные случайные данные. Сколько же энтро- пии для этого потребуется? Согласно нашим требованиям к уровню безопас- ности, злоумышленник должен потратить на осуществление атаки минимум 2 128 шагов, для чего понадобится 128 бит энтропии. Здесь, однако, мы стал- киваемся с серьезной проблемой: получить какую-либо оценку количества эн- тропии невероятно сложно, если вообще возможно. Оценка энтропии весьма существенно зависит от того, сколько знает или может знать злоумышлен- ник, а эта информация еще не доступна разработчикам системы на стадии проектирования. В этом и состоит основная проблема генератора Yarrow. Он пытается измерить энтропию источника, используя оценку энтропии, а полу- чить правильную оценку для всех ситуаций практически невозможно. 1 Многие, наверное, будут возмущены небрежностью наших вычислений. В этом примере нам следовало использовать оценочную энтропию (guessing entropy), а не стандартную шенноновскую энтропию. Более подробно о мерах энтропии можно прочитать в [14]. 10.3. Проект Fortuna 183 10.3 Проект Fortuna Во время работы над этой главой мы значительно усовершенствовали ге- нератор Yarrow. Новое решение получило название Fortuna в честь Форту- ны — древнеримской богини слепого случая и удачи 2 . Fortuna решает пробле- му необходимости определения оценок энтропии, просто отказавшись от них. Оставшаяся часть этой главы в основном посвящена рассмотрению деталей ГПСЧ Fortuna 3 . Fortuna состоит из трех частей. Генератор принимает на вход начальное число фиксированной длины и выдает произвольное количество псевдослу- чайных данных. Аккумулятор собирает и накапливает энтропию из различ- ных источников, а также время от времени изменяет начальное число генера- тора. И наконец, система управления файлом начального числа гарантирует, что генератор сможет производить случайные данные даже непосредственно после перезагрузки компьютера. 10.4 Генератор Генератор преобразует некоторое состояние фиксированной длины в вы- ходные данные произвольной длины. В качестве генератора мы будем ис- пользовать AES-подобный блочный шифр. Выберите тот, что вам больше нравится, — AES (Rijndael), Serpent или Twofish (см. раздел 4.5.7). Внутрен- нее состояние генератора включает в себя 256-битовый ключ блочного шифра и 128-битовый счетчик. По своей сути генератор — это всего лишь блочный шифр, работающий в режиме счетчика. Напомним, что режим счетчика или CTR генерирует случайный поток данных, которые мы будем использовать в качестве вы- ходных. Для повышения безопасности добавим к режиму работы блочного шифра еще несколько усовершенствований. Если пользователь или приложение запрашивает случайные данные, ге- нератор запускает свой алгоритм и производит псевдослучайные данные. Те- перь предположим, что злоумышленнику удается раскрыть состояние гене- ратора после выполнения очередного запроса. Было бы хорошо, если бы это не дискредитировало предыдущие результаты, выданные генератором. Для этого после выполнения каждого запроса будем генерировать еще 256 бит 2 Вначале мы собирались назвать его по имени древнегреческой богини счастья и благо- денствия Тюхэ, но затем поняли, что многие не смогут правильно прочитать слово “Tyche”. 3 Чтобы не путать генератор, являющийся одной из трех составных частей проекта For- tuna, и сам проект Fortuna (который, по сути, представляет собой реализацию криптогра- фического генератора псевдослучайных чисел), будем обозначать последний аббревиату- рой ГПСЧ (от “генератор псевдослучайных чисел”). — Прим. перев. |