lifeLOG + REPOsitory: 一意性の確保

以下は実験中の 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 のような「公開情報を読み取り専用で扱う」アプリでセッションを盗まれたとしても大した問題にはならないよ。