Как решить медленную Java `SecureRandom`?
Если вы хотите криптографически сильное случайное число в Java, вы используете SecureRandom, К несчастью, SecureRandom может быть очень медленным Если он использует /dev/random в Linux это может блокировать ожидание достаточной энтропии для наращивания. Как избежать штрафа за производительность?
Кто-нибудь использовал Uncommon Maths для решения этой проблемы?
Кто-нибудь может подтвердить, что эта проблема с производительностью была решена в JDK 6?
17 ответов
Если вам нужны настоящие случайные данные, то, к сожалению, вам придется их ждать. Это включает в себя семя для SecureRandom ПСЧ. Необычные математики не могут собирать настоящие случайные данные быстрее, чем SecureRandom, хотя он может подключаться к Интернету для загрузки начальных данных с определенного веб-сайта. Я думаю, что это вряд ли будет быстрее, чем /dev/random где это доступно.
Если вы хотите PRNG, сделайте что-то вроде этого:
SecureRandom.getInstance("SHA1PRNG");
Какие строки поддерживаются, зависит от SecureRandom Поставщик SPI, но вы можете перечислить их, используя Security.getProviders() а также Provider.getService(),
Солнце любит SHA1PRNG, поэтому оно широко доступно. Это не особенно быстро, как PRNGs, но PRNGs будут просто подсчитывать цифры, а не блокировать физическое измерение энтропии.
Исключением является то, что если вы не позвоните setSeed() перед получением данных, PRNG будет запущен один раз при первом вызове next() или же nextBytes(), Обычно это делается с использованием довольно небольшого количества истинных случайных данных из системы. Этот вызов может блокировать, но сделает ваш источник случайных чисел намного более безопасным, чем любой вариант "хеширования текущего времени вместе с PID, добавьте 27 и надейтесь на лучшее". Если все, что вам нужно, это случайные числа для игры, или если вы хотите, чтобы поток повторялся в будущем с использованием того же начального числа для целей тестирования, небезопасное начальное число все еще полезно.
Вы должны быть в состоянии выбрать более быстрый, но немного менее безопасный /dev/urandom в Linux, используя:
-Djava.security.egd=file:/dev/urandom
Однако это не работает с Java 5 и более поздними версиями ( Java Bug 6202721). Предложенный обходной путь должен использовать:
-Djava.security.egd=file:/dev/./urandom
(обратите внимание на дополнительные /./)
В Linux реализация по умолчанию для SecureRandom является NativePRNG (исходный код здесь), который имеет тенденцию быть очень медленным. В Windows по умолчанию SHA1PRNG, который, как другие отметили, вы также можете использовать в Linux, если вы укажете это явно.
NativePRNG отличается от SHA1PRNG и AESCounterRNG от Maths в том смысле, что он постоянно получает энтропию от операционной системы (читая из /dev/urandom). Другие PRNG не приобретают никакой дополнительной энтропии после посева.
AESCounterRNG примерно в 10 раз быстрее, чем SHA1PRNG, который IIRC сам в два или три раза быстрее, чем NativePRNG,
Если вам нужен более быстрый PRNG, который приобретает энтропию после инициализации, посмотрите, сможете ли вы найти реализацию Fortuna на Java. Базовый PRNG реализации Fortuna идентичен тому, который используется AESCounterRNG, но есть также сложная система объединения энтропии и автоматического повторного заполнения.
Многие дистрибутивы Linux (в основном на основе Debian) настраивают OpenJDK для использования /dev/random для энтропии.
/dev/random по определению медленный (и может даже блокировать).
Отсюда у вас есть два варианта, как разблокировать его:
- Улучшить энтропию, или
- Уменьшите требования случайности.
Вариант 1. Улучшение энтропии.
Чтобы получить больше энтропии в /dev/random, попробуйте демон beged. Это демон, который непрерывно собирает энтропию HAVEGE и работает также в виртуализированной среде, потому что для этого не требуется никакого специального оборудования, только сам процессор и часы.
В Ubuntu/Debian:
apt-get install haveged
update-rc.d haveged defaults
service haveged start
На RHEL/CentOS:
yum install haveged
systemctl enable haveged
systemctl start haveged
Вариант 2. Снижение требований случайности
Если по какой-либо причине приведенное выше решение не помогает или вас не волнует криптографически значимая случайность, вы можете переключиться на /dev/urandom вместо этого, который гарантированно не заблокировать.
Чтобы сделать это глобально, отредактируйте файл jre/lib/security/java.security в вашей установке Java по умолчанию для использования /dev/urandom (из-за другой ошибки это должно быть указано как /dev/./urandom).
Как это:
#securerandom.source=file:/dev/random
securerandom.source=file:/dev/./urandom
Тогда вам никогда не придется указывать это в командной строке.
Примечание: если вы занимаетесь криптографией, вам нужна хорошая энтропия. Показательный пример - проблема PRNG для Android снизила безопасность биткойн-кошельков.
У меня была похожая проблема со звонками на SecureRandom блокировка примерно на 25 секунд за раз на безголовом сервере Debian. Я установил haveged демон для обеспечения /dev/random на верхних серверах вам нужно что-то подобное, чтобы генерировать необходимую энтропию. Мои звонки SecureRandom теперь возможно займет миллисекунды.
Если вы хотите действительно "криптографически сильную" случайность, то вам нужен сильный источник энтропии. /dev/random медленный, потому что он должен ждать системных событий, чтобы собрать энтропию (чтение диска, сетевые пакеты, движение мыши, нажатия клавиш и т. д.).
Более быстрое решение - аппаратный генератор случайных чисел. Возможно, у вас уже есть один встроенный в материнскую плату; Изучите документацию hw_random, чтобы узнать, как выяснить, есть ли она у вас и как ее использовать. В пакет rng-tools входит демон, который будет передавать энтропию, генерируемую оборудованием. /dev/random,
Если HRNG не доступен в вашей системе, и вы готовы пожертвовать силой энтропии для повышения производительности, вам нужно получить хороший PRNG с данными из /dev/random и пусть PRNG выполнит основную часть работы. Существует несколько утвержденных NIST PRNG, перечисленных в SP800-90, которые легко внедрить.
Согласно документации, SecureRandom использует различные алгоритмы в порядке предпочтения:
- В большинстве систем *NIX
- Родной PRNG
- SHA1PRNG
- NativePRNG Блокировка
- NativePRNGNonBlocking
- В системах Windows
- SHA1PRNG
- Windows-PRNG
Поскольку вы спрашивали о Linux, я игнорирую реализацию Windows, а также SunPKCS11, который действительно доступен только в Solaris, если вы не установили его самостоятельно - и тогда вы бы об этом не спрашивали.
Согласно той же документации, эти алгоритмы используют
SHA1PRNG
Первоначальное заполнение в настоящее время выполняется с помощью комбинации системных атрибутов и устройства сбора энтропии java.security.
Родной PRNG
nextBytes() использует /dev/urandom
generateSeed() использует /dev/random
NativePRNG Блокировка
nextBytes() а также generateSeed() использовать /dev/random
NativePRNGNonBlocking
nextBytes() а также generateSeed() использовать /dev/urandom
Это означает, что если вы используете SecureRandom random = new SecureRandom(), он просматривает этот список, пока не найдет тот, который работает, как правило, NativePRNG. А это значит, что он зарождается из/dev/random (или использует это, если вы явно генерируете семя), затем использует /dev/urandom для получения следующих байтов, целых чисел, двойных, логических и т. д.
поскольку /dev/random блокирует (он блокируется до тех пор, пока в пуле энтропии не будет достаточно энтропии), что может снизить производительность.
Одно решение - использовать что-то вроде hasged для генерации достаточной энтропии, другое решение - использовать /dev/urandomвместо. Хотя вы можете установить это для всего jvm, лучшее решение - сделать это для этого конкретного экземпляраSecureRandom, используя SecureRandom random = SecureRandom.getInstance("NativePRNGNonBlocking"). Обратите внимание, что этот метод может вызвать исключение NoSuchAlgorithmException, если NativePRNGNonBlocking, поэтому будьте готовы вернуться к значению по умолчанию.
SecureRandom random;
try {
random = SecureRandom.getInstance("NativePRNGNonBlocking");
} catch (NoSuchAlgorithmException nsae) {
random = new SecureRandom();
}
Также обратите внимание, что в других системах *nix, /dev/urandomможет вести себя по-другому.
Является /dev/urandom достаточно случайный?
Расхожее мнение гласит, что только /dev/randomдостаточно случайный. Однако некоторые голоса различаются. В статьях "Правильный способ использования SecureRandom" и "Мифы о /dev/urandom" утверждается, что/dev/urandom/ так же хорошо.
Пользователи стека информационной безопасности согласны с этим. В принципе, если вам нужно спросить,/dev/urandom подходит для вашей цели.
Используя Java 8, я обнаружил, что в Linux вызов SecureRandom.getInstanceStrong() дал бы мне NativePRNGBlocking алгоритм. Это часто блокировало бы в течение многих секунд, чтобы генерировать несколько байтов соли.
Я переключился на явно просить NativePRNGNonBlocking вместо этого, как и следует из названия, он больше не блокируется. Я понятия не имею, каковы последствия этого для безопасности. Предположительно, неблокирующая версия не может гарантировать количество используемой энтропии.
Обновление: хорошо, я нашел это отличное объяснение.
В двух словах, чтобы избежать блокировки, используйте new SecureRandom(), Это использует /dev/urandom, который не блокирует и в основном так же безопасен, как /dev/random, Из поста: "Единственный раз, когда вы захотите вызвать /dev/random, это когда машина загружается впервые, а энтропия еще не накопилась".
SecureRandom.getInstanceStrong() дает вам самый сильный RNG, но его можно использовать только в ситуациях, когда блокировка не будет влиять на вас.
Проблема, на которую вы ссылались /dev/random не с SecureRandom алгоритм, но с источником случайности, который он использует. Два ортогональны. Вы должны выяснить, какой из двух замедляет вас.
На странице "Необычные математики", на которую вы ссылались, явно упоминается, что они не обращаются к источнику случайности.
Вы можете попробовать разные провайдеры JCE, такие как BouncyCastle, чтобы увидеть, если их реализация SecureRandom быстрее.
Краткий поиск также обнаруживает патчи для Linux, которые заменяют стандартную реализацию на Fortuna. Я не знаю больше об этом, но вы можете расследовать.
Я должен также упомянуть, что в то время как очень опасно использовать плохо реализованный SecureRandom алгоритм и / или источник случайности, вы можете свернуть свой собственный поставщик JCE с пользовательской реализацией SecureRandomSpi, Вам нужно будет пройти через Sun процесс, чтобы подписать вашего провайдера, но на самом деле это довольно просто; им просто нужно, чтобы вы отправили им по факсу форму, подтверждающую, что вы знаете об ограничениях на экспорт криптобиблиотек в США.
Я столкнулся с той же проблемой. После некоторого поиска в Google с правильными поисковыми терминами я наткнулся на эту прекрасную статью о DigitalOcean.
есть потенциальное решение без ущерба для безопасности.
Я просто цитирую соответствующую часть статьи здесь.
Основанный на принципе HAVEGE и ранее основанный на его ассоциированной библиотеке, hasged позволяет генерировать случайность на основе изменений во времени выполнения кода на процессоре. Поскольку для одного куска кода практически невозможно выполнить одно и то же точное время, даже в одной и той же среде на одном и том же оборудовании, время запуска одной или нескольких программ должно быть подходящим для создания случайного источника. Реализация с хэджами отбирает случайный источник вашей системы (обычно /dev/random), используя различия в счетчике меток времени вашего процессора (TSC) после многократного выполнения цикла
Как установить hasged
Следуйте инструкциям в этой статье. https://www.digitalocean.com/community/tutorials/how-to-setup-additional-entropy-for-cloud-servers-using-haveged
Я разместил это здесь
Существует инструмент (по крайней мере, в Ubuntu), который подает искусственную случайность в вашу систему. Команда просто:
rngd -r /dev/urandom
и вам может понадобиться sudo на фронте. Если у вас нет пакета rng-tools, вам необходимо установить его. Я попробовал это, и это определенно помогло мне!
Источник: Мэтт против мира
Используйте безопасный случайный случай в качестве источника инициализации для рекуррентного алгоритма; тогда вы могли бы использовать твистер Mersenne для массовых работ вместо того, что использовался в UncommonMath, который существовал некоторое время и оказался лучше, чем другие prng
http://en.wikipedia.org/wiki/Mersenne_twister
Обязательно обновите время от времени безопасное случайное число, используемое для инициализации, например, вы можете создать одно безопасное случайное случайное число для каждого клиента, используя один псевдослучайный генератор mersenne twister для каждого клиента, получая достаточно высокую степень рандомизации.
Я сам не сталкивался с этой проблемой, но я запускал поток при запуске программы, который сразу же пытался сгенерировать начальное число, а затем умирал. Метод, который вы вызываете для случайных событий, присоединится к этому потоку, если он жив, поэтому первый вызов блокируется только в том случае, если он происходит в самом начале выполнения программы.
Мой опыт был только с медленной инициализацией PRNG, а не с генерацией случайных данных после этого. Попробуйте более активную стратегию инициализации. Поскольку создавать их дорого, относитесь к ним как к одиночке и используйте один и тот же экземпляр. Если для одного экземпляра слишком много конфликтов потоков, объедините их в пул или сделайте их локальными.
Не идите на компромисс по генерации случайных чисел. Слабость там ставит под угрозу всю вашу безопасность.
Я не вижу много генераторов на основе атомного распада COTS, но есть несколько планов для них, если вам действительно нужно много случайных данных. Один сайт, на котором всегда есть интересные вещи, включая HotBits, это Fourmilab Джона Уокера.
Похоже, вы должны прояснить свои требования к ГСЧ. Самое сильное криптографическое требование ГСЧ (насколько я понимаю) заключается в том, что даже если вы знаете алгоритм, использованный для их генерации, и знаете все ранее сгенерированные случайные числа, вы не сможете получить никакой полезной информации о любом из случайных чисел, сгенерированных в будущее, не тратя непрактичное количество вычислительной мощности.
Если вам не нужна эта полная гарантия случайности, то, вероятно, существуют соответствующие компромиссы производительности. Я склонен согласиться с ответом Дэна Дайера об AESCounterRNG от Uncommons-Maths или Fortuna (одним из его авторов является Брюс Шнайер, эксперт по криптографии). Я никогда не использовал ни один, но идеи кажутся авторитетными на первый взгляд.
Я думаю, что если бы вы могли генерировать начальное случайное начальное число периодически (например, один раз в день, час или что-то еще), вы могли бы использовать быстрый потоковый шифр для генерации случайных чисел из последовательных фрагментов потока (если потоковый шифр использует XOR, тогда просто передать поток нулей или захватить биты XOR напрямую). Проект ECRYPT eStream содержит много полезной информации, в том числе тесты производительности. Это не будет поддерживать энтропию между моментами времени, когда вы его пополняете, поэтому, если кто-то знает одно из случайных чисел и алгоритм, который вы использовали, технически возможно, с большой вычислительной мощностью, сломать потоковый шифр и угадать его внутреннее состояние, чтобы иметь возможность предсказывать будущие случайные числа. Но вам придется решить, достаточно ли этого риска и его последствий, чтобы оправдать затраты на поддержание энтропии.
Изменить: вот некоторые заметки о криптографии курса по ГСЧ, которые я нашел в сети, которые выглядят очень актуальными для этой темы.
Если ваше оборудование поддерживает его, попробуйте использовать Java RdRand Utility, доступную по адресу: http://code.google.com/p/lizalab-rdrand-util/
Он основан на инструкции Intel RDRAND и примерно в 10 раз быстрее, чем SecureRandom, и не создает проблем с пропускной способностью для реализации больших объемов.
Полное раскрытие, я автор утилиты.
Еще нужно обратить внимание на свойство securerandom.source в файле lib/security/java.security.
Использование /dev/urandom может иметь преимущество в производительности, а не / dev / random. Помните, что если важно качество случайных чисел, не идите на компромисс, который нарушает безопасность.
Вы можете попробовать проект Math Apache commons, который имеет несколько реализаций хорошо известных алгоритмов:
https://commons.apache.org/proper/commons-math/userguide/random.html
Однако будьте осторожны с производительностью. Конструктор по умолчанию RandomDataGenerator создает выделенный экземпляр Well19937cэто очень дорогая операция.
Согласно документации, этот класс не является потокобезопасным, но если вы можете гарантировать, что только один поток будет иметь доступ к этому классу, вы можете инициализировать только один экземпляр для каждого потока.
Постановка задачи
Эта библиотека msprandom демонстрирует технику генерации случайных чисел для криптографических целей без аппаратных генераторов. Шифрование и подпись требует случайных чисел с хорошим качеством. Генерация случайных чисел (или последовательностей случайных байтов) без аппаратных генераторов не является тривиальной задачей. Особенно эта проблема актуальна для небольших устройств, где источники случайных данных отсутствуют или ограничены. Решение состоит в том, чтобы сохранить истинное случайное начальное число в защищенном файле (хранилище) и шифре, которые могут создавать зашифрованные псевдослучайно сгенерированные (PRNG) последовательности на основе случайного начального числа с хорошими случайными характеристиками.
Многие криптографические библиотеки (например, BouncyCastle) используют класс SecureRandom для шифрования и подписи для получения случайных чисел. SecureRandom зависит от реализации ОС. Другими словами, реализация случайного движка находится за пределами вашего приложения, которым вы не можете управлять. Чтобы избежать использования плохих случайных чисел, вы ДОЛЖНЫ сеять генератор SecureRandom с хорошими случайными данными каждый раз, когда вызываете криптографические функции, требующие случайных данных. Или вы можете расширить класс SecureRandom своей реализацией, которая генерирует случайные числа, качеством которых вы можете управлять.
идея
Нам нужно использовать настоящие случайные данные, хранящиеся в защищенном хранилище данных.
Несколько шагов, как сделать msprandom внутри вашего приложения:
- Создайте на своем компьютере или ноутбуке истинное случайное семя и поместите его в хранилище с помощью этой библиотеки.
- Поместите хранилище (файл) со случайным начальным числом на ваше устройство, компьютер или сервер, где вам необходимо зашифровать и подписать данные.
- Загрузите хранилище один раз в начале программы, когда вам нужно зашифровать или подписать данные.
- Вызовите функцию gen-rand из библиотеки msprandom, чтобы получить случайные байты столько раз, сколько вам нужно.
Хранилище со случайным начальным числом зашифровано и защищено с помощью HMAC. Случайное начальное число в хранилище обновляется каждый раз, когда вы загружаете хранилище непредсказуемым образом, поэтому меняется и HMAC. Смена хранилища производится намеренно в зависимости от ситуации, если злоумышленник в прошлом мог скопировать некоторую копию вашего хранилища.
Истинный генератор случайных данных
Для создания истинного случайного семени в msprandom используется человеческий вклад. Вот алгоритм сбора случайных данных:
- Мы запускаем отдельный поток, где атомный счетчик увеличивает каждый тик с 0..255 с очень высокой скоростью.
- Дождитесь нажатия небуферизованной клавиши человеком и получите код сканирования нажатой кнопки.
- Возьмите текущее значение наносекунды с начала Epoch и возьмите mod 256, чтобы преобразовать его значение в случайный байт.
- Xor значения между собой: скан-код-байт ^ текущее-счетчик-значение ^ наносекунды для получения случайного байта.
- Добавьте случайный байт к выходному вектору. Мы предполагаем, что только 3 бита имеют истинную случайность в этом случайном байте. Итак, чтобы получить истинные случайные 32 байта, нам нужно ~ 32*3 нажатия кнопки из пользовательского ввода.
- Повторите шаги 2-5, пока мы не получим необходимое количество случайных байтов. Если мы собрали необходимое количество случайных данных, выполните последний шаг -> выходной вектор хеша с криптографически сильной хеш-функцией, чтобы гарантировать, что вероятности 1 и 0 битов в выходном векторе будут равны 0,5. Обратите внимание, что хеш-функция используется здесь только для смешивания случайных битов и не влияет на качество случайных данных. Итак, хэш (случайные данные) = случайные данные. Используя этот алгоритм, msprandom собирает истинные 512 случайных битов в качестве начального числа, которое будет сохранено в хранилище.
Почему 512 случайных бит достаточно?
Ну, каждый PRNG нуждается в истинном случайном семени. Если злоумышленник знает начальное число, он может предсказать генерацию ключа и так далее. 256 бит начального случайного начального числа достаточно далеко, чтобы хранить секреты военного уровня. Я сделал 512, чтобы быть уверенным, что никто не сможет перебрать силу или угадать начальное случайное семя. Таким образом, вы можете свободно использовать msprandom для заполнения ваших генераторов PRNG или SecureRandom.