Используются ли теоретически обоснованные псевдослучайные генераторы на практике?

17

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

С другой стороны, теория сложности и криптография предоставляют очень богатую теорию псевдослучайности, и у нас даже есть подходящие конструкции псевдослучайных генераторов, которые могли бы обмануть ЛЮБОЙ эффективный статистический тест, который вы могли бы придумать, используя возможные односторонние функции-кандидаты.

Мой вопрос: эта теория нашла свое применение на практике? Я надеюсь, что для важных применений случайности, таких как криптография или научные вычисления, теоретически используются надежные PRG.

Кроме того, я мог бы найти ограниченный анализ того, насколько хорошо работают популярные алгоритмы, такие как быстрая сортировка, при использовании LSFR в качестве источника случайности, и, очевидно, они работают хорошо. См. Карлофф и Рагхаван "Рандомизированные алгоритмы и псевдослучайные числа" .

Генри Юн
источник
3
Есть даже универсальный PRG - это безопасно, если существуют безопасные PRG.
Вы имеете в виду криптографические PRG? Если так, то разве мы не знаем, что (криптографические) PRG эквивалентны OWF?
Генри Юн
2
Да. Разбейте битное начальное число на приблизительно блоки, каждый из которых приблизительно бит, запустите первых [количество блоков] машин Тьюринга на соответствующих блоках до шага дополняет выходные данные до битов и выводит xor этих выходных данных TM. (Точно так же, как универсальный поиск Левина, его нельзя использовать на практике.)КККК2К+1
1
может быть, более уместным для практики являются результаты, связанные со случайностью, необходимой для хеширования: от классических ограниченных семейств независимости до более поздних результатов, таких как Митценмахер-Вадхан (попарная независимость + некоторая энтропия во входных данных дает псевдослучайность, достаточную для линейного зондирования и фильтров Блума) или Патраску -Torup результаты хэширования таблиц.
Сашо Николов
1
«Тем не менее, эти методы используются без разбора во всех видах приложений, начиная от криптографических протоколов ...». Надеюсь нет. Твистеры Мерсенна не должны использоваться для криптографии, поскольку они не являются криптографически стойкими, хотя есть варианты, которые могут быть.
Майк Сэмюэл

Ответы:

13

Понятие «теоретически обоснованных» псевдослучайных генераторов не очень хорошо определено. В конце концов, ни у одного псевдослучайного генератора нет доказательства безопасности. Я не знаю, что можно сказать, что генератор псевдослучайных данных, основанный на сложности вычисления больших целых чисел, «более безопасен», чем, скажем, использование AES в качестве генератора псевдослучайных чисел. (На самом деле, есть ощущение, что он менее безопасен, так как мы знаем алгоритмы квантового факторинга, но не квантовые алгоритмы для взлома AES.)

У нас есть математические доказательства - это различные результаты композиции, говорящие о том, что если вы составляете блочные шифры или хэш-функции определенным образом, вы можете получить псевдослучайные генераторы или псевдослучайную функцию. Некоторые такие результаты широко используются на практике, например, HMAC . Но это правда, что результаты, которые достигают PRG и начинаются с предположения, что базовый компонент является простой односторонней функцией, недостаточно эффективны для использования в приложениях (и это, по крайней мере, частично присуще). Итак, обычно нам нужно принять PRG / потоковый шифр / блочный шифр / хэш-функцию в качестве базового примитива и начать строить из него другие вещи. Проблема не в асимптотическом анализе, поскольку по существу все криптографические сокращения (за исключением, возможно, универсальной PRG Левина) могут быть конкретизированы и, таким образом, давать конкретные гарантии при конкретных допущениях.

Но даже если они не основаны на односторонних функциях, в некотором смысле такие конструкции, как AES, «теоретически обоснованы», потому что: (1) существуют формальные предположения об их безопасности. (2) Есть работа, чтобы попытаться опровергнуть эти предположения, а также извлечь из них следствия.

И действительно, люди знают, что для многих приложений было бы неразумно использовать PRG, такие как LSFR, которые не удовлетворяют (1) и (2) выше.

Боаз Барак
источник
1
Полагаю, вы хотели разместить ссылку на одну из статей Джонатана Каца на его веб-странице. Кстати, вы хотели бы, чтобы мы слили это с другим вашим аккаунтом ?
Каве
9

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

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

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

Для криптографического использования люди стараются быть умнее. На этом этапе ваша критика имеет смысл: мы не можем знать, что конкретный используемый генератор псевдослучайных данных является «безопасным», и действительно некоторые старые были сломаны, например RC4, используемый в WEP. Однако по причинам, изложенным выше, использование теоретически (условно) звукового псевдослучайного генератора, к сожалению, не является реалистичным решением. Вместо этого криптологическое сообщество полагается на «экспертную оценку» - другие исследователи, которые пытаются «сломать» систему (их определение того, когда шифр взломан, очень широко).

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


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

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

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

Юваль Фильмус
источник
Спасибо за ваш ответ, Юваль. Однако я не совсем верю, что псевдослучайные конструкции генераторов из криптографии практически неэффективны. Насколько я вижу, никто не изучал это.
Генри Юн
2
Я также не согласен с общим утверждением, что стандартных псевдослучайных генераторов достаточно для «повседневных целей». Как показала недавняя статья «Рон был неправ, Уит был прав», дефектное псевдослучайное поколение привело к смущающим уязвимостям для значительного числа людей. Этот конкретный анализ был достаточно прост; Сколько приложений «реального мира» могут подвергаться более тонким уязвимостям, потому что LSFR не адекватны? Если дополнительные вычислительные затраты, необходимые для теоретически обоснованных PRG, не так уж и велики, почему бы не использовать их?
Генри Юн
1
@HenryYuen LSFR не используются для криптографических приложений в любой приличной, современной системе. (Конечно, существуют плохо спроектированные системы, такие как GSM, который преподается на вводных курсах, как не делать этого.) Проблемы, обнаруженные в статье «Рон был неправ, все верно», были не с качеством самих PRNG, но с качеством сбора энтропии.
Жиль "ТАК - перестань быть злым"