HashDoS脆弱性との戦い！ Rubyコミッター・卜部昌平が明かすプログラム堅牢化のノウハウ

過去、HashDosの影響を受けたRuby。言語開発者はいかにしてこうした問題に対応してきたのでしょうか。コミッターである卜部氏の貴重な記録を公開します。

HashDoS脆弱性との戦い！ Rubyコミッター・卜部昌平が明かすプログラム堅牢化のノウハウ

2011年の末頃、HashDoSという脆弱性が公表され、Rubyもこの影響を受けた。本稿の筆者である卜部昌平（うらべ・しょうへい／@shyouhei／以下、卜部）は、報告当初からRuby側のチームメンバーとしてプログラム本体の修正を担当した。以下はその記録である。言語開発者たちが普段どのようなことを考え、どういった技術を用いて開発やバグフィックスを行っているのか。その概要を知ってもらえれば幸いだ。

1 オブジェクト指向スクリプト言語 Ruby

HashDoSの概要

ごく簡単に脆弱性の概要を解説する。この脆弱性のターゲットはハッシュ関数と呼ばれる関数である。関数というからには定義域と値域があるわけで、定義域に相当するものは（任意の）文字列、値域は整数だ。

2011年頃のRubyの場合はCのintを利用していたので、整数とは典型的には32bit符号つき整数で、-2,147,483,648から2,147,483,647（両端を含む）の範囲ということになる。ある文字列にハッシュ関数を適用して得られる整数のことを、「その文字列のハッシュ値」と表現することがある。

ハッシュ関数はさまざまなものが考えられるが、基本的にはハッシュ値が値域の全体に一様に散らばって分布するのが良いハッシュ関数である、とされる*1。

また、ハッシュテーブルと呼ばれるデータ構造があり、このデータ構造におけるO(1)アクセスを理論面から保証しているのがハッシュ値の一様性だ。ハッシュ値の分布に偏りがある場合、一定の時間や一定のメモリ消費で終わることが期待される処理が、意図通り行われなくなる（要するに、パフォーマンスに課題を抱える）。

そして、HashDoSの概要は一言で言うと「完全に同じハッシュ値を持つ文字列の組を発見した」というものである。このような攻撃は"Algorithmic Complexity Attack"と呼ばれており、そもそも脆弱性を理解するには計算量についての理解や議論が不可欠であり、修正するにも計算量を悪化させないように用心する必要がある。

なぜ約6年後の今、修正内容を公開するに至ったか？

当時、これは貴重な記録だと思い、修正内容のメモを残していた。しかし、修正直後の段階では攻撃の影響を受けるシステムが多数残っていたため、詳細な修正点の公表はためらわれた。また、他の作業に忙殺されたこともあり公表せずじまいになっていた。

その後、約6年を経てHashDoSという攻撃手法は多くのエンジニアに認知されていること。また、卜部がHashアルゴリズムを修正したRubyバージョンはすでにEOL（サポート終了）となっており、新しいRubyバージョンではさらに本格的なアルゴリズム変更が入っていることから、公開しても問題ないと判断した。

同時に、当時の卜部が何を考えどう修正したかを記すことに歴史的意義が出てきたと考え、筆を執った。以下より時系列ごとに、RubyがどのようにしてHashDoS対応をしてきたのか。その道のりを振り返りたい。

前史：すでに内包されていたリスク

1999年ごろ

このアタックに最初に気づいたのは、イリノイ大学シカゴ校の数学および暗号学教授であるダニエル・ジュリアス・バーンスタインだと言われている。彼が開発したDNSサーバ用ソフトウェア「djbdns」のソースコードには、そのようなアタックを懸念するコメントが含まれているという。

しかし、djbdnsが採ったのは「アタックっぽい変なデータはキャッシュしない」という対策であった。これは、DNSキャッシュサーバの実装としては妥当であるが、他のツールや言語などでは、この対策を採ることは必ずしも可能ではない。

2003年ごろ

HashDoSの概要や危険性について記されたオリジナル論文「Denial of Service via Algorithmic Complexity Attacks」が発表される。

この時点ではまだ具体的な攻撃方法にまでは言及されておらず「こういう攻撃が理論上可能だよね」といったレベルの指摘にとどまっている。が、論文内でPerlは名指しで危険性を指摘されていたため、早急に修正が入りPerl バージョン5.8.1がリリースされた。

2005年7月9日

どういった経緯か不明ながら、Rubyコミッターの田中哲（@tanaka_akr）さんがPerlの変更に気づく。

2008年6月20日

