Разница между java.util.Random и java.security.SecureRandom

202

Моя команда получила серверный код (на Java), который генерирует случайные токены, и у меня есть вопрос относительно того же самого -

Назначение этих токенов довольно чувствительно - используется для идентификатора сеанса, ссылок для сброса пароля и т. Д. Поэтому они должны быть криптографически случайными, чтобы не допустить, чтобы кто-то их угадал или применил грубую силу. Токен является «длинным», поэтому он имеет длину 64 бита.

Код в настоящее время использует java.util.Randomкласс для генерации этих токенов. Документация для java.util.Randomчетко говорится следующее:

Экземпляры java.util.Random не являются криптографически безопасными. Вместо этого рассмотрите возможность использования SecureRandom для получения криптографически безопасного генератора псевдослучайных чисел для использования чувствительными к безопасности приложениями.

Однако в настоящее время код использует java.util.Randomследующее: он создает экземпляр java.security.SecureRandomкласса, а затем использует SecureRandom.nextLong()метод для получения начального числа, которое используется для создания экземпляра java.util.Randomкласса. Затем он использует java.util.Random.nextLong()метод для генерации токена.

Итак, мой вопрос сейчас - это все еще небезопасно, учитывая, java.util.Randomчто сеют с помощью java.security.SecureRandom? Нужно ли изменять код так, чтобы он использовался java.security.SecureRandomисключительно для генерации токенов?

В настоящее время начальный код является Randomединственным при запуске

user967973
источник
14
После заполнения выводом из java.util.Random является детерминированная последовательность чисел. Вы можете не хотеть этого.
Питер Штибраны
1
Код запускает Randomодин раз при запуске или новый для каждого токена? Надеюсь, это глупый вопрос, но я решил проверить.
Том Андерсон
8
Случайные имеет только внутреннее состояние 48-битную и будет повторяться через 2 ^ 48 звонков в nextLong () , что означает , что он не будет производить все возможные longили doubleзначения.
Питер Лори
3
Есть еще одна серьезная проблема. 64бит означает 1,84 * 10 ^ 19 возможных комбинаций, что слишком мало, чтобы выдержать изощренную атаку. Есть машины, которые взломали 56-битный код DES (менее 256 раз) с 90 * 10 ^ 9 ключами в секунду за 60 часов. Используйте 128 бит или два длинных!
Торстен С.

Ответы:

232

Стандартная реализация Oracle JDK 7 использует так называемый линейный конгруэнтный генератор для генерации случайных значений java.util.Random.

Взято из java.util.Randomисходного кода (JDK 7u2), из комментария к методу protected int next(int bits), который генерирует случайные значения:

Это линейный конгруэнтный генератор псевдослучайных чисел, как он определен Д.Х. Лемером и описан Дональдом Кнутом в книге «Искусство компьютерного программирования», том 3: Полу численные алгоритмы , раздел 3.2.1.

Предсказуемость линейных конгруэнтных генераторов

Хьюго Кравчик написал довольно хорошую статью о том, как можно прогнозировать эти LCG («Как прогнозировать конгруэнтные генераторы»). Если вам повезет и вы заинтересуетесь, вы все равно можете найти бесплатную загружаемую версию в Интернете. И есть еще много исследований, которые ясно показывают, что вы никогда не должны использовать LCG в целях безопасности. Это также означает , что ваши случайные числа имеют предсказуемый прямо сейчас, что вы не хотите для идентификаторов сеансов и тому подобное.

Как сломать линейный конгруэнтный генератор

Предположение, что злоумышленнику придется ждать повторения LCG после полного цикла, неверно. Даже при оптимальном цикле (модуль m в его рекуррентном соотношении) очень легко предсказать будущие значения за гораздо меньшее время, чем полный цикл. В конце концов, это просто набор модульных уравнений, которые необходимо решить, что становится легко, как только вы наблюдаете достаточно выходных значений LCG.

Безопасность не улучшается с «лучшим» семенем. Это просто не имеет значения, если вы посеете случайное значение, сгенерированное SecureRandomили даже произведенное, бросая кубик несколько раз.

Злоумышленник просто вычислит начальное значение из наблюдаемых выходных значений. Это занимает значительно меньше времени, чем 2 ^ 48 в случае java.util.Random. Неверующие могут попробовать этот эксперимент , где показано, что вы можете предсказать будущееRandom результаты, наблюдая только два (!) Выходных значения во времени примерно 2 ^ 16. На современном компьютере не требуется даже секунды, чтобы предсказать вывод ваших случайных чисел прямо сейчас.

Вывод

Замените свой текущий код. Используйте SecureRandomисключительно. Тогда, по крайней мере, у вас будет небольшая гарантия того, что результат будет трудно предсказать. Если вам нужны свойства криптографически защищенного PRNG (в вашем случае это то, что вы хотите), то вам нужно только идти SecureRandom. Умение менять способ его использования почти всегда приведет к чему-то менее безопасному ...

