Являются ли Java случайным UUID предсказуемым?

Я хотел бы использовать криптографически безопасный первичный ключ для важных данных в базе данных - это не может быть предсказуемым/прогнозируемым и не может быть сгенерировано базой данных (мне нужен ключ до того, как объект будет сохранен).

Я понимаю, что Java использует UUID типа 4 с криптографически защищенным генератором случайных чисел, однако я знаю, что UUID не является полностью случайным, поэтому мой вопрос заключается в том, насколько безопасно предположить, что uuids нельзя предсказать из набора существующих

Ответ 1

Хорошо, если вы хотите знать, насколько случайным является UUID, вам нужно посмотреть на источник.

Следующий раздел кода взят из OpenJDK7 (и он идентичен в OpenJDK6):

public static UUID randomUUID() {
        SecureRandom ng = numberGenerator;
        if (ng == null) {
            numberGenerator = ng = new SecureRandom();
        }

        byte[] randomBytes = new byte[16];
        ng.nextBytes(randomBytes);
        randomBytes[6]  &= 0x0f;  /* clear version        */
        randomBytes[6]  |= 0x40;  /* set to version 4     */
        randomBytes[8]  &= 0x3f;  /* clear variant        */
        randomBytes[8]  |= 0x80;  /* set to IETF variant  */
        return new UUID(randomBytes);
    }

Как видите, только 2 из 16 байтов не являются полностью случайными. В шестом байте вы теряете 4 из 8 бит, а на байте 8 вы теряете 2 бита случайности.

Поэтому вы получите 128-битное значение с 122-разрядной случайностью.

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

Ответ 2

Я всегда думал, что "криптографически безопасный генератор случайных чисел" (фактически "криптографически сильный генератор псевдослучайных чисел" ) Javadoc замечает это.

http://download.oracle.com/javase/1,5.0/docs/api/java/util/UUID.html#randomUUID()

Из Википедии http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator такое предсказание будет неполиномиальным алгоритмом.

Если вам нужно что-то "истинно", а не просто "псевдо" случайным образом, вам нужно использовать что-то внешнее, генератор аппаратного шума, случайные точки, созданные после перемещения мыши,...

EntropyPool, похоже, помогает в этом, еще не пробовал http://random.hd.org/ То, как я это понимаю, позволяет загружать некоторый шум реального мира и использовать его в вашем приложении Java. Он не связан с java.util.UUID api, однако, вероятно, может быть подключен с использованием метода nameUUIDFromBytes (или другого?).

Было бы здорово, если бы вы сообщили нам, как вы решили пойти.

Ответ 3

Если вы хотите создать безопасный случайный ключ, я предлагаю вам использовать SecureRandom. Это может генерировать ключ любого количества бит, который вам требуется. Он медленнее, чем Random, но гораздо безопаснее.

Ответ 4

Если вы действительно хотите быть уверенным, что не будет абсолютно никакого столкновения, просто добавьте текущие миллисекунды с эпохи перед UUID-Строкой, например.

String id = System.currentTimeMillis() + "-" + UUID.randomUUID().toString();

Итак, чтобы иметь 50% вероятность столкновения за миллисекунду, вам нужно будет создать 2,71 квинтиллиона за одну миллисекунду, что очень, очень маловероятно!

Фактически, было бы относительно безопасно использовать некоторые из первых цифр UUID. Я проверил безопасность следующей строки:

String id = UUID.randomUUID().toString().substring(0, 6);

Я тестировал, сколько из этих строк мне нужно создать, чтобы получить столкновение. В среднем столкновение произойдет после создания порядка 5163 строк! Минимальное количество строк, которые мне нужно было создать для создания столкновения, было 53 (я тестировал его 100000 раз). Однако, если бы я хотел сделать тот же тест с строкой длиной 8, я бы даже не смог ее вычислить один раз (я дал ей 20мин времени).