go bcryptのコードを読む

最近業務でログイン機能を実装する機会があり、特に迷うことなくbcryptを採用したが、そもそもgoのbcryptは内部で何をやっているのか気になったので調べてみました。
(bcryptについての記事は数多くあるので今更感はあるが、自分の言葉でまとめてみる。)

• bcrypt - GoDoc

そもそもbcryptとは何？

blowfishという暗号化方式を用いたパスワードハッシュアルゴリズムのこと。
ソルトを用いてハッシュ化していることと、ストレッチングもしてくれるので、より強固なハッシュ値を求められる。
bcryptはソルトを内包しているので別々に保存する必要はない。
※ちなみにソルトを内包するハッシュアルゴリズムは他にもある。

bcrypt.goのコードを見てみる

bcrypt.go

大きく分けて2つの関数が用意されている。

• GenerateFromPassword
• CompareHashAndPassword

GenerateFromPassword

引数にpasswordとcostをとる。

引数	説明
password	ハッシュ化前のパスワード。
cost	ストレッチングの回数を決める為の数値。

実装内容

1. バージョンの指定

bcryptアルゴリズムには、majorVersionとminorVersionがある。

バージョン	説明
majorVersion	言語に関わらず同じで 2。
minorVersion	言語によって不具合の修正があった為異なる。golangでは a。

2. コストの指定

引数で渡されたcostをそのまま使用。
ただし 4 <= cost <= 31の範囲である必要がある。

minが4の理由は調べても出てこなかったが、おそらくこの程度はストレッチングしないと強いハッシュ値は生成できないということなのだろう。

maxが31なのは、32だと言語によってはint32をオーバーフローしてしまうからである。
そもそもcostがどう使われているのかというと、goの実装では下記のようになっている。

code

var i, rounds uint64
rounds = 1 << cost
for i = 0; i < rounds; i++ {
    blowfish.ExpandKey(ckey, c)
    blowfish.ExpandKey(csalt, c)
}

uint64なのでgoではオーバーフローの心配はないが、仮にuint32だった場合、
1 << 31は2147483648なのでオーバーフローしてしまう。

ちなみに上記のコードのroundsがスレッチング回数である。
例えばcost = 10なら2**10 = 1028回ストレッチングすることになる。

3. ソルトの生成

code

unencodedSalt := make([]byte, maxSaltSize) // maxSaltSize is 16
_, err = io.ReadFull(rand.Reader, unencodedSalt) // rand from crypto/rand
if err != nil {
    return nil, err
}

p.salt = base64Encode(unencodedSalt)

指定サイズ分のランダムなバイト列を取得し、base64エンコードしている。
※base64Encodeの中で、パディングされた=は除去される。

4. パスワードをハッシュ化

コスト、ソルトを用いてハッシュ化する。

code

func expensiveBlowfishSetup(key []byte, cost uint32, salt []byte) (*blowfish.Cipher, error) {
    // keyにはpasswordが渡される

    csalt, err := base64Decode(salt)
    if err != nil {
        return nil, err
    }

    ckey := append(key[:len(key):len(key)], 0)

    c, err := blowfish.NewSaltedCipher(ckey, csalt)
    if err != nil {
        return nil, err
    }

    var i, rounds uint64
    rounds = 1 << cost
    for i = 0; i < rounds; i++ {
        blowfish.ExpandKey(ckey, c)
        blowfish.ExpandKey(csalt, c)
    }

    return c, nil
}

パスワード(ckey)とソルト(csalt)のキー拡張を2**cost回実行する。
特定のキーを使うblowfish暗号化のインスタンスを返す。

for i := 0; i < 24; i += 8 {
    for j := 0; j < 64; j++ {
        c.Encrypt(cipherData[i:i+8], cipherData[i:i+8])
    }
}

OrpheanBeholderScryDoubtという文字列のバイト列を64回暗号化する。
8文字毎に暗号化しているのは、Ecryptメソッドの仕様。

暗号化されたバイト列をbase64エンコードして、パスワードのハッシュ化は終了。

5. bcryptの最終的なハッシュ値を生成する

code