выбивать
источник
4
Очень полезно, может быть, вы могли бы также объяснить, как работает SecureRandom (так же, как вы объясняете, как работает Random) ..
gresdiplitude
4
Это побеждает цель secureRandom
Azulflame
Я знаю, что выучил этот урок трудным путем. Но жесткий шифр и трудно найти источник работает хорошо. Нотч мог кое-что узнать об этом (он кодирует пароль своего пользователя в файле .lastlogin, закодированном с помощью обычного шифрования с использованием «passwordfile» в качестве ключа)
Azulflame
1
Настоящий вопрос здесь: если java может создавать более безопасный prng с аналогичным API, почему они просто не заменили сломанный?
Джоэл Коухорн
11
@JoelCoehoorn Это не то, что Randomсломано - его просто нужно использовать в разных сценариях. Конечно, вы всегда можете использовать SecureRandom. Но в целом SecureRandomзаметно медленнее, чем чистый Random. И есть случаи, когда вас интересуют только хорошие статистические свойства и отличная производительность, но вы не очень заботитесь о безопасности: моделирование по методу Монте-Карло является хорошим примером. Я комментировал это в похожем ответе , может быть, вы найдете его полезным.
выбить
72

Случайный имеет только 48 бит, тогда как SecureRandom может иметь до 128 бит. Так что шансы на повтор в безопасном случае очень малы.

Random использует в system clockкачестве начального числа / или для создания начального числа. Таким образом, они могут быть легко воспроизведены, если злоумышленник знает время, когда было создано семя. Но SecureRandom берет Random Dataот вас os(они могут быть интервалом между нажатиями клавиш и т. Д. - большинство собирает эти данные, хранят их в файлах /dev/random and /dev/urandom in case of linux/solaris) и использует их в качестве начального числа.
Так что, если маленький размер токена в порядке (в случае Random), вы можете продолжать использовать свой код без каких-либо изменений, так как вы используете SecureRandom для генерации начального числа. Но если вы хотите, чтобы токены большего размера (которые не могут быть предметом brute force attacks), используйте SecureRandom -
В случае случайных 2^48попыток просто необходимо, с современными процессорами можно разбить его на практике. Но для обеспечения безопасности 2^128будут необходимы попытки, которые потребуют годы и годы, чтобы обойтись даже с современными современными машинами.

Смотрите эту ссылку для более подробной информации.
РЕДАКТИРОВАТЬ
После прочтения ссылок, предоставленных @emboss, становится ясно, что семя, каким бы случайным оно ни было, не должно использоваться с java.util.Random. Очень легко рассчитать начальное значение, наблюдая за выходными данными.

Перейти на SecureRandom - использовать собственный PRNG (как указано в ссылке выше), потому что он принимает случайные значения из /dev/randomфайла для каждого вызоваnextBytes(), Таким образом, злоумышленник, наблюдающий за выводом, не сможет ничего разобрать, если он не контролирует содержимое /dev/randomфайла (что очень маловероятно)
. Алгоритм sha1 prng вычисляет начальное значение только один раз, и если ваша виртуальная машина работает в течение нескольких месяцев, используя то же самое seed, он может быть взломан атакующим, который пассивно наблюдает за выходом.

ПРИМЕЧАНИЕ. - Если вы вызываете nextBytes()быстрее, чем ваша ОС способна записать случайные байты (энтропию) в /dev/random, вы можете столкнуться с проблемами при использовании NATIVE PRNG . В этом случае используйте экземпляр SecureRandom SHA1 PRNG и каждые несколько минут (или некоторый интервал) заполняйте этот экземпляр значением изnextBytes()НАТУРАЛЬНОГО экземпляра PRNG SecureRandom. Параллельный запуск этих двух параметров гарантирует, что вы будете регулярно сеять с истинными случайными значениями, а также не исчерпывает энтропию, полученную операционной системой.

Ashwin
источник
Требуется намного меньше, чем 2 ^ 48, чтобы предсказать a Random, OP не должен использовать Randomвообще.
выбить
@ emboss: я говорю о грубой силе.
Эшвин
1
Будьте осторожны с Linux: он может достичь исчерпания энтропии (больше в ВМ, чем с аппаратным обеспечением)! Посмотрите /proc/sys/kernel/random/entropy_availи проверьте с некоторыми дампами потока, что нет слишком долгого ожидания при чтении на/dev/random
Ив Мартин,
2
Обратите внимание, что Oracle JRE (как минимум 1.7) по умолчанию работает с / dev / urandom, а не с / dev / random, поэтому суффикс вашего ответа больше не верен. проверить проверку $ JAVA_HOME / lib / security / java.security для свойства securerandom.source
Boaz
1
Наш файл java.security содержал securerandom.source = file: / dev / urandom вместо file: /// dev / urandom (две косые черты после двоеточия для файлового протокола, затем еще одна косая черта для корня файловой системы), что привело к его откату в / dev / random, что вызвало проблемы с исчерпанием энтропийного пула. Не удалось отредактировать его, поэтому пришлось установить системное свойство java.security.egd на правильное при запуске приложения.
maxpolk
11

