Fortuna: генератор случайных чисел для параноиков


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

    Если у вас такого устройства нет, то прошу под кат.

    Итак, вам постоянно нужны хорошие случайные данные. Для генерации ключей шифрования, соли, паролей, не важно. Важно их качество.

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

    Поэтому, логично периодически этот ГПСЧ заново инициализировать новым, хорошим, случайным числом.
    Получается, чтобы генерировать хорошие случайные числа, нам нужны хорошие случайные числа. Круг замкнулся.

    Шум


    Или, говоря более строгим языком, источник энтропии. Конечно, в идеале он должен быть физической природы, но в среде выполнения ПО их тоже хватает. Не таких хороших, конечно, но тем не менее.
    Грубо говоря, любые изменяемые во времени данные могут служить источником шума. Например:
    • Входящие/исходящие запросы\сообщения
    • Состояние ОС (объем свободной памяти\загрузка CPU)
    • текущие координаты мыши
    • различные счетчики
    • текущий снимок экрана


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

    Если вы ограничены в источниках энтропии, то вот вам рецепт как подсобрать её почти на пустом месте:

    1. Запускаем отдельный поток, в котором в бесконечном цикле инкрементим целочисленную переменную
    2. Раз в миллисекунду смотрим из другого потока на её последний бит и сохраняем (не мешая ей инкрементиться)
    3. Через 1 сек у вас есть ~1000 бит энтропии неплохого качества

    Можно варьировать количество бит, которые вы забираете из этой переменной раз в миллисекунду. Качество энтропии будет обратно пропорционально количеству взятых бит, но зато скорость её генерации будет в количество бит выше.
    Так же, можно ждать больше чем 1 мсек, тогда влияние побочных процессов на этот доставаемый последний бит будет еще больше, а соответственно, качество его «случайности» улучшится.

    Минусы у такого генератора очевидны:
    • Очень низкая скорость генерации.
    • Полная загрузка одного из ядер процессора на время работы

    Но он неплохо подходит на роль «seedирующего» для более быстрых товарищей по цеху.

    Fortuna


    Итак, у нас есть какое то количество источников энтропии, что с ними делать?

    Постоянно кормить ими ГПСЧ

    Такой ГПСЧ называется continuously-seeded pseudo-random number generator. и Fortunа за авторством товарищей Шнайера и Фергюсона является замечательным представителем такого генератора.

    Она состоит из двух уровней.
    1. Пулы энтропии
    2. Внутренний генератор


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

    Чтобы было проще представить, эти 32 хэша до поры до времени как будто хэшируют большие большие- прибольшие файлы и никак не дохэшируют. Выделенное жирным важно, далее будет объяснение

    То есть, пришло вам новое сообщение/запрос, вы его отдали фортуне, она попросила пул №1 его обработать.
    Сгенерировали несколько байт генератором описанным выше, тоже туда же, она уже отдала их второму.
    И так далее.

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

    И так, у нас есть 32 откормленных пула, что дальше?

    Сначала немного про

    Внутреннюю Монголию Внутренний генератор


    Он представляет из себя блочный шифр (AES, например) и счетчик(число, размером с блок AES, увеличивающееся на 1 каждый раз когда кто то просит новые данные). То есть, задача счетчика просто в том, чтобы каждый раз шифровались разные данные.
    Не важно какие, их всё равно шифруют случайным ключом.
    Этот генератор фактически и есть та штука, которая выдает наружу случайные данные, которые получаются путём шифрования счетчика случайным ключом.
    При этом, каждый раз когда мы просим у него очередную порцию случайных данных, он генерирует немного больше чем нужно, а излишек используя как новый ключ шифрования для себя самого.

    Т.е., например попросили мы у генератора 100 байт, он сгенерировал 116, отдал нам 100, а 16 (128 бит) использовал как новый ключ шифрования для блочного шифра.

    При этом счетчик не обнуляется, а каждое следующее его значение шифруется разными ключами.

    In the mix


    Откуда берется самое первое значение ключа шифрования для генератора и как работает система пулов?

    Изначально внутренний генератор инициализируется внешними данными, как и все обычные генераторы. Тут никакого волшебства.

    Но когда количество байт, обработанных пулом(хэшем) под номером 1 превышает некоторый порог (64 байта), начинается самая красивая часть алгоритма.

    Fortuna ведет счет таким срабатываниям. Называются этот счетчик Reseed Count и обозначает «Сколько раз мы сменили ключ шифрования внутреннего генератора?»

    От текущего Reseed count зависит набор пулов, которые будут участвовать в генерации нового ключа шифрования

    Поскольку пулов у нас 32, то «степень их вовлеченности» зависит от того, до какой степени двойки добрался Reseed count.

    Первый пул используется каждый раз.
    Второй — если остаток от деления Reseed count на 2 равен нулю
    третий — если остаток от деления Reseed count на 4 равен нулю
    и.т.д

    То есть, чем выше номер пула, тем реже он используется и дольше накапливает энтропию. 32й пул отдаст свою только через 2^32 операций reseed.

    Reseed


    Итак, пришло время сменить ключ шифрования у внутреннего генератора.
    Мы, наконец, финализируем хэши тех пулов, которые участвуют в текущем Reseed. Получаем массивчик байт размером количество участвующих пулов*количество байт хэша.
    И отдаём его внутреннему генератору.
    Генератор эти все байтики берет, туда же подмешивает текущий свой ключ шифрования (который, как мы помним, меняется каждый раз после генерации данных), тоже всё хэширует и этот хэш использует как новый ключ шифрования для себя.

    Всё.

    Нафига всё это?


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

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

    Дополнительно


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

    На этом всё, спасибо за внимание.

    P.S. реализаций всяких много, вот например на жаве, используется любимый BouncyCastle:
    searchcode.com/codesearch/raw/16881031
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 43

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

      И выкладывать эти данные в сеть. Их может использовать любой желающих.
        +8
        такое уже есть www.random.org/
          +1
          Ну так это будет генератор для параноиков :) (хотя не знаю, по какому принципу там рабтает рандом...)
            0
            Насколько я помню, он слушает радио волны на определëнных частотах. (не раскрываются).
            У них на сайте написано.
              0
              Для параноиков — квантовый генератор.
            +5
            > На солнечном берегу моря где-нибудь в районе диких пляжей Бали, установить устройство, оцифровывающее выход с очень чувствительного микрофона.
            А потом некий параноик запишет пару лет этого шума, проанализирует — и обнаружит, что он с точностью 99.9% представляет собой сумму каких-нибудь трехсот периодических функций.
              –1
              и это вполне возможно — рандом может выдать и 50 подряд 1ц, и 5 миллионов единиц подряд.
              и он будет рандомом — если он честный рандом
                0
                Шум тоже можно прогонять через хэш
                  0
                  Хэш периодической функции — тоже периодическая функция.
                    +1
                    Ок, я понял, что вас не удовлетворяет шум моря как источник энтропии )
                +1
                До тех пор, пока сайт, выкладывающий данные, не окажется скомпрометирован и не начнет выкладывать данные, нужные Большому Брату.
                  0
                  Если открыть эти данные, число перестанет быть случайным, т.к. известно время запроса.
                  +4
                  Спасибо за интересную статью.
                  У меня вопрос появился. Так как при накоплении достаточной энтропии происходит постоянное обновление внутреннего ключа, значит если скормишь один и тот же seed получатся разные последовательности? Получается fortuna нельзя использовать в качестве классического поточного шифра?
                    +4
                    И не только Фортуну, но и вообще любой генератор случайных чисел, использующий дополнительные источники энтропии.
                      0
                      Я бы вообще не стал поточные использовать, на примере того же RC4 все вскрывали на раз при дурной реализации криптосистемы. И даже без ключа.
                        +1
                        Есть хорошие поточные шифры, тот же HC-128 например, и вообще все финалисты проекта estream. У них своя ниша, надо просто знать что где использовать
                          0
                          Несомненно! Мне поточные кажутся более чувствительными к косякам их использования. Да и привык уже к AES.
                            0
                            AES (да и любой другой блочный шифр) в режиме CTR становится поточным (:
                      –1
                      И я все-таки не понял, почему хэши не финализируются. При финализации добавляется длина данных и куча нулей, вряд ли это существенно испортит качество хэша. Единственный довод, который вижу — уменьшение времени выполнения.
                      Шифрование блочным шифром постоянно увеличивающегося счетчика — основная часть CTR-режима работы блочного шифра.

                      У меня возника идея: а зачем пулы, зачем усложнять? Берем какой-то даже поганый источник энтропии, хоть бы и системное время. Хэшируем, и используем как ключ для того же AES в том-же CTR-режиме. В отдельном потоке он будет с какой-то периодичностью лопатить, сохраняя последний блок. Как только приходит запрос — отдаем последний сохраненный блок, если не хватило — генерим следующий блок. Запросы на случайные данные будут приходить в случайные моменты времени, то есть чтобы их «угадать» придется от души попроматывать AES-CTR. Умножаем количество проматываний на число «разумных» с точки зрения атакующего значений системного времени при инициализации и получаем очень большое число :-) Дополнительно можно на каждом n-ном проходе шифра ксорить ключ с предыдущим результатом работы шифра и генерить новый блок для выдачи наружу.
                        0
                        Хэши финализируются когда приходит их время, т.е. когда мы сливаем пулы во внутренний генератор. После этого накапливают энтропию заного
                          0
                          Хм… Ну ладно. Финализация, IMHO, там тоже не нужна :-)
                            +1
                            Внутреннее состояние хэша != хэш. Там же внутри может быть все что угодно в каком угодно виде. Ну и после того как мы отдали энтропию генератору, она в этом пуле больше не имеет смысла, так что финализация тут само то)
                              +1
                              Как делается финализация в MD5 и ripeMD128: к данным подмешивается длина данных и куча нулей, причем при помощи HashUpdate, который же применяется для хэширования самих данных. Потом в ripeMD128 внутреннее состояние выплевывается в результат, БЕЗ преобразований, так что состояние хэша и есть хэш. Я уверен, что в MD5/SHA1 и других ripe-хэшах все делается также.
                                +2
                                Благодаря этим нулям и отсутствию преобразования, кстати, md5 сотоварищи уязвимы к length extension attack
                                А SHA-3 нет ) и там всё по другому
                            +2
                            Заново :)
                              0
                              Да, пожалуй хватит на сегодня печатать.
                            0
                            Видимо, потому что источник энтропии может оказаться слишком поганым, в результате чего хакеру окажется слишком легко угадать ключ. А дальше он может взять один сгенерённый блок, расшифровать его всеми ключами, которые он посчитает наиболее вероятными, и таким образом получить набор возможных значений счётчика. Инкрементируя эти значения счётчика и зашифровывая их соответствующими им ключами он получит набор следующих блоков «случайной» последовательности, среди которых с большой вероятностью окажется правильный (если разом было запрошено больше одного блока данных). Таким образом он узнаёт ваш ключ.
                            Дальше аналогичным образом имея i-ый блок он сможет узнать соответствующее ему значение счётчика и восстановить i+1, i+2,… блоки, если они были запрошены разом. Причём скорость восстановления блоков, запрошенных подряд, будет такой же, как и скорость их генерации. Если они были запрошены с небольшим интервалом, то он может поперебирать счётчик от полученного значения.
                            0
                            На солнечном берегу моря где-нибудь в районе диких пляжей Бали, установить устройство, оцифровывающее выход с очень чувствительного микрофона.

                            А если вместо солнца будет идти дождь?
                              0
                              К вашему сведению, микрофон, даже очень чувствительный, не реагирует на солнце (по крайней мере на расстоянии 1 а. е.). А шумный дождь только повысит энтропию.
                              –9
                              Может не по теме, но когда в университете я изучал c++ — нам преподаватель показал как генерировать случайное число. Сам способ уже не помню, но смысл был в том, что число было random'ное, но одинаковое все время — меня это сильно напрягало.
                                0
                                Скорее всего это был какой-то из стандартных детерменированных генераторов псевдослучайных чисел. Может быть, линейный конгруэнтный метод.
                                  +6
                                  способ был такой

                                  int getRandomNumber() { return 4; }
                                    0
                                    Отличный сарказм
                                    • UFO just landed and posted this here
                                    +1
                                    Скорее всего оно просто было инициализировано одним и тем же сидом. Помню в Бейсике рандом выдавал случайные числа, а в Паскале каждый раз одну и ту же последовательность. Потом выяснил, что нужно вызывать randomize для инициализации с другим сидом (подозреваю что от системного времени, но не уверен).
                                      0
                                      В том Бэйсике, на котором писал я, без строчки «RANDOMIZE TIMER» случайные числа тоже были каждый раз одни и те же.
                                    +1
                                    Запускаем отдельный поток, в котором в бесконечном цикле инкрементим целочисленную переменную
                                    Раз в миллисекунду смотрим из другого потока на её последний бит и сохраняем (не мешая ей инкрементиться)


                                    Столкнулся, как то с тем, что не могу получить случайного числа, правда не на компьютере а на контроллере: два одинаковых контроллера запитанных от одного источника с большой вероятностью генерировали одинаковое число :)
                                    Я пытался добиться, что бы сетевые адреса у них были уникальными. Что я только не предпринимал, считал микросекунды до первого полученного байта + значение байта — все оказывалось детерминированным: несколько контроллеров связанные rs485 вели себя одинаково, и у с большой вероятностью всех оказывались одинаковые адреса ;)
                                      0
                                      Генератор эти все байтики берет, туда же подмешивает текущий свой ключ шифрования, тоже всё хэширует
                                      А подмешивает он просто по очереди скармливая все эти байты хэшу?
                                      Подмешивание информации из пулов запускается только по набору 64 байт первым пулом? Другие пулы/события в этом не участвуют?
                                        0
                                        да, срабатывание процедуры reseed происходит только когда у первого накопилось столько, сколько нужно. И про подмешивание тоже вы правильно сказали.
                                        0
                                        Интересная статья и написано неплохо.
                                        Спасибо!
                                          0
                                          Сегодня в голову пришла мысль, что в качестве генератора случайных чисел можно использовать убитую в ноль флешку, у которой сыпется память из-за очень большого колличества перезаписей… Записываем на флешку псевдослучайную последовательность чисел, а считываем уже случайную…
                                          Надо будет эксперимент провести… как раз нарисовался образец…

                                        Only users with full accounts can post comments. Log in, please.