Есть ли законное использование для Intel RDRAND?

Сегодня я подумал: хорошо, даже если есть серьезные подозрения относительно реализации NIST SP 800-90A в RDRAND, это все же аппаратная реализация генератора псевдослучайных чисел (PRNG), которая должна быть достаточно хороша для нечувствительных приложений. Поэтому я подумал об использовании его в своей игре вместо Mersenne Twister.

Итак, чтобы увидеть, был ли какой-либо выигрыш в производительности при использовании инструкции, я сравнил время двух следующих кодов:

// test.cpp
#include <cstdio>

int main()
{
    unsigned int rnd = 0;
    for(int i = 0; i < 10000000; ++i) {
        __builtin_ia32_rdrand32_step(&rnd);
    }
    printf("%x\n", rnd);
}

а также

//test2.cpp
#include <cstdio>
#include <random>

int main()
{
    unsigned int rnd = 0;
    __builtin_ia32_rdrand32_step(&rnd);
    std::mt19937 gen(rnd);
    for(int i = 0; i < 10000000; ++i) {
        rnd ^= gen();
    }
    printf("%x\n", rnd);
}

и запустив два я получаю:

$ time ./test
d230449a

real    0m0.361s
user    0m0.358s
sys     0m0.002s

$ time ./test2 
bfc4e472

real    0m0.051s
user    0m0.050s
sys     0m0.002s

Итак, Mersenne Twister намного быстрее, чем RDRAND на моем процессоре. Ну, я был разочарован, исключен из моей игры. Но RDRAND - это криптографически безопасный PRNG (CSPRNG), поэтому он делает многое за кулисами... более справедливо было бы сравнить его с другими CSPRNG. Поэтому я взял свою реализацию Rabbit (простой перевод RFC на C, никаких хитростей для повышения производительности) и написал следующий тест:

// test3.cpp
#include <cstdio>

extern "C"
{
#include "rabbit.h"
}

int main()
{
    rabbit_state s;
    unsigned long long buf[2];
    __builtin_ia32_rdrand64_step(&buf[0]);
    __builtin_ia32_rdrand64_step(&buf[1]);
    rabbit_init_key(&s, (uint8_t*)&buf[0]);

    for(int i = 0; i < 10000000; ++i) {
        rabbit_extract(&s, (uint8_t*)&buf[0]);
    }
    printf("%llx\n", buf[0]);
}

И к моему удивлению, генерируя вдвое больше псевдослучайных данных, чем первые два из них, я получил лучшее время, чем RDRAND:

$ time ./test3 
8ef9772277b70aba

real    0m0.344s
user    0m0.341s
sys     0m0.002s

Все три были скомпилированы с включенной оптимизацией.

Итак, у нас широко распространена паранойя о том, что RDRAND был создан для того, чтобы встроить бэкдоры АНБ в криптографию программного обеспечения для всех. Также у нас есть по крайней мере одно программное CSPRNG быстрее, чем RDRAND, и наиболее широко используемый приличный PRNG, Mersenne Twister, намного быстрее, чем RDRAND. Наконец, у нас есть пулы энтропии программного обеспечения с открытым исходным кодом, такие как /dev/random а также /dev/urandom, которые не спрятаны за двумя слоями скремблера AES, как RDRAND.

Итак, вопрос: должны ли люди использовать RDRAND? Есть ли законное использование для этого? Или мы должны вообще перестать его использовать?

6 ответов

Решение

Как отметил Оулстед, RDRAND засеян с истинной случайностью. В частности, он часто повторно устанавливает свой внутренний CSPRNG со 128-битной аппаратной случайностью, гарантируя повторное заполнение, по крайней мере, один раз каждые 511 * 128 бит. Смотрите раздел 4.2.5 этого документа:

https://software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide

Итак, в ваших примерах вы использовали один 128-битный начальный номер для генерации 10 миллионов случайных отрисовок из rabbit_extract. В версии RDRAND у вас был эквивалент 2,5 миллионов 128-битных отрисовок, что означает, что CSPRING был повторно заполнен как минимум 2 500 000/511 = 4 892 раза.

Таким образом, вместо 128 бит энтропии, входящей в ваш пример с кроликом, в примере RDRAND было по меньшей мере 4,892 * 128 = 626,176 бит энтропии.

Это намного больше энтропии, чем вы получите за 0,361 секунды без поддержки оборудования. Это может иметь значение, если вы делаете вещи, в которых важно много реальной случайности. Одним из примеров является секретный обмен Шамиром больших объемов данных - не уверен, есть ли другие.

Итак, в заключение - это не для скорости, это для высокой безопасности. Вопрос о том, является ли он закулисным, беспокоит, конечно, но вы всегда можете XOR сделать это с другими источниками, и, по крайней мере, это не повредит вам.

RDRAND это не просто PRNG. Это отбеленный TRNG, который соответствует FIPS. Разница в том, что вы можете положиться на RDRAND содержать довольно много фактической энтропии, непосредственно полученной из процессора. Так что основное использование RDRAND заключается в предоставлении энтропии для ОС / библиотек / приложений.

Единственный другой хороший способ для приложений извлечь энтропию - это использовать предоставленный операционной системой источник энтропии, такой как /dev/random или же /dev/urandom (который обычно привлекает энтропию из /dev/random). Однако эта ОС также требует где-то найти энтропию. Обычно для этого используются крошечные различия во времени доступа к диску и сети (+ другой полуслучайный ввод). Эти устройства не всегда присутствуют и не предназначены в качестве источников энтропии; они часто не очень хорошие источники и не очень быстрые. Так что в системах, которые его поддерживают, RDRAND часто используется в качестве источника энтропии для криптографически безопасного генератора случайных чисел операционной системы.

