В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 10. Генерация случайных чисел источниках энтропии или же сам периодически генерирует ложные события? В этом случае он, вероятно, знает о содержимом пула P 0 достаточно, для того чтобы предсказать новое состояние генератора на основе его старого состоя- ния и выходных данных. Тем не менее, когда в обновлении будет участвовать пул P 1 , он будет содержать в два раза больше данных, не предсказуемых для злоумышленника, пул P 2 — в четыре раза больше непредсказуемых данных и т.п. Таким образом, если хотя бы один источник случайных событий не является предсказуемым для злоумышленника, то независимо от количества событий, которые генерирует сам злоумышленник или о которых у него есть информация, у нас всегда будет пул, содержащий достаточно энтропии для отражения атаки. Скорость восстановления системы после раскрытия злоумышленником информации о внутреннем состоянии генератора зависит от интенсивности, с которой энтропия (являющаяся таковой и для злоумышленника) поступает в пулы. Если предположить, что скорость поступления энтропии является фиксированной и равна ρ , тогда через t секунд у нас будет ρt бит энтро- пии. За этот период времени каждый пул получит около ρt/ 32 бит энтропии. Злоумышленник больше не сможет отслеживать внутреннее состояние гене- ратора, если оно будет обновлено с помощью пула, содержащего более 128 бит энтропии. Здесь возможны два случая. Если перед следующей операцией об- новления в пуле P 0 наберется более 128 бит энтропии, безопасность генерато- ра будет восстановлена. В этом случае быстрота восстановления безопасности зависит от того, сколько данных удастся собрать в пуле P 0 , прежде чем про- изойдет обновление. Второй случай — это когда сбрасывание пула P 0 проис- ходит слишком быстро из-за возникновения случайных событий, известных злоумышленнику (или сгенерированных им самим). Пусть t — это время меж- ду двумя обновлениями состояния генератора. За это время пул P i соберет 2 i ρt/ 32 бит энтропии. Отметим также, что этот пул будет участвовать в про- цедуре обновления каждые 2 i t секунд. Восстановление безопасности генера- тора произойдет при следующем обновлении его состояния с помощью перво- го пула P i , для которого будет справедливо неравенство 128 ≤ 2 i ρt/ 32 < 256 . (Наличие верхней границы неравенства объясняется следующим фактом: ес- ли бы число 2 i ρt/ 32 было больше или равно 256, это бы означало, что 128 бит энтропии накопилось еще в пуле P i − 1 , а это противоречит тому, что первым таким пулом является P i .) Из приведенного выше неравенства следует, что 2 i ρt 32 < 256 , а значит, 2 i t < 8192 ρ . 10.5. Аккумулятор 193 Другими словами, интервал времени между моментами восстановления ( 2 i t ) ограничен временем, необходимым для накопления 2 13 бит энтропии ( 8192 /ρ ) . На первый взгляд число 2 13 выглядит довольно большим, однако его появление можно объяснить следующим образом. Чтобы восстановить безопасность генератора, требуется по крайней мере 2 7 бит энтропии. Если нам не повезет и обновление системы произойдет как раз перед тем, как мы набрали 2 7 бит в некотором пуле, придется воспользоваться следующим пу- лом, который ко времени обновления соберет около 2 8 бит энтропии. И нако- нец. мы разбиваем данные на 32 пула, что добавляет еще один множитель 2 5 . Это очень хороший результат. Наше решение отличается от идеального не более чем на множитель 64 (нам понадобится максимум в 64 раза больше случайности, чем требует идеальное решение). Это постоянный множитель, который гарантирует, что ситуация никогда не станет слишком плохой и без- опасность генератора в конце концов будет восстановлена. Более того, нам не обязательно знать, сколько энтропии содержат наши события или сколько ин- формации есть у злоумышленника. Именно этим Fortuna выгодно отличается от Yarrow. Отсутствие оценок энтропии, которые практически невозможно построить правильно, пошло новому решению только на пользу. Механизм обновления полностью автоматизирован; если случайные данные поступают с хорошей интенсивностью, генератор быстро восстановит свою безопасность. Если же случайные данные поступают медленно, процесс восстановления бу- дет гораздо длительнее. До сих пор мы никак не учитывали тот факт, что у нас есть только 32 пу- ла. А что, если даже в пуле P 31 между двумя обновлениями не наберется достаточно энтропии для того, чтобы восстановить безопасность генератора? Это может произойти в том случае, если злоумышленник инициирует так много случайных событий, что генератор испытает 2 32 обновлений еще до того, как источники, не находящиеся под влиянием злоумышленника, успе- ют сгенерировать 2 13 бит энтропии. Вообще говоря, это маловероятно, но, чтобы полностью предотвратить подобную ситуацию, можно ограничить ча- стоту обновлений. Каждое новое обновление будет выполняться не ранее чем через 100 мс после предыдущего. Это ограничит частоту обновлений до 10 в секунду, а значит, пул P 32 , если бы таковой существовал, был бы впер- вые использован не ранее чем через 13 лет после начала работы генератора! Учитывая, что экономический и технологический срок жизни большинства современных компьютеров значительно меньше 10 лет, вполне достаточно и 32 пулов. |