一意性の確保 - ハッシュ関数

以下は実験中の Blogger Glass のコード、そのセッション管理を担当するモジュールの一部でセッション ID を生成す関数になっている。

(src/session.py より)
def generate_session_id(seed):
    m = hashlib.sha1()
    m.update(datetime.datetime.now().isoformat())
    m.update(str(seed))
    return m.hexdigest()

以前、ウェブアプリにおけるセッションを病院に治療に来る患者の関係にたとえた(→「Cookie の使い方 - GAE におけるセッションの保持」)。病気(やケガ)の治療では病院側が患者についてさまざまな情報を記録しておき(カルテ)、その記録と患者個人をひもづけるために番号を使うと書いた。この番号に相当するのがセッション ID なのだ、とも書いた。

カルテと患者のひもづけで大事なことはそれが一通りに定まることだ。これが混乱すると(あるカルテが別の患者のものだと扱われる等)大変なことになる。これを確実にするための 1 つの方法は、空白のカルテ用紙にあらかじめ重複しない通し番号を振っておくというものだ。番号の一意性 (uniqueness) が確保できていることが、患者という個人の識別に利用できる理由だ。

ウェブアプリにおけるセッション ID についても、同じことがそのままあてはまる。すなわち、ウェブアプリとクライアント(ブラウザ)のひもづけには、一意性の保証された何かを利用しなければならない。↑で示した関数は、この一意性の保証された何かを、ハッシュ関数(一方向ハッシュ関数とも言う)によって生成している(標準ライブラリの hashlib)。

ところで、このハッシュ関数が生成する「何か」は本当に一意 (unique) なのだろうか？ あるいは完全に一意なものではないとしてどれぐらい一意なのだろう？

一方向ハッシュ関数

先のコードで使っている hashlib.sha1 という関数はハッシュ関数の中でも一方向ハッシュ関数(Wikipedia:ja では暗号学的ハッシュ関数)と呼ばれるものだ。

(「入門SSH」p.44 より)
一方向ハッシュ関数は、任意の長さの入力から固定長の出力を返す関数です。一方向ハッシュ関数の出力は一方向性(出力から入力を得るのが困難)と衝突困難性(同じ出力を得る 2 つの入力を得るのが困難、衝突耐性)を持ちます。この特徴から、ファイルなどが改ざんされていないことのチェック(もしファイルが改ざんされていれば、出力が異なるはず)や電子署名のために入力を短く固定長にするためなどに利用されます。[...snip...]

代表的な一方向ハッシュ関数には、MD5、SHA-1、SHA-256、SHA-512 があります。

もともと、一方向ハッシュ関数はデータの改ざんの有無を検査するような(セキュリティに関係する)目的に使われるが、上記の 2 つの特性のうち「衝突困難性」があるため「一意性の保証された何か」を生成するためにも利用できるわけだ。

さて、hashlib.sha1 で使われている SHA-1 という一方向ハッシュ関数では常に 160 ビットの値を生成する。言い換えると、生成できるのは高々 2^160 個の「何か(符号なしの整数値)」でしかない。もし、毎回異なる値を生成できるとしても、2^160 回以上 ID を生成させれば同じ ID が出てくることになる。そう、これで生成できる「何か」は完全に一意なものではないのだ。

ほどほどの一意性

確かに一方向ハッシュ関数では「完全な一意性」を得ることはできない。でも、良く考えてみれば 2^160 (2 の 160 乗) というのは、結構大きな数だ(→ 「2^64 (2 の 64 乗) って、どれぐらい？」)。うん、いや、結構っていうか、日常生活のスケールでは決して出会うことのないぐらいの大きさだ。ちょっと、Python で計算させてみた。

