Наверняка многие из вас неоднократно сталкивались с мифами о /dev/urandom и /dev/random. Может быть, в некоторые из них вы даже верите. В этом посте мы сорвём покровы со всех этих мифов и разберём настоящие сильные и слабые стороны этих генераторов случайных чисел.
Миф 1: /dev/urandom небезопасен. Для криптографии всегда используйте /dev/random
В основном это утверждается применительно к достаточно «свежим» системам на базе Linux, а не вообще ко всем UNIX-подобным системам. На самом деле /dev/urandom является предпочтительным генератором случайных чисел для криптографических задач в UNIX-подобных системах.
Миф 2: /dev/urandom — это генератор псевдослучайных чисел (PRNG), а /dev/random — генератор «истинно» случайных чисел
На самом деле они оба являются криптографически стойкими генераторами псевдослучайных чисел (CSPRNG). Различия между ними очень невелики и не имеют отношения к степени случайности.
Миф 3: для криптографических задач однозначно лучше использовать /dev/random. В использовании /dev/urandom нет смысла, даже если бы он был относительно безопасен
На самом деле у /dev/random есть очень неприятная проблема: блокировки.
Но это же замечательно! Чем больше энтропии в пуле /dev/random, тем выше уровень случайности. А /dev/urandom генерирует небезопасные случайные числа, даже если энтропия уже исчерпана
Нет. «Исчерпание энтропии» — это пугало, даже если не брать в расчёт доступность и последующие манипуляции со стороны пользователей. Порядка 256 бит энтропии вполне достаточно для ОЧЕНЬ длительного генерирования вычислительно стойких чисел.
Куда забавнее другое: откуда /dev/random может знать, сколько ещё энтропии у него есть в запасе?
Но специалисты по криптографии всё время твердят о постоянном обновлении начального состояния (re-seeding). Не противоречит ли это вашему последнему утверждению?
Это верно отчасти. Да, генератор случайных чисел постоянно обновляет своё начальное состояние с помощью всевозможных источников энтропии, которые ему доступны. Но причины этого заключаются в другом (отчасти). Я не утверждаю, что применение энтропии — это плохо. Вовсе нет. Я лишь говорю о вреде блокировки при падении уровня энтропии.
Это всё прекрасно, но даже справочник по /dev/(u)random противоречит вашим утверждениям. Вообще хоть кто-нибудь разделяет вашу точку зрения?
Я вовсе не опровергаю справочные данные. Могу предположить, что вы пока не совсем понимаете весь этот криптографический жаргон, поэтому увидели в справочнике подтверждение небезопасности /dev/urandom для криптографических задач. Но в справочнике лишь не рекомендуется использовать /dev/urandom в некоторых случаях. С моей точки зрения, это не критично. В то же время в справочнике рекомендуется использовать /dev/urandom для «нормальных» криптографических задач.
Апеллирование к авторитетам — не повод для гордости. В криптографии необходимо осторожно подходить к решению вопросов, прислушиваясь к мнению специалистов в конкретных сферах.
И да, немало экспертов разделяют мою точку зрения, что в контексте криптографии в UNIX-подобных системах наилучший генератор случайных чисел — /dev/urandom. Как вы понимаете, это их совокупное мнение повлияло на меня, а не наоборот.
* * *
Вероятно, многим из вас трудно во всё это поверить. «Он наверняка ошибается!» Что ж, давайте подробно разберём всё сказанное, и вы решите сами, прав я или нет. Но прежде чем приступить к разбору, ответьте себе: что такое случайность? Точнее, о случайности какого рода мы тут говорим? Я не пытаюсь быть снисходительным. Этот текст был написан для того, чтобы ссылаться на него в будущем, когда снова возникнет дискуссия о генераторах случайных чисел. Так что здесь я оттачиваю свои доводы и аргументы. Кроме того, меня интересуют другие мнения. Недостаточно просто утверждать, что «/dev/urandom — это плохо». Вам нужно выяснить, с чем именно вы не согласны, и разобраться с этим.
«Он идиот!»
Категорически не согласен! Я сам когда-то верил, что /dev/urandom небезопасен. Да мы все просто вынуждены были в это поверить, потому что об этом нам твердит множество всех этих уважаемых программистов и разработчиков на форумах и в соцсетях. И многим кажется, что даже в man говорится о том же. А кто мы такие, чтобы спорить с их убедительным аргументом об «исчерпании энтропии»?
Это глубоко ошибочное мнение укоренилось не потому, что люди глупы, а просто мало кто серьёзно разбирается в криптографии (а именно в туманном понятии «энтропии»). Поэтому авторитеты легко нас убеждают. Даже интуиция с ними соглашается. К сожалению, интуиция также ничего не смыслит в криптографии, как и большинство из нас.
Истинная случайность
Каковы критерии «истинной случайности» числа? Не будем углубляться в дебри, поскольку обсуждение быстро перейдёт в область философии. В подобных дискуссиях очень быстро обнаруживается, что каждый твердит о своей любимой модели случайности, не слушая других и даже не заботясь о том, чтобы его поняли.
Я считаю, что настоящим эталоном «истинной случайности» служат квантовые эффекты. Например, возникающие при прохождении фотонов сквозь полупрозрачное зеркало, при испускании альфа-частиц радиоактивным материалом и т. д. То есть идеальная случайность встречается в каких-то физических явлениях. Кто-то может считать, что и они не могут быть истинно случайными. Или что в мире вообще ничто не может быть случайным. Короче, «всем пис».
Криптографы обычно избегают участия в подобных философских дебатах, поскольку не признают понятия «истинности». Они оперируют понятием «непредсказуемость». Если никто не обладает какой-либо информацией о следующем случайном числе, то всё в порядке. Я считаю, что именно на это нужно ориентироваться при использовании случайных чисел в криптографии.
В общем, меня мало волнуют все эти «философско-безопасные» случайные числа, как я для себя называю «истинно» случайные.
Из двух видов безопасности значение имеет лишь одна
Но давайте предположим, что вам удалось получить «истинно» случайные числа. Что вы с ними будете делать? Распечатаете и повесите на стенах в спальне, наслаждаясь красотой квантовой вселенной? Почему бы и нет, я могу понять такое отношение.
Но вы же наверняка их используете, причём для криптографических нужд? А это уже выглядит не так позитивно. Видите ли, ваши истинно случайные, осенённые благостью квантового эффекта числа попадают в приземлённые алгоритмы реального мира. И проблема в том, что почти все из используемых криптографических алгоритмов не соответствуют теоретико-информационной безопасности. Они обеспечивают «лишь» вычислительную безопасность. На память приходят только два исключения: схема разделения секрета Шамира и шифр Вернама. И если первый может выступать в качестве контрапункта (если вы действительно собираетесь его использовать), то второй крайне непрактичен. Все же остальные алгоритмы: AES, RSA, Диффи — Хеллмана, эллиптических кривых, такие криптопакеты, как OpenSSL, GnuTLS, Keyczar, и криптографические API являются вычислительно безопасными.
В чём разница? Теоретико-информационно безопасные алгоритмы обеспечивают безопасность в течение какого-то периода, а все остальные алгоритмы не гарантируют безопасности перед лицом злоумышленника, обладающего неограниченными вычислительными мощностями и перебирающего все возможные значения ключей. Мы используем эти алгоритмы только потому, что если собрать все компьютеры в мире, то они будут решать задачу перебора дольше, чем существует вселенная. Вот о каком уровне «небезопасности» идёт речь.
Но это лишь до тех пор, пока какой-нибудь шибко умный парень не взломает очередной алгоритм с помощью куда более скромных вычислительных мощностей. О таком успехе мечтает любой криптоаналитик: обрести славу, взломав AES, RSA и т. д. И когда взламывают «идеальные» алгоритмы хэширования или «идеальные» блочные шифры, то уже совершенно неважно, что у вас есть ваши «философско-безопасные» случайные числа. Вам просто негде их безопасно использовать.Так что лучше применяйте в вычислительно безопасных алгоритмах вычислительно безопасные случайные числа. Иными словами, пользуйтесь /dev/urandom.
Структура генератора случайных чисел в Linux: неверное представление
Скорее всего, вы примерно так представляете себе работу генератора случайных чисел, встроенного в ядро:
«Истинная» случайность, хоть и наверняка искажённая, попадает в систему. Вычисляется её энтропия и немедленно добавляется к значению внутренней энтропии счётчика. После исправления и привнесения белого шума (whitening) получившаяся энтропия передаётся в пул ядра, откуда берут случайные числа /dev/random и /dev/urandom. /dev/random получает их из пула напрямую, если у счётчика энтропии имеется запрашиваемое количество чисел. Конечно, при этом счётчик уменьшается. В противном случае счётчик блокируется до тех пор, пока в систему не попадёт новая порция энтропии.
Важный момент заключается в том, что получаемые /dev/random данные обязательно подвергаются операции привнесения белого шума. С /dev/urandom та же самая история, за исключением момента, когда в системе не оказывается нужного количества энтропии: вместо применения блокировки он получает «низкокачественные» случайные числа от CSPRNG, работающего вне рассматриваемой нами системы. Стартовое число для этого CSPRNG выбирается лишь один раз (или каждый раз, неважно) исходя из имеющихся в пуле данных. Его нельзя считать безопасным.
Для многих это убедительная причина избегать использования /dev/urandom в Linux. Когда энтропии достаточно, используются те же данные, что и в случае с /dev/random, а когда её мало, то подключается внешний CSPRNG, который почти никогда не получает данных с высокой энтропией. Ужасно, не правда ли? К сожалению, всё описанное выше в корне неверно. На самом деле внутренняя структура генератора случайных чисел выглядит иначе:
Упрощение довольно грубое: на самом деле используется не один, а три пула энтропии:
- первичный,
- для /dev/random,
- для /dev/urandom.
Последние два пула получают данные из первичного. У каждого пула свой счётчик, но у последних двух они близки к нулю. «Свежая» энтропия подаётся из первого пула по мере надобности, при этом его собственный счётчик уменьшается. Также активно применяется смешивание и возврат данных обратно в систему, но все эти нюансы неважны для предмета нашего разговора.
Замечаете разницу? CSPRNG не работает в дополнение к основному генератору, а является составной частью процесса генерации случайных чисел. Для /dev/random не выдаются «чистые и хорошие» случайные данные, в которые привнесён белый шум. Входящие данные от каждого источника тщательно смешиваются и хэшируются внутри CSPRNG и только потом выдаются в виде случайных чисел для /dev/random или /dev/urandom.
Ещё одно важное отличие заключается в том, что энтропия здесь не считается, а оценивается. Количество энтропии от какого-либо источника не является чем-то очевидным, словно какие-то данные. Помните о том, что ваш нежно любимый /dev/random лишь выдаёт то количество случайных чисел, которое доступно благодаря имеющейся энтропии. К сожалению, оценивать количество энтропии довольно трудно. В ядре Linux применяется такой подход: берётся время начала какого-то события, интерполируется его полином и вычисляется, «насколько неожиданно», согласно некой модели, началось это событие. Есть определённые вопросы по эффективности такого подхода к оценке энтропии. Также нельзя сбрасывать со счетов и влияние аппаратных задержек на время начала событий. Может играть роль и частота опроса аппаратных компонентов, поскольку она напрямую влияет на значение и гранулярность времени начала событий.
В целом нам известно лишь, что оценка энтропии в ядре реализована весьма неплохо. Что означает — консервативно. Кто-то может поспорить о том, насколько хорошо всё сделано, но это уже выходит за рамки нашей беседы. Вы можете нервничать по поводу нехватки энтропии для генерирования случайных чисел, но лично меня устраивает текущий механизм оценки.
Подытожу: /dev/random и /dev/urandom работают за счёт одного и того же CSPRNG. Различаются они лишь поведением при исчерпании пула энтропии: /dev/random блокирует, а /dev/urandom — нет.
Что плохого в блокировке?
Вам когда-нибудь приходилось ждать, пока /dev/random выдаст случайные числа? Например, генерируя PGP-ключи внутри виртуальной машины? Или при подключении к веб-серверу, который ожидает порцию случайных чисел для создания динамического ключа сессии? Вот в этом-то и заключается проблема. По сути, происходит блокировка доступности, ваша система временно не работает. Она не делает то, что должна.
Кроме того, это даёт негативный психологический эффект: людям не нравится, когда им что-то препятствует. Я, к примеру, работаю над безопасностью систем промышленной автоматизации. Как вы думаете, из-за чего чаще всего происходят нарушения системы безопасности? Из-за сознательных действий самих пользователей. Просто какая-нибудь мера, призванная обеспечивать защиту, выполняется слишком долго, по мнению сотрудника. Или она слишком неудобна. И когда нужно найти «неофициальные решения», люди проявляют чудеса находчивости. Они будут искать обходные пути, выдумывать причудливые махинации, чтобы заставить систему работать. Люди, не разбирающиеся в криптографии. Нормальные люди.
Почему бы не пропатчить вызов random()? Почему бы не спросить кого-нибудь на форумах, как можно использовать странные ioctl для увеличения счётчика энтропии? Почему бы полностью не отключить SSL? В конце концов, вы просто учите своих пользователей делать идиотские вещи, компрометирующие вашу систему безопасности, даже не зная об этом. Можно сколь угодно презрительно относиться к доступности и удобству использования системы и прочим важным вещам. Безопасность превыше всего, да? Лучше пусть будет неудобной, малодоступной или бесполезной, вместо того чтобы симулировать обеспечение безопасности.
Но это всё фальшивая дихотомия. Безопасность можно обеспечивать и без блокировок, ведь /dev/urandom предоставляет вам точно такие же случайные числа, что и /dev/random.
В CSPRNG нет ничего плохого
Но теперь ситуация выглядит совсем уныло. Если даже высококачественные числа от /dev/random генерируются CSPRNG, то как же можно их использовать в задачах, требующих высокого уровня безопасности? Похоже, что основным требованием к большинству наших криптографических модулей является необходимость «выглядеть случайными». Чтобы выходные данные криптографического хэша были приняты криптографами, они должны быть неотличимы от случайного набора строк. А выходные данные блочного шифра без знания ключа должны быть неотличимы от случайных данных.
Не бойтесь, что кто-то сможет воспользоваться какими-то слабостями CSPRNG и взломает криптографические модули. Вам всё равно ничего не остаётся, кроме как смириться с этим, поскольку и блочные шифры, и хэши, и всё остальное основано на том же самом математическом фундаменте, что и CSPRNG. Так что расслабьтесь.
Что насчёт исчерпания энтропии?
Это не имеет значения. Базовые криптографические элементы разработаны с учётом того, что атакующий не сможет предсказать результат, если в начале было достаточно много случайности (энтропии). Обычно нижний предел «достаточности» составляет 256 бит, не больше. Так что забудьте уже про свою энтропию. Как мы уже разобрали выше, встроенный в ядро генератор случайных чисел даже не может точно посчитать количество поступающей в систему энтропии. Он её может лишь оценить. К тому же неясно, как именно осуществляется оценивание.
Обновление начального состояния (re-seeding)
Но если энтропия имеет так мало значения, то для чего в генератор постоянно передаётся свежая энтропия? Надо сказать, что избыток энтропии вреден. Но для обновления начального состояния генератора есть другая важная причина. Представьте, что атакующему стало известно внутреннее состояние вашего генератора. Это самая кошмарная ситуация с точки зрения безопасности, какую вы можете вообразить, ведь атакующий получает полный доступ к системе. Вы в полном пролёте, с этого момента злоумышленник может вычислять все будущие выходные данные.
Но со временем станут поступать всё новые порции свежей энтропии, которые будут подмешиваться к внутреннему состоянию, и степень его случайности снова начнёт расти. Так что это своеобразный защитный механизм, встроенный в архитектуру генератора. Однако обратите внимание: энтропия добавляется к внутреннему состоянию, она не имеет никакого отношения к блокированию генератора.
Страницы man по random и urandom
Man нет равных по внушению страхов в разумы программистов:
При чтении из /dev/urandom блокировка в ожидании необходимой энтропии осуществляться не будет. В результате если в пуле недостаточно энтропии, то возвращаемые данные теоретически уязвимы к криптографическим атакам на используемые драйвером алгоритмы. В открытых источниках не содержится информации, как это можно сделать, но существование таких атак теоретически возможно. Если это может касаться вашего приложения, то используйте /dev/random.
Про подобные атаки нигде ничего не говорится, но у АНБ/ФСБ наверняка есть что-то на вооружении, верно? И если вас это волнует (должно волновать!), то все ваши проблемы решит /dev/random. Даже если способ проведения подобной атаки известен спецслужбам, кулхацкерам или бабайке, то просто взять и устроить её будет нерационально. Скажу больше: в открытой литературе не описаны также практические способы атак на AES, SHA-3 или какие-либо иные подобные шифры и хэши. Вы и от них тоже откажетесь? Конечно, нет. Особенно умиляет совет «используйте /dev/random» в свете того, что мы уже знаем об общем источнике его и /dev/urandom. Если вам прямо позарез нужны теоретико-информационно безопасные случайные числа (а они вам не нужны!) и по этой причине вы не можете использовать CSPRNG, то и /dev/random для вас бесполезен! В справочнике написана ерунда, вот и всё. Но авторы хотя бы пытаются как-то исправиться:
Если вы не уверены в том, что вам следует использовать — /dev/random или /dev/urandom, то, скорее всего, лучше будет применять второй. В большинстве случаев, за исключением генерирования многоразовых ключей GPG/SSL/SSH, следует использовать /dev/urandom.
Замечательно. Если хотите использовать /dev/random для многоразовых ключей — флаг вам в руки, хоть я и не считаю, что это необходимо. Ну подождёте несколько секунд, прежде чем сможете что-нибудь набрать на клавиатуре, подумаешь. Только умоляю вас, не заставляйте бесконечно коннектиться к почтовому серверу только потому, что вы «хотите быть в безопасности».
Ортодоксам посвящается
Ниже представлены некоторые интересные высказывания, найденные мной в интернете. А если вам очень захочется, чтобы кто-то поддержал вас с /dev/random, то обратитесь к настоящим криптографам.
Daniel Bernstein aka djb:
Криптографы не имеют отношения к этому суеверию. Задумайтесь: тот, кто написал мануал по /dev/random, действительно в это верит.
- Мы не знаем, как можно детерминированно трансформировать одно 256-битное число от /dev/random в бесконечный поток непредсказуемых ключей (а это нам и нужно от urandom), но
- мы можем вычислить, как использовать единственный ключ для безопасного шифрования многочисленных сообщений. Что, собственно, нам нужно от SSL, PGP и т. д.
Криптографы от всего этого даже не улыбнутся.
Thomas Pornin, один из самых полезных пользователей, с которыми я сталкивался на Stack Exchange:
Если коротко — да. Если развёрнуто — тоже да. /dev/urandom предоставляет данные, которые с помощью имеющихся технологий нельзя отличить от истинно случайных. Нет никакого смысла стремиться к ещё «лучшей» случайности, чем обеспечиваемая /dev/urandom, если только вы не используете один из нескольких «теоретико-информационных» криптоалгоритмов. А вы их точно не используете, иначе вы бы об этом знали. Справочник по urandom вводит в заблуждение своим предложением, что из-за «иссякания энтропии» /dev/urandom следует использовать /dev/random.
Thomas Ptacek не является настоящим криптографом с точки зрения разработки алгоритмов или создания криптосистем. Но зато он основал консалтинговое агентство в сфере безопасности, заработавшее хорошую репутацию многочисленными тестированиями на проникновение и взломами некачественной криптографии:
Используйте urandom. Используйте urandom. Используйте urandom. Используйте urandom. Используйте urandom. Используйте urandom.
Нет в мире совершенства
/dev/urandom не идеален, и тому есть две причины. В отличие от FreeBSD, в Linux он никогда не вызывает блокировки. А как вы помните, вся система безопасности базируется на некой начальной случайности, т. е. на выборе стартового числа. В Linux /dev/urandom без зазрения совести выдаёт вам не слишком случайные числа ещё до того, как у ядра появится хоть какая-то возможность собрать энтропию. Когда это происходит? При старте машины, во время загрузки компьютера. Во FreeBSD всё устроено более правильно: там нет никакого различия между /dev/urandom и /dev/random, это одно и то же. Только при загрузке /dev/random однократно блокирует, пока не накопится достаточно энтропии. После этого блокировок уже нет.
В Linux всё тоже не так плохо, как выглядит на первый взгляд. Во всех дистрибутивах на стадии загрузки некоторое количество случайных чисел сохраняется в seed-файл, считываемый при следующей загрузке системы. Но запись производится только после того, как набирается достаточное количество энтропии, поскольку скрипт не запускается моментально после нажатия кнопки включения. Так что вы несёте ответственность за накопление энтропии с предыдущего сеанса работы. Конечно, это не так хорошо, как если бы вы позволили записывать стартовое число скриптам, завершающим работу системы. Ведь приходится гораздо дольше копить энтропию. Зато вы не зависите от корректности завершения системы с выполнением соответствующих скриптов (например, вам не страшны ресеты и падения системы). Кроме того, такое решение не поможет вам при самом первом запуске машины. Но в дистрибутивах Linux seed-файл записывается во время работы инсталлятора, так что в целом пойдёт.
В то же время в Linux был реализован новый системный вызов getrandom(2), изначально появившийся в OpenBSD как getentropy(2). Он осуществляет блокировку до тех пор, пока не накопится достаточное начальное количество энтропии, и впоследствии уже не блокирует. Правда, это не символьное устройство, а системный вызов, поэтому к нему не так просто получить доступ из терминала или скриптовых языков.
Ещё одна проблема связана с виртуальными машинами. Люди любят их клонировать или возвращаться к предыдущим состояниям, и в этих случаях seed-файл вам не поможет. Но решается это не поголовным использованием /dev/random, а очень точным выбором стартового числа для каждой виртуальной машины после клонирования, возвращения к предыдущему состоянию и т. д.
Tl;dr
Просто используйте /dev/urandom.
Автор: Mail.Ru Group
