В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 10. Генерация случайных чисел 10.5.3 Вопросы реализации Ниже приводится несколько соображений по поводу реализации аккуму- лятора. Распределение событий между пулами Поступающие события должны каким-то образом распределяться меж- ду пулами. Заниматься распределением событий мог бы и сам аккумулятор, но это опасно по следующей причине. Нам понадобится реализовать функ- цию, которая будет передавать события аккумулятору. Вполне вероятно, что к этой же функции сможет обращаться и злоумышленник. Последний мо- жет выполнять дополнительные вызовы функции каждый раз при генерации “настоящего” события, тем самым влияя на выбор пула, в который должно было бы поступить следующее “настоящее” событие. Если злоумышленнику удастся собрать все “настоящие” события в пуле P 0 , то система пулов станет неэффективной и злоумышленник сможет осуществлять атаки на один пул. Если же все настоящие события окажутся собранными в пуле P 31 , то они вообще никогда не будут использованы. Наше решение состоит в том, чтобы каждый источник энтропии переда- вал вместе с событием и номер пула, в который следует поместить это со- бытие. В этом случае, чтобы повлиять на распределение событий, злоумыш- леннику потребовался бы доступ к памяти программы, которая генерирует событие. Если же злоумышленник действительно обладает доступом тако- го высокого уровня, тогда, вероятно, дискредитированным следует считать и сам источник энтропии. Аккумулятор мог бы осуществлять проверку того, в правильном ли по- рядке каждый источник энтропии распределяет свои события между пулами. Хорошие функции часто проверяют, правильно ли сформированы их входные параметры, поэтому на первый взгляд такая идея кажется довольно удач- ной. Тем не менее в нашей ситуации не совсем понятно, как должен вести себя аккумулятор, если такая проверка выявит нарушения. Если весь ГПСЧ выполняется как пользовательский процесс, он мог бы сгенерировать неис- правимую ошибку и завершить выполнение программы. Но зачем же лишать систему генератора псевдослучайных чисел только из-за неправильного пове- дения одного источника энтропии? Если же ГПСЧ является частью ядра опе- рационной системы, ситуация становится еще сложнее. Представим себе, что какой-нибудь драйвер генерирует случайные события, но не в состоянии от- слеживать даже простенький 5-битовый циклический счетчик событий. Что должен делать аккумулятор? Возвратить код ошибки? Но если программист делает такие простые ошибки, он, скорее всего, не будет проверять коды воз- врата. Остановить работу ядра? Это слишком радикальная мера, которая 10.5. Аккумулятор 195 приведет к полному отказу системы из-за какого-то одного неправильного драйвера. Лучшее, что мы смогли придумать на данный момент, — это “на- казать” драйвер задержкой в предоставлении процессорного времени. Если проверка распределения событий выявит нарушения, аккумулятор может за- держать выполнение соответствующего драйвера примерно на одну секунду. Подобную идею тоже нельзя назвать полезной. Напомним: мы разрешили источнику событий самому определять номера пулов, так как предположили, что злоумышленник может осуществлять ложные обращения к аккумулято- ру, используя поддельные события. Если это случится и аккумулятор выпол- нит проверку порядка распределения событий, за плохое поведение злоумыш- ленника будет наказан ни в чем не повинный генератор настоящих событий. Наше заключение таково: аккумулятору не стоит проверять порядок распре- деления событий, поскольку даже в случае обнаружения нарушений он не сможет сделать что-нибудь полезное. Каждый источник энтропии отвечает за распределение своих событий между пулами по циклическому принци- пу. Если же работа какого-нибудь источника будет нарушена, мы потеряем энтропию, предоставляемую этим источником (чего мы, собственно, и ожи- дали), но этим все и ограничится. Время обработки события Желательно ограничить количество вычислений, которые могут выпол- няться при передаче события аккумулятору. Большинство событий являются временн ´ ыми и генерируются драйверами реального времени. Драйверам не нужен аккумулятор, который слишком долго обрабатывает события. Существует определенный минимальный объем вычислений, необходи- мый для обработки каждого события. В частности, нам нужно присоединить данные события к содержимому выбранного пула. Конечно, мы не собира- емся хранить в памяти всю строку пула, так как ее длина потенциально не ограничена. Вместо этого мы выделим каждому пулу небольшой буфер па- мяти и будем подсчитывать частичный хэш-код строки по мере заполнения буфера. Это и есть минимальный объем вычислений, которые необходимо выполнить для обработки события. Не хотелось бы лишний раз выполнять обновление начального числа, в ко- тором задействованы один или несколько пулов. Каждая из таких операций занимает на порядок больше времени, нежели простое добавление события к пулу. Поэтому мы отложим обновление начального числа до тех пор, по- ка пользователь не запросит случайные данные. Как только это произойдет, аккумулятор выполнит обновление начального числа непосредственно перед генерацией случайных данных. Применение подобной схемы позволяет хотя бы немного сместить вычислительную нагрузку с генераторов событий на |