さらに、どういった経緯か不明ながら、田中さんがバージョン1.9のRubyにハッシュ関数のランダム化を入れる。

2009年1月21日

手元のメモによるとこの日、卜部がRuby Bug #929の追跡中にバージョン1.9における田中さんの変更に気づく。しかし、そのままではバージョン1.8にすんなり持ってこれないので、バックポートを断念した。ハッシュ関数の初期化で乱数が必要になるということは、それ以前に srand していないといけないので、初期化順序に依存関係がある。当時そこをきちんと整理できていなかった。

また、正直なところ、まだ攻撃が世間にほとんど認知されていない状態で、バックポートに大きな労力をかける気にはなれなかった。ちょっと試してバックポートできたのであれば、入れていたと思う。が、実際は簡単に適応できず断念した。後悔先に立たず。

この時点でのRuby 1.8系のハッシュ関数はだいたいこんな形だった。

int
hash(str, len)
    char *str;
    long len;
{
    int key = 0;

    while (len--)
        key = key * 65599 + *p++;
    return key + (key >> 5);
}

このハッシュ関数は当時としては一般的な、他のプロジェクトでもよく使われていたアルゴリズムであり、オリジナリティはあまりない。

報告から初期対応

2011年11月1日

オープンソースのセキュリティ問題に対処する機関「oCERT」から、Rubyセキュリティチームに連絡が入る。この時点での連絡内容は以下の通りだ。

  • oCERTはすでにPerl バージョン5.8.1における修正を把握していた
  • oCERTはすでにRubyバージョン1.9系に田中さんの変更が入っていることを知っていた
  • 「具体的な攻撃が存在する」とは共有されたが、詳細な攻撃手段は教えてくれなかった
  • 12月27日まで秘密にしてね、というお願い入り

卜部としては、この時点ではまだどのような攻撃手段なのかよく分かっていなかったが、ともかく重い腰をあげて田中さんのパッチを解読しはじめた。oCERTとの連絡は他のメンバーにお任せ。

2011年11月2日

oCERT経由で、報告者からハッシュ値が衝突するような文字列が200万個ほど送られてきた。Rubyセキュリティチーム一同、実際に手元のPCが固まるのを見て頭を抱える。

2011年11月6日

卜部、とりあえずパッチを作成するも全然ダメ。急いで田中さんの変更を当てようとしたがどうも上手くいかないので、変更を当てるのではなくtrunkのソースコードをじっくり読んで、どのような意図でコードが書かれているのか理解しないとダメということに考えを改める。

2011年11月22日

だいぶ悩んだ結果、ついにハッシュ関数のランダム化が成る。しかしパッチは結構大きく、以下のようなものになった。

ChangeLog                |   17 ++++++++++
ext/openssl/extconf.rb   |    3 +
ext/openssl/ossl_ssl.c   |    3 +
inits.c                  |    2 +
random.c                 |   74 ++++++++++++++++++++++++++++++++++++-----------
string.c                 |   17 ++++++++++
test/ruby/test_string.rb |   13 ++++++++
7 files changed, 112 insertions(+), 17 deletions(-)

この時点でのハッシュ関数はだいたいこう。

static unsigned hash_seed; /* <- hash_seedは乱数、起動時に初期化 */

int
hash(str, len)
    char *str;
    long len;
{
    int key = 0;

    while (len--)
        key = key * 65599 + *p++;
    key = key + (key >> 5);
    return key ^ hash_seed; /* <- new! */
}

卜部の作ったパッチはプロセス起動時に初期化した乱数でハッシュ値を撹乱するので、攻撃者が予測することが困難になる。前バージョンのコードと1行しか変わってないじゃん、と思うかもしれないが、この変数を初期化する部分がむずいのよ。

後期対応：乱数をrotate shiftし、ハッシュ値の衝突を回避する

2011年11月26日

風邪をひいて寝込みつつ病床で気づいたのだが、ハッシュ関数がランダムになっただけでは、報告者の報告した文字列がやっぱり衝突してしまう。つまり修正としては不完全なのだ。

最初のハッシュ関数で文字列Aと文字列Bが同じハッシュ値になるのであれば、前述のバージョンのハッシュ関数でhash_seed をどんなに変えても同じハッシュ値になってしまうのは当然だ（6年後のいま考えりゃ当然だが、当時は本気で気づいていなかった）。

2011年11月28日

ただランダムにするだけじゃだめだ、というわけで考え直し。乱数をrotate shiftしながらハッシュ値に練り込んでいくのはどうだろうとチームに提案。チームメンバーのみんなの意見も参考にしつつ、このころのハッシュ関数はこんな感じになった。