[imac] mnbi% python
Python 2.6.1 (r261:67515, Feb 11 2010, 00:51:29) 
[GCC 4.2.1 (Apple Inc. build 5646)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> n = 2 ** 160
>>> len(str(n))
49
>>> print n
1461501637330902918203684832716283019655932542976

10 進数で 49 ケタ。つまり、10^48 より大きく、10^49 より小さい。読み方は、10^48 が「極(ごく)」なので……

(2^160 の 10進数表現の読み方)
1    (極)
4615 (載)
0163 (正)
7330 (澗)
9029 (溝)
1820 (穣)
3684 (じょ)
8327 (垓)
1628 (京)
3019 (兆)
6559 (億)
3254 (万)
2976

……となる。つまり「一極四千六百十五載(飛んで)百六十三正七千三百三十澗九千(飛んで)二十九溝千八百二十穣三千六百八十四じょ八千三百二十七垓千六百二十八京三千(飛んで)十九兆六千五百五十九億三千二百五十四万二千九百七十六」だ。

意図的に(たいていは悪意を持って)同じハッシュ値を作ろうとしない限り、同じ値が生成されることはないと言って良い。「完全な」ではないにしろ、「ほどほどの一意性」(実際には「実用的な」と言うべきだろうな)は保証されているようだ。

ちなみに「新版暗号技術入門 秘密の国のアリス」によれば、SHA-1 の「強衝突耐性」は 2005 年に破られたとのこと(同 p.176)。ここで「強衝突耐性」とは

(「新版暗号技術入門 秘密の国のアリス」p.170 より)
強衝突耐性とは、ハッシュ値が一致するような、異なる 2 つのメッセージを見つけ出すことが非常に困難である、という性質です。

のことだ。

もっとも、ウェブアプリとクライアント(ブラウザ)のひもづけるセッション ID としてハッシュ値を使う場合、セッション ID を知られただけでアウトだけどね。病院のたとえで言えば、診察券に書かれた患者番号を誰かに知られてしまい、診察券を偽造されてしまうかもってところか。ま、病院と患者の場合は、そんなことをしても意味がないがね(診察券に病院で治療を受ける以外の使い道があれば別)。

ウェブアプリのセッションを管理する「何か」としてハッシュ値を使う場合、大事なことは異なるクライアントに同じ「何か」をわたさないようにすることだ。「何か」を(通信の)途中で盗まれないようにすることは別問題。

そもそも、Blogger Glass のような「公開情報を読み取り専用で扱う」アプリでセッションを盗まれたとしても大した問題にはならないよ。

参考文献

入門SSH (My UNIX series (04))

春山 征吾
アスキー ( 2004-11 )
ISBN: 9784756145536
おすすめ度:

物読みファイル (別館)で詳細を見る

MediaMarker

新版暗号技術入門 秘密の国のアリス

結城 浩
ソフトバンククリエイティブ ( 2008-11-22 )
ISBN: 9784797350999
おすすめ度:

物読みファイル (別館)で詳細を見る

MediaMarker

The Art of Computer Programming Volume 3 Sorting and Searching Second Edition 日本語版 (Ascii Addison Wesley programming series)

ドナルド・E. クヌース
アスキー ( 2006-04 )
ISBN: 9784756146144
おすすめ度:

物読みファイル (別館)で詳細を見る

MediaMarker

「6.4 ハッシュ法」の一部としてハッシュ関数を扱っている(p.487 〜 492)。ただし、扱っているのは一般的なハッシュ関数であり一方向ハッシュ関数ではない。

関連リンク

• ハッシュ関数 (Wikipedia:ja)
• 暗号学的ハッシュ関数 (同上)
• 命数法 (同上)
• Blogger Glass (GAE アプリ)

関連記事

• Cookie の使い方 - GAE におけるセッションの保持
• 2^64 (2 の 64 乗) って、どれぐらい？

twitter より (2010-11-01)

• 08:31  キレイな図でわかりやすい。ところで、どこからも参照されないコミットは削除されるとは知らなかった。実験はブランチしてどんどんコミットして、いならくなったらブランチを消せばコミットも消える、と。今さらだけど良くできてるなあ > git → http://bit.ly/afxII7

Powered by twtr2src.

リングバッファを作る - リクエスト URL をためておく仕組み (BloggerGlass)

「Back」ボタンを実装するためには、戻るべき画面を記録しておかなければならない。現状の画面遷移だけなら 1 つ前の画面を覚えておけば十分なはずだが、将来のことも考えて、画面遷移の履歴を保持するための仕組みを作ってみることにした。

履歴保存用クラス

実体はリクエスト URL (文字列)を保存しておくためのリスト(Ruby で言うなら配列)に過ぎない。ただし、「前の画面に戻る」ための履歴だから、最後に登録した URL を最初に取り出すことになる。つまり、LIFO (Last In First Out)と呼ばれるデータ構造になる。別の呼び方にスタックというのもある。

スタックなら、操作のためのインタフェースは以下のようになる。

スタックの操作

名称	機能
is_empty	空かどうかを返す
push	データを 1 つ追加する
pop	最後に追加したデータを取り出す(取り出しされたデータはスタックから削除する)
peek	最後に追加したデータを見る(取り出さない)

最低限必要なのは push と pop で、他はあると便利なものだ。

また、この履歴保存用クラスは、スタックであると同時にリングバッファでもある。これは平たく言えば、バッファが一杯になったとき、古いデータが新しいデータで上書きされていくデータ構造だ。

リングバッファにしたかったのには理由がある。直前の画面に戻るための履歴なのだから、バッファが一杯になったからと言って履歴が保存できなくなるのは困る。一方で、古い履歴よりも新しい履歴の方が重要だ。そういう意味で、新しいデータを常に保存することができる(その代わり古いデータは消えていく)リングバッファは最適だと言える。

export_history と import_history は、履歴をセッションデータとしてデータストアに収めるときに使用する(ことになるはず)。

単体テスト

RequestHistory クラスは、以下のような単体テストを書きながら、そしてテストしながら実装した。50 行足らずの短いプログラムだと言うのに意外に難しかった。何度「これで良い(はず)！」と思ってからテストに失敗したことか。こういう一般的なプログラムを書くときは、本当にテストが役に立つ。

(tests/util_test.py より)
import unittest

import pathconf
# target module 
import util

class RequestHistoryTest(unittest.TestCase):
    def setUp(self):
        self.history = util.RequestHistory()

    def test_is_empty(self):
        """empty?(EMPTY) == True"""
        self.assert_(self.history.is_empty())

    def test_peek(self):
        """peek(push(EMPTY, A)) == A,
        then pop() also returns A
        """
        self.history.push('/1')
        self.assertEqual(self.history.peek(), '/1')
        self.assertEqual(self.history.pop(), '/1')

    def test_pop_against_empty(self):
        """pop(EMPTY) == None"""
        self.assertEqual(self.history.pop(), None)

    def test_push_1_pop_1(self):
        """pop(push(EMPTY, A)) == A"""
        self.history.push('/')
        self.assertEqual(self.history.pop(), '/')

    def test_push_2_pop_2(self):
        """pop(push(push(EMPTY, A), B)) == B
        pop(pop(push(push(EMPTY, A), B))) == A
        """
        self.history.push('/')
        self.history.push('/foo')
        self.assertEqual(self.history.pop(), '/foo')
        self.assertEqual(self.history.pop(), '/')

    def test_push_10_pop_10(self):
        """H = push(push(...(push(EMPTY, 0), 1), ...), 9)
        then, pop(pop(...(pop(H))...)) = 0
        """
        for i in range(10):
            self.history.push("/%d" % i)
        for i in reverse_range(10):
            self.assertEqual(self.history.pop(), ("/%d" % i))

    def test_push_11_pop_10(self):
        """H = push(push(...(push(EMPTY, 0), 1), ...), 10)
        then, pop(pop(...(pop(H))...)) = 1
        """
        for i in range(11):
            self.history.push("/%d" % i)
        r = reverse_range(11)
        r.pop()
        for i in r:
            self.assertEqual(self.history.pop(), ("/%d" % i))

    def test_export_history(self):
        for i in range(10):
            self.history.push("/%d" % i)
        h = self.history.export_history()
        for i in range(10):
            self.assertEqual(h[i], ("/%d" % i))

    def test_import_history(self):
        h = []
        for i in range(10):
            h.append("/%d" % i)
        self.history.import_history(h)
        r = range(10)

    def test_pickle(self):
        """Make sure that it can be pickled in and out."""
        for i in range(10):
            self.history.push("/%d" % i)
        pickled = pickle.dumps(self.history)
        history = pickle.loads(pickled)

        for i in reverse_range(10):
            self.assertEqual(history.pop(), ("/%d" % i))

def reverse_range(n):
    r = range(n)
    r.reverse()
    return r

def suite():
    return unittest.TestSuite((
            unittest.makeSuite(RequestHistoryTest, 'test'),
            ))

if __name__ == '__main__':
    unittest.TextTestRunner().run(suite())

関連リンク

• リングバッファ (Wikipedia:ja)
• 構造としてのFIFO(リングバッファ) (Super Technique 講座)

関連記事

• GAE アプリ用に PyUnit を使って単体テストを書く

Cookie の使い方 - GAE におけるセッションの保持

前回(「iPhone アプリらしく #2」)にも書いたように、Blogger Glass は「画面遷移だけの(とても古臭い)ウェブアプリ」だ。これを iPhone アプリらしく見せるためには、ぜひとも「Back」ボタンが必要だ。というのも、iPhone アプリでは、ある画面からボタンやら何やらを押すことで子画面を開き、そこで作業が完了すると親画面に戻る、という操作が良く実装されている。このユーザ体験を実現することは、iPhone アプリとしてごく標準的なことなのだ。

しかし、ウェブアプリでこれ(一つ前に開いていた画面に戻る)をやろうとすると、セッションの保持(と管理)という壁にぶつかる。ステートレスな HTTP 上に作られるウェブアプリの宿命だ。

Blogger Glass では、ここまでセッション管理にまつわることを避けてこれたが、それもそろそろ限界。このあたりで、ちゃんとセッション周りを実装することにしよう。

実現方法

ウェブアプリにおけるセッションの概念とは、たとえるなら病院(医者)とそこに治療に来る患者の間にあるものだ。初診時に治療セッションが始まり、完治によって終了する。

患者は病気なりケガなりの治療で数回、病院を訪れることになる(セッションの継続)。その度に、病院(医者)の側が患者のことをすっかり忘れてしまっては治療は成立しない。病院(医者)は個々の患者について、病気(やケガ)の状態と治療の経過を記録しておかなければならない。それが患者ごとに用意されるカルテと呼ばれる記録だ。

一方、カルテに書かれた記録を有効に利用するためには、患者一人一人を識別できるようにする必要がある。大抵は(カルテに書かれた)患者の名前で間に合うが、中には同姓同名の患者もいるから常に確実な方法とは言えない。そんなわけで患者に一意の番号を割り当て、それでカルテと患者をひもづける。でも、患者にとったら何桁にもなる番号を覚えるのは大変なので、病院はこの番号を記録したカード、すなわち診察券を用意して、初診時に患者にわたす。

病院がウェブアプリで患者がブラウザ、カルテはウェブアプリが記録するセッション情報で、カルテと患者をひもづける番号がセッション ID という対応関係になる。

残るは診察券に対応するモノ(ブラウザ側にセッション ID をわたすための仕組み)だが、これには 3 つの方法がある。すなわち、(1) URL に埋め込む方式、(2) HTML のフォームに隠し要素として埋め込む方式、(3) cookie を使ってわたす方式、の 3 つだ。

練習も兼ねて、今回は (3) の方式でセッションを実現してみる。

サンプルプログラム

以下のサンプルプログラムでは、セッション情報(整数値 1 つ)は GAE の提供するストレージサービスの 1 つである memcache を利用している。このサービスはもう 1 つのデータストアとは違い、「揮発性」のストレージだ。容量も(データストアに比べればかなり)小さい。その代わり、ずっと高速に動作するらしい。頻繁にアクセスする少量のデータは、memcache に置く方が良い。

このプログラムを GAE アプリのリクエストハンドラにしてアクセスすると、「Back」と「Forward」という 2 つのリンクを持つページが開く。Forward をたどると memcache 中のデータ(カウンタ)がインクリメントされ、Back をたどればデクリメントされる。ただ、それだけのプログラムだが、内部的にはセッション管理がなされており、memcache に保持される値はクライアントごとに用意される。実際に複数のブラウザで開けばそのことがわかる。

memcache に保存するカウンタとは別に、データストアにも 1 つ値を保存している。これはセッション管理そのものとは関係ない。この値は、セッションを作るために必須の ID (先の病院と患者のたとえで言うなら、カルテと患者をひもづける番号だ) を作るための「種」になっている。

セッション管理の仕組み自体は単純で、リクエストを受けたら(ハンドラの get メソッドが呼ばれたら)、ブラウザが送ってきた cookie からセッション ID を取り出す。次にセッション ID をキーとして memcache からカウンタの値を取り出す。

ブラウザが cookie を送ってこなかった、あるいは(このプログラム用の)セッション ID がふくまれていないときは、新しくセッション ID を生成しレスポンスヘッダに入れる。

「Back」ボタンを実装するには

Blogger Glass (の iPhone 用画面)に「Back」ボタンを実装するには、画面を開くときにリクエスト URL をセッション情報として保存すれば良い。「Back」ボタンには専用のリクエスト URL を用意しておく(たとえば /back)。そのリクエストハンドラでは、セッション情報から保存されたリクエスト URL を取り出し、そこにリダイレクトする。

まだ、コードを書いていないから確信はないけれど、だいたいこんな感じで動きそうだ。

関連リンク

• HTTP Cookies (Studying HTTP)
• How to use HTTP cookies in Python (jayconrod.com)
• Using Memcache (GAE 公式ドキュメントより)

関連記事

• iPhone アプリらしく #2 - 実装 (Blogger Glass)

twitter より (2010-10-30)

• 18:12  知らなかったよ(´・ω・｀) → 「ホームシェアリング間で iTunes Store コンテンツを自動転送」 http://support.apple.com/kb/HT3819?viewlocale=ja_JP

Powered by twtr2src.