Python の hash関数

Google Code University に Gruyere というデモサイトを使って、Webアプリケーションの脆弱性と対策を説明しているガイドがあります。

少しずつ読み進めているのですが、cookie処理の部分について少し調べてみました。

gruyere.py (601行目)

def _CreateCookie(self, cookie_name, uid):
    ....
    h_data = str(hash(cookie_secret + c_data) & 0x7FFFFFF)

発行するcookieにハッシュ値を付与している部分ですが、「Pythonのhash関数はセキュアでないため、"違う文字列で同じハッシュ値" を短い時間で発見できる」と説明されています。

そうすると cookie_secret を知らなくても、cookieの改ざんができてしまうため、この用途にhash関数は向いていないとのこと。対策として「セキュアなhash関数を使用する」とあるので、hashlib などを使用するべきなのかな。

そもそも、Pythonのhash関数は dict での使用に適するようにされていて、ランダムよりも（末尾の文字がインクリメントされるような）よく似たケースにおいて規則的な変化をする性質を重視していると dictobject.c のコメントに書かれているんですね。

python/Objects/dictobject.c

/*
Major subtleties ahead:  Most hash schemes depend on
having a "good" hash function, in the sense of simulating
randomness.  Python doesn't:  its most important hash
functions (for strings and ints) are very regular in
common cases:
'''
>>> map(hash, (0, 1, 2, 3))
[0, 1, 2, 3]
>>> map(hash, ("namea", "nameb", "namec", "named"))
[-1658398457, -1658398460, -1658398459, -1658398462]

また、Pythonのhash関数はFNVというアルゴリズムに近いものだそうだ。

FNV-1 hash algorithm

hash = FNV_offset_basis
for each octet_of_data to be hashed
    hash = hash  FNV_prime
    hash = hash XOR octet_of_data

python/Objects/stringobject.c

string_hash(PyStringObject *a)
{
    ...
    x = *p << 7;
    while (--len >= 0)
        x = (1000003*x) ^ *p++;

この辺りがそうなのかな。
きちんと理解できるように、がんばらねば。