int
hash(str, len)
    char *str;
    long len;
{
    unsigned long key = hash_seed;                           /* <- new! */
    #define width (sizeof(key) * CHAR_BIT)

    while (len--) {
        int x = *p % width;
        key ^= (hash_seed << x) | (hash_seed >> (width - x)); /* <- new! */
        key = key * 65599 + *p++;
    }
    return key + (key>>5);
}

コードのループ内に追加された行は、hash_seedをrotate shiftしている。シフト幅は入力文字から得ているので、ループの中で毎回変わっていく。このようにすることで、とあるhash_seed値の元でハッシュ値が一致した文字列Aと文字列Bがあったとしても、hash_seedが入力文字によって変更されることで、衝突しなくなる。

2011年11月30日

セキュリティチームの他のメンバーが突如「Ruby 1.8.7 程度のハッシュ関数なら、その逆計算はプログラミングコンテストレベルの問題です」と言って攻撃コードをメーリングリストに送ってくる……。すごい人が集まっているチームだ。

この攻撃コードより、“任意の”文字列とハッシュ値が衝突するような文字列を“無限に”作り出せる、第二原像攻撃が成立していることが明らかとなる。これは、ハッシュ関数に対する攻撃としてはいちばん強烈。

2011年12月5日

報告者やセキュリティチームに改訂した修正案を開示し意見を募る。すると「まあたぶん大丈夫なんだけど、ローテーションの幅が入力文字の下の方のビットだけに依存するのは好きじゃない」という趣旨の返答。32bitローテーションだと下5bitしか使いようがない、ということは逆から言えば文字の上3bitが無視されているわけで、これはたしかに良くない。

こうした意見を反映して、この頃のハッシュ関数はこう。

int
hash(str, len)
    char *str;
    long len;
{
    unsigned long key = hash_seed;
    #define width (sizeof(key) * CHAR_BIT)

    while (len--) {
        key = key * 65599 + *p++;
        key = (key << (width - 13)) | (key >> 13); /* <- new! */
    }
    return key + (key>>5);
}

ループの途中でrotate shiftする変数を hash_seed から key に変更。rotate shiftする幅13は（記憶が確かなら）提案された素数の中から選んだはず。8より大きいので、隣り合うbyte同士が同じbitに情報を重ねないようにする、という配慮だったと記憶している。

2011年12月9日

「*65599 ってさあ、だいたい16bit左シフトだよねえ（65599=216+63）。それを >>13 で13bit右に戻すのって、なんか処理が部分的にキャンセルされてるよね？」 という疑問が湧き上がり、以下のような実装はどうだろう、と再度チームに提案してみる。

int
hash(str, len)
    char *str;
    long len;
{
    unsigned long key = hash_seed;
    #define width (sizeof(key) * CHAR_BIT)

    while (len--) {
        key = key * 65599 + *p++;
        key ^= (key << 13) | (key >> (width - 13)); /* <- new! */
        /*  ↑ XOR */
    }
    return key + (key>>5);
}

しかしこれは報告者に即、ダメ出しされてしまう。rotしてXORとると全射じゃなくなるからデータが欠けていくのだそうだ。へぇー。

% cat b.c 
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
int main() {
    srand(time(NULL));
    uint32_t a = rand();
    int i;
    for (i = 0; i < 33; i++) {
        printf("%08x\n",a);
        a ^= (a<<13)|(a>>19);
    }
    return 0;
}
% gcc b.c 
% ./a.out 
73aff684
8d7f78f1
6261495e
4b4a8512
1be8cc7b
0267af06
f7876f4a
1a6e31ba
dc5972f7
f207897c
0328173c
01cf9759
f324b760
65c8a904
70e825bd
745f8ba0
852b852b
f58ef58e
2b3f2b3f
ce58ce58
d793d793
ad61ad61
98cd98cd
2bd42bd4
aeaeaeae
7b7b7b7b
14141414
96969696
44444444
cccccccc
55555555
ffffffff
00000000

2011年12月11日

ハッシュ関数の実装を固める。最終的なアルゴリズムは以下のようになった。

int
hash(str, len)
    char *str;
    long len;
{
    unsigned long key = hash_seed;
    #define width (sizeof(key) * CHAR_BIT)

    while (len--) {
        key = key * 65599 + *p++;
        key = (key << 13) | (key >> (width - 13));
    }
    return key + (key>>5);
}

途中で考えていたものとほぼ同じで、rotationの向きだけ違う。65599倍との相殺を避けようというせめてものあがきだが、今考えるとどのくらい効果があったか疑わしい。

