[Ruby 1.8 - Bug #5105][Open] CGI::Session#session id の生成方法について

Issue #5105 has been reported by Masahiro T…


Bug #5105: CGI::Session#session_id の生成方法について
http://redmine.ruby-lang.org/issues/5105

Author: Masahiro T.
Status: Open
Priority: Normal
Assignee:
Category:
Target version:
ruby -v: ruby 1.8.7 (2011-06-30 patchlevel 352) [i686-linux]

とみたです。

古い話ですが、 r13672 で CGI::Session#session_id が SecureRandom が生成
した乱数を単純に使用するようになっています。それまではタイムスタンプ &
プロセスID & 乱数 & 固定文字から生成した MD5 ダイジェスト値が使用されて
いました。

このように生成した MD5 ダイジェスト値よりも、単純に乱数をそのまま使用す
る方が重複が発生しやすくなってしまっているんじゃないかと思うのですがど
うでしょう。

というか、実際に重複が発生してしまったので。

以下、SecureRandom を使いつつ元の挙動に戻すパッチです。

— lib/cgi/session.rb.orig 2009-02-20 19:35:11.000000000 +0900
+++ lib/cgi/session.rb 2011-07-27 12:27:57.000000000 +0900
@@ -25,6 +25,8 @@

require ‘cgi’
require ‘tmpdir’
+require ‘securerandom’
+require ‘digest/md5’

class CGI

@@ -174,21 +176,15 @@
# is used internally for automatically generated
# session ids.
def create_new_id

  •  require 'securerandom'
    
  •  begin
    
  •    session_id = SecureRandom.hex(16)
    
  •  rescue NotImplementedError
    
  •    require 'digest/md5'
    
  •    md5 = Digest::MD5::new
    
  •    now = Time::now
    
  •    md5.update(now.to_s)
    
  •    md5.update(String(now.usec))
    
  •    md5.update(String(rand(0)))
    
  •    md5.update(String($$))
    
  •    md5.update('foobar')
    
  •    session_id = md5.hexdigest
    
  •  end
    
  •  session_id
    
  •  r = SecureRandom.random_bytes(16) rescue rand(0).to_s
    
  •  md5 = Digest::MD5::new
    
  •  now = Time::now
    
  •  md5.update(now.to_s)
    
  •  md5.update(String(now.usec))
    
  •  md5.update(r)
    
  •  md5.update(String($$))
    
  •  md5.update('foobar')
    
  •  md5.hexdigest
    
    end
    private :create_new_id

Issue #5105 has been updated by Yui NARUSE.

まともな乱数・まともなハッシュ関数を前提とした場合、衝突確率は単純に空間の広さに依存するので、
16バイトならば空間はMD5と等しく、重複する確率は同じはずです。

単純に運が悪かったと言えるような確率でもないので、何かを踏んだ可能性が高い気はしますが

Bug #5105: CGI::Session#session_id の生成方法について
http://redmine.ruby-lang.org/issues/5105

Author: Masahiro T.
Status: Open
Priority: Normal
Assignee:
Category:
Target version:
ruby -v: ruby 1.8.7 (2011-06-30 patchlevel 352) [i686-linux]

とみたです。

古い話ですが、 r13672 で CGI::Session#session_id が SecureRandom が生成
した乱数を単純に使用するようになっています。それまではタイムスタンプ &
プロセスID & 乱数 & 固定文字から生成した MD5 ダイジェスト値が使用されて
いました。

このように生成した MD5 ダイジェスト値よりも、単純に乱数をそのまま使用す
る方が重複が発生しやすくなってしまっているんじゃないかと思うのですがど
うでしょう。

というか、実際に重複が発生してしまったので。

以下、SecureRandom を使いつつ元の挙動に戻すパッチです。

— lib/cgi/session.rb.orig 2009-02-20 19:35:11.000000000 +0900
+++ lib/cgi/session.rb 2011-07-27 12:27:57.000000000 +0900
@@ -25,6 +25,8 @@

require ‘cgi’
require ‘tmpdir’
+require ‘securerandom’
+require ‘digest/md5’

class CGI

@@ -174,21 +176,15 @@
# is used internally for automatically generated
# session ids.
def create_new_id

  •  require 'securerandom'
    
  •  begin
    
  •    session_id = SecureRandom.hex(16)
    
  •  rescue NotImplementedError
    
  •    require 'digest/md5'
    
  •    md5 = Digest::MD5::new
    
  •    now = Time::now
    
  •    md5.update(now.to_s)
    
  •    md5.update(String(now.usec))
    
  •    md5.update(String(rand(0)))
    
  •    md5.update(String($$))
    
  •    md5.update('foobar')
    
  •    session_id = md5.hexdigest
    
  •  end
    
  •  session_id
    
  •  r = SecureRandom.random_bytes(16) rescue rand(0).to_s
    
  •  md5 = Digest::MD5::new
    
  •  now = Time::now
    
  •  md5.update(now.to_s)
    
  •  md5.update(String(now.usec))
    
  •  md5.update(r)
    
  •  md5.update(String($$))
    
  •  md5.update('foobar')
    
  •  md5.hexdigest
    
    end
    private :create_new_id

$B$H$_$?$G$9!#(B

On Wed, 27 Jul 2011 16:40:18 +0900
Yui NARUSE [email protected] wrote:

$B$^$H$b$JMp?t!&$^$H$b$J%O%C%7%e4X?t$rA0Ds$H$7$?>l9g!">WFM3NN($OC1=c$K6u4V$N9-$5$K0MB8$9$k$N$G!"(B

16$B%P%$%H$J$i$P6u4V$O(BMD5$B$HEy$7$/!"=EJ#$9$k3NN($OF1$8$O$:$G$9!#(B

$B$J$k$[$I!#(B

$BC1=c$K1?$,[email protected]$($k$h$&$J3NN($G$b$J$$$N$G!"2?$+$rF’[email protected][email protected]$,9b$$5$$O$7$^$9$,(B

$B$G$9$h$M$’!D!#:G=i$K$=$&;W$C$F?’!9$HD4$Y$F$$?$N$G$9$,!D!#(B
$B$b$&$A$g$C$H9M$($F$
$^$9!#(B

(2011/07/27 19:47), $B$H$_$?$^$5$R$m(B wrote:

$B$G$9$h$M$’!D!#:G=i$K$=$&;W$C$F?’!9$HD4$Y$F$$?$N$G$9$,!D!#(B
$B$b$&$A$g$C$H9M$($F$
$^$9!#(B

$B$"!"$o$+$C$?!"(Br32050 $B$G$9$M!#(B
$B$D$^$j!"(BRuby 1.8.7
$B$J$i$P:G?7$N%Q%C%A%l%Y%k$r;H$C$FD:$1$l$PBg>fIW$J$O$:$G$9!#(B

$B$H$_$?$G$9!#(B

On Thu, 28 Jul 2011 00:40:28 +0900
“NARUSE, Yui” [email protected] wrote:

$B$"!"$o$+$C$?!"(Br32050 $B$G$9$M!#(B
$B$D$^$j!"(BRuby 1.8.7
$B$J$i$P:G?7$N%Q%C%A%l%Y%k$r;H$C$FD:$1$l$PBg>fIW$J$O$:$G$9!#(B

$B$$!(B $B$"$j$,$H$&$4$6$$$^$9!(B

$B$H$$$&$+!"(B1.8.7-p352 $B$r;H$C$F$?$D$b$j$,!"8=>]$,H/@8$7$?4D6-$O(B
1.8.7-p334 $B$G$7$?!D(B orz…

$B$3$s$J46$8"-$N%o%s%i%$%J!<$G!“F1$8(BPID$B$N;~$KF1$8Mp?t$,@8@.$5$l$k$3$H$H!”(B
p352 $B$GD>$C$F$k$3$H$,3NG’$G$-$^$7$?!#(B

% ruby -rsecurerandom -e ‘p [$$, SecureRandom.hex(16)];
33000.times{pid=fork{p [$$,SecureRandom.hex(16)]}; Process.waitpid pid}’

$B$H$3$m$G!"?’!9$HD4$Y$F$$$k;~$K8+$D$1$?$N$G$9$,!"(Bsecurerandom.rb
$B$N<!$N9T$G!"(B

    ary = [now.to_i, now.usec, @pid, pid]
    OpenSSL::Random.seed(ary.to_s)

1$BIC0JFb$KFCDj$N(B usec $B$H(B PID $B$N%Q%?!<%s$,H/@8$9$k$H!"(B1.8.7
$B$G$OF1$8(B
ary.to_s
$B$,@8@.$5$l$k$h$&$K;W$&$N$G$9$,!“LdBj$J$$$G$7$g$&$+!#$?$H$($P!”(B

now.to_i now.usec @pid pid
1311785953 11 2222 22233
1311785953 1122 2222 233

[email protected]$H!"(Bary.to_s $B$N7k2L$,N>J}$H$b(B “131178595311222222233”
$B$K$J$j$^$9!#(B

1.9.2 [email protected]$H(B Array#to_s

$B$NI=8=$,JQ$o$C$?$N$GF1$8$K$O$J$j$^$;$s$G$7$?!#(B

ary.to_s $B$8$c$J$/$F(B ary.join(’.’)
$BEy$N$h$&$K$7$?J}$,$$$$$s$8$c$J$$$+$H(B
$B;W$$$^$9!#(B

$B$H$_$?$G$9!#(B

On Thu, 28 Jul 2011 02:13:07 +0900
$B$H$_$?$^$5$R$m(B [email protected] wrote:

$B$3$s$J46$8"-$N%o%s%i%$%J!<$G!“F1$8(BPID$B$N;~$KF1$8Mp?t$,@8@.$5$l$k$3$H$H!”(B
p352 $B$GD>$C$F$k$3$H$,3NG’$G$-$^$7$?!#(B

% ruby -rsecurerandom -e ‘p [$$, SecureRandom.hex(16)];
33000.times{pid=fork{p [$$,SecureRandom.hex(16)]}; Process.waitpid pid}’

$B%@%a$G$7$?!D!#<!$N%9%/%j%W%H$GF1$8Mp?t$,@8@.$5$l$^$7$?!#(B

% ruby -rsecurerandom -e ‘OpenSSL::Random.random_bytes(16);
33000.times{pid=fork{p [$$,SecureRandom.hex(16)]}; Process.waitpid pid}’

SecureRandom.random_bytes $B$,$=$N%W%m%;%9$G:G=i$K8F$P$l$?;~$K$O>o$K(B
OpenSSL::Random.seed
$B$r8F$V$h$&$K$7$F$_$?$i$&$^$/$$$-$^$7$?!#@h$N%a!<%k(B
$B$N(B ary.to_s [email protected]$7$F$$$^$9!#(B

Index: lib/securerandom.rb

— lib/securerandom.rb (revision 32735)
+++ lib/securerandom.rb (working copy)
@@ -50,12 +50,12 @@
def self.random_bytes(n=nil)
n ||= 16
if defined? OpenSSL::Random

  •  @pid = $$ if !defined?(@pid)
    
  •  @pid = 0 if !defined?(@pid)
     pid = $$
     if @pid != pid
       now = Time.now
       ary = [now.to_i, now.usec, @pid, pid]
    
  •    OpenSSL::Random.seed(ary.to_s)
    
  •    OpenSSL::Random.seed(ary.join('.'))
       @pid = pid
     end
     return OpenSSL::Random.random_bytes(n)

2011$BG/(B7$B7n(B29$BF|(B20:04 $B$H$_$?$^$5$R$m(B [email protected]:

$B%@%a$G$7$?!D!#<!$N%9%/%j%W%H$GF1$8Mp?t$,@8@.$5$l$^$7$?!#(B

% ruby -rsecurerandom -e ‘OpenSSL::Random.random_bytes(16);
33000.times{pid=fork{p [$$,SecureRandom.hex(16)]}; Process.waitpid pid}’

$B$J$k$[$I!#(Bsecurerandom.rb $B0J30$G(B OpenSSL::Random.random_bytes
$B$,8F$P$l$k$H!"(B
securerandom.rb $B$O(B fork $B$7$?$3$H$K5$$,$D$1$J$$$N$G$9$M!#(B

SecureRandom.random_bytes $B$,$=$N%W%m%;%9$G:G=i$K8F$P$l$?;~$K$O>o$K(B
OpenSSL::Random.seed $B$r8F$V$h$&$K$7$F$_$?$i$&$^$/$$$-$^$7$?!#@h$N%a!<%k(B
$B$N(B ary.to_s [email protected]$7$F$$$^$9!#(B

$BF~$l$F$*$-$^$9!#(B

2011$BG/(B8$B7n(B13$BF|(B17:31 NARUSE, Yui [email protected]:

$B$U$H;W$C$?$N$G$9$,!"(B openssl $B$r;H$&$H$-$G$b!"(B/dev/urandom
$B$,$"$k$J$i$P!"(B
openssl $B$N(B seed $B$K(B /dev/urandom
$B$r0lIt;H$C$F$b$$$$$s$8$c$J$$$G$7$g$&$+!#(B

fork $B$9$kIQEY$G(B /dev/urandom $B$+$iFI$_=P$9$3$H$,K>$^$7$$$+!"(B
$B$H$$$&LdBj$G$9$+$M!#(B

$B$U$H;W$C$?$N$G$9$,!"(B openssl $B$r;H$&$H$-$G$b!"(B/dev/urandom
$B$,$"$k$J$i$P!"(B

openssl $B$N(B seed $B$K(B /dev/urandom
$B$r0lIt;H$C$F$b$$$$$s$8$c$J$$$G$7$g$&$+!#(B

fork $B$9$kIQEY$G(B /dev/urandom $B$+$iFI$_=P$9$3$H$,K>$^$7$$$+!"(B
$B$H$$$&LdBj$G$9$+$M!#(B

$B$"$s$^$j>$7$/$J$$$s$G$9$,!#(B

PRNG$B$G$"$k0J>e!"(Bseed$B$,M=B,$5$l$?$i!“A4Mp?tNs$,M=B,$5$l$F$7$^$&$N$G!”(B
$B0BA4B&$KE]$9$[$&$,%(%s%H%m%T!<8O3i$h$j$b=EMW$J$s$8$c$J$$$+$H$$$&5$$,$9$k$s$G$9$1$I$M$(!&!&(B

OS$B$N%l%Y%k$G$b!"(BASLR$B$N<B8=$N$?$a$K(Bprocess
spawn$B$9$k$?$S$K(B/dev/urandom$BFI$s$G$k$N$G!“5vMFHO0OFb$G$O$J$$$+$J$”!#Ws0UE*$J1?MQ$r9M$($?$i%@%a$J%1!<%9$OH/@8$7$&$k$+$b$7$l$J$$$1$I(B

(2011/07/29 23:55), Tanaka A. wrote:

SecureRandom.random_bytes $B$,$=$N%W%m%;%9$G:G=i$K8F$P$l$?;~$K$O>o$K(B
OpenSSL::Random.seed $B$r8F$V$h$&$K$7$F$_$?$i$&$^$/$$$-$^$7$?!#@h$N%a!<%k(B
$B$N(B ary.to_s [email protected]$7$F$$$^$9!#(B

$BF~$l$F$*$-$^$9!#(B

$B$U$H;W$C$?$N$G$9$,!"(B openssl $B$r;H$&$H$-$G$b!"(B/dev/urandom
$B$,$"$k$J$i$P!"(B
openssl $B$N(B seed $B$K(B /dev/urandom
$B$r0lIt;H$C$F$b$$$$$s$8$c$J$$$G$7$g$&$+!#(B

(2011/08/13 20:35), KOSAKI Motohiro wrote:

OS$B$N%l%Y%k$G$b!"(BASLR$B$N<B8=$N$?$a$K(Bprocess

spawn$B$9$k$?$S$K(B/dev/urandom$BFI$s$G$k$N$G!“5vMFHO0OFb$G$O$J$$$+$J$”!#Ws0UE*$J1?MQ$r9M$($?$i%@%a$J%1!<%9$OH/@8$7$&$k$+$b$7$l$J$$$1$I(B

/dev/random $B$G$O$J$/(B urandom $B$J$N$G$$$$$s$8$c$J$$$G$7$g$&$+!"(B
$B$b$A$m$s%(%s%H%m%T!<$O>CHq$9$k$o$1$G$9$,!#(B

$B2C$($F!“8=:_967bB&$K7P$C$F9M$($k$H(B usec/nsec * pid
$B$”$?$j$,M=B,[email protected]$rC4J]$7$F$$$k$H$3$m!"(B
$B$3$l$C$F(B 100$BK|(B~1$B2/(B * 6$BK|$J$o$1$G!"(B42bit
$B$/$i$$$7$+6u4V$"$j$^$;$s$h$M!#(B
$B$A$g$C$H(B seed $B$,<e$$$H;W$&$s$G$9!#(B

2011$BG/(B8$B7n(B13$BF|(B23:12 NARUSE, Yui [email protected]:

PRNG$B$G$"$k0J>e!"(Bseed$B$,M=B,$5$l$?$i!“A4Mp?tNs$,M=B,$5$l$F$7$^$&$N$G!”(B

$B0BA4B&$KE]$9$[$&$,%(%s%H%m%T!<8O3i$h$j$b=EMW$J$s$8$c$J$$$+$H$$$&5$$,$9$k$s$G$9$1$I$M$(!&!&(B

OS$B$N%l%Y%k$G$b!"(BASLR$B$N<B8=$N$?$a$K(Bprocess

spawn$B$9$k$?$S$K(B/dev/urandom$BFI$s$G$k$N$G!“5vMFHO0OFb$G$O$J$$$+$J$”!#Ws0UE*$J1?MQ$r9M$($?$i%@%a$J%1!<%9$OH/@8$7$&$k$+$b$7$l$J$$$1$I(B

/dev/random $B$G$O$J$/(B urandom $B$J$N$G$$$$$s$8$c$J$$$G$7$g$&$+!"(B
$B$b$A$m$s%(%s%H%m%T!<$O>CHq$9$k$o$1$G$9$,!#(B

forking server [email protected]$H(B request
$B$4$H$K>CHq$7$A$c$&$H$$$&$N$,7y$J46$8$J$N$G$9$,!"(B
OS $B<+BN$N>[email protected]~7A$J$i$$$$$+$J$!$H;W$$$D$D$b!"(B

$B2C$($F!“8=:_967bB&$K7P$C$F9M$($k$H(B usec/nsec * pid
$B$”$?$j$,M=B,[email protected]$rC4J]$7$F$$$k$H$3$m!"(B
$B$3$l$C$F(B 100$BK|(B~1$B2/(B * 6$BK|$J$o$1$G!"(B42bit
$B$/$i$$$7$+6u4V$"$j$^$;$s$h$M!#(B
$B$A$g$C$H(B seed $B$,<e$$$H;W$&$s$G$9!#(B

$B$3$l$O0c$$$^$9!#(B
RAND_seed() $B$O$=$N;[email protected]$N<o$K%G!<%?$r:.$<$k$b$N$J$N$G!"(B
$B:G=i$K(B openssl $B$,(B /dev/urandom
[email protected]<o$,>C$($k$o$1$G$O$"$j$^$;$s!#(B

RAND_add(3SSL):
RAND_add() mixes the num bytes at buf into the PRNG state.

2011$BG/(B8$B7n(B15$BF|(B12:55 KOSAKI Motohiro
[email protected]:

RAND_add(3SSL):
RAND_add() mixes the num bytes at buf into the PRNG state.

$B$*$C$H!#KM$O$3$3$r8m2r$7$F$$$^$7$?!#(B
[email protected]$N<gD%$OE12s$7$?$$$H;W$$$^$9!#(B

$B$o$?$7$b8m2r$7$F$$$^$7$?!#(B
$B$7$P$i$/9M$($?$s$G$9$,A0=P$N%Q%C%AE,MQ8e$O967b$G$-$k5$$,$7$J$$$N$GE12s$7$^$9!#(B

RAND_add(3SSL):
RAND_add() mixes the num bytes at buf into the PRNG state.

$B$*$C$H!#KM$O$3$3$r8m2r$7$F$$$^$7$?!#(B
[email protected]$N<gD%$OE12s$7$?$$$H;W$$$^$9!#(B