Пользователь
250,2
рейтинг
18 сентября 2011 в 18:38

Разработка → Как работает новый генератор случайных чисел Intel перевод



Представьте, что сейчас 1995 год и вы собираетесь совершить первую покупку в онлайне. Вы открываете браузер Netscape и прихлёбываете из чашечки кофе, пока главная страница медленно загружается. Ваш путь лежит на Amazon.com — новый онлайн-магазинчик, о которой рассказал вам друг. Когда наступает этап оформить покупку и ввести персональные данные, адрес в браузере меняется с «http» на «https». Это сигнализирует о том, что компьютер установил зашифрованное соединение с сервером Amazon. Теперь можно передавать серверу данные кредитной карты, не опасаясь мошенников, которые хотят перехватить информацию.

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

Проблема в том, что секретные ключи, которые использовал Netscape, были недостаточно случайными. Их длина составляла всего 40 бит, что означает около триллиона возможных комбинаций. Это кажется большим числом, но хакерам удалось взломать эти коды, даже на компьютерах 1990-х годов, примерно за 30 часов. Якобы случайное число, которое Netscape использовал для генерации секретного ключа, базировалось всего на трёх значениях: времени суток, идентификационном номере процесса и идентификационном номере материнского процесса — все они являются предсказуемыми. Из-за этого злоумышленник имел возможность сократить количество вариантов для перебора и найти нужный ключ гораздо раньше, чем предполагали в Netscape.

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

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

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

В течение последних лет в онлайне работает источник случайных чисел под названием Lavarand. Он был создан в 1996 году для автоматической генерации случайных значений путём обработки фотографий декоративного светильника — лавовой лампы, которая непредсказуемым образом меняет облик каждую секунду. С тех пор случайными значениями из этого источника воспользовались более миллиона раз.

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

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

Первая попытка Intel сделать лучший генератор случайных чисел на обычных ПК датируется 1999-м годом, когда компания Intel представила компонент Firmware Hub для чипсетов. Генератор случайных чисел в этом чипе (PDF) представляет собой аналоговый дизайн на базе кольцевого осциллятора, который регистрирует тепловой шум с резисторов, усиливает его и использует результирующий сигнал для изменения периода относительно медленного генератора тактовых импульсов. На каждый непредсказуемый «тик» этого медленного генератора микросхема накладывала частоту колебаний второго, быстрого генератора, который регулярно меняет своё значение между двумя бинарными состояниями: 0 и 1. В результате получается непредсказуемая последовательность нулей и единиц.

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

Вот почему в 2008 году Intel принялась за разработку генератора случайных чисел, который работает исключительно на цифровой основе. Исследователи компании в Хиллсборо (Орегон, США), совместно с инженерами Design Lab в Бангалоре (Индия) начали изучать ключевую проблему — как получить случайный поток битов без использования аналоговых схем.

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


НЕОПРЕДЕЛЁННЫЕ СХЕМЫ: Когда транзистор 1 и транзистор 2 включаются, пара инвертеров поворачивают узлы Node A и Node B в одинаковое положение [налево]. Если возрастает тактовая частота [жёлтый график справа], эти транзисторы отключаются. Первоначально оба инвертера обращаются в неопределённое положение, но случайный тепловой шум в инвертерах скоро поворачивает один узел в логическое положение 1, а другой узел — в логическое положение 0.

Дизайн состоит из пары инвертеров — элементов цепи, у которых значение на выходе является обратным значению на входе. Мы соединили выход одного инвертера со входом другого инвертера. Если на выходе у первого инвертера 0, то второй инвертер получает это на входе и, соответственно, выдаёт 1. Или если первый инвертер выдаёт 1, то второй инвертер будет выдавать 0.

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

Самое интересное начинается, когда транзисторы отключают. Двум инвертерам не нравится, что у них на выходах одинаковое состояние, и они стремятся принять противоположное положение, то есть одно из двух устойчивых состояний. Но какой инвертер поменяется на 0? Это неизвестно.

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

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

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

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

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

