(Я не криптограф, но за эти годы я многое усвоил. Мне пришлось помочь тщательно изучить генерацию случайных чисел клиентом много лет назад, что и привело к обнаружению этой ошибки 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. Наверное, ему нужна любовь. В большинстве других языков есть более совершенные генераторы случайных чисел.
person
Schwern
schedule
20.10.2012
