雑な k|m の生態について

その 45 - 光ファイバの先端で,蒼い歌姫は何人踊れるか?

2009-10-17

"http://" の "//" は要らなかった?

って Sir Tim Berners-Lee が言い出しました.確かに,これが便利となる場面はそう多くはありません.

一体,どういう時に便利なんだろう?

TCP/IP 上でハイパーテキストを転送する主なプロトコルは 2 種類.HTTP と HTTPS です.HTTP なページから HTTPS なページに移る時は,まあ特にセキュリティ的な問題を考察する必要は無いと思います.しかし HTTPS なページから HTTP なページに移る際には,ブラウザは「ここから先の通信は暗号化されてないよ!」と警告を出すべきです.

「警告なんてうざい! HTTP から移れば HTTP のまま,HTTPS から移れば HTTPS のまま通信をしてもらうべきだよ! 何に気をつけてサイトを作ればいいの?」

ちょっと規模の大きいショッピングサイトなどでは,まれにそのような悩みが出るようです.特に,ドメインをまたがってページ遷移をするほどの大規模なサイトではね.

そんな時は,これ:

ようこそ one.example.com のショッピングサイトへ!

我々のもう一つのサイト,
  <a href="//another.example.com/">another.example.com</a>
もどうぞ!

href 要素で URI を指定する時に,スキーム名 "http:" を省き,スラッシュ 2 つとドメイン名から書き出す事で,それまで HTTP 通信をしていたお客さんはそのまま HTTP 通信,それまで HTTPS 通信をしていたお客さんもそのまま HTTPS 通信でページを遷移する事ができます.このルールは,URI の厳密な文法を提案する RFC 3986 の 5.4 "Reference Resolution Examples" に詳しく書かれています (もちろん,この RFC は Sir Tim Berners-Lee らによるものです).

もしもスラッシュ 2 つが無ければ?

ここは one.example.com のショッピングサイトなんだけど
HTTP や HTTPS 通信のままでドメインを移るには

  <a href="another.example.com/">これじゃだめだよね</a>

  <a href=":another.example.com/">実はこれもだめ</a>

私が慣れ親しんでいる Windows のファイルシステムでは ":"(コロン) はファイル名として使えないので,その常識からすれば,後者のコロンで始まる href 要素は「ああ,スキームが省略されたんだね」と分かります.しかし他の OS が採用するファイルシステムでは,コロンもファイル名として使えるものがあります.このページを置いてある New Coara さんのサーバも,ファイル名にコロンを使う事ができます.そういう事もあってか,前述の RFC 3986 でも,パスにコロンを使う事は禁止されていません.

つまり上記の例では,前者はもちろん,後者も,「現在のディレクトリからの相対パス」と見なさざるを得ないのです.

……と熱く語ってみても,2 つのスラッシュが便利なのは,こういう限られた状況以外には無さそうなんですけどね.

熱血度:85%

[ コロン ]
NTFS では,「ストリーム」という機能のためにコロンが使われます.でも,便利に使われているか否かというと……どうなんすかね.

2009-10-11

標準のランダム関数 rand() がどれだけ弱いのか

「なぜ弱いのか」という本質については,「そういうアルゴリズムだから」以外の専門的なことは分かりませんけども.とりあえず,どれだけ弱いのかを実感する事が出来たのでメモ.

Windows 2000, Perl 5.8.8 (ActiveState のやつ) で次のバッチファイルを動かしました.バッチファイルとはいえ,結局 perl.exe で自分自身を動かすわけですけども.

@echo off
#
# 弱いと言われている乱数生成器が,実際にどれだけ弱いのかを
# 知るためのバッチファイル + perl コード
#

for /l %%c in (1, 1, 50) do (
  perl -x %0
)
goto :EOF

-----------------------------------------------------------
ここから perl コードです

#!perl

print random_phrase(). "\n";
exit;