func (p *hashed) Hash() []byte {
    arr := make([]byte, 60)
    arr[0] = '$'
    arr[1] = p.major
    n := 2
    if p.minor != 0 {
        arr[2] = p.minor
        n = 3
    }
    arr[n] = '$'
    n++
    copy(arr[n:], []byte(fmt.Sprintf("%02d", p.cost)))
    n += 2
    arr[n] = '$'
    n++
    copy(arr[n:], p.salt)
    n += encodedSaltSize
    copy(arr[n:], p.hash)
    n += encodedHashSize
    return arr[:n]
}

この結果を文字列に置き換えると、
$2a$10$mwjwL9TurdHGlJpO4LTL9ONo0ca.NLKkMl022.nncI62YPfZF393K
のようなハッシュ値になる。

分割すると、

文字	説明
2a	バージョン
10	コスト
mwjwL9TurdHGlJpO4LTL9O	ソルト部（22文字）
No0ca.NLKkMl022.nncI62YPfZF393K	パスワード部（31文字）

過去に生成されたbcryptのハッシュ値を考慮すると、minorVersionがない場合もあるので、
ハッシュ値の長さは59 or 60ということになる。

CompareHashAndPassword

引数にhashedPasswordとpasswordをとる。

引数	説明
hashedPassword	パスワードのハッシュ値
password	ハッシュ化前のパスワード

実装内容

こちらの実装はいたってシンプル。

1. ハッシュ値からバージョンを抽出

code

func (p *hashed) decodeVersion(sbytes []byte) (int, error) {
    if sbytes[0] != '$' {
        return -1, InvalidHashPrefixError(sbytes[0])
    }
    if sbytes[1] > majorVersion {
        return -1, HashVersionTooNewError(sbytes[1])
    }
    p.major = sbytes[1]
    n := 3
    if sbytes[2] != '$' {
        p.minor = sbytes[2]
        n++
    }
    return n, nil
}

2. ハッシュ値からコストを抽出

code

// sbytes should begin where decodeVersion left off.
func (p *hashed) decodeCost(sbytes []byte) (int, error) {
    cost, err := strconv.Atoi(string(sbytes[0:2]))
    if err != nil {
        return -1, err
    }
    err = checkCost(cost)
    if err != nil {
        return -1, err
    }
    p.cost = cost
    return 3, nil
}

前段でバージョン部が除去された状態で渡されてくる。

3. ハッシュ値からソルトを抽出

code

// The "+2" is here because we'll have to append at most 2 '=' to the salt
// when base64 decoding it in expensiveBlowfishSetup().
p.salt = make([]byte, encodedSaltSize, encodedSaltSize+2)
copy(p.salt, hashedSecret[:encodedSaltSize])

前段でさらにコスト部が除去された状態で渡されてくる。
コスト部の後の22文字を抽出。base64エンコードされたソルトが抽出できる。

4. ハッシュ値からパスワードを抽出

code

hashedSecret = hashedSecret[encodedSaltSize:]
p.hash = make([]byte, len(hashedSecret))
copy(p.hash, hashedSecret)

ソルトの後の全て。パスワードのハッシュ値が抽出できる。

5. コストとソルトとパスワードをハッシュ化

GenerateFromPassword内のbcryptを実行する

6. ハッシュ値を比較する

引数passwordのハッシュ値と、引数hashedPasswordを比較し、一致していればOK。

コードを読んでいて気が付いたこと

ストレッチング回数に関して、2**cost回分行われるので、costの数値が大きい方がより強固なハッシュ値が求められる。
それだけ聞くと、じゃあ cost = 31 でいいのでは？と思うかもしれない。
しかし 2**31 だと約21億回もストレッチングするので、ハッシュ化にものすごい時間がかかってしまう。
注意してほしいのは、パスワードの検証(CompareHashAndPassword)の内部でもハッシュ値を求めているということだ。
つまり最初のハッシュ値の生成で高いcostを指定すると、パスワードを検証する度にものすごい回数ストレッチングすることになり、なかなか検証が終わらないということになる。

主にログインなどの認証で使われると思うので
「いつまで経ってもログインできないじゃん！なんだこのサービスくそ！」
とならないように、costはある程度制限した方がよさそう。

ストレッチとはそういうものである。