Если вы бежите дважды java.util.Random.nextLong()с одним и тем же семенем, оно даст одинаковое число. По соображениям безопасности вы хотите придерживаться, java.security.SecureRandomпотому что это гораздо менее предсказуемо.

2 класса похожи, я думаю, вам просто нужно перейти Randomна SecureRandomинструмент рефакторинга, и большая часть вашего существующего кода будет работать.

Mualig
источник
11
Если вы берете два экземпляра любого PRNG и заполняете его одним и тем же значением, вы всегда получаете одни и те же случайные числа, даже использование SecureRandom не меняет этого. Все PRNG являются детерминированными и, следовательно, предсказуемыми, если вы знаете семя.
Роберт
1
Существуют различные реализации SecureRandom, некоторые являются PRNG, некоторые нет. С другой стороны, java.util.Random всегда PRNG (как определено в его Javadoc).
Петр Штибраны
3

Если изменение существующего кода является доступной задачей, я предлагаю вам использовать класс SecureRandom, как это предлагается в Javadoc.

Даже если вы обнаружите, что реализация класса Random внутренне использует класс SecureRandom. Вы не должны принимать это как должное, что:

  1. Другие реализации VM делают то же самое.
  2. Реализация класса Random в будущих версиях JDK все еще использует класс SecureRandom

Поэтому лучше следовать рекомендациям по документации и перейти непосредственно к SecureRandom.

Андреа Пароди
источник
Я не верю, что в первоначальном вопросе говорилось, что java.util.Randomреализация используется SecureRandomвнутренне, в нем говорится, что их код использует SecureRandomдля заполнения Random. Тем не менее, я согласен с обоими ответами до сих пор; Лучше всего использовать, SecureRandomчтобы избежать явно детерминированного решения.
Палпатим
2

Текущая эталонная реализация java.util.Random.nextLong()делает два вызова метода, next(int)который непосредственно предоставляет 32-битный текущий разряд:

protected int next(int bits) {
    long nextseed;
    // calculate next seed: ...
    // and store it in the private "seed" field.
    return (int)(nextseed >>> (48 - bits));
}

public long nextLong() {
    // it's okay that the bottom word remains signed.
    return ((long)(next(32)) << 32) + next(32);
}

Старшие 32 бита результата nextLong()являются битами начального числа в то время. Поскольку ширина начального числа равна 48 битам (говорит javadoc), достаточно * перебрать оставшиеся 16-битные значения (это всего лишь 65,536 попыток), чтобы определить начальное число, которое произвело вторые 32-битные значения.

Как только семя известно, все последующие токены могут быть легко вычислены.

Используя вывод nextLong()непосредственно, частично секрета PNG до такой степени, что весь секрет может быть вычислен с очень небольшим усилием. Опасные!

* Необходимы некоторые усилия, если вторые 32 бита отрицательны, но это можно выяснить.

Matt
источник
Верный. Посмотрите, как быстро взломать java.util.random на jazzy.id.au/default/2010/09/20/… !
здесь
2

Семя бессмысленно. Хороший генератор случайных чисел отличается выбранным основным номером. Каждый генератор случайных чисел начинается с числа и проходит через «кольцо». Это означает, что вы переходите от одного числа к другому со старым внутренним значением. Но через некоторое время вы достигаете начала снова и начинаете все сначала. Итак, вы запускаете циклы. (возвращаемое значение от случайного генератора не является внутренним значением)

Если вы используете простое число для создания кольца, выбираются все числа в этом кольце, прежде чем завершить полный цикл по всем возможным числам. Если вы берете не простые числа, выбираются не все числа, и вы получаете более короткие циклы.

Чем выше простые числа, тем больше циклов, прежде чем вы снова вернетесь к первому элементу. Таким образом, безопасный генератор случайных чисел просто имеет более длинный цикл, прежде чем снова достичь начала, поэтому он безопаснее. Вы не можете предсказать генерацию чисел так же просто, как с более короткими циклами.

Другими словами: вы должны заменить все.

никола
источник
0

Я постараюсь использовать самые простые слова, чтобы вы могли легко понять разницу между Random и secureRandom и важность класса SecureRandom.

Вы никогда не задумывались, как генерируется OTP (одноразовый пароль)? Для генерации OTP мы также используем класс Random и SecureRandom. Теперь, чтобы сделать ваш OTP сильным, SecureRandom лучше, потому что потребовалось 2 ^ 128 попыток, чтобы взломать OTP, что практически невозможно на нынешней машине, но если используется Случайный класс, тогда ваш OTP может быть взломан кем-то, кто может повредить ваши данные, потому что он потребовал просто 2 ^ 48 попробуй, взломать.

Сачин Патхак
источник