安全な文字列比較を再確認：タイミング攻撃への備え

この記事は何

先日Go言語の認証系ミドルウェアの実装を見ていたら、subtle.ConstantTimeCompareという関数が使われているのを見かけました。サイドチャネル攻撃の1種であるタイミング攻撃への対策として使われるものですね。

この記事ではsubtle.ConstantTimeCompareの実装詳細を見ながら、タイミング攻撃への対策として行われていることを再確認してみます。また視野を広げて他のプログラミング言語ではどのような対応がされているかも調べてみましょう。

タイミング攻撃とは？

まず最初に、タイミング攻撃とは何だったでしょうか？

タイミング攻撃（タイミングこうげき、英:timing attack）とは、アルゴリズムの動作特性を利用したサイドチャネル攻撃のひとつ。暗号処理のタイミングが暗号鍵の論理値により変化することに着目し、暗号化や復号に要する時間を解析することで暗号鍵を推定する手法。(Wikipedia: タイミング攻撃 より引用)

「暗号化や復号に」とありますが、単純な文字列の比較でも理論的には^[1]攻撃が起こり得ます。例えば文字列を先頭から順に比較していき、文字列の途中で文字が異なった場合に即座にfalseを返すような処理を行っている場合は、理論的には合致する文字数分だけ処理時間が延びるためです^[2]。そこで各プログラミング言語において、内容に依らず一定時間(文字列の長さによる)で文字列を比較する関数が用意されています。Go言語ではcrypto/subtleパッケージのConstantTimeCompareがそれに当たります。

subtle.ConstantTimeCompareの実装

では、subtle.ConstantTimeCompareのような関数は何をしているのでしょうか。Go1.23.4のcrypto/subtleパッケージのソースコードをここに引用します。

constant_time.go

func ConstantTimeCompare(x, y []byte) int {
	if len(x) != len(y) {
		return 0
	}

	var v byte

    // 補足：全てのbyteが等しければ0,そうでなければ1
	for i := 0; i < len(x); i++ {
		v |= x[i] ^ y[i]
	}

    // 補足：上記評価結果が0なら1,そうでなければ0を返す
	return ConstantTimeByteEq(v, 0)
}

1. まず2つの文字列の長さを比較し、長さが違う場合は即座に0を返します。
2. その後は全てのbyte値のXORをORで取ります。つまり全ての値が等しければ0、そうでなければ1です。
3. 最後に評価結果が0なら1、そうでなければ0を返します。

処理の途中で値が異なっても中断しないようになっていますね。これによりタイミング攻撃への耐性を高めているようです。

ただし処理の冒頭で文字列の長さを比較し、長さが異なる場合は即時0を返しています。したがって、この実装では文字列の長さが異なる場合に即座に処理が終了するため、タイミング攻撃によって文字列の長さを推測される可能性はあります。

冒頭で記載したような認証系ミドルウェアの使い方としてはトークンとの比較になるので、トークン長さはある程度は既知とも言えます。文字列長が推測可能であっても懸念は低いかもしれません(セキュリティの要件次第)。
そうでないケース（例えば何か独自の秘密のキーワードと照会する場合）では、正解文字列長さで比較対象をトリム/パディングするなど、文字列長さを揃える実装を加える検討の余地はありそうですね。

他のプログラミング言語での対応

各プログラミング言語が同様の処理を用意しているので、文字列長さの比較処理も含めてどう実装しているのか確認してみたいと思います。

私があまり詳しくない言語であっても、ドキュメントが分かりやすいものを優先して取り上げさせて頂きました。何か認識違いがあればコメントを頂戴できると幸いです。

PHPではhash_equals関数があるのですね。
https://www.php.net/manual/ja/function.hash-equals.php

以下のように注意書きがあるため、Go言語同様に文字列長さは理論的には推測されうるようです。

注意:指定するパラメータは両方、長さが等しくなければいけません。 違う長さの文字列が指定されると、この関数はすぐに false を返すので、 タイミング攻撃が行われた場合に既知の文字列の長さが漏洩するかもしれません。

Pythonではcompare_digest関数があるのですね。
https://docs.python.org/ja/3/library/hmac.html#hmac.compare_digest

こちらも同様の注意書きがあります。

注釈 a と b が異なる長さであったりエラーが発生した場合には、タイミング攻撃で理論上 a と b の型と長さについての情報が暴露されますが、その値は明らかになりません。

おまけでRuby、と思いましたが、こちらは記事が書かれていましたね。Rack::Utils.secure_compareがあるようです。長さが異なる場合の扱いは同じですね。

https://zenn.dev/noraworld/articles/secure-compare-confidential-info

おわりに

以上、安全な文字列比較の方法について調べた結果のメモでした。このような比較処理の必要性と実装上の留意点を把握しておくことは大切ですね。

余談

なんだかんだGo言語の==での文字列比較の実装を探すのが一番大変でしたね…。ソースコード読解力を磨きます…。

脚注

1. 「理論的には」としたのは、文字列の比較アルゴリズムによる一致・不一致による処理時間の差はごくわずかであり、実際のリクエスト時間には様々な要因による変動（バラツキ）が加わるため、適切な測定手法を用いなければ、その差を正確に評価することが困難であるためです。

2. ただし、実際のGo言語の文字列比較処理では、ある程度の長さのデータをまとめて処理する最適化もあり、単純に文字単位で比較していく例のような明確な時間差が生じるとは限りません。https://cs.opensource.google/go/go/+/refs/tags/go1.23.4:src/internal/bytealg/compare_arm64.s;drc=9f252a0462bd8c279beec56d1538e8a6c26c44c5;l=35