天泣記

乱数については、以前調べたことがある。

結局、/dev/urandom があればそこから取り出して種にするというのがそこそこまともだという結論に達したのだが、世の中には /dev/urandom ではだめだというひともいるらしい。

・ http://www.securityfocus.com/bid/6855
・ http://icat.nist.gov/icat.cfm?cvename=CAN-2001-0950

/dev/random を使っちゃうと、むしろブロックして危ないと思うのだが、/dev/urandom で本当にまずいケースはあるだろうか。

http://www.securityfocus.com/bid/6855 で指摘されている util-linux のソースは、次のようになっている。

util-linux-2.12r/misc-utils/mcookie.c:37-48,76,132-150

37: #define BUFFERSIZE 4096
38:
39: struct rngs {
40:    const char *path;
41:    int minlength, maxlength;
42: } rngs[] = {
43:    { "/dev/random",              16,  16 }, /* 16 bytes = 128 bits suffice */
44:    { "/proc/interrupts",          0,   0 },
45:    { "/proc/slabinfo",            0,   0 },
46:    { "/proc/stat",                0,   0 },
47:    { "/dev/urandom",             32,  64 },
48: };

...

76:    unsigned char     buf[BUFFERSIZE];

...

132:    for (i = 0; i < RNGS; i++) {
133:       if ((fd = open( rngs[i].path, O_RDONLY|O_NONBLOCK )) >= 0) {
134:          int count = sizeof(buf);
135:
136:          if (rngs[i].maxlength && count > rngs[i].maxlength)
137:             count = rngs[i].maxlength;
138:          r = read( fd, buf, count );
139:          if (r > 0)
140:             MD5Update( &ctx, buf, r );
141:          else
142:             r = 0;
143:          close( fd );
144:          if (Verbose)
145:             fprintf( stderr, _("Got %d bytes from %s\n"), r, rngs[i].path );
146:          if (rngs[i].minlength && r >= rngs[i].minlength)
147:             break;
148:       } else if (Verbose)
149:          fprintf( stderr, _("Could not open %s\n"), rngs[i].path );
150:    }

つまり、/dev/random, /proc/interrupts, /proc/slabinfo, /proc/stat, /dev/urandom を順に O_NONBLOCK で読んでいる。