Что касается скорости, особенно для игр, вполне допустимо использовать (небезопасный) PRNG. Если вы хотите получить разумное случайное семя, посеять его с результатом RDRAND может быть хорошей идеей, хотя заполнение его из поставляемой ОС RNG может быть более портативным и даже более безопасным вариантом (в случае, если вы не полностью доверяете Intel или США).


Обратите внимание, что в настоящее время RDRAND реализован с использованием (AES) CTR_DRBG вместо (менее хорошо проанализированного) потокового шифра, который был создан для такой скорости, как Rabbit, поэтому неудивительно, что Rabbit быстрее.

Есть ли законное использование для Intel RDRAND?

Да.

Рассмотрим симуляцию Монте-Карло. У него нет криптографических потребностей, поэтому не имеет значения, если он замаскирован АНБ.


Или мы должны вообще перестать его использовать?

Мы не можем ответить на это. Это стечение вариантов использования, требований и личных предпочтений.


... Также у нас есть как минимум одно программное обеспечение CSPRNG быстрее, чем RDRAND, и наиболее широко используемый приличный PRNG... "

Mersenne Twister может быть быстрее для слова в момент времени после инициализации и без Twists, потому что он возвращает слово из массива состояний. Но я сомневаюсь, что это так же быстро, как RDRAND для непрерывного потока. Я знаю, что RDRAND может достичь теоретических ограничений на основе ширины шины в непрерывном потоке.

По словам Дэвида Джонстона из Intel (который разработал схему), это что-то вроде 800+ МБ / с. См. Ответ диджея на Какова задержка и пропускная способность инструкции RDRAND на Ivy Bridge?,


Итак, у нас широко распространена паранойя о том, что RDRAND был создан для того, чтобы встроить бэкдоры АНБ в криптографию программного обеспечения для всех.

У параноиков есть как минимум два варианта. Во-первых, они могут отказаться от использования RDRAND и RDSEED. Во-вторых, они могут использовать выходные данные RDRAND и RDSEED для заполнения другого генератора, а затем использовать выходные данные второго генератора. Я считаю, что ядро ​​Linux использует второй подход.

Здесь есть статья по исследованию астрофизики ( http://iopscience.iop.org/article/10.3847/1538-4357/aa7ede/meta;jsessionid=A9DA9DDB925E6522D058F3CEEC7D0B21.ip-10-40-2-120), (не платная) версия здесь ( https://arxiv.org/abs/1707.02212), которая дает законное использование для RdRand.

В нем рассматривается влияние RdRand на симуляторе Монте-Карло, как было рекомендовано в предыдущем посте. Но автор не обнаружил каких-либо статистических различий в результатах, которые используют или не используют RdRand. С точки зрения производительности, похоже, что Mersenne Twister намного быстрее. Я думаю, что в разделах 2.2.1 и 5 есть все детали.

Истинная случайность против псевдослучайности.

rdrand - это аппаратный источник истинной энтропии, притом довольно мощный (к тому же он не эксклюзивен для Intel - AMD предлагает то же самое - почему тогда вы выделяете Intel? ну, я концентрируюсь на реализации Intel, поскольку они предлагают немного больше информации и имеют гораздо более высокую пропускную способность по сравнению даже с Zen2 [ryzen 3xxx])

Забудьте о пропускной способности clockcyle- здесь эта метрика вводит в заблуждение, поскольку на самом деле она не связана. Пропускная способность ограничена двусторонней задержкой для одного потока и фактической аппаратной реализацией, работающей на частоте 800 МГц, имеет фиксированные 8 циклов и может выдавать 64-битное случайное значение за транзакцию. Если посмотреть только на тактовые циклы, выполняемые потоком, выполняющим код, будет очень зависеть от текущей тактовой частоты - на холостом ходу на 800 МГц это было в 6 раз быстрее, чем при работе на 4,8 ГГц. Но задержка между ядрами и DRNG находится в порядке задержки между ядрами, и у вас это дважды, поэтому около 80 нс - с результатами примерно 12 МГц при 8 байтах => ~100 МБ / с / поток и максимум 800. МБ / с.

еще одно преимущество этого: он не использует ресурсы ЦП, как большинство ГПСЧ, поэтому, хотя другие генераторы могут иметь немного более высокую пропускную способность (на 1-2 порядка), им также требуется больше ресурсов. В ситуациях, когда вам нужно много случайных чисел и вы находитесь в жестком вычислительном цикле, rdrand может действительно дать лучшую производительность, но это, конечно, сильно зависит от точного сценария и оборудования.

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

По поводу лазеек АНБ. При разработке логики DRNG я уклонился от бэкдоров:

  1. Двойной EC-DRNG. Очевидно, это было глупо еще до утечки информации о Сноудене. Я использовал CTR-DRBG, который имеет независимо проверенные свойства безопасности и является наиболее эффективным и поддающимся защите от атак по времени и атак по побочным каналам.
  2. ДФ СП800-90А. Вероятно, это черный ход. Посмотрите на основную конструкцию и на способность вытягивать больше энтропии, чем можете вложить.
  3. FIPS140-2 CRNGT. Задняя дверь, снижающая энтропию. ISO удалил его из ISO/IEC 19790-2012, который является ISO-версией FIPS140.

Итак, три задних двери увернуты по цене одной. Однако только один из них присутствует в общественном сознании как черный ход. Пожалуйста.

Другие вопросы по тегам