Нашей целью было создать систему, которая выдаёт поток случайных чисел, соответствующий признанным криптографическим критериям, таким как стандарты Национального института стандартов и технологий США. Чтобы гарантировать качество наших случайных чисел, мы разработали трёхступенчатый процесс, в котором задействованы первоначальная цифровая схема, «нормализатор» (conditioner) и генератор псевдослучайных чисел — теперь известный под кодовым названием Bull Mountain.

Наш предыдущий аналоговый генератор был способен выдавать только пару сотен килобит случайных чисел в секунду, в то время как новый генерирует их потоком около 3 Гб/с. Он начинает работу, собирая практически случайные значения двух инвертеров блоками по 512 бит. В дальнейшем эти блоки разбиваются на пары 256-битных чисел. Конечно, если оригинальные 512 бит не полностью случайны, эти 256-битные числа тоже не будут полностью случайными. Но их можно математически скомбинировать таким образом, чтобы получить 256-битное число, близкое к идеальному.


ТРИ УРОВНЯ ЧИСЕЛ: Генератор случайных чисел Intel Bull Mountain предотвращает любые варианты предсказуемости с помощью трёхступенчатого процесса. Сначала цифровой контур генерирует поток случайных битов. Потом «нормализатор» (conditioner) генерирует на основе этого потока хорошие случайные начальные значения (random seeds). На третьем этапе генератор псевдослучайных чисел выдаёт поток цифр для использования в программном обеспечении.

Всё это лучше показано на простой иллюстрации. Предположите на секунду, что генератор случайных битов выдаёт 8-битные комбинации, то есть как бы числа в диапазоне от 0 до 255. Предположите также, что эти 8-битные числа не полностью случайны. Теперь представьте, что, к примеру, какой-то неуловимый изъян в цепи смещает выдаваемые значения в нижнюю часть диапазона. На первый взгляд, поток случайных чисел кажется хорошим, но если вы обработаете миллионы значений, то заметите, что числа из верхней части диапазона встречаются немножко реже, чем числа из нижней части.

Одно из возможных решений этой проблемы простое: всегда берите пару 8-битных чисел, перемножайте их, а потом отбрасывайте верхние восемь бит из получившегося 16-битного числа. Такая процедура устранит перекос практически целиком.

Bull Mountain не работает с 8-битными числами: он работает, как уже было сказано, с 256-битными числами. И он их не перемножает, а производит более сложные криптографические операции. Но основная идея та же самая. Вы можете представить этот этап как «нормализацию» по устранению тех отклонений от случайного распределения чисел, которое может возникнуть в схеме с двумя инвертерами.

Нам действительно хочется хорошо спать по ночам, так что спроектировали дополнительную схему, которая проводит тестирование потоков 256-битных чисел, которые поступают в «нормализатор», чтобы они не были слишком смещёнными в какую-то сторону. Если такое обнаруживается, мы помечаем его как бракованный и не соответствующий стандартам. Таким образом, операции производятся только с качественными парами чисел.

Гарантированной случайности недостаточно, если случайные значения не выдаются достаточно быстро, чтобы соответствовать стандартам. Хотя аппаратный контур генерирует поток значительно быстрее, чем его предшественники, этого всё ещё недостаточно для некоторых современных задач. Чтобы Bull Mountain мог выдавать случайные числа так же быстро, как выдают поток программные генераторы псевдослучайных чисел, но при этом сохранять высокое качество случайных чисел, мы добавили ещё один уровень в схему. Здесь 256-битные случайные числа используются как криптографически надёжные начальные значения (random seeds) для генерации большого количества псевдослучайных 128-битных чисел. Поскольку 256-битные числа поступают с частотой 3 ГГц, то гарантируется достаточное количество материала для быстрой генерации криптографических ключей.