(そこで Vulnerable とされている Debian 3.0 の util-linux 2.11n を ftp://aist.ring.gr.jp/pub/linux/debian/debian/pool/main/u/util-linux/util-linux_2.11n.orig.tar.gz からとってきて確かめてもコードは同様に見える。)

たしかに、このコードでは /dev/random のエントロピーが枯渇して即座に読めなければ /dev/urandom から読む。でも、それってそんなにいけないことなのだろうか？

あと、そもそもエントロピーが枯渇しているときに /dev/urandom を読むのであれば、/dev/random を読む意味はあるのだろうか？

#2 ruby の乱数 [CODE blog]

以前調べたのは ruby で使うためで、その結果、現在は次のようになっている。

ruby-1.8.3/random.c:256-306

256: random_seed()
257: {
258:     static int n = 0;
259:     struct timeval tv;
260:     int fd;
261:     struct stat statbuf;
262:
263:     int seed_len;
264:     BDIGIT *digits;
265:     unsigned long *seed;
266:     NEWOBJ(big, struct RBignum);
267:     OBJSETUP(big, rb_cBignum, T_BIGNUM);
268:
269:     seed_len = 4 * sizeof(long);
270:     big->sign = 1;
271:     big->len = seed_len / SIZEOF_BDIGITS + 1;
272:     digits = big->digits = ALLOC_N(BDIGIT, big->len);
273:     seed = (unsigned long *)big->digits;
274:
275:     memset(digits, 0, big->len * SIZEOF_BDIGITS);
276:
277: #ifdef S_ISCHR
278:     if ((fd = open("/dev/urandom", O_RDONLY
279: #ifdef O_NONBLOCK
280:             |O_NONBLOCK
281: #endif
282: #ifdef O_NOCTTY
283:             |O_NOCTTY
284: #endif
285: #ifdef O_NOFOLLOW
286:             |O_NOFOLLOW
287: #endif
288:             )) >= 0) {
289:         if (fstat(fd, &statbuf) == 0 && S_ISCHR(statbuf.st_mode)) {
290:             read(fd, seed, seed_len);
291:         }
292:         close(fd);
293:     }
294: #endif
295:
296:     gettimeofday(&tv, 0);
297:     seed[0] ^= tv.tv_usec;
298:     seed[1] ^= tv.tv_sec;
299:     seed[2] ^= getpid() ^ (n++ << 16);
300:     seed[3] ^= (unsigned long)&seed;
301:
302:     /* set leading-zero-guard if need. */
303:     digits[big->len-1] = digits[big->len-2] <= 1 ? 1 : 0;
304:
305:     return rb_big_norm((VALUE)big);
306: }

/dev/urandom を 4 * sizeof(long) だけ読んで種を生成している。つまり、long の長さによるが、128 ないし 256bit 読む。 (/dev/urandom がなかったときの保険というかごまかしと言うか以前のコードの名残として、時刻などいくつかの情報を xor している)

なお、ruby は Mersenne Twister を内部に抱えていて、こういう長い種もとくに問題なく扱えるし、システムによって生成される乱数が異なることもない。まぁ、ruby のバージョンが変われば変わる可能性はあるが。

こういうコードになったのは ruby-1.8.3 からで、/dev/urandom を使っていなかった他、いくつか問題があった。なので、1.8.3 でいろいろと変えたのだが、乱数だけあって気がつくひとはあまりいない。ただ、何回か、種を設定しても生成される乱数が異なることに気がついたひとはいたようである。あと、srand が以前の種を返すので、

% ruby-1.8.2 -e 'srand; p srand'
1138591551
% ruby-1.8.3 -e 'srand; p srand'
255108505494104843374021615775162945381

というようにあからさまに長くなっていることを気にするひとがいるか思ったが、いまのところ見かけた覚えがない。

#3 perl の乱数 [CODE blog]

perl も /dev/urandom を使っている。 (というか、ruby で使おうと思ったのは perl で使っていることに気がついたからである)

perl-5.8.7/util.c:4446-4525

4446: U32
4447: Perl_seed(pTHX)
4448: {
4449:     /*
4450:      * This is really just a quick hack which grabs various garbage
4451:      * values.  It really should be a real hash algorithm which
4452:      * spreads the effect of every input bit onto every output bit,
4453:      * if someone who knows about such things would bother to write it.
4454:      * Might be a good idea to add that function to CORE as well.
4455:      * No numbers below come from careful analysis or anything here,
4456:      * except they are primes and SEED_C1 > 1E6 to get a full-width
4457:      * value from (tv_sec * SEED_C1 + tv_usec).  The multipliers should
4458:      * probably be bigger too.
4459:      */
4460: #if RANDBITS > 16
4461: #  define SEED_C1       1000003
4462: #define   SEED_C4       73819
4463: #else
4464: #  define SEED_C1       25747
4465: #define   SEED_C4       20639
4466: #endif
4467: #define   SEED_C2       3
4468: #define   SEED_C3       269
4469: #define   SEED_C5       26107
4470:
4471: #ifndef PERL_NO_DEV_RANDOM
4472:     int fd;
4473: #endif
4474:     U32 u;
4475: #ifdef VMS
4476: #  include <starlet.h>
4477:     /* when[] = (low 32 bits, high 32 bits) of time since epoch
4478:      * in 100-ns units, typically incremented ever 10 ms.        */
4479:     unsigned int when[2];
4480: #else
4481: #  ifdef HAS_GETTIMEOFDAY
4482:     struct timeval when;
4483: #  else
4484:     Time_t when;
4485: #  endif
4486: #endif
4487:
4488: /* This test is an escape hatch, this symbol isn't set by Configure. */
4489: #ifndef PERL_NO_DEV_RANDOM
4490: #ifndef PERL_RANDOM_DEVICE
4491:    /* /dev/random isn't used by default because reads from it will block
4492:     * if there isn't enough entropy available.  You can compile with
4493:     * PERL_RANDOM_DEVICE to it if you'd prefer Perl to block until there
4494:     * is enough real entropy to fill the seed. */
4495: #  define PERL_RANDOM_DEVICE "/dev/urandom"
4496: #endif
4497:     fd = PerlLIO_open(PERL_RANDOM_DEVICE, 0);
4498:     if (fd != -1) {
4499:         if (PerlLIO_read(fd, &u, sizeof u) != sizeof u)
4500:             u = 0;
4501:         PerlLIO_close(fd);
4502:         if (u)
4503:             return u;
4504:     }
4505: #endif
4506:
4507: #ifdef VMS
4508:     _ckvmssts(sys$gettim(when));
4509:     u = (U32)SEED_C1 * when[0] + (U32)SEED_C2 * when[1];
4510: #else
4511: #  ifdef HAS_GETTIMEOFDAY
4512:     PerlProc_gettimeofday(&when,NULL);
4513:     u = (U32)SEED_C1 * when.tv_sec + (U32)SEED_C2 * when.tv_usec;
4514: #  else
4515:     (void)time(&when);
4516:     u = (U32)SEED_C1 * when;
4517: #  endif
4518: #endif
4519:     u += SEED_C3 * (U32)PerlProc_getpid();
4520:     u += SEED_C4 * (U32)PTR2UV(PL_stack_sp);
4521: #ifndef PLAN9           /* XXX Plan9 assembler chokes on this; fix needed  */
4522:     u += SEED_C5 * (U32)PTR2UV(&when);
4523: #endif
4524:     return u;
4525: }

/dev/urandom 以外には時刻などを使う。

ただ、この Perl_seed という関数の返り値は U32 なので、(おそらく) 32bit しかない。32bit というのは現在の計算機の brute force attack に対抗するには危うい。

あと、perl の乱数アルゴリズムはシステムが提供している drand48, random, rand のどれかを使う。長い種を扱わないのはこのへんに起因するのかもしれない。

perl-5.8.7/pod/perl56delta.pod:390-396

390: =head2 Better pseudo-random number generator
391:
392: In 5.005_0x and earlier, perl's rand() function used the C library
393: rand(3) function.  As of 5.005_52, Configure tests for drand48(),
394: random(), and rand() (in that order) and picks the first one it finds.
395:
396: These changes should result in better random numbers from rand().

#4 bash の乱数 [CODE blog]

そういえば、bash には $RANDOM という疑似変数がある。

bash-3.1/doc/bashref.texi:4694-4697

4694: @item RANDOM
4695: Each time this parameter is referenced, a random integer
4696: between 0 and 32767 is generated.  Assigning a value to this
4697: variable seeds the random number generator.

せっかくなのでたどってみよう。

とりあえず RANDOM で検索すると次の行が見つかった。

bash-3.1/variables.c:1451

1451:   INIT_DYNAMIC_VAR ("RANDOM", (char *)NULL, get_random, assign_random);

きっと get_random というのが乱数を生成する関数で、 assign_random はおそらく種をセットするのだろう。

bash-3.1/variables.c:1137-1161,1175-1191,1200-1201

1137: /* The random number seed.  You can change this by setting RANDOM. */
1138: static unsigned long rseed = 1;
1139: static int last_random_value;
1140: static int seeded_subshell = 0;
1141:
1142: /* A linear congruential random number generator based on the example
1143:    one in the ANSI C standard.  This one isn't very good, but a more
1144:    complicated one is overkill. */
1145:
1146: /* Returns a pseudo-random number between 0 and 32767. */
1147: static int
1148: brand ()
1149: {
1150:   rseed = rseed * 1103515245 + 12345;
1151:   return ((unsigned int)((rseed >> 16) & 32767));       /* was % 32768 */
1152: }
1153:
1154: /* Set the random number generator seed to SEED. */
1155: static void
1156: sbrand (seed)
1157:      unsigned long seed;
1158: {
1159:   rseed = seed;
1160:   last_random_value = 0;
1161: }

...

1175: int
1176: get_random_number ()
1177: {
1178:   int rv;
1179:
1180:   /* Reset for command and process substitution. */
1181:   if (subshell_environment && seeded_subshell == 0)
1182:     {
1183:       sbrand (rseed + getpid() + NOW);
1184:       seeded_subshell = 1;
1185:     }
1186:
1187:   do
1188:     rv = brand ();
1189:   while (rv == last_random_value);
1190:   return rv;
1191: }

...

1200:   rv = get_random_number ();
1201:   last_random_value = rv;

アルゴリズムは線形合同法で、種は pid と時刻という感じだろうか。

コメントにもあるようにそんなによくないというのは自覚しているようではある。しかし、last_random_value とかいうので、同じ値が連続して出てこないようにしているのはいかがなものかと思う。どちらかというと、見識があってこれで十分と判断したというよりは、素人っぽさを感じる。

#5 python の乱数 [CODE blog]

Python には os.urandom というのがある。 (なお、Windows の場合は C で定義されるようである)

Python-2.4.2/Lib/os.py:710-725

710: if not _exists("urandom"):
711:     def urandom(n):
712:         """urandom(n) -> str
713:
714:         Return a string of n random bytes suitable for cryptographic use.
715:
716:         """
717:         try:
718:             _urandomfd = open("/dev/urandom", O_RDONLY)
719:         except:
720:             raise NotImplementedError("/dev/urandom (or equivalent) not found")
721:         bytes = ""
722:         while len(bytes) < n:
723:             bytes += read(_urandomfd, n - len(bytes))
724:         close(_urandomfd)
725:         return bytes

疑似乱数は Mersenne Twister が random.py で定義される。

Python-2.4.2/Lib/random.py:29,46,108-112

29: General notes on the underlying Mersenne Twister core generator:

...

46: from os import urandom as _urandom

...

108:             try:
109:                 a = long(_hexlify(_urandom(16)), 16)
110:             except NotImplementedError:
111:                 import time
112:                 a = long(time.time() * 256) # use fractional seconds

種は、os.urandom を使って16バイト (128bit) 読んで作る。読めなければ時刻。

#6 php の乱数 [CODE blog]

php-5.1.0/ext/standard/rand.c:58-82

58: /* {{{ php_rand
59:  */
60: PHPAPI long php_rand(TSRMLS_D)
61: {
62:         long ret;
63:
64:         if (!BG(rand_is_seeded)) {
65:                 php_srand(GENERATE_SEED() TSRMLS_CC);
66:         }
67:
68: #ifdef ZTS
69:         ret = php_rand_r(&BG(rand_seed));
70: #else
71: # if defined(HAVE_RANDOM)
72:         ret = random();
73: # elif defined(HAVE_LRAND48)
74:         ret = lrand48();
75: # else
76:         ret = rand();
77: # endif
78: #endif
79:
80:         return ret;
81: }
82: /* }}} */

疑似乱数には random, lrand48, rand のどれかを使っている。

php-5.1.0/ext/standard/php_rand.h:49-53

49: #ifdef PHP_WIN32
50: #define GENERATE_SEED() ((long) (time(0) * GetCurrentProcessId() * 1000000 * php_combined_lcg(TSRMLS_C)))
51: #else
52: #define GENERATE_SEED() ((long) (time(0) * getpid() * 1000000 * php_combined_lcg(TSRMLS_C)))
53: #endif

種は時刻と pid と、えーと、この lcg ってのはそれ自身が疑似乱数なのか。うぅむ。

あ、php_rand_r というのが使われる可能性もある？

php-5.1.0/main/reentrancy.c:278,318-333

278: #ifndef HAVE_RAND_R

...

318: static int
319: do_rand(unsigned long *ctx)
320: {
321:         return ((*ctx = *ctx * 1103515245 + 12345) % ((u_long)PHP_RAND_MAX + 1));
322: }
323:
324:
325: PHPAPI int
326: php_rand_r(unsigned int *ctx)
327: {
328:         u_long val = (u_long) *ctx;
329:         *ctx = do_rand(&val);
330:         return (int) *ctx;
331: }
332:
333: #endif

うぅむ。これはあまりよろしくない。でも、HAVE_RAND_R というところからみると、rand_r があれば使われないか。でも、rand_r って rand と同程度で、それもそんなに良くない気がするなぁ。

#7 graphviz [CODE blog]

どうも graphviz は Debian のが古い (古すぎる) のが問題らしい。 graphviz-2.7.20060126.0540.tar.gz をとってきて試しに install してみたら問題が起きない。

Debian BTS にも新しいのが欲しいというリクエストが出ているが、反応がないようだ。

http://bugs.debian.org/cgi-bin/pkgreport.cgi?which=pkg&data=graphviz&archive=no&version=&dist=unstable

天泣記

2006-01-01 (Sun)

2006-01-02 (Mon)

2006-01-03 (Tue)

2006-01-04 (Wed)

2006-01-05 (Thu)

2006-01-06 (Fri)

2006-01-07 (Sat)

2006-01-08 (Sun)

2006-01-09 (Mon)

2006-01-11 (Wed)

2006-01-12 (Thu)

2006-01-13 (Fri)

2006-01-14 (Sat)

2006-01-15 (Sun)

2006-01-16 (Mon)

2006-01-18 (Wed)

2006-01-19 (Thu)

2006-01-20 (Fri)

2006-01-21 (Sat)

2006-01-22 (Sun)

2006-01-23 (Mon)

2006-01-24 (Tue)

2006-01-25 (Wed)

2006-01-26 (Thu)

2006-01-27 (Fri)

2006-01-28 (Sat)

2006-01-29 (Sun)

2006-01-30 (Mon)