Дэвид Лебланк - 19 смертных грехов, угрожающих безопасности программ
Генераторы случайных чисел, которые применяются уже много лет, с точки зрения безопасности не выдерживают никакой критики. Пусть даже числа выглядят случайными, противник все равно может угадать следующее число. Даже применяя хороший генератор случайных чисел, вы должны убедиться в том, что его внутреннее состояние не легко предсказать, а это совсем не простая задача.
Рассмотрим проблему внимательнее. Для этого опишем три разных механизма:
□ некриптографические генераторы псевдослучайных чисел (некриптографические PRNG);
□ генераторы псевдослучайных чисел криптографического качества (CRNG);
□ генераторы «истинно» случайных чисел (TRNG), известные также под названием энтропийные генераторы.
Греховность некриптографических генераторов
До появления сети Интернет случайные числа не использовались в критических с точки зрения безопасности приложениях. Они находили применение лишь в статистическом моделировании. Для испытаний методом Монте Карло нужны были числа, прошедшие все статистические тесты на случайность. Такие испытания по самому замыслу должны были быть повторяемыми. Поэтому API строился так, чтобы, получив на входе одно число, можно было порождать из него длинную серию чисел, выглядящих случайными. В подобных генераторах использовалась довольно простая математическая формула, порождающая последовательность элементов из начального значения (затравки).
Когда стали задумываться о безопасности, требования к случайным числам ужесточились. Нужно было, чтобы они не только успешно проходили статистические тесты, но еще чтобы противник не мог предсказать, какое число будет следующим, даже если видел несколько предыдущих.
Задача ставится следующим образом: если противник не знает затравку, то не может угадать число, которое еще не видел, сколько бы чисел ни наблюдал перед этим.
В случае традиционного некриптографического генератора его внутреннее состояние можно определить по одному–единственному результату. Но в большинстве приложений результат не используется непосредственно, а отображается на некоторый небольшой диапазон. Впрочем, это лишь ненадолго задержит противника. Предположим, что вначале противник ничего не знает о внутреннем состоянии генератора. Для большинства некриптографическоих генераторов существует 232 различных состояний. Каждый раз, когда программа выдает пользователю один бит информации о случайном числе (обычно четное оно или нечетное), противник может отбросить половину состояний. Таким образом, даже если противник получает минимальную информацию, ему необходима лишь небольшая выборка (в данном случае примерно 32 результата), чтобы полностью определить состояние генератора.
Ясно, что нам нужны генераторы, не обладающие таким свойством. Оказывается, что выработка хороших случайных чисел по существу эквивалентна разработке хорошего алгоритма шифрования, поскольку в ходе работы многих алгоритмов шифрования вырабатываются последовательности случайных чисел из начального значения (ключа), которые затем с помощью операции XOR объединяются с открытым текстом. Поэтому мы можем рассматривать генератор случайных чисел как шифр. Если криптографу удастся вскрыть его, значит, кто–то сможет предсказывать числа с большей вероятностью, чем вам хотелось бы.
Греховность криптографических генераторов
Простейшие криптографические генераторы псевдослучайных чисел (CRNG) работают примерно так же, как традиционные генераторы: вырабатывают из затравки длинную последовательность чисел. Если затравки одинаковы, то и последовательность будет той же самой. Единственная разница в том, что если противник не знает затравку, то вы можете показать ему первые 4000 чисел, и он не сможет предсказать 4001–ое с вероятностью, большей, чем в случае простого кидания монеты.
Проблема в том, что противник не должен знать затравку. Чтобы CRNG–гене–ратор был безопасным, затравка должна быть неугадываемой, а это, как мы вскоре убедимся, непростая задача.
Таким образом, безопасность CRNG не может быть больше, чем безопасность затравки. Если у противника есть один шанс из 224 угадать затравку, значит, с такой же вероятностью он сможет предсказать поток вырабатываемых чисел. Следовательно, у системы есть только 24 бита безопасности, пусть даже лежащий в ее основе криптографический алгоритм обладает 128 битами безопасности. Задачу противника лишь немного осложняет тот факт, что он не знает, в каком месте потока находится.
CRNG–генераторы часто считаются синонимами потоковых шифров. Технически это правильно. Например, RC4 – это потоковый шифр, который порождает строку случайных битов, которую можно объединить с помощью операции XOR с открытым текстом. Или использовать непосредственно, и тогда мы получим CRNG–генератор.
Но, говоря о CRNG–генераторах, мы включаем в рассмотрение инфраструктуру изменения затравки, а не только сам алгоритм генерации псевдослучайных чисел. Поэтому современные CRNG–генераторы не так полезны, как шифры, ибо они стремятся как можно чаще подмешивать новые истинно случайные данных (энтропию). Можно провести аналогию с потоковым шифром, в котором ключ случайно изменяется без уведомления второй стороны. Таким шифром пользоваться было бы невозможно.
Следует также отметить, что стойкость криптографического генератора не может быть выше стойкости ключа. Например, если вы хотите генерировать 256–битовые ключи для шифра AES, поскольку ключ длиной 128 битов кажется вам недостаточным, то не стоит в качестве генератора случайных чисел использовать шифр RC4. Мало того, что RC4 обычно генерирует 128–битовые ключи, так еще и эффективная стойкость этих ключей составляет всего 30 битов.
В состав большинства современных операционных систем уже входит тот или иной CRNG–генератор. Кроме того, они умеют получать истинно случайные числа, так что умение создавать собственные алгоритмы для этой цели уже не так важно.
Греховность генераторов истинно случайных чисел
Если CRNG–генератору все равно нужны для работы истинно случайные числа и если вы не занимаетесь испытаниями по методу Монте Карло, которые должны быть воспроизводимы, то почему бы просто не обратиться к генераторам истинно случайных чисел?
Если бы это было возможно, все были бы в восторге. Но на практике это трудно, ведь компьютеры по своей природе детерминированы. Да, в машине происходят некоторые случайные события, и их даже можно измерить. Например, часто измеряют время между нажатиями на клавиши или между перемещениями мыши. Но степень случайности таких событий оставляет желать лучшего. Дело в том, что процессор работает очень быстро, и по сравнению с его частотой события клавиатуры и им подобные поступают со слишком регулярными интервалами, поскольку они привязаны к внутреннему тактовому генератору устройства, который во много раз медленнее системного тактового генератора. С другой стороны, трудно сказать точно, какими возможностями располагает противник. Считается, что источники такого рода обеспечивают лишь несколько битов случайной информации на одну выборку.
Есть попытки получить случайные данные из других частей системы, но, увы, нельзя сказать, что состояние системы меняется непредсказуемо. Некоторые популярные источники (например, состояние ядра и процессов) изменяются куда медленнее, чем хотелось бы.
В результате предложение случайных чисел со стороны машины значительно уступает спросу, особенно когда речь идет о сервере, где никто не пользуется ни клавиатурой, ни мышью. Можно решить проблему с помощью специальной аппаратуры, но это дорого. Поэтому обычно приходится использовать имеющееся небольшое количество истинно случайных чисел для затравки CRNG–генератора.
Отметим еще, что данные, содержащие энтропию, например перемещения мыши, невозможно использовать в качестве случайных чисел напрямую. Даже данные, поступающие от аппаратного генератора, могут быть статистически смещены. Поэтому считается правильным «выделять» истинную энтропию, устраняя статистически определимые закономерности. Один из способов добиться этого – подать исходное значение на вход CRNG–генератора в качестве затравки и воспользоваться выработанным результатом.
Родственные грехи
Из–за предсказуемости случайных чисел криптосистема может оказаться ненадежной. Так, один из способов неправильного применения SSL как раз и заключается в использовании недостаточно хорошего источника случайности, в результате чего противник может угадать сеансовый ключ. Ниже в этой главе мы приведем соответствующий пример.
Где искать ошибку
Этот грех может проявиться в любой ситуации, когда нужно хранить некоторые данные в секрете, не допуская даже случайного угадывания. Вне зависимости от того, используется шифрование или нет, наличие хорошего источника случайных чисел – одно из ключевых требований к безопасности системы.
