В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 10. Генерация случайных чисел псевдослучайных данных и использовать их в качестве нового ключа шиф- рования. Старый ключ при этом уничтожается, чтобы исключить любую воз- можность утечки информации о предыдущих запросах. Чтобы сгенерированные данные обладали статистической случайностью, не следует генерировать слишком много данных одновременно. Действитель- но, в истинно случайных данных значения блоков могут периодически повто- ряться, в то время как выходные данные режима счетчика никогда не содер- жат повторяющихся блоков. (Более подробно это описано в разделе 5.8.2.) Су- ществует несколько способов решения этой проблемы. Например, можно ис- пользовать только половину каждого блока шифрованного текста, что прак- тически устранит статистическое отклонение от истинно случайной последо- вательности блоков. В качестве альтернативы вместо блочного шифра мож- но было бы использовать так называемую псевдослучайную функцию (pseu- dorandom function) , но нам пока что не попадалось хорошо исследованных и эффективных предложений. Самое простое, что можно сделать в данной ситуации, — это ограничить количество байтов случайных данных, которые могут выдаваться в ответ на один запрос. Это значительно затруднит выявле- ние статистического отклонения от истинно случайной последовательности. Если бы нам понадобилось сгенерировать 2 64 блока данных с помощью одного и того же ключа, мы бы могли ожидать появления одной коллизии среди значений блоков. Несколько повторяющихся запросов такого размера быстро бы показали, что выходные данные генератора не являются истинно случайными; им не хватает ожидаемого числа коллизий. Поэтому мы ограни- чиваем максимальный размер данных, которые могут быть выданы в ответ на один запрос, 2 16 блоками (т.е. 2 20 байт). Для идеального генератора слу- чайных чисел вероятность обнаружения коллизии среди 2 16 блоков данных составляет около 2 − 97 , поэтому полное отсутствие коллизий может быть об- наружено только после выполнения около 2 97 запросов. Общее количество работы, которое придется проделать злоумышленнику, составит примерно 2 113 шагов. Это, конечно же, меньше запланированных нами 2 128 шагов, но все равно довольно неплохо. Мы знаем, что изменяем своим принципам, соглашаясь на более низкий (правда, лишь немного более низкий) уровень безопасности. К сожалению, хорошей альтернативы этому решению, кажется, нет. У нас нет подходящих криптографических функций, на основе которых можно было бы построить генератор псевдослучайных чисел с полным 128-битовым уровнем безопас- ности. Мы бы могли применить функцию SHA-256, но она слишком мед- ленная. Люди всегда будут спорить о том, нужно ли использовать хороший криптографический генератор псевдослучайных чисел, и одним из аргумен- тов против использования последнего является скорость. Заметное снижение скорости работы генератора для выигрыша еще нескольких бит безопасности 10.4. Генератор 185 совершенно не устроит основную массу пользователей. Слишком многие из них просто предпочтут другой, действительно плохой генератор, чем напрочь испортят уровень безопасности всей системы. Если бы у нас был блочный шифр с 256-битовым размером блока, то- гда вопрос коллизий не стоял бы вообще. Впрочем, на практике описанная атака не представляет собой какой-либо серьезной угрозы. Для ее осуществ- ления недостаточно тех самых 2 113 шагов, которые должен выполнить зло- умышленник. Атакуемому компьютеру тоже придется провести 2 113 операций шифрования. Как видите, успешность подобной атаки зависит не столько от скорости работы компьютера злоумышленника, сколько от скорости работы компьютера самого пользователя. Большинство пользователей не собираются увеличивать вычислительную мощность своего компьютера только для того, чтобы помочь злоумышленнику. Честно говоря, нам не нравятся подобные ар- гументы в пользу безопасности решения. Они слишком неоднозначны, и если генератор псевдослучайных чисел когда-нибудь будет использован в непри- вычном окружении, эти аргументы могут и не сработать. Все же, учитывая ситуацию, наше решение представляется наилучшим компромиссом, к кото- рому мы могли бы прийти. Когда по окончании выполнения каждого запроса мы пересчитываем ключ блочного шифра, то не сбрасываем счетчик. Это второстепенный мо- мент, однако он позволяет избежать проблемы коротких циклов. Представим, что нам необходимо сбрасывать счетчик после выполнения каждого запроса. Если значение ключа когда-нибудь повторится во второй раз, а все запросы будут получать фиксированный объем данных, тогда следующее значение ключа также повторится во второй раз. В результате можно получить корот- кий цикл значений ключа. Вообще-то подобная ситуация маловероятна, но, не сбрасывая счетчик, этой проблемы можно избежать вообще. Поскольку дли- на счетчика составляет 128 бит, мы никогда не повторим значение счетчика (генерация 2 128 блоков выходит за пределы вычислительных возможностей наших компьютеров), что автоматически не допустит образования каких-ли- бо циклов. Вдобавок ко всему мы можем использовать значение счетчика 0 для указания того, что генератор еще не имеет ключа и, следовательно, не может выдавать данные. Обратите внимание: ограничение максимального объема данных, кото- рый может быть выдан в ответ на один запрос, до 1 Мбайт, вовсе не явля- ется непреодолимым. Если вам нужно больше мегабайта случайных данных, просто повторите запрос. В действительности реализация системы может со- держать интерфейс, который будет автоматически выполнять подобные по- вторяющиеся запросы. Сам по себе генератор является очень полезным модулем. Думаем, в боль- шинстве реализаций он будет доступен не только как компонент ГПСЧ For- |