Новая инструкция под названием RdRand даёт возможность программе, которой нужны случайные числа, обратиться с запросом к аппаратному обеспечению, которое их производит. Созданная для 64-битных процессоров Intel, инструкция RdRand — это ключ к генератору Bull Mountain. Она извлекает 16-, 32- или 64-битные случайные значения и помещает их в регистр, доступный для программы. Инструкция RdRand была открыта для публики около года назад, и первым процессором Intel, который будет поддерживать её, станет Ivy Bridge. Новый чипсет работает на 37% быстрее, чем его предшественник, а размер его минимальных элементов уменьшен с 32 до 22 нанометров. Общее увеличение производительности хорошо сочетается с потребностями нашего генератора случайных чисел.

Хотя лавовые лампы выглядят круто, они впишутся не в каждый интерьер. Мы думаем, что наш подход к генерации случайных чисел, напротив, найдёт самое универсальное применение.

Как уже было упомянуто, регистрация точного времени нажатия на клавиши использовалась как удобный источник случайных стартовых значений для генераторов в прошлом. Для тех же целей использовали передвижения мыши и даже скорость поиска секторов на жёстком диске. Но такие события не всегда дают вам достаточное количество случайных битов, и при определённом времени измерений эти биты становятся предсказуемыми. Хуже того, поскольку мы теперь живём в мире серверов с SSD и виртуализацией, эти физические источники случайностей просто недоступны на многих компьютерах. На этих машинах требуется получать случайные числа каким-то другим способом, а не событиями на периферийных устройствах. Bull Mountain предлагает решение.