sub random_phrase
{
    # 12文字のランダムな文字列を作るよ
    my $len = 12;

    # 使用する文字は,この中からランダムで選ぶ
    my @chars = ('a'..'z', 'A'..'Z', '0'..'9');

    my $result = '';

    # srand(time);
    #   乱数のシードは明示的には設定しないものとする.
    #   この場合,perldocによると,5.004 よりも古いバージョンでは
    #   自動的に srand(time) が行われていた,との事.
    #   5.004 以降は,もっとよいシードが設定されているのかな?

    # でも少しくらいプロセス番号でひっかきまわした方がいいかも
    for (my $i = 0; $i <= ($$ % 17); $i++) {
        rand();
    }

    while (length($result) < $len) {
        my $rand = int(rand(0x100_0000));  # 0 〜 0xff_ffff の乱数

        # なんか微妙にヘンな事をやって result を生成しているけども
        # とにかくランダムであれば何だっていいと思ったから...
        while (0 < $rand) {
            $result .= $chars[$rand % @chars];
            $rand >>= 8;
        }
    }

    return substr($result, 0, $len);
}

以下のリストは,上記スクリプトで得られた文字列 50 個のうち,ある条件で 26 個抽出したもの.生成された 50 個の完全なリストは ./SPECIAL/20091011/randoms.htm を参照してください.

skNAQuusGgyf
82jwAUeqUAQA
usyqcQQSQ0wB
kOzU8baaMwAQ
cijskGYo14Mh
YoCmWwgyrmWY
mWkKuowAXgy5
E6eAQqyIjOKI
AQNOK20w9WgV
AQJo420weYoy
eqIgynmWVMC3
wAlciFskho4o
wAZQShskccim
skCE6UU87CYb
gytmWIIm5MCp
usWqcmciici8
YoUus9iGCciV
iGesk34MfgyD
wAIgyzyIsciu
OKyaangy0S0R
mWXAQfAQSU89
skoOKfgyoMCY
gy8OKfkOwE65
QSjgyICYaCY5
GeRS0TKuAskG
S0gaamYonusL

最初に得られた文字列は skNAQuusGgyf でした.さてこの先頭の 2 文字 "sk" が並ぶ確率は,62分の1 × 62分の1 = 3844分の1 です.じゃあ実際に "sk" がどれだけ含まれているのかを見てみると…… (注意:視覚的ブラウザでないと色が見えません.CSS2 にちゃんと対応したブラウザを推奨)

skNAQuusGgyf
82jwAUeqUAQA
usyqcQQSQ0wB
kOzU8baaMwAQ
cijskGYo14Mh
YoCmWwgyrmWY
mWkKuowAXgy5
E6eAQqyIjOKI
AQNOK20w9WgV
AQJo420weYoy
eqIgynmWVMC3
wAlciFskho4o
wAZQShskccim
skCE6UU87CYb
gytmWIIm5MCp
usWqcmciici8
YoUus9iGCciV
iGesk34MfgyD
wAIgyzyIsciu
OKyaangy0S0R
mWXAQfAQSU89
skoOKfgyoMCY
gy8OKfkOwE65
QSjgyICYaCY5
GeRS0TKuAskG
S0gaamYonusL

およ!? なんかヤバいくらい多くないすか.じゃあ "kN" は? "NA" は? ……そうして調べていくと……

skNAQuusGgyf
82jwAUeqUAQA  AQ が含まれていた
usyqcQQSQ0wB  us    〃
kOzU8baaMwAQ  AQ
cijskGYo14Mh  sk
YoCmWwgyrmWY  gy
mWkKuowAXgy5  gy
E6eAQqyIjOKI  AQ
AQNOK20w9WgV  AQ
AQJo420weYoy  AQ
eqIgynmWVMC3  gy
wAlciFskho4o  sk
wAZQShskccim  sk
skCE6UU87CYb  sk
gytmWIIm5MCp  gy
usWqcmciici8  us
YoUus9iGCciV  us
iGesk34MfgyD  sk  gy
wAIgyzyIsciu  gy
OKyaangy0S0R  gy
mWXAQfAQSU89  AQ
skoOKfgyoMCY  sk  gy
gy8OKfkOwE65  gy
QSjgyICYaCY5  gy
GeRS0TKuAskG  sk
S0gaamYonusL  us

惨憺たる結果に.

文字列生成のアルゴリズムを再度確認してみると,これら文字列は,rand() で得られた数値の 0〜7 ビット目を 0 文字目,8〜16 ビット目を 1 文字目……などとして取得します.つまり,rand() で得られた数値 0〜7 ビット目,8〜16 ビット目には,何かしらの,非常に簡単な相関が見えそうです.

