Рейтинг:0

Каковы были бы преимущества быстрого ГПСЧ, который производит 8-битный вывод и может пройти тест PractRand на 1 петабайт?

флаг cn

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

Насколько важно, чтобы алгоритм мог пройти PractRand с указанными спецификациями?

fgrieu avatar
флаг ng
Создать PRNG, который выбрасывает байты, который может пройти тест PractRand на 1 петабайт и полное внутреннее состояние которого вычислить невозможно с вычислительной точки зрения, сделать ГПСЧ несложно, но он небезопасен для криптографических целей. Сделайте свой собственный вывод о том, что именно спрашивают.
Tunnel_Vision avatar
флаг cn
Спасибо за ваш отзыв! Какой еще статистический тест должен пройти? Например: NBT (Next Bit Test) достаточно?
poncho avatar
флаг my
«Какой еще статистический тест должен пройти?» - все они, включая тесты, разработанные с учетом дизайна вашего алгоритма...
SAI Peregrinus avatar
флаг si
Статистические тесты не могут показать, что ГСЧ безопасен, только то, что он не является явно ужасным. Они используются для тестирования реализации хорошо проанализированных проектов, а не для анализа безопасности проекта.
Рейтинг:2
флаг fr

Когда мы разрабатываем криптографический генератор случайных чисел, мы хотим, чтобы он прошел больше, чем просто статистические тесты. Золотым стандартом здесь является тест следующего бита, который говорит, что, учитывая все выходные данные до определенной точки, это лишь незначительно легче, чем даже угадать следующий бит. Это не статистический тест, а тест, подразумевающий, что злоумышленник обладает полным знанием алгоритма и способностью его криптоанализа, и все же не может найти лучшего решения, чем грубая сила.

Чтобы показать пример небезопасной CSPRNG, которая вполне может пройти любой статистический тест, но не пройдет проверку следующего бита, представьте себе секретное начальное число. $ С $, безопасная хэш-функция $ Н(х) $, и PRNG, который выводит $ H(S) || Н(Н(S)) || Н(Н(Н(С))) || ... $. Поскольку наша хеш-функция безопасна, ее вывод выглядит случайным, но на самом деле очень легко угадать следующий вывод, зная существующий вывод.

Конечно, вполне возможно создать CSPRNG, который выводит по одному байту за раз. RC4 — это потоковый шифр, который имеет такую ​​конструкцию и использовался как CSPRNG во многих системах, хотя он больше не считается безопасным. Мы вполне могли бы разработать другие CSPRNG, которые были бы безопасными и ориентированными на байты. Однако с практической точки зрения обычно более эффективно работать с большими блоками данных, поэтому такие алгоритмы, как ChaCha20 или NIST DRBG, как правило, используются чаще.

Что касается преимуществ быстрого некриптографического ГПСЧ, то причин для их использования немного. ChaCha20 может выводить данные со скоростью 3 ГБ/с в моей системе и криптографически безопасен. В маловероятном случае этого недостаточно быстро, можно было бы использовать меньшее количество раундов (например, ChaCha12), и производительность была бы выше, но при этом сохраняя криптографическую безопасность. Генерация случайных чисел с помощью подходящего алгоритма почти никогда не является узким местом, поэтому почти во всех случаях достаточно использования CSPRNG, который всегда проходит проверку следующего бита и, следовательно, имеет максимально возможное качество.

Paul Uszak avatar
флаг cn
Скорость не имеет отношения к реальной криптографии.
bk2204 avatar
флаг fr
Конечно, но в реальном мире это имеет значение, потому что люди используют скорость как предлог для использования небезопасных систем. Вот как мы заставляем людей использовать MD5: это быстро и «достаточно хорошо».

Ответить или комментировать

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