署名などの検証に定数時間の比較関数を使う

Go

全裸bot for LINE - すぎゃーんメモ の記事にフィードバックをいただきまして。

全然知らなかったのだけど、Timing attackという攻撃手法が存在するそうで。

たとえば文字列の比較で、先頭から1文字ずつ比較していってその中身が異なっていたらreturnする、という処理をしている場合。

func cmpstring(s1, s2 string) int {
	l := len(s1)
	if len(s2) < l {
		l = len(s2)
	}
	for i := 0; i < l; i++ {
		c1, c2 := s1[i], s2[i]
		if c1 < c2 {
			return -1
		}
		if c1 > c2 {
			return +1
		}
	}
	if len(s1) < len(s2) {
		return -1
	}
	if len(s1) > len(s2) {
		return +1
	}
	return 0
}

パスワードや署名の検証など「正しい文字列が与えられたらtrue、そうでない場合はfalse」という場面でこういう方法で文字列比較を行っていると、与える文字列によって処理の演算回数が変わるので、その実行時間を計測しながら何度も試行することで正しい文字列が推測できてしまう、ということらしい。

今回のようなHTTP経由での数バイトの文字列比較ではネットワーク遅延などの誤差の方が遥かに大きく この手法で破れるとはあまり思えないけれど、こういったものを防ぐために「入力の値にかかわらず定数時間で処理を行う比較関数」がちゃんと用意されているので、それを使うのがベターでしょう。

func (bot *Bot) checkSignature(signature string, body []byte) bool {
	decoded, err := base64.StdEncoding.DecodeString(signature)
	if err != nil {
		return false
	}
	hash := hmac.New(sha256.New, []byte(bot.ChannelSecret))
	hash.Write(body)
	return hmac.Equal(decoded, hash.Sum(nil))
}

このhmac.Equalが中でsubtle.ConstantTimeCompareを使うようになっていて、その実装が

// ConstantTimeCompare returns 1 iff the two slices, x
// and y, have equal contents. The time taken is a function of the length of
// the slices and is independent of the contents.
func ConstantTimeCompare(x, y []byte) int {
	if len(x) != len(y) {
		return 0
	}

	var v byte

	for i := 0; i < len(x); i++ {
		v |= x[i] ^ y[i]
	}

	return ConstantTimeByteEq(v, 0)
}

// ConstantTimeByteEq returns 1 if x == y and 0 otherwise.
func ConstantTimeByteEq(x, y uint8) int {
	z := ^(x ^ y)
	z &= z >> 4
	z &= z >> 2
	z &= z >> 1

	return int(z)
}

のようになっていて、必ずすべてのbyteについて比較してその結果が等しくなっているかどうか、という計算になっているようだ。
こういった比較関数を使うことでTiming attackを防ぐことができる。