Так что если вы программист, будьте готовы к появлению обильного источника случайности прямо под рукой. И даже если вы не хотите отказываться от любимого генератора псевдослучайных чисел, который привыкли использовать для криптографии, научных вычислений или даже в играх — у вас теперь есть Bull Mountain для получения начальных значений к нему. Мы ожидаем, что такое применение Bull Mountain будет весьма популярным, в результате чего вырастут и расцветут разные виды замечательного софта.
Перевод: Greg Taylor, George Cox
Анатолий Ализар @alizar
карма
739,5
рейтинг 250,2
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (112)

  • +13
    Фактически они ускорили медленный, но хороший ГСЧ при помощи быстрого старого, доброго ГПСЧ, тем самым получив BM.

    ИМХО, я бы не стал использовать эту штуку где-нибудь у себя. Я хочу, чтобы мои программы работали везде, где только можно. RdRand не будет работать нигде, кроме как на новейших, пока еще не вышедших в продажу, Intell'овских процессорах.
    • +4
      Не спешите с выводами, возможно, вам понадобится серверная, криптографическая программка для одного и только одного из ваших проектов. Там, очевидно, логично и допустимо использование зависимой от платформы функции.
    • +3
      Ну как раз проблема «чтобы работало везде» легко снимается универсальным интерфейсом с подменным ГПСЧ (со стороны ОС). Тот же /dev/random, ну и аналоги в АПИ других ОС. А там, если идея действительно будет использовать, глядишь — и другие производители процессоров подтянутся, так что пару лет и аппаратные ГСЧ будут везде.
    • +1
      Ну так по идее это за нас должна делать ОС. Ждём поддержку этой фичи в /dev/random (и аналогичном виндовом API, который наверняка есть, но название которого мне не известно).
    • +10
      а что мешает сделать как-то так?

      function myrnd() {
      if($cpu == 'mega cool intel cpu')
      return intel_random_value();
      else
      return rand();
      }
      • –22
        PHP?
        • +18
          да не суть
        • +9
          Псевдокод.
      • –4
        • +2
          Астрологи объявили неделю кармадрочерства на хабре?
          Тем более, у Вас пока вполне достаточно. ;)
          • 0
            Да просто обидно получать минусы в карму, за вполне адекватный вопрос. :)
      • 0
        полиморфизм
    • +4
      Чем раньше начнёшь, тем раньше настанет мир во всём мире. HTML5 тоже казался несбыточной мечтой.
    • +1
      Пройдёт 8 лет… И вы уже не будете думать о поддержке вашего по такими старыми процессорами…
  • –6
    Спасибо за познавательную статью.
    • +22
      Никогда не понимал таких комментариев.
      Есть что сказать, чтобы другие почитали — пиши.
      Хочется сказать спасибо — поставь плюс.

      Такие комментарии, имхо, пишутся только ради того, чтобы другие читатели поддержали и поплюсовали вас.
      • +32
        Никогда не понимал таких комментариев.
        Хочется сделать замечание — напиши в хабрапочту.
        Нечего сказать, но просто не нравится — поставь минус.

        Такие комментарии, имхо, пишутся только ради того, чтобы другие читатели втянулись в холивар и слили кого-нибудь в минус.


        Если же по теме, то такие комментарии — альтернативный способ поблагодарить автора, когда плюсы, например, закончились.
        • –7
          Да пусть даже и холивар, если это уменьшит количество бесполезных комментариев.
          В данном случае, мы уже вступили =)
        • +1
          Интересно сколько + в этих 24 из тех 16. И испытывали ли плюсущие из пересечения муки совести?
        • –1
          Альтернативно поблагодарить — это занести в избранное. А написать «Спасибо» в комментариях — это спам.
      • +21
        Бывает иногда хочется похвалить человека теплым словцом, а не только безличным плюсом за топик :)
        • –5
          Хочется похвалить-хвалите, но не стоит писать спамо-подобное сообщение в качестве благодарности, что и было основным поводом для моего коммента.
          • 0
            «И чо?» (с).
  • –9
    Никогда не думал, что случайные числа — это так сложно!
    • +5
      Что вы, мне казалось все намного сложнее.
  • +7
    Генераторы нужны, но
    в результате чего вырастут и расцветут разные виды замечательного софта

    А без генератора они завянут, зачахнут и не расцветут ;-)
  • 0
    А разве в процессоре нет температурного датчика?
    • 0
      слишком медленно это
      • 0
        А если использовать датчик напряжения?
        • +1
          Под нагрузкой напруга стабильно-максимальная почти.
          • 0
            Ну дык мы будем брать несколько знаков после запятой, вряд ли она на столько постоянная.
            • 0
              Ну дык и не везде датчик вернет достаточно цыфр после запятой.
              • –3
                по-моему тогда дешевле сделать более точный датчик, чем изобретать новую технологию
                • 0
                  Они изобрели новую технологию с целью удешевить простейший аналоговый осциллятор. А вы предлагаете встраивать куда более дорогой прецизионный аналоговый прибор — АЦП!
            • 0
              В кустарных условиях берут младшие биты с микрофона.
              • +1
                А если выключен?
                • +1
                  throw MicrophoneException
                  • 0
                    То есть то, что случайное число так и не сгенерилось — не проблема? Зачем тогда вообще пытаться?
                    • 0
                      Не проблема. Будем знать что микрофон выключен или его нет. И как следствие — обратимся к иным источникам энтропии.

                      Всяко лучше, чем брать «случайные» биты с выключенного микрофона.
                      • 0
                        Я имел ввиду, а почему тогда сразу не обратиться к «иным источникам»?
                        К тому же, что делать, если микрофон просто нерабочий или в комнате слишком тихо, так что он часто просто не улавливает звуков вообще? Ну, или же не слишком качественный и часто возвращает одинаковые значения?
              • +1
                в промышленных условиях зашумленной серверной берут все биты с микрофона :)
      • +1
        В статье ведь шла речь (в том числе) про генераторы, способные создавать действительно случайные последовательности, им нужно только начальное значение (random seed). Как раз такое значение и может дать температурный датчик.
        • +2
          Слишком маленький разброс температур.
    • 0
      После чего все криптоаналитики будут выкладывать кирпичи от получаемых цифр?
  • 0
    Интересно, а как на такие генераторы влияют на температурные сдвиги? В принципе элементы вполне могут иметь несимметричную характеристику в зависимости от температуры. да и со временем они могут расходиться. Это, часом, не повлияет на «случайность»?
    • 0
      Инженеры же не дураки) Народ давно смекнул, что если транзистора размещать на подложке рядышком, то и температурный дрейф у них будет одинаковый. А вообще эта фича с «кто-кого перетянет» давно уже используется в КМОП аналоговой технике(усилители), так что странно, что в интеле только сейчас это сделали.
      • –1
        Ну, я не электронщик — этого не знал)
        Но я имел в виду немножко другое: используются два одинаковых элемента. Насколько они одинаковы? Если у них при температуре t1 одинаковая характеристика, то обязательно ли при t2 она будет тоже одинаковая?
        • 0
          Да, при Т2 характеристика тоже будет одинаковая. Вообще она одинаковая будет почти у всех транзисторов на кристалле :)
        • 0
          В статье написано что они придумали для этого, ну прочитайте же.
          • 0
            Чтобы соблюсти сбалансированность инвертеров, мы встроили механизм обратной связи
  • +3
    Оно лучше, чем /dev/random в линуксе? (Напомню, что в linux есть два штатных источника случайных чисел — один из них генерированный — /dev/urandom, второй — /dev/random, представляет из себя младшие биты времени асинхронных прерываний, такие как ввод с клавиатуры, прерывания от сетевой карты и жёсткого диска и т.д.; прерывания таймера по понятным причинам в этот список не включаются).

    Я не слышал, чтобы хоть кто-то говорил плохие вещи про /dev/random, единственная претензия — скорость.
    • –15
      А я вообще про линукс не слышал, не то что про /dev/urandom ;)
      • +2
        Господа, куда на этот раз провели интернет?
      • 0
        не тот факт, которым можно было бы хвастаться на хабре…
        • 0
          Теперь я знаю отличный сценарий для толстого вброса на лор.
          • 0
            Ну там всё просто. «Достаем двойные листочки, поля четыре клеточки» — и ЛОР-эксперты моментально преображаются.

            Как бы там ни было, я бы не стал ждать чудес от нового генератора, тем более, что мутная логика обработки сырых данных вполне может обладать согласованными с АНБ характеристиками.
    • 0
      Эта команда может использоваться /dev/random как ещё один источник случайных значений.
      • 0
        Я к тому, что эта штука меня смущает. Любая генерация ущербна по определению, потому что следующее число зависит от предыдущего (сколь бы там хитрый не был алгоритм).

        Если лет через 7 (когда эта инструкция станет стандартом де-факто) мы услышим, что какой-нибудь мудрый Вася нашёл метод ломания sha-чексум через использование неслучайности последовательности (из 256 бит сделать 64 — ну не подарок ли?), что делать будем?
        • 0
          > метод ломания sha-чексум через использование неслучайности последовательности (из 256 бит сделать 64 — ну не подарок ли?)

          Я вас не понял.
          • +2
            Если у нас в основе случайного числа лежит последовательность с seed, то вместо длинного числа мы можем ломать только seed, перебирая результаты применения последовательности.

            Если у нас random выдаёт 64 бита (и берёт 64 бита как seed), а мы делаем 256 бит из 4х последовательных чтений, то достаточно перебрать 2^64 seed'ов, чтобы получить все возможные комбинации 256-битной последовательности. Это очень серьёзная уязвимость. Даже если seed берётся рандомом, нам достаточно перебрать все варианты seed'а. Конкретные битности тут не важны — важен принцип, что часть значений зависит от предыдущих.
            • 0
              Именно поэтому в /dev/random подмешивается понемногу отовсюду.
              • +1
                В любом случае, если у нас есть наличие генерации, это ослабляет алгоритм. Собственно, именно упоминание генерации меня и смущает в этой фиче.

                Специализированные ГСЧ используются уже давно (обычно это USB/PCI устройства, типа «вьюги»), засунуть их в процессор идея правильная, однако, не с режимом генерации…
                • 0
                  А, теперь я вас понимаю. Пользовательская программа сгенерила число, затем ядро сгенерило число и подмешало в /dev/random, пользовательская программа рассчитала, какое число получило ядро.
                • 0
                  /dev/random — это не совсем генератор. Ядро копит энтропию (случайные битики) от внешних источников: клацания по клавиатуре, задержек сетевых пакетов и так далее. И от этого уже seed-ится генератор, который /dev/urandom, который пере-seed-ивается из /dev/random через определённые интервалы времени или количества выданных случайных байтов. Как-то так. Есть ощущение, что это вполне надёжно.
              • +1
                … и пользователю выдается блок данных в разы меньше размера внутреннего состояния (pool).

                От всего pool берется sha; затем полученный хеш примешивается к pool:

                «We mix the hash back into the pool to prevent backtracking attacks (where the attacker knows the state of the pool plus the current outputs, and attempts to find previous ouputs), unless the hash function can be inverted. By mixing at least a SHA1 worth of hash data back, we make brute-forcing the feedback as hard as brute-forcing the hash.»

                Затем к исходному хешу добавляется еще один блок данных из пула; затем хеш ополовинивается:

                hash[0] ^= hash[3]; hash[1] ^= hash[4];
                hash[2] ^= rol32(hash[2], 16);

                Дополнительно, ядро не позволяет получать слишком много случайных данных из /dev/random подряд без подмешивания в pool свежей энтропии.

                Т.о. знание «что часть значений зависит от предыдущих», дает мало преимуществ для ситуации, т.к. размер пула = 32*128 бит = 4 кбит — 512 байт больше объема данных, выдаваемых за один раз и больше объема данных, который может быть получен через /dev/random без добавления энтропии извне.

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

                Была описана атака www.cs.huji.ac.il/~reinman/presentations/LRNG.pdf — оценка сложности 2^96 — 2^64 для устройства, имеющего малое количество источников энтропии = openwrt. Тем не менее, это не перебор seed, а его предсказание для достаточно специфичного случая.
    • +2
      > единственная претензия — скорость.

      Она же самая существенная. Вы не поверите, десяток виртуалок с апачами на ssl выгребают весь пул рандома хост машины за секунды.
      • +1
        Повторю, я ничего не имею против переноса ssl-акселераторов из специализированных железок в процессор. Меня смущает только описание алгоритма, когда неудачи аппаратной генерации корректируют программно. Либо число рандомное, либо нет. Дальше это уже (в режиме доведения до абсурда):

        int get_random()
        {
        /* 
            return the random number
            it was generated by throwing a dice
        */
              return 4;
        }
        
        • 0
          Нас с коллегами тоже смутило описание корректора-нормализатора
          • 0
            Да весьма мутное описание, возможно оно упрощено для широкой публики.

            На мой взгляд было бы лучше постоянно подмешивать вывод блока инверторов в состояние ГПСЧ.
    • НЛО прилетело и опубликовало эту надпись здесь
  • +1
    Гм, кому может понадобиться поток случайных данных в 3 гб/с (или сколько там)?
    • +1
      модельные вычисления, заполнение массивов, например генерация картинок.
      Там довольно сильно тормозить будет.
      • 0
        Генерация картинок? Кому это нужна картинка состоящая из цветного шума? :-)

        И хотелось бы увидеть практический пример модельных вычислений или нужность больших массивов со случайными числами.

        Я с этим не сталкивался ни разу. :-)
        • +10
          Почему «цветной шум»? Простейшим математическим преобразованием линейное распределение превращается и в Гаусса и в Пуассона и во множество других. Где применяется? В ситуациях когда надо настроить алгоритм на обработку изображений, примеров которых мало или вообще нет. Например съёмка камерой со спутника. Для каждой орбиты/камеры, спектрального диапазона изображение будет весьма специфично. Построение изображения, которое потом будет обрабатываться требует значительного времени. Или в ситуации когда надо проверить алгоритм на работу в условиях сильных шумов, понять его границы, когда он разваливается. Берутся изображения из архива, для которых известно решение и на них накладываются шумы. Если хочется получить хорошую статистику — то это много тысяч тестов.
          Между прочем, псевдослучайный генератор в винде имеет неплохую периодичность (по крайней мере лет 6-7 назад имел). Если заполнить плоскость случайными значениями, то была видна полсасатость полученной плоскости.
          • 0
            Ага, спасибо :-)
        • +1
          Простой пример картинки, состоящей из цветного шума — распечатанная цветная фотография.
      • 0
        Кстати, для модельных вычислений лучше использовать свой ГПСЧ и сохранять seed, тк повторяемость результатов удобное свойство.
    • 0
      Любому серверу, который устанавливает много защищённых соединений. У меня есть пакет, конфигурирующий сервера. Там в ходе установки генерируются пароли/ключи, так вот, это довольно занудная процедура на две минуты. Если бы оно пролетало быстро, было бы мило. Но только если это настоящий рандом, а не последовательности.
    • 0
      В полиграфии, для стохастического растрирования, например.
    • 0
      Гм, кому может понадобиться поток случайных данных в 3 гб/с (или сколько там)?

      Покерные румы смотрят на вас с непониманием…
  • +2
    Все клево, только есть два но:
    1) Я бы не называл эту схему цифровой, т.к. в базе лежат явления аналоговой электроники
    2) Поиметь геморроя при производстве такой схемы можно, на мой взгляд, не меньше, чем с той, что они называют аналоговой.
    И даже
    3) Темное место здесь — «алгоритм обратной связи», с помощью которого выравнивается число 1 и 0. Тут можно крупно промахнуться…
    • +3
      1 — по большему счету вся цифра построена на аналоговой базе.

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

      2 — какой геморрой? схема целиком цифровая, типовые элементы.
      Ну кроме «переделки» инверторов, хотя это может быть типовой открытый коллектор…

      3) ну, в ЦК не дураки сидят, полетите ночью мне кажется, что инженеры Интела думают головой перед тем как запускать решение в серию…
      • +1
        Гонки в цифровых схемах рассматриваются как досаждающий фактор и в синхронных устройствах мало кого волнуют — лишь бы выполнялись временные требования. По большому счету, это все казуистика — одна и та же схема может рассматриваться и как цифровая (на макроуровне), так и как аналоговая (на микроуровне). И вот пока она пребывает лишь в состояниях 0 и 1 — она цифровая. Как только начинаем копать вглубь и ловить промежуточные напряжения — она становиться аналоговой. ИМХО, конечно.
        Ну а по последнему пункту — будем надеяться.
  • 0
    А мне нравится идея с приемом шумов из внешнего мира через АЦП микроконтроллера. Предварительно можно усилить сигнал. На выходе непредсказуемая комбинация.
    • 0
      Во-первых неодинаковая полоса пропускания приведет к тому, что часть шумов будет иметь больший уровень
      Во-вторых весьма вероятно, что будут какие то регулярные шумы
  • 0
    Мне всегда было интересно, насколько в среднем случайны числа, получаемые при помощи движений мышкой (этого часто требуют программы, связанные с генерацией ключей), т.е. я понимаю, что все зависит от пользователя, но все таки?
    • +1
      Эти значения используются не целиком, а младшие биты. Для мыши учитываются:

      1) Младшие биты (допустим, 2) координат (итого 4 бита)
      2) Младшие биты (аналогично, 2) задержки между позиционированием мыши.

      Для лучшей непредсказуемости нужно использовать младший бит.
  • +4
    Напомнили анекдот времён Фидо.
    Два программиста:
    «У тебя есть генератор случайных чисел?»
    Второй не поворачиваясь,
    "-137".
  • 0
    Поясните, пожалуйста, насколько безопасно это «усреднение», откидывание крайних значений?
    Получается, что, если взять числа от 0 до 255, то 0 и 255 будут выпадать значительно реже вероятности их выпадения?
  • 0
    У меня где-то была древняя карточка, с радиоактивным веществом, которая генерила всегда псевдослучайные числа, такой метод используется стопицот лет во всех серьезных системах, что там интел изобрела нового я не понимаю.
    • +1
      встроили карточку в процессор.
  • +1
    А нельзя ли поставить маленькую антенну и ловить электромагнитные помехи вроде тех, что на экране телевизора при ненастроенном канале?
    • 0
      Станислав Лем. «Голос неба». Можно даже за хау-то взять.
    • +2
      Подходим к знанию конкурента, врубаем передатчик, через день ломаем пароли.
    • +1
      А потом поймать Маяк и привет
      • 0
        Если поймана радиостанция, то переключаться на другой «пустой канал».
        Алгоритм поиска пустого канала это инвертированный алгоритм поиска радиостанций из любой магнитолы с автосканированием.
        • 0
          Это же шутка, с долей правды =)
          Примерно как: От Маяка так просто не отключиться
          • +2
            Любой начинающий радиотехник знает, что самое сложное — избавиться от приёма «Маяка».
    • +1
      Так уже.
      Почитайте что-такое random radio. USB долгл с радиоприемником, использующим радиоволны для генерирования случайных чисел… Ну или random sound, делающий тоже самое используюя звуковую карту и помехи на ее аналоговых цепях.
    • +1
      можно — так работает random.org
      • 0
        Эх, ещё одна моя гениальная идея отличного стартапа оказалась перечёркнута с подписью «уже реализовано»…
        • 0
          Довольно простенький, я думаю, можно сделать круче.
  • +8
    К счастью, несложно получить действительно непредсказумые значения, используя хаотическую вселенную, которая со всех сторон окружает строго детерминированный мир компьютерных битов.

    На этой фразе мне показалось что я читаю «Автостопом по галактике» Дугласа Адамса :)
    • 0
      Вот оно что, никак не мог впомнить, что мне напомнила эта же фраза.
  • +4
    А пароли всё равно qwerty и q1w2e3r4!
  • +1
    Меня одного смущает картинка для привлечения внимания, где как-бы из строго случайных битов сложилась вполне себе детерминированная надпись?
  • +7
    >спроектировали дополнительную схему, которая проводит тестирование потоков 256-битных чисел, которые поступают в «нормализатор», чтобы они не были слишком смещёнными в какую-то сторону. Если такое обнаруживается, мы помечаем его как бракованный и не соответствующий стандартам.

    Во всем известной книжке «Криптономикон» в Блечтли-парке бабушки доставали буквы из лотерейного барабана (и возвращали назад), и записывали букву в шифроблокнот.

    Когда им «казалось», что буква не случайна, они возвращали букву в барабан без записи в шифроблокнот.

    Это сформировало дырку в случайности, которой враги сумели воспользоваться.
  • +2
    Не имея возможности заглянуть внутрь процессора и посмотреть, не заложена ли туда спец функция для облегчения жизни всякого рода спецслужбам, предпочитаю использовать мегапараноидальный FortunaGenerator от того же Шнайера. Пока что единственный генератор, глядя на который моё артериальное давление понижается, а не наоборот.
    • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    Было бы интересно посмотреть результаты тестов ГСЧ для такого генератора.
  • 0
    Помнится была успешная атака на их генераторы через генераторы ЭМ-шума. причём атака совсем упрощалась, если шифрующий чип охлаждали.

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