Go to Qiita Advent Calendar 2024 Top
LoginSignup
8
6

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

第二のドワンゴAdvent Calendar 2018

Day 13
@saka1_pin株式会社 ドワンゴ

タイミング攻撃とDouble HMAC Verification

Last updated at Posted at 2018-12-13

Double HMACパターンというものの存在を最近知ったので、まとめました。

記事の前半では、文字列比較に関するタイミング攻撃の概要と、対策方法（特に定数時間比較について）をまとめます。後半では対策方法の一つであるDouble HMAC Verificationについて紹介します。

……などと偉そうに書いてはいますが、筆者はセキュリティ専門家でもなんでもないので、記述内容を参照される方はその点ご留意ください。セキュリティの分野は本来、素人が実装をするべきではないとは思います。

読んだサイト

Double HMAC Verification

タイミング攻撃

サイドチャンネル攻撃という攻撃方法があります。処理にかかる時間・消費電力・電磁波など、その処理から漏れ出た情報を元に、本来入手できないはずの情報を得る手法です。

サイドチャンネル攻撃の一形態として、タイミング攻撃というものがあります。
例えば、あるWeb APIを使うにはトークンによる認可が必要だという状況を考えます。APIサーバはHTTPリクエストのパラメータを見て、そのアクセスの正当性を確認します（普通はこんな実装をしないとは思いますが……）。

$ curl https://example.com/api?key=qdYYhLZzgk0w4fFQeEblwUWTjW
OK
$ curl https://example.com/api?key=yyyyyyyyy
BadRequest

APIサーバ側の実装はこんな感じになるでしょうか。雰囲気だけRubyで書きました。

require 'sinatra'

SECRET_KEY = 'qdYYhLZzgk0w4fFQeEblwUWTjW'

get '/api' do
  key = params['key']
  if key == SECRET_KEY
    # keyを知っている人だけが呼べる処理
    # ...
    return 200
  end
  401
end

さて、 攻撃者が入力を任意に選び、多数の試行ができるという条件においては、 key == SECRET_KEY のようにトークンの検証を一般的な同値比較で行うのは不適切だと知られています。

攻撃のシナリオとしては、攻撃者は適当な文字列で試行を繰り返します1。

$ curl https://example.com/api?key=axxxxxxxx
BadRequest
$ curl https://example.com/api?key=bxxxxxxxx
BadRequest
$ curl https://example.com/api?key=cxxxxxxxx
BadRequest

...

$ curl https://example.com/api?key=qxxxxxxxx
BadRequest

通常の文字列一致の実装は「先頭から1文字ずつ比較」であるなら、 qxxxxxxxx の時だけ、わずかに処理時間が伸びるはずです。なぜなら1文字目が合っているので弾かれず、2文字目までを比較することになるからです。このわずかな差を（時には統計的手法などで）検出できれば、 SECRET_KEY の先頭が q である事がわかります。以下同様に、2文字目3文字目と秘密にしてあったはずのトークンが割り出されてしまいます。
つまり、秘密情報が処理時間差によって漏れてしまうのです。

ちなみに、ここではWeb APIの認証トークンのようなものを例として使いましたが、例えば何らかのハッシュ値の比較をする時など、実装上ケアしなければならない箇所は潜在的に非常に広いです。

対策（定数時間比較）

前節の議論から、「情報が漏れ出るような比較処理をしてはならない」という事がわかります。
そんなわけで、たいていのプログラミング言語では文字列の定数時間比較（constant time string comparison）をするための実装があります。比較回数が入力の内容に依存しないように、文字列全体の情報を使う実装になっているのが特徴的です。

例として、OpenBSDのC実装例です。

int
timingsafe_bcmp(const void *b1, const void *b2, size_t n)
{
	const unsigned char *p1 = b1, * p2 = b2;
	int ret = 0;

	for (; n > 0; n--)
		ret |= *p1++ ^ *p2++;
	return (ret != 0);
}

文字列全体について、文字単位でbit xorしたものをbit orで畳み込んでいます。どこか一致しない箇所があったらxor結果が非0になるので、それが ret に蓄積されたかで判定できるというアルゴリズムのようです。

他の例として、Ruby on Railsも似たような戦略を採用しています。

def fixed_length_secure_compare(a, b)
  raise ArgumentError, "string length mismatch." unless a.bytesize == b.bytesize

  l = a.unpack "C#{a.bytesize}"

  res = 0
  b.each_byte { |byte| res |= byte ^ l.shift }
  res == 0
end

