О документе
Рабочая группа сети D. Eastlake, 3rd
Запрос комментариев: 4086 Motorola Laboratories
BCP: 106 J. Schiller
Заменяет: 1750 MIT
Категория: Лучшая современная практика S. Crocker
Июнь 2005
Требования к случайности для безопасности
1. Введение и обзор
Программная криптография получает всё более широкое применение, хотя
до её повсеместного распространения ещё далеко. Такие системы, как SSH,
IPSEC, TLS, S/MIME, PGP, DNSSEC и Kerberos, развиваются и становятся
частью сетевого ландшафта [SSH] [IPSEC] [TLS] [S/MIME] [MAIL_PGP*]
[DNSSEC*]. Для сравнения: когда в 1994 году была опубликована
предыдущая версия этого документа [RFC1750], единственной спецификацией
криптографической безопасности Интернета в IETF был протокол Privacy
Enhanced Mail [MAIL_PEM*].
Эти системы обеспечивают существенную защиту от перехвата и подмены.
Однако имеется потенциальный изъян. В основе всех криптографических
систем лежит генерация секретных, неугадываемых (то есть случайных)
чисел.
Отсутствие общедоступных средств генерации таких случайных чисел (то
есть отсутствие повсеместно доступных действительно непредсказуемых
источников) образует открытую рану в проектировании криптографического
программного обеспечения. Для разработчика программного обеспечения,
который хочет создать процедуру генерации ключей или паролей, работающую
на широком диапазоне оборудования, это весьма реальная проблема.
Следует отметить, что требуются данные, вероятность угадывания или
определения которых противником очень мала. Это требование может легко
не выполняться при использовании псевдослучайных данных, проходящих
только традиционные статистические тесты случайности, либо основанных
на источниках с ограниченным диапазоном, таких как часы. Иногда такие
псевдослучайные величины могут быть угаданы противником, перебирающим
до неловкости малое пространство возможностей.
Этот документ «Лучшая современная практика» описывает методы создания
случайных величин, устойчивых к атакам. Он рекомендует включать в
будущие системы аппаратную генерацию случайных чисел либо предоставлять
доступ к имеющемуся оборудованию, которое может использоваться для этой
цели. Он предлагает методы применения, если такое оборудование
недоступно, и даёт некоторые оценки количества случайных битов,
требуемых для примеров применений.
2. Общие требования
Сегодня часто встречающееся требование к случайности состоит в выборе
пользовательского пароля, обычно простой символьной строки. Очевидно,
что угадываемый пароль не обеспечивает безопасности. Для многократно
используемых паролей желательно, чтобы пользователи могли запомнить
пароль. Это может обусловить целесообразность использования
произносимых символьных строк или фраз, состоящих из обычных слов. Но
это влияет лишь на формат информации пароля, а не на требование, чтобы
пароль было очень трудно угадать.
Многие другие требования исходят из криптографической области.
Криптографические методы могут использоваться для предоставления
различных служб, включая конфиденциальность и аутентификацию. Такие
службы основаны на величинах, традиционно называемых «ключами», которые
неизвестны противнику и не могут быть им угаданы.
Даже в протоколе TCP/IP случайность используется при выборе начальных
номеров последовательности [RFC1948].
В целом приведённые выше примеры также иллюстрируют два различных типа
случайных величин, которые могут требоваться. В случае пригодных для
использования человеком паролей единственная важная характеристика —
их неугадываемость. Не имеет значения, например, что они могут состоять
из символов ASCII, так что старший бит каждого байта равен нулю. С
другой стороны, для ключей фиксированной длины и тому подобного обычно
нужны величины, которые выглядят действительно случайными, то есть
величины, биты которых проходят статистические тесты случайности.
В некоторых случаях, таких как использование симметричного шифрования
с одноразовыми блокнотами или алгоритмом вроде US Advanced Encryption
Standard [AES], все стороны, желающие конфиденциально обмениваться
информацией и/или обмениваться ею с аутентификацией, должны знать один
и тот же секретный ключ. В других случаях, когда используются
асимметричные или криптографические методы «с открытым ключом», ключи
образуют пары. Один ключ пары является закрытым и должен храниться в
секрете одной стороной; другой является открытым и может быть
опубликован всему миру. Вычислительно неосуществимо определить закрытый
ключ по открытому ключу, и знание открытого ключа не помогает
противнику [ASYMMETRIC]. См. общие ссылки [SCHNEIER, FERGUSON,
KAUFMAN].
Частота и объём потребности в случайных величинах существенно
различаются для разных криптографических систем. При чистом RSA
случайные величины требуются только при генерации новой пары ключей;
после этого может быть подписано любое число сообщений без дальнейшей
потребности в случайности. Digital Signature Algorithm с открытым
ключом, разработанный US National Institute of Standards and
Technology (NIST), требует хороших случайных чисел для каждой подписи
[DSS]. И
шифрование с помощью одноразового блокнота (в принципе сильнейший
возможный метод шифрования) требует случайности в объёме, равном объёму
всех подлежащих обработке сообщений. См. общие ссылки [SCHNEIER,
FERGUSON, KAUFMAN].
В большинстве этих случаев противник может попытаться определить
«секретный» ключ методом проб и ошибок. Это возможно, пока ключ
настолько меньше сообщения, что правильный ключ может быть однозначно
определён. Вероятность успеха противника должна быть сделана приемлемо
низкой в зависимости от конкретного применения. Размер пространства,
которое противник должен перебрать, связан с объёмом присутствующей
ключевой «информации» в теоретико-информационном смысле [SHANNON]. Это
зависит от количества различных возможных секретных значений и
вероятности каждого значения следующим образом:
-----
\
Bits of information = \ - p * log ( p )
/ i 2 i
/
-----
где i изменяется от 1 до числа возможных секретных значений, а p с
нижним индексом i является вероятностью значения с номером i. (Поскольку
p с нижним индексом i меньше единицы, логарифм будет отрицательным, так
что каждый член суммы будет неотрицательным.)
Если имеются 2^n различных значений с равной вероятностью, то
присутствует n битов информации, и противнику пришлось бы испробовать в
среднем половину значений, или 2^(n-1), прежде чем угадать секретную
величину. Если вероятность различных значений неодинакова, то
присутствует меньше информации, и противнику в среднем потребуется
меньше попыток. В частности, любые значения, которые противник может
считать невозможными или маловероятными, могут быть первоначально
проигнорированы противником, который сначала будет перебирать более
вероятные значения.
Например, рассмотрим криптографическую систему, использующую 128-битные
ключи. Если эти ключи получены с помощью фиксированного генератора
псевдослучайных чисел, инициализированного 8-битным начальным значением,
то противнику нужно перебрать лишь 256 ключей (запустив генератор
псевдослучайных чисел с каждым возможным начальным значением), а не
2^128 ключей, как могло бы сначала показаться. В этих 128-битных ключах
содержится лишь 8 битов «информации».
Хотя приведённый выше анализ в среднем верен, в некоторых случаях он может вводить в заблуждение при криптографическом анализе, где действительно важен объём работы для противника. Например, предположим, что имеется генератор псевдослучайных чисел, генерирующий 128-битовые ключи, как в предыдущем абзаце, но половину времени он генерирует ноль, а в остальное время — случайную выборку из оставшихся 2^128 - 1 значений. Приведённое выше уравнение Шеннона говорит, что в одном из этих значений ключа имеется 64 бита информации, но противник, просто испробовав значение ноль, может взломать безопасность половины случаев использования, хотя и случайной половины. Поэтому для криптографических целей также полезно рассматривать другие меры, такие как минимальная энтропия, определяемая как
Min-entropy = - log ( maximum ( p ) )
i
где i имеет указанное выше значение. Используя это уравнение, мы получаем 1 бит минимальной энтропии для нашего нового гипотетического распределения, в отличие от 64 бит классической энтропии Шеннона.
Определён непрерывный спектр энтропий, иногда называемый энтропией Реньи, задаваемый параметром r. Здесь r = 1 — энтропия Шеннона, а r = infinity — минимальная энтропия. Когда r = zero, она представляет собой просто log (n), где n — число ненулевых вероятностей. Энтропия Реньи является невозрастающей функцией r, поэтому минимальная энтропия всегда является наиболее консервативной мерой энтропии и обычно наилучшей для криптографической оценки [LUBY].
Статистически проверенная случайность в традиционном смысле — НЕ то же самое, что непредсказуемость, необходимая для использования в целях безопасности.
Например, использование широко доступной постоянной последовательности, такой как таблица случайных чисел из CRC Standard Mathematical Tables, весьма слабо против противника. Противник, который узнает о ней или угадает её, может легко взломать всю безопасность, будущую и прошлую, основанную на этой последовательности [CRC]. В качестве другого примера: использование AES с постоянным ключом для шифрования последовательных целых чисел, таких как 1, 2, 3, ..., даст выходные данные, также обладающие превосходными статистическими свойствами случайности, но предсказуемые. С другой стороны, последовательные броски шестигранного кубика и кодирование получающихся значений в ASCII дали бы статистически некачественный вывод со значительной непредсказуемой составляющей. Поэтому обратите внимание: прохождение или непрохождение статистических тестов не показывает, является ли нечто непредсказуемым или предсказуемым.
3. Источники энтропии
Источники энтропии, как правило, сильно зависят от реализации. После сбора достаточной энтропии её можно использовать в качестве затравки для получения требуемого количества криптографически стойкой псевдослучайности, как описано в разделах 6 и 7, после устранения смещения или смешивания по необходимости, как описано в разделах 4 и 5.
Есть ли надежда на подлинную, стойкую, переносимую случайность в будущем? Возможно. Всё, что необходимо, — физический источник непредсказуемых чисел.
Тепловой шум (в интегральных схемах иногда называемый шумом Джонсона), либо источник радиоактивного распада, либо быстрый свободно работающий генератор колебаний непосредственно решили бы эту задачу [GIFFORD]. Это тривиальное количество аппаратуры, и её легко можно было бы включить в качестве стандартной части архитектуры компьютерной системы. Пригодно большинство устройств аудио- (или видео-) ввода [TURBID]. Кроме того, любая система с вращающимся диском либо кольцевым генератором и стабильным (кварцевым) источником времени или аналогичным устройством имеет достаточный источник случайности ([DAVIS] и раздел 3.3). Всё, что необходимо, — общее понимание среди производителей компьютеров, что это небольшое дополнительное аппаратное обеспечение и программное обеспечение для доступа к нему необходимы и полезны.
ANSI X9 в настоящее время разрабатывает стандарт, включающий часть, посвящённую источникам энтропии. См. часть 2 [X9.82].
3.1. Требуемый объём
Какой объём непредсказуемости необходим? Возможно ли выразить требование количественно, скажем, в числе случайных битов в секунду?
Ответ: требуется не очень много. Для AES ключ может иметь размер 128 бит, и, как показано на примере в разделе 8, даже системе с наивысшим уровнем безопасности, вероятно, не потребуется стойкий ключевой материал объёмом намного более 200 бит. Если необходима серия ключей, их можно сгенерировать из стойкой случайной затравки (начального значения), используя криптографически стойкую последовательность, как объяснено в разделе 6.2. Нескольких сотен случайных битов, сгенерированных при запуске или раз в день, достаточно, если применяются такие методы. Даже если случайные биты генерируются со скоростью лишь один в секунду и невозможно перекрыть процесс генерации, в большинстве приложений с высокой безопасностью должно быть приемлемо изредка ждать 200 секунд.
Эти числа тривиально достижимы. Их можно было бы получить, если человек многократно подбрасывал бы монету, и почти любой процесс на основе аппаратного обеспечения, вероятно, будет намного быстрее.
3.2. Существующее аппаратное обеспечение можно использовать для получения случайности
Как описано ниже, многие компьютеры оснащены аппаратным обеспечением, которое при осторожном использовании может применяться для генерации подлинно случайных величин.
3.2.1. Использование существующего звукового/видеоввода
Многие компьютеры построены с входами, которые оцифровывают некоторый аналоговый источник реального мира, такой как звук с микрофона или видеовход с камеры. «Вход» от звукового оцифровщика, к которому не подключён источник, либо от камеры с надетой крышкой объектива, по существу является тепловым шумом. Если система имеет достаточное усиление, чтобы обнаружить что-либо, такой вход может давать случайные биты достаточно высокого качества. Этот метод чрезвычайно зависит от аппаратной реализации.
Например, в некоторых системах на основе UNIX можно читать из устройства /dev/audio, когда к гнезду микрофона ничего не подключено либо когда микрофон принимает только фоновый шум низкого уровня. Такие данные по существу являются случайным шумом, хотя им не следует доверять без некоторой проверки на случай отказа аппаратуры, и потребуется устранить их смещение.
Сочетая этот подход со сжатием для устранения смещения (см. раздел 4), можно сгенерировать огромное количество случайных данных среднего качества с помощью командной строки в стиле UNIX:
cat /dev/audio | compress - >random-bits-file
Подробное исследование источника случайности такого типа приведено в [TURBID].
3.2.2. Использование существующих дисковых накопителей
Дисковые накопители имеют небольшие случайные колебания скорости вращения вследствие хаотической турбулентности воздуха [DAVIS, Jakobsson]. Добавление низкоуровневого инструментирования времени позиционирования головок диска даёт ряд измерений, содержащих эту случайность. Такие данные обычно сильно коррелированы, поэтому необходима значительная обработка, как описано ниже в разделе 5.2. Тем не менее эксперименты десятилетней давности показали, что при такой обработке даже медленные дисковые накопители на более медленных компьютерах того времени могли легко производить 100 бит в минуту или более превосходных случайных данных.
Каждое увеличение скорости процессора, увеличивающее разрешение, с которым можно измерять время движения диска, либо увеличивающее частоту позиционирований головок диска, повышает скорость генерации случайных битов, возможную при использовании этой техники. На момент написания данной статьи и при современном аппаратном обеспечении более типичная скорость производства случайных битов составляла бы свыше
10 000 бит в секунду. Эта техника используется в генераторах случайных чисел, включённых во многие библиотеки операционных систем.
Примечание: включение кэш-памяти в контроллеры дисков мало влияет на эту технику, если очень короткие времена позиционирования, представляющие попадания в кэш, просто игнорируются.
3.3. Источники на кольцевых генераторах
Если проектируется интегральная схема или выполняется программирование на месте, нечётное число вентилей может быть соединено последовательно для создания свободно работающего кольцевого генератора. Посредством выборки точки в кольце с фиксированной частотой (например, определяемой стабильным кварцевым генератором) некоторое количество энтропии можно извлечь вследствие вариаций времени работы свободно работающего генератора. Можно увеличить скорость получения энтропии, выполняя XOR над выборочными значениями от нескольких кольцевых генераторов с взаимно простыми длинами. Иногда рекомендуется использовать нечётное число колец, чтобы даже если кольца каким-либо образом синхронно зафиксируются друг с другом, всё ещё происходили переходы выборочных битов. Другим возможным источником для выборки является выход шумящего диода.
Выбранные биты из таких источников потребуется существенно устранять от смещения, как необходимо делать с моментами вращения диска (см. раздел 4). Для определения количества производимой энтропии в зависимости от конкретной конструкции потребовалось бы инженерное исследование. В любом случае это могут быть хорошие источники, стоимость которых по современным меркам составляет тривиальное количество аппаратного обеспечения.
В качестве примера IEEE 802.11i предлагает приведённую ниже схему при уделении в конструкции должного внимания изоляции колец друг от друга и от тактируемых схем во избежание нежелательной синхронизации и т. п., а также при обширной последующей обработке [IEEE_802.11i].
|\ |\ |\
+-->| >0-->| >0-- 19 total --| >0--+-------+
| |/ |/ |/ | |
| | |
+----------------------------------+ V
+-----+
|\ |\ |\ | | output
+-->| >0-->| >0-- 23 total --| >0--+--->| XOR |------>
| |/ |/ |/ | | |
| | +-----+
+----------------------------------+ ^ ^
| |
|\ |\ |\ | |
+-->| >0-->| >0-- 29 total --| >0--+------+ |
| |/ |/ |/ | |
| | |
+----------------------------------+ |
|
Other randomness, if available ---------+
3.4. Проблемы с часами и серийными номерами
Компьютерные часы и аналогичные значения операционной системы или аппаратного обеспечения дают существенно меньше реальных битов непредсказуемости, чем может показаться из их спецификаций.
На часах многочисленных систем проводились тесты, и было обнаружено, что их поведение может сильно различаться и быть неожиданным. Одна версия операционной системы, работающая на одном наборе аппаратного обеспечения, может фактически обеспечивать, скажем, микросекундное разрешение часов, тогда как иная конфигурация «той же» системы может всегда предоставлять одинаковые младшие биты и считать только старшие биты со значительно меньшим разрешением. Это означает, что последовательные считывания часов могут давать идентичные значения, даже если прошло достаточно времени, чтобы значение «должно было» измениться исходя из номинального разрешения часов. Также встречаются случаи, когда частое считывание часов может давать искусственные последовательные значения из-за дополнительного кода, который проверяет, не изменились ли часы между двумя считываниями, и увеличивает их на единицу! Разработка переносимого прикладного кода для генерации непредсказуемых чисел на основе таких системных часов особенно сложна, поскольку разработчик системы не всегда знает свойства системных часов.
Использование аппаратного серийного номера (такого как Ethernet MAC-адрес) также может давать меньше битов уникальности, чем можно было бы предположить. Такие величины обычно имеют сильно структурированный вид, а подполям может быть доступен только ограниченный диапазон возможных значений, либо значения могут быть легко угадываемы на основе приблизительной даты изготовления или других данных.
Например, вероятно, что компания, производящая как компьютеры, так и Ethernet-адаптеры, будет, по крайней мере внутри компании, использовать собственные адаптеры, что существенно ограничивает диапазон встроенных адресов.
Проблемы, подобные описанным выше, затрудняют создание кода для генерации непредсказуемых величин, если этот код предполагается переносить между различными компьютерными платформами и системами.
3.5. Время и значения внешних событий
Можно измерять время и содержимое перемещений мыши, нажатий клавиш и аналогичных пользовательских событий. Это разумный источник неугадываемых данных, с некоторыми оговорками. На некоторых машинах ввод, такой как нажатия клавиш, буферизуется. Хотя интервалы между нажатиями клавиш пользователем могут иметь достаточную вариативность и непредсказуемость, может не существовать простого способа получить доступ к этой вариативности. Другая проблема заключается в том, что стандартного метода выборки временных деталей не существует. Это затрудняет использование этой техники для создания стандартного программного обеспечения, предназначенного для распространения на широком диапазоне машин.
Количество перемещений мыши и сами нажатия клавиш обычно проще получить, чем временные характеристики, но они могут давать меньшую непредсказуемость, поскольку пользователь может предоставлять сильно повторяющийся ввод.
Другие внешние события, такие как время прибытия и длины сетевых
пакетов, также могут использоваться, но только с большой осторожностью. В
частности, необходимо тщательно учитывать возможность манипулирования
противником такими измерениями сетевого трафика и отсутствие истории при
запуске системы. Если этот вход подвержен манипулированию, ему нельзя
доверять как источнику энтропии.
В принципе, может использоваться почти любой внешний датчик, например
приём необработанного радиосигнала или измерение температуры на
соответствующим образом оснащённых компьютерах. Однако в каждом случае
необходимо тщательно рассмотреть, насколько эти данные подвержены
манипулированию противником и сколько энтропии они фактически могут
предоставить.
Описанные выше методы весьма эффективны против атакующих, не имеющих
доступа к измеряемым величинам. Например, эти методы были бы эффективны
против офлайновых атакующих, не имевших доступа к чьему-либо окружению и
пытавшихся постфактум взломать чьё-либо случайное начальное значение.
Во всех случаях чем точнее можно измерить время или значение внешнего
датчика, тем быстрее можно генерировать биты.
3.6. Неаппаратные источники случайности
Наилучшим источником входной энтропии был бы аппаратный источник
случайности, такой как кольцевые генераторы, временные характеристики
работы дискового накопителя, тепловой шум или радиоактивный распад. Однако,
если ничего из этого недоступно, существуют другие возможности. К ним
относятся системные часы, системные буферы или буферы ввода-вывода,
серийные номера или адреса пользователя/системы/оборудования/сети и их
временные характеристики, а также пользовательский ввод. К сожалению,
каждый из этих источников при некоторых обстоятельствах может выдавать
очень ограниченные или предсказуемые значения.
Некоторые из перечисленных выше источников были бы достаточно сильными в
многопользовательских системах, где каждый пользователь системы, по сути,
является источником случайности. Однако в небольшой однопользовательской
или встроенной системе, особенно при запуске, противник мог бы собрать
похожую конфигурацию. Это могло бы предоставить противнику входные данные
процесса смешивания, достаточно коррелированные с использованными
первоначально, чтобы сделать полный перебор практически осуществимым.
Рекомендуется использовать несколько случайных входов с сильной функцией
смешивания; это может преодолеть слабость любого конкретного входа.
Временные характеристики и содержимое запрошенных «случайных» нажатий
клавиш пользователем могут давать сотни случайных битов, но необходимо
делать консервативные предположения. Например, одним достаточно
консервативным предположением было бы то, что интервал между нажатиями
клавиш предоставляет не более нескольких битов случайности, но только когда
этот интервал уникален в последовательности интервалов до данного момента.
Аналогичным предположением было бы то, что код клавиши предоставляет
несколько битов случайности, но только когда этот код уникален в
последовательности. Таким образом, считалось бы, что интервал или код
клавиши, дублирующий предыдущее значение, не предоставляет дополнительной
случайности. Результаты смешивания этих временных характеристик с
введёнными символами могли бы далее комбинироваться со значениями часов и
другими входами.
Эта стратегия может сделать практически осуществимым переносимый код для
получения хороших случайных чисел в целях безопасности, даже если некоторые
из входов очень слабы на некоторых целевых системах. Однако она всё ещё
может не выдержать атаки высокого уровня на небольшие, однопользовательские
или встроенные системы, особенно если противник когда-либо имел возможность
наблюдать процесс генерации в прошлом. Аппаратный источник случайности всё
ещё предпочтителен.
4. Устранение смещения
Существует ли какое-либо специальное требование к форме распределения
величин, собранных для энтропии, чтобы получать случайные числа? Хорошая
новость состоит в том, что распределение не обязано быть равномерным. Чтобы
установить границы характеристик, требуется лишь консервативная оценка того,
насколько оно неравномерно. Ниже приведены простые методы устранения
смещения из потока битов, а более сильные криптографические методы описаны
в разделе 5.2.
4.1. Использование чётности потока для устранения смещения
В качестве простого, но не особенно практичного примера рассмотрим взятие
достаточно длинной строки битов и отображение строки в «ноль» или «единицу».
Отображение не даст совершенно равномерного распределения, но оно может
быть настолько близким, насколько требуется. Одно отображение, служащее
этой цели, — взять чётность строки. Его преимущества заключаются в том, что
оно устойчиво при всех степенях смещения вплоть до оценённого максимального
смещения и что его тривиально реализовать аппаратно.
Следующий анализ определяет количество битов, которое необходимо выбрать:
Предположим, что отношение единиц к нулям равно ( 0.5 + E ) к
( 0.5 - E ), где E находится между 0 и 0.5 и является мерой
«эксцентриситета» распределения. Рассмотрим распределение функции чётности
для N выборок битов. Соответствующие вероятности того, что чётность будет
единицей или нулём, будут суммой нечётных или чётных членов в биномиальном
разложении (p + q)^N, где p = 0.5 + E — вероятность единицы, а q =
0.5 - E — вероятность нуля.
Эти суммы можно легко вычислить как
N N
1/2 * ( ( p + q ) + ( p - q ) )
и
N N
1/2 * ( ( p + q ) - ( p - q ) ).
(Какая формула соответствует вероятности того, что чётность будет равна
1, зависит от того, является ли N нечётным или чётным.)
Поскольку p + q = 1 и p - q = 2E, эти выражения сводятся к
N
1/2 * [1 + (2E) ]
и
N
1/2 * [1 - (2E) ].
Ни одно из них никогда не будет в точности равно 0.5, если только E не
равно нулю, но мы можем сделать их сколь угодно близкими к 0.5. Например,
если мы хотим, чтобы вероятности находились в пределах некоторой дельты d
от 0.5, то
N
( 0.5 + ( 0.5 * (2E) ) ) < 0.5 + d.
Решая относительно N, получаем N > log(2d)/log(2E). (Обратите внимание, что
2E меньше 1, поэтому его логарифм отрицателен. Деление на отрицательное
число меняет направление неравенства.)
Следующая таблица показывает длину N строки, которую необходимо выбрать
для различных степеней смещения, чтобы приблизиться к распределению 50/50
с точностью до 0.001.
+---------+--------+-------+
| Prob(1) | E | N |
+---------+--------+-------+
| 0.5 | 0.00 | 1 |
| 0.6 | 0.10 | 4 |
| 0.7 | 0.20 | 7 |
| 0.8 | 0.30 | 13 |
| 0.9 | 0.40 | 28 |
| 0.95 | 0.45 | 59 |
| 0.99 | 0.49 | 308 |
+---------+--------+-------+
Последняя запись показывает, что, даже если распределение на 99% смещено в
пользу единиц, чётность строки из 308 выборок будет находиться в пределах
0.001 от распределения 50/50. Но, как мы увидим в разделе 5.2, существуют
гораздо более сильные методы, извлекающие больше доступной энтропии.
4.2. Использование отображений переходов для устранения смещения
Другой метод, первоначально предложенный фон Нейманом [VON_NEUMANN],
заключается в рассмотрении потока битов как последовательности
неперекрывающихся пар. Затем можно было бы отбрасывать все найденные пары
00 или 11, интерпретировать 01 как 0, а 10 как 1. Предположим, что
вероятность 1 равна 0.5+E, а вероятность 0 равна 0.5-E, где E —
эксцентриситет источника, описанный в предыдущем разделе. Тогда
вероятность каждой пары показана в следующей таблице:
+------+-----------------------------------------+
| пара | вероятность |
+------+-----------------------------------------+
| 00 | (0.5 - E)^2 = 0.25 - E + E^2 |
| 01 | (0.5 - E)*(0.5 + E) = 0.25 - E^2 |
| 10 | (0.5 + E)*(0.5 - E) = 0.25 - E^2 |
| 11 | (0.5 + E)^2 = 0.25 + E + E^2 |
+------+-----------------------------------------+
Этот метод полностью устранит любое смещение, но требует неопределённого
числа входных битов для любого конкретного желаемого числа выходных битов.
Вероятность отбрасывания любой конкретной пары равна 0.5 + 2E^2, поэтому
ожидаемое количество входных битов для получения X выходных битов равно
X/(0.25 - E^2).
Этот метод предполагает, что биты поступают из потока, в котором каждый
бит имеет такую же вероятность быть 0 или 1, как и любой другой бит в
потоке, и что биты некоррелированы, то есть что биты происходят из
идентичных независимых распределений. Например, если чередующиеся биты
поступают из двух коррелированных источников, приведённый выше анализ
перестаёт работать.
Описанный выше метод также даёт ещё одну иллюстрацию того, как простой
статистический анализ может ввести в заблуждение, если постоянно не
следить за шаблонами, которые могли бы быть использованы противником. Если
бы алгоритм был немного неверно понят так, что использовались бы
перекрывающиеся пары последовательных битов вместо неперекрывающихся пар,
приведённый статистический анализ был бы тем же. Однако вместо выдачи
несмещённой, некоррелированной последовательности случайных 1 и 0 он
создавал бы полностью предсказуемую последовательность строго
чередующихся 1 и 0.
4.3. Использование FFT для устранения смещения
Когда данные реального мира состоят из сильно коррелированных битов, они
всё ещё могут содержать полезные объёмы энтропии. Эта энтропия может быть
извлечена различными преобразованиями, наиболее мощные из которых описаны
ниже, в разделе 5.2.
Использование преобразования Фурье данных или его оптимизированного
варианта, FFT, представляет интерес главным образом по теоретическим
причинам. Можно показать, что этот метод отбросит сильные корреляции. Если
обрабатывается достаточно данных и если оставшиеся корреляции затухают,
могут быть получены спектральные линии, приближающиеся к статистической
независимости и нормально распределённой случайности [BRILLINGER].
4.4. Использование сжатия для устранения смещения
Обратимые методы сжатия также предоставляют грубый метод устранения
смещения из смещённого потока битов. Это напрямую следует из определения
обратимого сжатия и формулы раздела 2 для количества информации в
последовательности. Поскольку сжатие обратимо, в более коротком выходе
должно присутствовать то же количество информации, что присутствовало в
более длинном входе. Согласно уравнению информации Шеннона, это возможно
только если в среднем вероятности различных более коротких
последовательностей распределены более равномерно, чем вероятности более
длинных последовательностей. Следовательно, более короткие
последовательности должны иметь устранённое смещение относительно входа.
Однако многие методы сжатия добавляют несколько предсказуемую преамбулу к
своему выходному потоку и могут периодически вставлять в свой выход
подобную последовательность либо иным образом вносить собственные тонкие
шаблоны. По сравнению с методами, описанными в разделе 5.2, их следует
считать лишь грубыми методами. Как минимум, следует пропускать начало
сжатой последовательности и использовать для приложений, требующих
приблизительно случайных битов, только более поздние биты.
5. Смешивание
Какова наилучшая общая стратегия получения неугадываемых случайных чисел
при отсутствии сильного, надёжного аппаратного источника энтропии? Она
состоит в получении входа от ряда некоррелированных источников и их
смешивании сильной функцией смешивания. Такая функция сохранит энтропию,
присутствующую в любом из источников, даже если другие объединяемые
величины окажутся фиксированными или легко угадываемыми (с низкой
энтропией). Этот подход может быть целесообразен даже при наличии хорошего
аппаратного источника, поскольку оборудование также может отказать. Однако
это следует сопоставлять с возможным увеличением вероятности общего отказа
из-за дополнительной сложности программного обеспечения.
После использования хороших источников, таких как некоторые из
перечисленных в разделе 3, и их смешивания, как описано в этом разделе,
получается сильное начальное значение. Затем оно может использоваться для
получения больших объёмов криптографически сильного материала, как описано
в разделах 6 и 7.
Сильная функция смешивания — это функция, которая объединяет входы и
создаёт выход, в котором каждый выходной бит является отличной сложной
нелинейной функцией всех входных битов. В среднем изменение любого
входного бита изменит примерно половину выходных битов. Но поскольку эта
зависимость сложна и нелинейна, не гарантируется, что какой-либо конкретный
выходной бит изменится при изменении какого-либо конкретного входного бита.
Рассмотрим задачу преобразования потока битов, смещённого в сторону 0 или
1 либо имеющего несколько предсказуемый шаблон, в более короткий поток,
который более случаен, как обсуждалось в разделе 4. Это просто ещё один
случай, когда желательна сильная функция смешивания, чтобы смешать входные
биты и получить меньшее число выходных битов. Метод, приведённый в разделе
4.1 и использующий чётность нескольких битов, является просто результатом
их последовательного применения XOR. Непосредственно ниже он рассматривается
как тривиальная функция смешивания. Использование более сильных функций
смешивания для извлечения большей доли случайности из потока смещённых
битов рассматривается в разделе 5.2. См. также [NASLUND].
5.1. Тривиальная функция смешивания
Для целей изложения опишем тривиальный пример для однобитовых
входных данных с использованием функции исключающего ИЛИ (XOR).
Эта функция эквивалентна сложению без переноса, как показано в
таблице ниже. Это вырожденный случай, в котором единственный
выходной бит всегда изменяется при изменении любого входного бита.
Но, несмотря на свою простоту, он даёт полезную иллюстрацию.
+-----------+-----------+----------+
| вход 1 | вход 2 | выход |
+-----------+-----------+----------+
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
+-----------+-----------+----------+
Если входы 1 и 2 некоррелированы и объединены таким способом, то
выход будет ещё лучшим (менее смещённым) случайным битом, чем
входы. Если принять «эксцентриситет» E, определённый выше в
разделе 4.1, то эксцентриситет выхода связан с эксцентриситетами
входов следующим образом:
E = 2 * E * E
output input 1 input 2
Поскольку E никогда не превышает 1/2, эксцентриситет всегда
улучшается, кроме случая, когда по меньшей мере один вход является
полностью смещённой константой. Это показано в следующей таблице,
где значения в верхней строке и левом столбце — два эксцентриситета
входов, а ячейки содержат эксцентриситет выхода:
+--------+--------+--------+--------+--------+--------+--------+
| E | 0.00 | 0.10 | 0.20 | 0.30 | 0.40 | 0.50 |
+--------+--------+--------+--------+--------+--------+--------+
| 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 |
| 0.10 | 0.00 | 0.02 | 0.04 | 0.06 | 0.08 | 0.10 |
| 0.20 | 0.00 | 0.04 | 0.08 | 0.12 | 0.16 | 0.20 |
| 0.30 | 0.00 | 0.06 | 0.12 | 0.18 | 0.24 | 0.30 |
| 0.40 | 0.00 | 0.08 | 0.16 | 0.24 | 0.32 | 0.40 |
| 0.50 | 0.00 | 0.10 | 0.20 | 0.30 | 0.40 | 0.50 |
+--------+--------+--------+--------+--------+--------+--------+
Однако обратите внимание, что приведённые выше расчёты предполагают,
что входы не коррелированы. Если бы входы были, скажем, чётностью
числа минут после полуночи на двух часах с точностью до нескольких
секунд, то каждый из них мог бы казаться случайным при выборке через
случайные интервалы, значительно превышающие минуту.
Однако, если бы они оба выбирались и объединялись с помощью XOR,
результат большую часть времени был бы нулём.
5.2. Более сильные функции смешивания
Advanced Encryption Standard (AES) правительства США [AES] является
примером сильной функции смешивания для многобитовых величин. Она
принимает до 384 битов входных данных (128 битов «данных» и 256
битов «ключа») и выдаёт 128 битов на выходе, каждый из которых
зависит от сложной нелинейной функции всех входных битов. Другие
функции шифрования с этой характеристикой, такие как [DES], также
можно использовать, рассматривая их как смешивающие все их входные
биты ключа и данных.
Ещё одно хорошее семейство функций смешивания — функции «дайджеста
сообщения» или хеширования, такие как стандарты Secure Hash
Standards правительства США [SHA*] и серия MD4, MD5 [MD4, MD5]. Все
эти функции принимают практически неограниченный объём входных
данных и выдают сравнительно короткий выход фиксированной длины,
смешивающий все входные биты. Серия MD* выдаёт 128 битов, SHA-1
выдаёт 160 битов, а другие функции SHA выдают до 512 битов.
Хотя функции дайджеста сообщения предназначены для переменного
объёма входных данных, AES и другие функции шифрования также можно
использовать для объединения любого числа входов. Если достаточно
128 битов выхода, входы можно упаковать в 128-битовую величину
данных и последовательные «ключи» AES, дополнив при необходимости
нулями; затем величина последовательно шифруется «ключами» с
использованием AES в режиме электронной кодовой книги (Electronic
Codebook Mode). В качестве альтернативы вход можно упаковать в один
128-битовый ключ и несколько блоков данных, а затем вычислить
CBC-MAC [MODES].
Следует использовать более сложное смешивание, если требуется более
128 битов выхода и желательно применить AES (но обратите внимание,
что получить больше битов «случайности», чем было введено, абсолютно
невозможно). Например, предположим, что входы упакованы в три
величины A, B и C. Можно использовать AES для шифрования A с B, а
затем с C в качестве ключей, чтобы получить первую часть выхода,
затем шифровать B с C, а затем с A для получения дополнительного
выхода и, при необходимости, шифровать C с A, а затем с B для ещё
большего выхода. Ещё больше выхода можно получить, изменив порядок
ключей, приведённый выше, на обратный. То же можно сделать с
хеш-функциями, хешируя различные подмножества входных данных или
разные копии входных данных с разными префиксами и/или суффиксами
для получения нескольких выходов.
В качестве примера использования сильной функции смешивания вновь
рассмотрим строку из 308 битов, каждый из которых смещён на 99 % к
нулю. Метод чётности, приведённый в разделе 4.1, сводит это к одному
биту с отклонением от равной вероятности нуля или единицы всего на
1/1000. Но при применении уравнения для информации, приведённого в
разделе 2, эта
смещённая последовательность из 308 битов содержит более 5 битов
информации. Таким образом, её хеширование с помощью SHA-1 и взятие
младших 5 битов результата дало бы 5 несмещённых случайных битов, а
не единственный бит, получаемый вычислением чётности строки. В
качестве альтернативы для некоторых приложений можно использовать
весь выход хеша, чтобы сохранить почти все более чем 5 битов энтропии
в 160-битовой величине.
5.3. Использование S-Boxes для смешивания
Многие современные функции блочного шифрования, включая DES и AES,
включают модули, известные как S-Boxes (блоки подстановки). Они
вырабатывают меньшее число выходов из большего числа входов через
сложную нелинейную функцию смешивания, которая концентрирует
ограниченную энтропию входов в выходе.
S-Boxes иногда включают bent-булевы функции (функции от чётного
числа битов, вырабатывающие один выходной бит с максимальной
нелинейностью). При рассмотрении выходов для всех пар входов,
различающихся в какой-либо конкретной битовой позиции, ровно
половина выходов различается. S-Box, в котором каждый выходной бит
вырабатывается bent-функцией так, что любая линейная комбинация этих
функций также является bent-функцией, называется «совершенным
S-Box».
S-boxes, а также различные повторные применения или каскады таких
блоков могут использоваться для смешивания [SBOX1, SBOX2].
5.4. Diffie-Hellman как функция смешивания
Экспоненциальный обмен ключами Diffie-Hellman — это метод, который
даёт общий секрет двум сторонам. Третьей стороне может быть
вычислительно неосуществимо определить этот секрет, даже если она
может наблюдать все сообщения между двумя взаимодействующими
сторонами. Этот общий секрет является смесью исходных величин,
сгенерированных каждой из сторон [D-H].
Если эти исходные величины случайны и некоррелированы, то общий
секрет объединяет их энтропию, но, разумеется, не может создать
больше случайности, чем размер созданного общего секрета.
Хотя это верно, если вычисление Diffie-Hellman выполняется
конфиденциально, противнику, который может наблюдать один из
открытых ключей и знает используемый модуль, достаточно перебрать
пространство другого секретного ключа, чтобы получить возможность
вычислить общий секрет [D-H]. Поэтому консервативно было бы лучше
считать, что публичный Diffie-Hellman создаёт величину, чья
угадываемость соответствует худшему из двух входов. По этой причине
и ввиду вычислительной затратности Diffie-Hellman его использование
в качестве функции смешивания не рекомендуется.
5.5. Использование функции смешивания для растягивания случайных битов
Хотя функции смешивания не обязательно выдавать столько же или
меньше выходных битов, чем имеется во входах, смешивание битов не
может «растянуть» величину случайной непредсказуемости, имеющейся во
входах. Таким образом, четыре входа по 32 бита каждый, в каждом из
которых имеется непредсказуемость величиной 12 битов (например,
4 096 равновероятных значений), не могут выдать более 48 битов
непредсказуемого выхода. Выход можно расширить до сотен или тысяч
битов, например смешивая с последовательными целыми числами, но
пространство поиска умного противника всё равно составляет 2^48
возможностей. Кроме того, смешивание в меньшее число битов, чем
подано на вход, будет иметь тенденцию усиливать случайность выхода.
Последняя таблица в разделе 5.1 показывает, что смешивание
случайного бита с постоянным битом посредством исключающего ИЛИ
выдаст случайный бит. Хотя это верно, это не даёт способа
«растянуть» один случайный бит в более чем один. Если, например,
случайный бит смешивается с 0, а затем с 1, это создаёт
двухбитовую последовательность, но она всегда будет либо 01, либо
10. Поскольку возможны только два значения, исходная случайность
по-прежнему составляет лишь один бит.
5.6. Другие факторы при выборе функции смешивания
Для локального использования AES имеет преимущества: он был широко
проверен на недостатки, достаточно эффективен в программном
обеспечении, широко документирован и реализован; аппаратные и
программные реализации доступны по всему миру, включая открытый
исходный код. Семейство SHA* изучалось несколько меньше и обычно
требует больше циклов CPU, чем AES, но нет оснований полагать, что
оно имеет недостатки. И SHA*, и MD5 были выведены из более раннего
алгоритма MD4. Для всех них доступен исходный код [SHA*, MD4, MD5].
В MD4 и MD5 были обнаружены некоторые признаки слабости. В
частности, MD4 имеет лишь три раунда, и существует несколько
независимых взломов первых двух или последних двух раундов. Кроме
того, в выходе MD5 были обнаружены некоторые коллизии.
AES был выбран в ходе надёжного, открытого и международного
процесса. За него и SHA* поручилось Агентство национальной
безопасности США (NSA) на основании критериев, которые по большей
части остаются секретными, как ранее поручилось за DES. Хотя это
стало причиной многочисленных спекуляций и сомнений, исследование
DES за прошедшие годы показало, что участие NSA в изменениях его
конструкции, первоначально разработанной IBM, было главным образом
направлено на её усиление. Не было объявлено об обнаружении в DES
скрытой или особой слабости. Вероятно, изменения NSA в MD4 для
создания алгоритмов SHA аналогично усилили эти алгоритмы, возможно,
против угроз, ещё не известных публичному криптографическому
сообществу.
Когда длины входов непредсказуемы, хеш-алгоритмы удобнее в
использовании, чем алгоритмы блочного шифрования, поскольку они
обычно предназначены для приёма входов переменной длины. Алгоритмы
блочного шифрования обычно требуют дополнительного алгоритма
дополнения для обработки входов, которые не кратны точно размеру
блока.
На момент подготовки этого документа авторам не известно о каких-либо
патентных притязаниях на основные алгоритмы AES, DES, SHA*, MD4 и
MD5, кроме патентов, для которых всему миру была предоставлена
безотзывная безвозмездная лицензия. Разумеется, могут существовать
существенные патенты, о которых авторам неизвестно, или патенты на
реализации либо применения, а также иные относящиеся к делу патенты,
выданные или подлежащие выдаче.
6. Генераторы псевдослучайных чисел
Когда начальное значение имеет достаточную энтропию, полученную из
входных данных, как описано в разделе 3, и, возможно, устранённую от
смещения и смешанную, как описано в разделах 4 и 5, это начальное
значение можно алгоритмически расширить для создания большого числа
криптографически стойких случайных величин. Такие алгоритмы не
зависят от платформы и могут работать одинаковым образом на любом
компьютере. Чтобы алгоритмы были безопасны, их входные данные и
внутренняя работа должны быть защищены от наблюдения противником.
Разработка таких алгоритмов генерации псевдослучайных чисел, как и
разработка алгоритмов симметричного шифрования, не является задачей
для любителей. В приведённом ниже разделе 6.1 перечислен ряд плохих
идей, использованных неудачными алгоритмами. Чтобы узнать, что
работает, пропустите раздел 6.1 и просто прочитайте оставшуюся часть
этого раздела и раздел 7, где описаны некоторые стандартные
алгоритмы генерации псевдослучайных чисел и приведены ссылки на них.
См. раздел 7 и часть 3 [X9.82].
6.1. Некоторые плохие идеи
В подразделах ниже описан ряд идей, которые могут казаться разумными,
но приводят к небезопасной генерации псевдослучайных чисел.
6.1.1. Ошибочность сложных манипуляций
Один из подходов, который может создавать обманчивое впечатление
непредсказуемости, состоит в том, чтобы взять очень сложный алгоритм (или
превосходный традиционный генератор псевдослучайных чисел с хорошими
статистическими свойствами) и вычислить криптографический ключ, начиная с
ограниченных данных, таких как значение системных часов компьютера в
качестве начального значения. Злоумышленники, которые приблизительно знали,
когда генератор был запущен, имели бы относительно небольшое число значений
начального значения для проверки, поскольку они знали бы вероятные значения
системных часов. Большие количества псевдо-
случайных битов могли бы быть сгенерированы, но пространство поиска,
которое злоумышленнику пришлось бы проверить, могло бы быть довольно
небольшим.
Таким образом, очень сильная или сложная обработка данных не поможет, если
злоумышленник может узнать, в чём состоит эта обработка, и если в исходном
начальном значении недостаточно энтропии. Как правило, они могут
использовать ограниченное число результатов, вытекающих из ограниченного
числа значений начального значения, чтобы преодолеть защиту.
Другая серьёзная стратегическая ошибка состоит в предположении, что очень
сложный алгоритм генерации псевдослучайных чисел создаст сильные случайные
числа, когда за этим алгоритмом не стоит никакой теории или анализа. Ближе к
началу главы 3 в [KNUTH] имеется a превосходный пример этой ошибки, где автор
описывает сложный алгоритм. Предполагалось, что программа на машинном языке,
соответствующая алгоритму, будет настолько сложной, что человек, пытающийся
прочитать код без комментариев, не поймёт, что делает программа. К
сожалению, фактическое использование этого алгоритма показало, что в одном
случае он почти немедленно сходился к одному повторяющемуся значению, а в
другом случае — к малому циклу значений.
Сложная обработка не только не помогает при ограниченном диапазоне
начальных значений, но и слепо выбранная сложная обработка может уничтожить
энтропию хорошего начального значения!
6.1.2. Ошибочность выбора из большой базы данных
Другой подход, который может создавать обманчивое впечатление
непредсказуемости, состоит в случайном выборе величины из базы данных и
предположении, что её стойкость связана с общим числом битов в базе данных.
Например, типичные серверы USENET обрабатывают много мегабайт информации в
день [USENET_1, USENET_2]. Предположим, что случайная величина была выбрана
путём извлечения 32 байтов данных из случайной начальной точки в этих
данных. Это не даёт 32*8 = 256 битов неугадываемости. Даже если большая
часть данных представляет собой человеческий язык, содержащий не более 2
или 3 битов информации на байт, это не даёт 32*2 = 64 битов
неугадываемости. Для злоумышленника, имеющего доступ к той же базе данных
Usenet, неугадываемость основывается только на начальной точке выбора. Это,
возможно, чуть более пары десятков битов неугадываемости.
Тот же аргумент применим к выбору последовательностей из данных общедоступной
записи CD/DVD или любой другой большой общедоступной базы данных. Если
злоумышленник имеет доступ к той же базе данных, этот шаг «выбор из большого
объёма данных» даёт мало. Однако если выбор может быть сделан из данных, к
которым злоумышленник не имеет доступа, таких как системные буферы в
активной многопользовательской системе, это может помочь.
6.1.3. Традиционные псевдослучайные последовательности
В этом разделе говорится о традиционных источниках детерминированных или
«псевдослучайных» чисел. Обычно они начинаются с величины «начального
значения» и используют простые числовые или логические операции для
получения последовательности значений. Обратите внимание, что ни один из
методов, обсуждаемых в этом разделе, не подходит для криптографического
использования. Они представлены для общей информации.
В [KNUTH] содержится классическое изложение псевдослучайных чисел.
Упоминаемые им применения — моделирование природных явлений, выборка,
численный анализ, тестирование компьютерных программ, принятие решений и
игры. Ни одно из них не имеет тех же характеристик, что и виды применений в
области безопасности, о которых мы говорим. Только в последних двух мог бы
существовать злоумышленник, пытающийся найти случайную величину. Однако в
этих случаях злоумышленник обычно имеет лишь одну возможность использовать
угаданное значение. При угадывании паролей или попытке взломать схему
шифрования злоумышленник обычно имеет много, возможно неограниченно много,
возможностей угадать правильное значение. Иногда злоумышленник может
сохранить подлежащее взлому сообщение и атаковать его повторно. Следует также
предполагать, что злоумышленники are also be получают помощь от компьютера.
Для проверки «случайности» чисел Кнут предлагает различные показатели,
включая статистические и спектральные. Эти тесты проверяют такие вещи, как
автокорреляция между различными частями «случайной» последовательности или
распределение её значений. Однако этим тестам могла бы удовлетворять
постоянная сохранённая случайная последовательность, такая как «случайная»
последовательность, напечатанная в CRC Standard Mathematical Tables [CRC].
Несмотря на соответствие всем тестам, предложенным Кнутом, эта
последовательность непригодна для криптографического us, так как следует
предполагать, что злоумышленники имеют копии всех широко публикуемых
«случайных» последовательностей и способны распознать источник и
предсказать будущие значения.
Типичным методом генерации псевдослучайных чисел является линейный
конгруэнтный генератор псевдослучайных чисел. Этот метод использует
модульную арифметику, в которой значение с номером N+1 вычисляется из
значения с номером N по формуле
V = ( V * a + b )(Mod c)
N+1 N
Приведённый выше метод тесно связан с генераторами псевдослучайных чисел на
линейных регистрах сдвига, которые хорошо изучены криптографически [SHIFT*].
В таких генераторах биты вводятся с одного конца регистра сдвига как
исключающее ИЛИ (двоичная сумма без переноса) битов из выбранных
фиксированных отводов регистра. Например, рассмотрим следующее:
+----+ +----+ +----+ +----+
| B | <-- | B | <-- | B | <-- . . . . . . <-- | B | <-+
| 0 | | 1 | | 2 | | n | |
+----+ +----+ +----+ +----+ |
| | | |
| | V +-----+
| V +----------------> | |
V +-----------------------------> | XOR |
+---------------------------------------------------> | |
+-----+
V = ( ( V * 2 ) + B XOR B ... )(Mod 2^n)
N+1 N 0 2
Качество традиционных алгоритмов генераторов псевдослучайных чисел измеряется
статистическими тестами таких последовательностей. Тщательно выбранные
значения a, b, c и начального V либо тщательно выбранное размещение отвода
регистра сдвига в приведённом выше простом процессе могут давать превосходную
статистику.
Эти последовательности могут быть достаточны при моделировании (экспериментах
Монте-Карло), пока последовательность ортогональна структуре исследуемого
пространства. Даже там тонкие закономерности могут вызывать проблемы.
Однако такие последовательности явно плохи для применения в приложениях
безопасности. Они полностью предсказуемы, если известно начальное состояние.
В зависимости от формы генератора псевдослучайных чисел последовательность
может быть определима по наблюдению короткого участка последовательности
[SCHNEIER, STERN]. Например, с приведёнными выше генераторами можно
определить V(n+1), зная V(n). Фактически было показано, что при этих
методах, даже если раскрывается только один бит псевдослучайных значений,
начальное значение может быть определено по коротким последовательностям.
Были взломаны не только линейные конгруэнтные генераторы, но теперь известны
и методы взлома всех полиномиальных конгруэнтных генераторов [KRAWCZYK].
6.2. Криптографически сильные последовательности
В случаях, когда необходимо генерировать ряд случайных величин,
злоумышленник может узнать некоторые значения в последовательности. В общем
случае злоумышленники не должны иметь возможности предсказывать другие
значения по тем, которые им известны.
Правильный метод состоит в том, чтобы начать с сильного случайного начального
значения, выполнить из этого начального значения криптографически сильные
шаги [FERGUSON, SCHNEIER] и не раскрывать полное состояние генератора в
элементах последовательности. Если каждое значение в последовательности
может быть вычислено фиксированным
способом из предыдущего значения, то при компрометации любого значения могут
быть определены все будущие значения. Так было бы, например, если бы каждое
значение являлось постоянной функцией ранее использованных значений, даже
если бы функцией была очень сильная необратимая функция дайджеста сообщения.
(Обратите внимание, что если метод генерации последовательности значений
ключей достаточно быстр, его можно тривиально использовать как основу для
системы конфиденциальности. Если две стороны используют один и тот же метод
генерации последовательности и начинают с одного и того же материала
начального значения, они будут генерировать идентичные последовательности.
Их, например, можно было бы применять с XOR на одном конце к отправляемым
данным для их шифрования и с XOR к этим данным при получении для их
расшифрования благодаря обратимым свойствам операции XOR. Это обычно
называется простым поточным шифром.)
6.2.1. Последовательности OFB и CTR
Один из способов получить сильную последовательность — взять значение
начального значения и хешировать величины, получаемые конкатенацией
начального значения с последовательными целыми числами или аналогичными
величинами, а затем маскировать полученные значения, чтобы ограничить
объём состояния генератора, доступного злоумышленнику.
Также может быть возможно использовать алгоритм «шифрования» со случайным
ключом и значением начального значения для шифрования последовательных целых
чисел, как при шифровании в режиме счётчика (CTR). Альтернативно можно
подавать обратно всё выходное значение шифрования во входное значение,
подлежащее шифрованию на следующей итерации. Это частный пример режима
обратной связи по выходу (OFB) [MODES].
Ниже показан пример, в котором сдвиг и маскирование используются для
объединения части обратной связи по выходу с частью старого входа. Следует
избегать такого типа частичной обратной связи по причинам, описанным ниже.
+---------------+
| V |
| | n |--+
+--+------------+ |
| | +---------+
shift| +---> | | +-----+
+--+ | Encrypt | <--- | Key |
| +-------- | | +-----+
| | +---------+
V V
+------------+--+
| V | |
| n+1 |
+---------------+
Обратите внимание, что если используется сдвиг на единицу, это то же самое,
что и метод регистра сдвига, описанный в разделе 6.1.3, но с крайне важным
отличием: обратная связь определяется сложной нелинейной функцией всех
битов, а не простой линейной или полиномиальной комбинацией выходных данных
нескольких отводов битовых позиций.
Дональд У. Дейвис показал, что этот вид сдвинутой частичной обратной связи
по выходу существенно ослабляет алгоритм по сравнению с подачей всех
выходных битов обратно на вход. В частности, для DES повторное шифрование
полной 64-битной величины даст ожидаемое повторение примерно через 2^63
итерации. Обратная подача менее 64 (и более 0) битов даст ожидаемое
повторение между 2^31 и 2^32 итерациями!
Предсказание значений одной последовательности по другим, когда
последовательность была сгенерирована этими методами, эквивалентно взлому
криптосистемы или обращению «необратимого» хеширования при наличии только
частичной информации. Чем меньше информации раскрывается на каждой
итерации, тем труднее злоумышленнику будет предсказать последовательность.
Таким образом, лучше всего использовать только один бит из каждого значения.
Было показано, что в некоторых случаях это делает невозможным взлом системы,
даже когда криптографическая система обратима и могла бы быть взломана, если
бы каждое сгенерированное значение раскрывалось полностью.
6.2.2. Генератор последовательности Blum Blum Shub
В настоящее время генератор, имеющий самое сильное публичное доказательство
стойкости, называется генератором Blum Blum Shub, по именам его изобретателей
[BBS]. Он также очень прост и основан на квадратичных вычетах. Его
единственный недостаток состоит в том, что он вычислительно интенсивен по
сравнению с традиционными методами, приведёнными в разделе 6.1.3. Это не
является серьёзным недостатком, если он используется для умеренно нечастых
целей, таких как генерация сеансовых ключей.
Просто выберите два больших простых числа (скажем, p и q), каждое из которых
даёт остаток 3 при делении на 4. Пусть n = p * q. Затем выберите случайное
число x, взаимно простое с n. Тогда начальное значение генератора и метод
вычисления последующих значений имеют вид:
2
s = ( x )(Mod n)
0
2
s = ( s )(Mod n)
i+1 i
Следует соблюдать осторожность и использовать лишь несколько младших
битов каждого s. Всегда безопасно использовать только бит младшего
порядка. Если используется не более чем:
log ( log ( s ) )
2 2 i
битов младшего порядка, то предсказание каких-либо дополнительных битов
из последовательности, сгенерированной таким образом, доказуемо столь же
сложно, как факторизация n. Пока начальное x хранится в секрете, n при
желании можно сделать общедоступным.
Интересной характеристикой этого генератора является то, что любое из
значений s можно вычислить напрямую. В частности,
( (2^i) (Mod ((p-1)*(q-1)) ) )
s = ( s )(Mod n)
i 0
Это означает, что в приложениях, где таким способом генерируется много
ключей, нет необходимости сохранять их все. Каждый ключ можно
эффективно индексировать и восстановить по этому небольшому индексу, а
также начальному s и n.
6.3. Методы пула энтропии
Многие современные источники псевдослучайных чисел, такие как описанные
в разделах 7.1.2 и 7.1.3, используют метод поддержания «пула» битов и
предоставляют операции для сильного смешивания входных данных с некоторой
случайностью в пуле и извлечения псевдослучайных битов из пула. Это
проиллюстрировано на рисунке ниже.
+--------+ +------+ +---------+
--->| Mix In |--->| POOL |--->| Extract |--->
| Bits | | | | Bits |
+--------+ +------+ +---------+
^ V
| |
+-----------+
Биты, подаваемые в пул, могут поступать из любых различных источников
аппаратных средств, окружающей среды или пользовательского ввода,
рассмотренных выше. Также обычно сохранять состояние пула при выключении
системы и восстанавливать его при перезапуске, когда доступно стабильное
хранилище.
Необходимо позаботиться о том, чтобы в пул было добавлено достаточно
энтропии для поддержки требуемых конкретных вариантов использования
выходных данных. Аналогичные рекомендации см. в [RSA_BULL1].
7. Примеры и стандарты генерации случайности
В настоящее время существует несколько общедоступных стандартов и широко
развернутых примеров для генерации ключей или других криптографически
случайных величин. Некоторые, в разделе 7.1, включают источник энтропии.
Другие, описанные в разделе 7.2, предоставляют генератор сильной
последовательности псевдослучайных чисел, но предполагают ввод случайного
начального значения или ввод от источника энтропии.
7.1. Полные генераторы случайности
Ниже описаны три стандарта. Два более старых стандарта используют DES с
его ограничением размера блока и ключа в 64 бита, однако вместо него могла
бы быть подставлена любая столь же сильная или более сильная функция
смешивания [DES]. Третий — более современный и сильный стандарт,
основанный на SHA-1 [SHA*]. Наконец, описываются широко развернутые
современные генераторы случайных чисел UNIX и Windows.
7.1.1. Рекомендации Министерства обороны США по генерации паролей
Министерство обороны Соединенных Штатов имеет конкретные рекомендации по
генерации паролей [DoD]. Оно предлагает использовать американский
стандарт шифрования данных [DES] в режиме Output Feedback [MODES]
следующим образом:
Использовать вектор инициализации, определяемый по
системным часам,
идентификатору системы,
идентификатору пользователя и
дате и времени;
использовать ключ, определяемый по
регистрам системных прерываний,
регистрам состояния системы и
системным счетчикам; и
в качестве открытого текста использовать внешнюю случайно
сгенерированную 64-битную величину, такую как байты ASCII для
8 символов, введенных системным администратором.
Затем пароль можно вычислить из 64-битного «шифротекста», сгенерированного
DES в 64-битном режиме Output Feedback. Из этих 64 битов можно взять
столько битов, сколько нужно, и развернуть их в произносимое слово, фразу
или иной формат, если пароль должен запоминать человек.
7.1.2. Устройство /dev/random
Несколько версий операционной системы UNIX предоставляют генератор
случайных чисел, находящийся в ядре. Некоторые из этих генераторов
используют события, захватываемые ядром в ходе обычной работы системы.
Например, в некоторых версиях Linux генератор состоит из случайного пула
размером 512 байтов, представленного 128 словами по 4 байта каждое. Когда
происходит событие, например прерывание дискового накопителя, время
события складывается по XOR с пулом, а пул перемешивается посредством
примитивного многочлена степени 128. Сам пул рассматривается как
кольцевой буфер; новые данные складываются по XOR (после перемешивания
многочленом) по всему пулу.
Каждый вызов, добавляющий энтропию в пул, оценивает количество вероятной
истинной энтропии, содержащееся во входных данных. Сам пул содержит
накопитель, оценивающий суммарную энтропию всего пула.
Входные события поступают из нескольких источников, перечисленных ниже.
К сожалению, для серверных машин без операторов-людей первый и третий
недоступны, и в таком случае энтропия может добавляться медленно.
1. Прерывания клавиатуры. В пул добавляются время прерывания и код
сканирования. Тем самым фактически добавляется энтропия от оператора-
человека посредством измерения времени между нажатиями клавиш.
2. Завершение операций с диском и другие прерывания. В системе,
используемой человеком, вероятно, будет трудно предсказуемая картина
обращений к диску.
(Но не все драйверы дисков поддерживают захват этой временной
информации с точностью, достаточной для ее полезности.)
3. Движение мыши. Добавляются время и положение мыши.
Когда требуются случайные байты, пул хешируется с помощью SHA-1 [SHA*],
чтобы получить возвращаемые байты случайности. Если требуется больше
байтов, чем вывод SHA-1 (20 байтов), хешированный вывод перемешивается
обратно в пул и выполняется новое хеширование для получения следующих 20
байтов. По мере удаления байтов из пула оценка энтропии соответственно
уменьшается.
Чтобы обеспечить достаточно случайный пул при запуске системы, стандартные
сценарии запуска и завершения работы сохраняют пул в файл на диске при
завершении работы и считывают этот файл при запуске системы.
Существуют два экспортируемых пользователю интерфейса. /dev/random
возвращает байты из пула, но блокируется, когда оценка энтропии падает до
нуля. По мере добавления энтропии в пул из событий через /dev/random
становится доступно больше данных. Случайные данные, полученные от такого
устройства /dev/random, пригодны для генерации ключей долгосрочного
использования, если в пуле достаточно случайных битов либо они добавляются
за разумное время.
/dev/urandom работает как /dev/random; однако он предоставляет данные
даже тогда, когда оценка энтропии для случайного пула падает до нуля. Это
может быть достаточно для сеансовых ключей или других задач генерации
ключей, для которых блокировка в ожидании дополнительных случайных битов
неприемлема. Риск продолжения получения данных даже при малой оценке
энтропии пула состоит в том, что прошлые выходные данные могут быть
вычислимы по текущим выходным данным, при условии что атакующий может
обратить SHA-1. Учитывая, что SHA-1 разработан как необратимый, это
разумный риск.
Чтобы получить случайные числа в Linux, Solaris или других системах UNIX,
оснащенных кодом, описанным выше, приложению достаточно открыть либо
/dev/random, либо /dev/urandom и прочитать требуемое количество байтов.
(Устройство случайных чисел Linux было написано Theodore Ts'o. Оно было
в общих чертах основано на генераторе случайных чисел в PGP 2.X и PGP 3.0
(также известном как PGP 5.0).)
7.1.3. Windows CryptGenRandom
Рекомендация Microsoft пользователям широко развернутой операционной
системы Windows в целом состоит в использовании вызова генерации
псевдослучайных чисел CryptGenRandom с поставщиком криптографических услуг
CryptAPI. Он принимает дескриптор поставщика криптографических услуг
библиотеки, указатель на буфер, посредством которого вызывающая сторона
может предоставлять энтропию и в который возвращается сгенерированная
псевдослучайность, а также указание того, сколько октетов случайности
требуется.
Поставщик криптографических услуг Windows CryptAPI хранит переменную
состояния начального значения для каждого пользователя. При вызове
CryptGenRandom она объединяется с любой случайностью, предоставленной при
вызове, и с различными системными и пользовательскими данными, такими как
идентификатор процесса, идентификатор потока, системные часы, системное
время, системный счетчик, состояние памяти, свободные кластеры диска и
хешированный блок пользовательской среды. Все эти данные подаются в
SHA-1, а его вывод используется для инициализации потока ключей RC4. Этот
поток ключей используется для получения запрошенных псевдослучайных данных
и обновления переменной состояния начального значения пользователя.
Пользователям Windows ".NET", вероятно, будет проще использовать
интерфейс метода RNGCryptoServiceProvider.GetBytes.
Дополнительную информацию см. в [WSC].
7.2. Генераторы, предполагающие источник энтропии
Генераторы псевдослучайных чисел, описанные в следующих трех разделах,
все предполагают, что им предоставляется начальное значение с достаточной
энтропией. Затем они генерируют сильную последовательность (см. раздел
6.2) из этого начального значения.
7.2.1. Генерация псевдослучайных чисел X9.82
Комитет ANSI X9F1 находится на завершающих этапах создания стандарта для
генерации случайных чисел, охватывающего как генераторы истинной
случайности, так и генераторы псевдослучайных чисел. Он включает ряд
генераторов псевдослучайных чисел, основанных на хеш-функциях, один из
которых, вероятно, будет основан на конструкциях хеширования HMAC SHA
[RFC2104]. Черновая версия этого генератора описана ниже, с исключением
ряда необязательных возможностей [X9.82].
В подразделах ниже конструкция хеширования HMAC для простоты именуется
HMAC, но, разумеется, при конкретном использовании должна быть выбрана
определенная стандартная функция SHA. В общем случае, если сила
генерируемых псевдослучайных значений должна составлять N битов, выбранная
функция SHA должна генерировать N или более битов вывода, и потребуется
источник не менее N битов входной энтропии. Одна и та же хеш-функция
должна использоваться во всей экземпляризации этого генератора.
7.2.1.1. Обозначения
В следующих разделах используется приведенное ниже обозначение:
hash_length — размер вывода используемой базовой хеш-функции.
input_entropy — входная битовая строка, предоставляющая энтропию
генератору.
K — битовая строка размером hash_length, являющаяся частью состояния
генератора и обновляемая не менее одного раза при каждой генерации
случайных битов.
V — битовая строка размером hash_length, являющаяся частью состояния
генератора. Она обновляется при каждой генерации hash_length битов
вывода.
"|" обозначает конкатенацию.
7.2.1.2. Инициализация генератора
Установить V в байты, все биты которых равны нулю, за исключением того,
что бит младшего порядка каждого байта устанавливается в единицу.
Установить K в байты, все биты которых равны нулю, затем установить:
K = HMAC ( K, V | 0x00 | input_entropy )
V = HMAC ( K, V )
K = HMAC ( K, V | 0x01 | input_entropy )
V = HMAC ( K, V )
Примечание: Все алгоритмы SHA производят целое число байтов, поэтому
длины K и V будут целыми числами байтов.
7.2.1.3. Генерация случайных битов
Когда требуется вывод, просто установить:
V = HMAC ( K, V )
и использовать старшие биты из V. Если требуется больше битов, чем длина
V, установить "temp" в пустую битовую строку, а затем многократно
выполнять:
V = HMAC ( K, V )
temp = temp | V
прекращая выполнение, как только temp станет равна или длиннее числа
запрошенных случайных битов. Использовать запрошенное число старших битов
из temp. Определение алгоритма запрещает запрашивать более 2^35 битов.
После извлечения и сохранения выходных битов псевдослучайной
последовательности, как описано выше, перед возвратом также необходимо
выполнить еще два HMAC следующим образом:
K = HMAC ( K, V | 0x00 )
V = HMAC ( K, V )
7.2.2. Генерация ключей X9.17
Американский национальный институт стандартов определил следующий
метод генерации последовательности ключей [X9.17]:
s — начальное 64-битное начальное значение.
0
g — последовательность сгенерированных 64-битных ключевых величин.
n
k — случайный ключ, зарезервированный для генерации этой
последовательности ключей.
t — время, в которое генерируется ключ, с настолько высоким разрешением,
насколько доступно (до 64 битов).
DES ( K, Q ) — шифрование DES величины Q с ключом K.
Затем:
g = DES ( k, DES ( k, t ) XOR s )
n n
s = DES ( k, DES ( k, t ) XOR g )
n+1 n
Если g с индексом n предполагается использовать в качестве ключа DES, то
для такого использования каждый восьмой бит следует скорректировать для
обеспечения чётности, но при вычислении следующего s следует использовать
весь неизменённый 64-битный g.
7.2.3. Генерация псевдослучайных чисел DSS
Приложение 3 стандарта цифровой подписи NIST [DSS] предоставляет
метод получения последовательности псевдослучайных 160-битных величин
для использования в качестве закрытых ключей или подобных целей. Он был
изменён Уведомлением об изменении 1 [DSS_CN1], в результате чего получен
следующий алгоритм генерации псевдослучайных чисел общего назначения:
t = 0x 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0
XKEY = initial seed
0
For j = 0 to ...
XVAL = ( XKEY + optional user input ) (Mod 2^512)
j
X = G( t, XVAL )
j
XKEY = ( 1 + XKEY + X ) (Mod 2^512)
j+1 j j
Получаемые таким образом величины X образуют псевдослучайную
последовательность 160-битных значений. Для указанной выше функции «G»
могут использоваться две функции. Каждая из них выдаёт 160-битное значение
и принимает два аргумента: 160-битное значение и 512-битное значение.
Первая основана на SHA-1 и работает посредством задания пяти переменных
связывания, обозначаемых H с индексами в спецификации SHA-1, равными
первому аргументу, разделённому на пятые части. Затем шаги (a)–(e) раздела
7 спецификации NIST SHA-1 выполняются над вторым аргументом так, как если
бы он был 512-битным блоком данных. Значения переменных связывания после
этих шагов затем конкатенируются для получения вывода G [SHA*].
В качестве альтернативного метода NIST также определил альтернативную
функцию G, основанную на многократном применении функции шифрования DES
[DSS].
8. Примеры требуемой случайности
Ниже приведены два примера, показывающие приблизительные расчёты
случайности, необходимой для безопасности. Первый относится к паролям
умеренной защищённости, тогда как второй предполагает необходимость
криптографического ключа очень высокой защищённости.
Кроме того, [ORMAN] и [RSA_BULL13] содержат сведения о длинах открытых
ключей, которые следует использовать для обмена симметричными ключами.
8.1. Генерация паролей
Предположим, что пользовательские пароли изменяются раз в год и желательна
вероятность менее одной тысячной того, что противник сможет угадать пароль
для конкретной учётной записи. Далее предположим, что отправка пароля в
систему — единственный способ попытаться проверить пароль. Тогда решающий
вопрос состоит в том, как часто противник может испытывать варианты.
Предположим, что в систему внесены задержки, так что противник может
предпринимать не более одной попытки пароля каждые шесть секунд. Это 600
попыток в час, или около 15 000 в день, или около 5 000 000 попыток в год.
При наличии какого бы то ни было мониторинга маловероятно, что кто-то мог
бы действительно пробовать непрерывно в течение года. Даже если файлы
журналов проверяются лишь ежемесячно, 500 000 попыток более правдоподобны
до того, как атака будет замечена и будут предприняты меры по смене
паролей и усложнению дальнейших попыток подбора паролей.
Чтобы при 500 000 попытках вероятность угадать пароль составляла одну
тысячную, требуется пространство как минимум из 500 000 000 паролей, или
около 2^29. Следовательно, необходимо 29 бит случайности. Вероятно, этого
можно достичь, используя рекомендованные Министерством обороны США входные
данные для генерации паролей, поскольку в них имеется 8 входов, которые,
вероятно, в среднем содержат более 5 бит случайности каждый (см. раздел
7.1). Используя список из 1 000 слов, пароль можно выразить трёхсловной
фразой (1 000 000 000 возможностей). При использовании букв без учёта
регистра и цифр было бы достаточно шести символов ((26+10)^6 =
2,176,782,336 возможностей).
Для пароля более высокой защищённости требуемое число бит возрастает.
Чтобы уменьшить вероятность в 1 000 раз, требуется увеличить пространство
паролей на тот же множитель, что добавляет около 10 бит. Следовательно,
чтобы в приведённом выше сценарии вероятность угадывания пароля составляла
лишь одну миллионную, потребовались бы 39 бит случайности и пароль в виде
четырёхсловной фразы из списка в 1 000 слов либо восьми букв/цифр. Для
вероятности одна на 10^9 необходимы 49 бит случайности, что предполагает
пятисловную фразу либо пароль из десяти букв/цифр.
В реальной системе, разумеется, существуют и другие факторы. Например,
чем длиннее и труднее для запоминания пароли, тем вероятнее, что
пользователи будут bed записывать их, создавая дополнительный риск
компрометации.
8.2. Криптографический ключ очень высокой защищённости
Предположим, что для симметричного шифрования/расшифрования между двумя
сторонами необходим ключ очень высокой защищённости. Предположим также,
что противник может наблюдать коммуникации и знает используемый алгоритм.
В пространстве случайных возможностей противник может испытывать значения
ключа в надежде найти используемое. Далее предположим, что перебор ключей
грубой силой — лучшее, что может сделать противник.
8.2.1. Усилия на одну попытку ключа
Сколько усилий потребуется для испытания каждого ключа? Для приложений
очень высокой защищённости лучше предполагать низкое значение усилий. Даже
если очевидно, что для испытания одного ключа потребуются десятки тысяч
компьютерных циклов или больше, может существовать некоторая закономерность,
позволяющая проверять огромные блоки значений ключа с намного меньшими
усилиями на ключ. Поэтому, вероятно, лучше предполагать не более пары сотен
циклов на ключ. (Для этого нет ясной нижней границы, поскольку компьютеры
параллельно работают с несколькими битами и слабый алгоритм шифрования мог
бы позволить параллельно проверять много ключей или даже группы ключей.
Однако нам необходимо предположить некоторое значение и можно надеяться,
что для нашей гипотетической задачи высокой защищённости был выбран
достаточно сильный алгоритм.)
Если противник может задействовать высокопараллельный процессор или большую
сеть рабочих станций, 10^11 циклов в секунду, вероятно, является сегодня
минимальным предположением. Если заглянуть на несколько лет вперёд, должно
быть как минимум улучшение на порядок. Следовательно, разумно предполагать,
что в секунду можно проверить 10^10 ключей, или 3.6*10^12 в час, или
6*10^14 в неделю, или 2.4*10^15 в месяц. Это подразумевает необходимость
как минимум 63 бит случайности в ключах, чтобы быть уверенным, что их нельзя
найти за месяц. Даже тогда возможно, что через несколько лет крайне
решительный и находчивый противник сможет взломать ключ за 2 недели; в
среднем ему нужно испытать лишь половину ключей.
Эти вопросы подробно рассматриваются в работе «Minimal Key Lengths for
Symmetric Ciphers to Provide Adequate Commercial Security: A Report by an
Ad Hoc Group of Cryptographers and Computer Scientists» [KeyStudy],
финансировавшейся Business Software Alliance. В ней сделан вывод, что
разумная длина ключа в 1995 году для очень высокой защищённости находится
в диапазоне от 75 до 90 бит, и, поскольку стоимость криптографии не сильно
зависит от размера ключа, рекомендуется 90 бит. Чтобы обновить эти
рекомендации, просто добавляйте 2/3 бита в год согласно закону Мура
[MOORE]. Из этого следует вывод, что в 2004 году разумная длина ключа
находится в диапазоне от 81 до 96 бит. Фактически сегодня всё чаще
используются ключи длиннее 96
бит, например 128-битные (или более длинные) ключи с AES и ключи с
эффективной длиной 112 бит с тройным DES.
8.2.2. Атаки «встреча посередине»
Если доступны выбранный или известный открытый текст и полученный в
результате зашифрованный текст, атака «встреча посередине» возможна, если
её допускает структура алгоритма шифрования. (При атаке с известным
открытым текстом противник знает все или часть (возможно, некоторые
стандартные поля заголовка или концевика) шифруемых сообщений. При атаке с
выбранным открытым текстом противник может принудить к шифрованию некоторого
выбранного открытого текста, возможно, «слив» захватывающий текст, который
противник отправляет по зашифрованному каналу, поскольку этот текст столь
интересен.
Далее приведено чрезмерно упрощённое объяснение атаки «встреча
посередине»: противник может наполовину зашифровать известный или выбранный
открытый текст всеми возможными первыми половинами ключа, отсортировать
вывод, а затем наполовину расшифровать закодированный текст всеми вторыми
половинами ключа. Если найдено совпадение, полный ключ можно собрать из
половин и использовать для расшифрования других частей сообщения или иных
сообщений. В лучшем случае этот вид атаки может вдвое уменьшить показатель
степени объёма работы, требуемой противнику, добавляя при этом очень большой,
но приблизительно постоянный множитель усилий. Следовательно, если эта атака
может быть осуществлена, для 2004 года на основе анализа [KeyStudy]
необходимо удвоить объём случайности в очень сильном ключе до минимума в
192 бита (96*2).
Этот объём случайности намного превышает предел случайности во входных
данных, рекомендованных Министерством обороны США для генерации паролей, и
может потребовать учёта времени ввода пользователем, аппаратной генерации
случайных чисел или иных источников случайности.
Атака «встреча посередине» предполагает, что криптографический алгоритм
можно разложить таким способом. Будем надеяться, что ни один современный
алгоритм не обладает этой слабостью, но могут быть случаи, когда мы не
уверены в этом или даже в том, с каким алгоритмом будет использоваться ключ.
Даже если базовый алгоритм не подвержен атаке «встреча посередине», попытка
получить более сильный алгоритм посредством двукратного применения базового
алгоритма (либо последовательного применения двух различных алгоритмов) с
разными ключами даст меньше дополнительной безопасности, чем ожидалось.
Такой составной алгоритм будет подвержен атаке «встреча посередине».
Для осуществления атаки «встреча посередине» могут потребоваться огромные
ресурсы, но они, вероятно, находятся в пределах возможностей служб
национальной безопасности крупной страны. По существу, все страны
шпионят за трафиком других стран.
8.2.3. Другие соображения
[KeyStudy] также рассматривает возможности специализированного аппаратного
обеспечения для взлома кодов и наличие достаточного запаса безопасности.
Следует отметить, что расчёты длины ключа, подобные приведённым выше,
спорны и зависят от различных предположений о применяемых криптографических
алгоритмах. В некоторых случаях специалист, глубоко знающий методы взлома
алгоритмов и стойкость используемого алгоритма, мог бы удовлетвориться
размером ключа менее половины от выведенного выше 192-битного размера.
Дополнительные примеры консервативных принципов проектирования см. в
[FERGUSON].
9. Заключение
Генерация неугадываемых «случайных» секретных величин для использования в
целях безопасности является необходимой, но трудной задачей.
Аппаратные методы получения требуемой энтропии были бы относительно
просты. В частности, объём и качество не должны были бы быть высокими, и
можно использовать существующее аппаратное обеспечение компьютера, такое
как аудиовход или дисковые накопители.
Широко доступные вычислительные методы могут обрабатывать случайные
величины низкого качества из нескольких источников либо большее количество
такого низкокачественного ввода из одного источника, чтобы получать меньшее
количество ключевого материала более высокого качества. При отсутствии
аппаратных источников случайности вместо них часто, с осторожностью, можно
использовать различные пользовательские и программные источники. Однако
большинство современных систем уже имеют аппаратное обеспечение, такое как
дисковые накопители или аудиовход, которое можно использовать для получения
высококачественной случайности.
Когда доступно достаточное количество высококачественного начального
ключевого материала (пара сотен бит), имеются вычислительные методы для
получения из этого начального материала криптографически сильных
последовательностей вычислительно непредсказуемых величин.
10. Соображения безопасности
Весь этот документ посвящён методам и рекомендациям по генерации
неугадываемых «случайных» величин для использования в качестве паролей,
криптографических ключей, векторов инициализации, номеров последовательности
и в аналогичных приложениях безопасности.
11. Благодарности
Особая благодарность Полу Хоффману и Джону Келси за их обширные комментарии,
а также Питеру Гутманну, который разрешил включить материал из своей работы
«Software Generation of Practically Strong Random Numbers».
Следующие лица (в алфавитном порядке) внесли существенный вклад в этот
документ:
Steve Bellovin, Daniel Brown, Don Davis, Peter Gutmann, Tony
Hansen, Sandy Harris, Paul Hoffman, Scott Hollenback, Russ
Housley, Christian Huitema, John Kelsey, Mats Naslund, and Damir
Rajnovic.
Следующие лица (в алфавитном порядке) внесли вклад в RFC 1750,
предшественник этого документа:
David M. Balenson, Don T. Davis, Carl Ellison, Marc Horowitz,
Christian Huitema, Charlie Kaufman, Steve Kent, Hal Murray, Neil
Haller, Richard Pitkin, Tim Redmond, and Doug Tygar.
Приложение A: Изменения по сравнению с RFC 1750
1. Добавлены дополнительные выражения признательности.
2. Вставлен раздел 5.3 о смешивании с S-блоками.
3. Добавлен раздел 3.3 об источниках случайности на кольцевых генераторах.
4. Добавлены AES и члены серии SHA, производящие более 160 битов. Использованию AES уделено особое внимание, а использованию DES — меньшее.
5. Добавлен раздел 6.3 о методах пула энтропии.
6. Добавлены раздел 7.2.3 о методах генерации псевдослучайных чисел, приведённых в FIPS 186-2 (с Change Notice 1), раздел 7.2.1 о методах, приведённых в X9.82, раздел 7.1.2 о методах генерации случайных чисел устройства /dev/random в Linux и других системах UNIX, а также раздел 7.1.3 о методах генерации случайных чисел в операционной системе Windows.
7. Добавлены ссылки на исследование "Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security", опубликованное в январе 1996 года [KeyStudy], и на [RFC1948].
8. Добавлены предостережения относительно использования Diffie-Hellman в качестве функции смешивания и, вследствие этих предостережений и его вычислительно интенсивного характера, рекомендовано не использовать его.
9. Добавлены ссылки на работу X9.82 и статьи [TURBID] и [NASLUND].
10. Добавлено обсуждение мин-энтропии и энтропии Реньи, а также ссылки на книгу [LUBY].
11. Выполнены крупная реструктуризация, незначительные изменения формулировок и разнообразные обновления ссылок.