Каковы слабые стороны Perl srand() по умолчанию, версия 5.004?

Question

Я могу найти много документации по вопросам с использованием time() до версии Perl 5.004, но ничего не последовало.

Для выполнения домашнего задания нас просят перепроектировать результаты программы, исходя из предположения, что Perl по умолчанию srand() все еще испорчен в посеве по умолчанию. В журнале изменений для выпуска perl 5.004 говорится, что srand() начальное число по умолчанию теперь основано на "сложном сочетании трудно предсказуемых значений, зависящих от системы".

Так ли это, и если да, то каковы эти ценности и есть ли у них слабые места?

Answer 1

(Я не криптограф, но за многие годы я многое освоил. Мне пришлось помогать тщательно исследовать случайное число клиентов, генерируемое годами назад, что и привело к обнаружению упомянутой ниже ошибки Crypt::Random.)

Начальный код имеет больше смысла, если вы правильно сделаете отступ для всех этих ifdef. Это код в 5.16.0.

U32
Perl_seed(pTHX)
{
    dVAR;
    /*
     * This is really just a quick hack which grabs various garbage
     * values.  It really should be a real hash algorithm which
     * spreads the effect of every input bit onto every output bit,
     * if someone who knows about such things would bother to write it.
     * Might be a good idea to add that function to CORE as well.
     * No numbers below come from careful analysis or anything here,
     * except they are primes and SEED_C1 > 1E6 to get a full-width
     * value from (tv_sec * SEED_C1 + tv_usec).  The multipliers should
     * probably be bigger too.
     */
#if RANDBITS > 16
#  define SEED_C1   1000003
#  define SEED_C4   73819
#else
#  define SEED_C1   25747
#  define SEED_C4   20639
#endif

#define   SEED_C2   3
#define   SEED_C3   269
#define   SEED_C5   26107

#ifndef PERL_NO_DEV_RANDOM
    int fd;
#endif

    U32 u;

#ifdef VMS
#  include <starlet.h>
    /* when[] = (low 32 bits, high 32 bits) of time since epoch
     * in 100-ns units, typically incremented ever 10 ms.        */
   unsigned int when[2];
#else
#  ifdef HAS_GETTIMEOFDAY
       struct timeval when;
#  else
       Time_t when;
#  endif
#endif

/* This test is an escape hatch, this symbol isn't set by Configure. */
#ifndef PERL_NO_DEV_RANDOM
#    ifndef PERL_RANDOM_DEVICE
         /* /dev/random isn't used by default because reads from it will block
          * if there isn't enough entropy available.  You can compile with
          * PERL_RANDOM_DEVICE to it if you'd prefer Perl to block until there
          * is enough real entropy to fill the seed. */
#        define PERL_RANDOM_DEVICE "/dev/urandom"
#    endif
     fd = PerlLIO_open(PERL_RANDOM_DEVICE, 0);
     if (fd != -1) {
        if (PerlLIO_read(fd, (void*)&u, sizeof u) != sizeof u)
        u = 0;
    PerlLIO_close(fd);
    if (u)
        return u;
    }
#endif

#ifdef VMS
    _ckvmssts(sys$gettim(when));
    u = (U32)SEED_C1 * when[0] + (U32)SEED_C2 * when[1];
#else
#  ifdef HAS_GETTIMEOFDAY
        PerlProc_gettimeofday(&when,NULL);
        u = (U32)SEED_C1 * when.tv_sec + (U32)SEED_C2 * when.tv_usec;
#  else
        (void)time(&when);
        u = (U32)SEED_C1 * when;
#  endif
#endif

    u += SEED_C3 * (U32)PerlProc_getpid();
    u += SEED_C4 * (U32)PTR2UV(PL_stack_sp);

#ifndef PLAN9           /* XXX Plan9 assembler chokes on this; fix needed  */
    u += SEED_C5 * (U32)PTR2UV(&when);
#endif

    return u;
}

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

• Система случайного устройства.

Это самый простой и, вероятно, самый сильный метод. Если в вашей ОС есть случайное устройство, которое не блокируется, т.е. /dev/urandom прочитайте 32 бита из этого. Готово! #ifndef PERL_NO_DEV_RANDOM (хороший двойной отрицательный) контролирует этот бит. Это делается практически во всех системах Unix. На этом этапе анализ случайного начального числа Perl переключается на реализацию вашей конкретной ОС. /dev/urandom,

• Получите что-нибудь из часов, pid и стека указателя.

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

• Время в микросекундах или секундах зависит от того, gettimeofday() существует.
• Идентификатор процесса, PerlProc_getpid(),
• Расположение в памяти текущего указателя стека, PTR2UV(PL_stack_sp),

Что она должна делать с этой информацией, и это то, о чем идет речь в самом начале, - объединить их, используя настоящий алгоритм хеширования. Вместо этого он умножает их на различные константы (SEED_C1, SEED_C2 и так далее) и складывает их. Это обязательно будет ошибочным.

Вся эта информация теоретически предсказуема. Я не знаю, как обстоят дела с предсказанием системной информации, но указатель времени + pid + стека является довольно распространенным методом получения энтропии, и по этому вопросу обязательно будут статьи.

Существует дополнительный недостаток, свойственный всем методам Perl, он делает все это, используя только 32 бита даже на 64-битных машинах. Это не будет вытягивать 64 бит из /dev/urandom, всего 32. Он будет смотреть только 32-битный идентификатор процесса, указатель стека или информацию о времени, даже если есть 64-битная информация.

Прочитав код у меня три проблемы.

• Его использование всего 32 бита случайности.

Вполне возможно, что система с несколькими графическими процессорами может перебор.

• (Unix) Насколько хорошо твое /dev/urandom,

/dev/urandom может закончиться энтропия, если вы слишком быстро вытяните ее. Вместо того, чтобы блокировать это будет генерировать более слабую энтропию. Это вне контроля Perl, но это слабость всей системы. Кроме того, некоторые программы могут тянуть больше энтропии, чем им нужно /dev/urandom, Мы нашли ошибку несколько лет назад в Crypt::Random, которая делала именно это.

• (Windows) Этот слабый алгоритм хеширования.

Рядом с 32-битной проблемой это, вероятно, самое слабое звено.

• Какую случайную функцию он использует?

После того, как начальное число задано, в какую функцию случайного числа оно передается? Плохая функция ранда облегчает угадывание семени. Perl ищет несколько, обычно заканчивая drand48, Вы можете увидеть, что его использует с: use Config; print $Config{randfunc}', Я понятия не имею, насколько хорошо это работает, но страница руководства OS X drand48 говорит random(3) является более мощным, и страница руководства Linux говорит, что drand48 устарел.

Эту функцию не трогали с... о дорогой конец 90-х. Он был перемещен в util.c, но не был серьезно затронут. git blame 132efe8bfb7cd0fb1beb15aaf284e33bf44eb1fa^ pp.c показывает реальную историю, ищите S_seed, Наверное, нужна любовь. Большинство других языков имеют более продвинутые генераторы случайных чисел.