脆弱性公開

2011年12月13日

JRubyはRubyバージョン1.8由来のハッシュを捨て、バージョン1.9と同じmurmurhashに移行する、という連絡をJRuby開発チームから受ける*2。

2011年12月14日

Rubiniusはそもそも全く違うFNV hashを使っているから今回の攻撃は対応不要だ、という連絡がRubinius開発チームからあった*3。つまり、メジャーなRuby処理系3種はHashDoSの影響を受けなくなったことになる。

2011年12月27日

oCERTよりセキュリティ・アドバイザリ公開。

oCERT-2011-003 multiple implementations denial-of-service via hash algorithm collision

追ってMRI（CRuby）、JRubyともにリリースを出す。

Denial of service attack was found for Ruby's Hash algorithm (CVE-2011-4815)

JRuby 1.6.5.1 Released — JRuby.org

その後、報告者によるプレゼンが行われ、Rubyセキュリティチームへの謝辞があり胸が熱くなる。

おわりに

Rubyのハッシュ関数に脆弱性が発見された当時、卜部が行ったようなシンプルな撹乱が有効だったのはラッキーだった。暗号学の素人でも、大学院レベルの計算機科学の基礎知識でなんとか立ち向かえたからだ。

2018年の現在では、HashDoSは攻撃側も防御側もよく研究されており、対策も進んでいる。今となっては、素人が浅く考えたような対策ではなく、きちんと専門家が考えたアルゴリズムを採用することが求められている状況だ。

本対応を通し、卜部が学んできたことを、最後に読者である若手エンジニアに伝えておきたい。

問題を正しく理解すること

HashDoSに限らず、サイバーセキュリティは研究の対象になっており、攻撃法などは論文として公表されることがままある。これらの論文を読んで意味を理解できないと対策は困難なので、セキュリティ領域に携わりたいと考えている方は、プログラミングの最低限の素養に加えて論文を読めるだけの計算機科学の基礎知識は身につけておいてほしい。

もちろん、修正するにあたってはコードのデバッグ能力も求められるが、これについては恐れる必要はないと思う。問題を正しく理解することの方が、問題を正しく修正するより何倍も難しいからだ。

他のメンバーとのコミュニケーションの重要性

本対応でラッキーだったもうひとつの点は、脆弱性公表以前に報告者らと修正案をやりとりし、レビューを受けられたことだ。前述のとおり、修正案は何度も書き直しており、最初の修正案では不十分だった。

不適切な修正を世の中に公表してしまうのは攻撃を誘発しているようなものなので、公表するならば同時に完璧な修正が求められる。だが、その作業をひとりで全部やるというのは大変なストレスである。報告者や他のメンバーとのコミュニケーションが（自分にしては奇跡的なことに）円滑に進んだのは本当に良かったと思う。

脆弱性と戦う言語開発者たちが、人々の暮らしを支えている

2018年の現在、卜部はRubyセキュリティーチームで脆弱性を修正する担当ではなくなった。だが、脆弱性の報告そのものはなくなったわけではない。統計は取っていないが、報告数はむしろ増加傾向にあると思う。その脆弱性を突かれてサービスが攻撃されれば、私たちの生活も脅かされてしまう。

今この瞬間も、言語やツールの脆弱性をハンドリングしている人々がいるからこそ、私たちは安心して暮らすことができる。普段はあまり表に出てこないし、出るにしてもこの記事のように数年後とかになるわけだが、世の中には人知れず活躍しているエンジニアたちがいる。彼らが素晴らしい仕事をしていることを、どうか知っておいてほしい。

執筆者プロフィール

卜部昌平（{$image_2}@shyouhei）

{$image_3}
株式会社マネーフォワードのフルタイムRubyコミッター。プログラミング言語Rubyコミッター、日本Rubyの会監事。大学院在学中の2008年ごろからRuby開発に携わる。大学院修了後は趣味としてRuby開発を続けるかたわらプログラマーとして数社に勤務。その後2015年よりマネーフォワードにてフルタイムでRuby開発に携わり現職。監訳にオライリー『プログラミング言語Ruby』。

企画：中薗昴（サムライト）

【2018年1月10日16時 修正】ご指摘により、記事の公開日付を修正しました。

  1. 全射であるだけではまだ弱くて、すべての値の出現確率がだいたい同じになるべきとされる。↩

  2. 本稿執筆時の2017年12月現在では、さらに変更されている。↩

  3. 本稿執筆時の2017年12月現在では、さらに変更されている。↩
若手ハイキャリアのスカウト転職