ちゃんと調査するならば,いろいろ確率を求めてさあナントカ検定だ帰無仮説だあーだこーだですけども,残念ながら私にちゃんとした知識が無いので省略.でも「誕生日のパラドックス」を考慮するまでもなく,直感的に,こりゃまずい事が分かります.

これをパスワード (や,Web アプリのセッションID) に使っちゃうとしましょう.攻撃者は「このシステムのパスワードに使われる文字のうち,どの 2 文字も必ず "sk" とか "AQ" とか……うん,たった 1000 種類くらいに絞れるんだぜ」のように,意外にコンパクトな攻撃用辞書を作る事が出来てしまうかもしれません.

もっとじっくり観察すれば,さらに他の特徴を見抜くでしょう.例えば "sk" も "AQ" もどれもこれも,0 文字目から始まっているか,あるいは 3 文字目からか,あるいは 6 文字目からか,つまり 3 の倍数が関係している事が多いという規則があります (もっとも,その問題の本質は rand() ではなく私のアルゴリズムにありますが),仮に文字列生成アルゴリズムを公開しなかったとしても,そのアルゴリズムがなんとなく推測できてしまう気がしませんか?

[ 0 文字目 ]
ゼロオリジンです.
[ 非常に簡単な相関 ]
とはいえ,「暗号やハッシュ関数を突破しようとする人たちにとっては」というレベルではありますけども.
[ セッション ID ]
Web アプリが「あなた(ユーザさん)の情報は私がしっかり憶えておくから,もう入力しなくていいよ.そのかわり,はい,これセッション ID ね.次に来る時はこれを教えてね」と言いつつブラウザに渡すもの.つまり,パスワードと同程度に重要な極秘情報.

じゃあ,どうすればいいのか

例えば今回のようにランダムな文字列を作りたいのであれば,良質なライブラリが揃っています.

しかし,現実として,それらが使えない場合も多々あります.

最近,シビアな動作速度を求められる仕事の中で「HTTP レスポンスとして JSON で結果を返す」というものがありました.任意のオブジェクトから JSON 文字列を返すライブラリはいくつかありましたが,しかしどのライブラリも最低限の速度を達成できず,結局,自前での処理に落ち着いてしまいました.自分のプロジェクト内のオブジェクトなら,構造が自明なのでリフレクション等を使う必要が無く,速度が稼げたというわけです.

お世話になっているプロバイダ "New Coara" さんの共用 CGI サーバの環境は……詳しく書くのはあれですけども,必ずしも最新のイロイロが入っているとは限りません.例えば Digest や CGI::Session といったモダンなパッケージは入っていません.すでに我々ユーザが自前の CGI を動かしているのに,パッケージをアップデートしちゃって「なんか動かなくなったよ」となれば,coara さんには余計な仕事が増えてしまいます.我々ユーザに対するサポートは大切ですけども,そこは費用対効果.

あまり質の良くない rand() も,下位 16 ビット程度を切り捨てれば何とかなる,という話を聞きますね.
メルセンヌ・ツイスタ以外で,実装も簡単で評価されている擬似乱数といえば XorShift.しかしシードをどのような形で与えればいいのか,よく分からない人多数……私もその一人…….
他には,Web アプリのセッション ID を生成するならば,一方向ハッシュ関数を通すのが手軽で良さそう.大抵のセッションライブラリは,やはりハッシュ関数を用いているようです.

で,1 年と 9 ヶ月くらい前に作ったまま,使い道が無くて放置していた Perl のコードを公開するわけです.

SHA1 の Perl による実装とテスト用スクリプト

処理速度などの特徴は特にないわけですけども,どうしてもこんな軽量ライブラリが必要な時ってありますよね.

2009-10-10

[Win][メモ] Windows Server 2008 さわってます

ええ,さわってますとも.PowerShell とか初めて知りました.そんな感じで知った知識を,エライヒトに怒られない程度にメモ.よく分からない事が多すぎるので,以下の情報は間違いを多く含む可能性があります.

なんか素人丸出しですな (;´Д`) こんなんですいません

Written by kuri|minima(tkuri {at} fat.coara.or.jp) - all rights reserved.(warai
このリソースの位置情報は http://www.coara.or.jp/%7etkuri/D/045.htm で安定しています。