go bcryptのコードを読む

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

- [bcrypt - GoDoc](https://godoc.org/golang.org/x/crypto/bcrypt)

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

# bcrypt.goのコードを見てみる
[bcrypt.go](https://github.com/golang/crypto/tree/master/bcrypt/bcrypt.go)

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

- [GenerateFromPassword](https://github.com/golang/crypto/blob/master/bcrypt/bcrypt.go#L89)
- [CompareHashAndPassword](https://github.com/golang/crypto/blob/master/bcrypt/bcrypt.go#L99)

## 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](https://github.com/golang/crypto/blob/master/bcrypt/bcrypt.go#L224)

```go
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](https://github.com/golang/crypto/blob/master/bcrypt/bcrypt.go#L144)

```go
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](https://github.com/golang/crypto/blob/master/bcrypt/bcrypt.go#L208)

```go
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暗号化のインスタンスを返す。

```go
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](https://github.com/golang/crypto/blob/master/bcrypt/bcrypt.go#L234)

```go
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](https://github.com/golang/crypto/blob/master/bcrypt/bcrypt.go#L256)

```go
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](https://github.com/golang/crypto/blob/master/bcrypt/bcrypt.go#L272)

```go
// 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](https://github.com/golang/crypto/blob/master/bcrypt/bcrypt.go#L175)

```go
// 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](https://github.com/golang/crypto/blob/master/bcrypt/bcrypt.go#L180)

```go
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はある程度制限した方がよさそう。

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