def secure_compare(a, b)
  fixed_length_secure_compare(::Digest::SHA256.hexdigest(a), ::Digest::SHA256.hexdigest(b)) && a == b
end

fixed_length_secure_compareの方針はOpenBSDのアルゴリズムと同じです。 secure_compare では事前に入力をSHA-256に通すことで長さを揃えていることがわかります。また、ハッシュ値の比較後に、さらにわざわざ&& a == bを付ける念の入れようも見てとれます2。

この対策は本当に大丈夫なのか？

定数時間比較は、理論的には正しいアルゴリズムです。しかし、意図した性質を壊さないまま正しく実装できると確信できるかというと、ちょっと怪しい気持ちになってきます。

  • 言語処理系がコードを「最適化」してしまうことはないか？ していないことを保証できるか？
    • コンパイラによる最適化で意図した定数時間比較になっていない可能性はないか
    • コンパイル時に問題なくとも、JITコンパイルがかかる言語処理系でも大丈夫なのか
    • 正しさのテストはできるか
  • Cのような比較的低水準の言語と同等の実装を、例えばスクリプト言語で実現できるか
    • 高水準な言語ほど、実装がどういう処理に落とし込まれているのか不明瞭なことがある

そんなわけで、解決策はあるわけですが、簡単解決とはいきません。

Double HMAC Verification

本題です。

  • タイミング攻撃対策には、入力に応じた情報が漏れ出ない文字列比較アルゴリズムが求められる
  • アルゴリズムとしては、文字列の定数時間比較がある
  • 素朴な定数時間比較はとても単純なアルゴリズムだが、適切な実装は意外に自明ではない

実装しやすくセキュアな文字列比較アルゴリズムとして、Brad HillさんはMAC（メッセージ認証コード）を使うことを提案しました。アルゴリズムとしてはごく単純で、入力のHMACを取った上で3そのまま普通に比較します。

require 'securerandom'
require 'openssl'

def double_hmac_compare(a, b)
  key = SecureRandom.random_bytes(32)
  ah = OpenSSL::HMAC.hexdigest('sha256', key, a)
  bh = OpenSSL::HMAC.hexdigest('sha256', key, b)
  ah == bh
end

なるほど確かに、入力a, bは比較前にHMACによる撹拌を受けるので、タイミング攻撃が成立しなくなっているように見受けられます。タイミング差から情報を取り出すことがとても難しくなっています。

なぜ Double HMACなのかというと、HMACのダイジェスト一致確認のための比較方法を考案したという経緯があるようです。HMACから得たダイジェストを比較するためにHMACを使うことになるのでDouble HMACというわけです。

この方式には、いくつかの利点があります。

  • 実装が非常に簡単
  • 比較の安全性はHMACの特性に依存しているので、処理系の影響を受けるおそれがない
  • （Double HMACとして使う場合には）他の暗号プリミティブを増やさずに済む。HMACだけで実装できる

欠点がないわけではありません。

  • 前節の定数時間比較と比べると、相対的に遅い
    • とはいえ作者は十分に高速だと述べています

なお、HMACでなく単に一方向ハッシュ関数であればよいのでは？ という疑問も出てきます。Brad Hill氏によると、HMACの構成法は、一方向ハッシュ関数よりもある面でよりセキュアだという知見から採用したとのことのようです（詳細は理解に自信がないので、前述のサイト記事を参照していただければと思います）。

まとめ

  • タイミング攻撃（の一例）とその対策についてまとめました
  • Double HMAC Verificationについて紹介しました

元の記事にはもう少し詳細な解説や議論、高度な話題へのリンクが載っています。もっと興味のある方はそちらを参照していただければと思います（筆者も全部ちゃんと読んだわけではありません……）。

全体的にあまりよく知らない分野だったので挑戦してみましたが、とてもむずかしい……。

参考リンク

  1. もっと効率的な方法はあるのかもしれないです。 ↩

  2. 正直、ここまでやる必要があるのかはよくわかりません……一方向ハッシュ関数が正しく動作していれば、事実上衝突は起きないことにしていいはずですが。コメントではそうは言っても比較は必要という感じのことが書いてありますが……？ ↩

  3. HMACは秘密鍵を取るアルゴリズムですが、この時に使うkeyは元の記事では特に記載されていません。既存の実装例では暗号学的擬似乱数を使うものが見受けられたので、ここではそうしてみました。node.jsの過去のPRを見ると、ハッシュ比較の後にもう一度abの同値比較を入れたほうがいいんじゃないか、いや不要である等々、繊細な点について多数の議論が行われています。 ↩

8
6
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
8
6

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?