セキュリティの大御所が集まり、代替暗号法を話し合う
ワークショップは、中国山東大学の王小云（Wang Xiaoyun）博士の発表から始まった。王博士の研究チームがMD5ハッシュアルゴリズムにコリジョンを発見し、それをきっかけとしてさまざまなクラッキング法が続々と登場してきたのは周知のことである。ハッシュアルゴリズムの本格的セキュリティ実装など、いまやお笑い種になったと言ってよい。今年前半、王チームがSHA1の弱点を発見し、それによって保護レベルが2^80から2^63に低下したと発表したとき、暗号界は上を下への大騒動になった。大学と業界の主だった人々が米国標準技術局（NIST）に顔をそろえ、2日間を費やして、かつて愛用され、いまや危機に瀕している暗号プリミティブの1つ、ハッシュアルゴリズムについて話し合うことになったのは、王チームのせいと言って過言ではない。
王博士のプレゼンテーションのあと、グループは状況の重大性を話し合った。ハッシュアルゴリズムに代わる何があるのか。当面、暗号コミュニティがこのセキュリティホールをふさぐ努力をしている間、開発者はどうしたらよいのか。
参加者は大物ぞろいで、Counterpane Security社のBruce Schneier、Microsoft社のNiels Ferguson、Diffie-Hellman鍵交換で有名なSun Microsystems社のWhitfield Diffie、TLS/SSLで知られるEric Rescorla、コロンビア大学のSteven Bellovin、DBAとUVSQのAntoine Joux、IBM研究センターのHugo Krawczyk、Twofishの共同考案者でもあるNISTのJohn Kelsey、KULのBart Preneelらの顔が見えた。
| ハッシュとは何か |
|---|
|
暗号ハッシュは、現代暗号法を支える土台の1つである。Bruce Schneierはこれを「現代暗号法の牽引役」と呼んでいる。ハッシュとは、与えられたメッセージの暗号的要約を作り出す1方向関数を言う。ハッシュ関数にテキストを入力すると、固定長の暗号テキストが出力される。この暗号テキストからもとのメッセージを復元することはできない。 この変換の応用範囲は広く、デジタル署名、鍵配布機能の保護、乱数の生成、ファイル配布システムの検証など、さまざまな使い道がある。また、金融取引システム、撤回不能サービス、ホストベースの侵入検知システム、多くの人々が毎日接続しているVPNなどにも、ハッシュが欠かせない。バンキング、料金の支払い、ショッピングなどにインターネットを利用している人は多いだろう。そこでの取引は暗号Webによって保護されており、その暗号Webの一部を構成しているのが、ほかならぬハッシュアルゴリズムである。暗号システムどうしを結び合わせる糊――それがハッシュアルゴリズムであり、インターネットとは切っても切り離せない関係にある。 |
何が問題か
よいハッシュアルゴリズムの特徴の1つは、コリジョンがないことである。コリジョンとは衝突であり、複数のメッセージをハッシュ関数に入力したとき、まったく同じ要約が作られることを言う。コリジョンが起こるようだと、そのアルゴリズムでは情報の信憑性がもはや保証されない。さらに、攻撃者がその弱点を利用してシステムをだまし、危険もしくは不正確な情報を本物と思い込ませることさえできる。現に、王博士のチームが作成した2つのPKI証明書は、異なる情報を記載しているにもかかわらず、ハッシュ関数にかけると同一のMD5要約に変換された。これは実に怖いことである。
王博士のチームが現れるまで、SHA1は最も進んだハッシュアルゴリズムであり、弱点らしきものがなくて、設計どおり2^80の保護レベルを提供できるものと見なされていた。だが、王チームがSHA1の弱点を発見したことにより、この2年間でSHA1の保護レベルは2^63まで低下した。これでも、現在のコンピュータが力尽くで破れるような保護レベルではないが、2つの懸念が残る。1つは、計算力の増大である。コンピュータの計算速度は18か月ごとに倍増する――そう予測するムーアの法則は誰でも知っているだろう。そこへボットネットの出現である。百万台を超えるマシンをもってすれば、2^63の鍵空間を力尽くで打ち破ることもさほど荒唐無稽な夢物語ではないかもしれない。
2つ目は、さらに差し迫った危険である。暗号システムへの攻撃は進歩しこそすれ、退歩することは絶対にない。SHA1にわずかな弱点でも発見されれば、このアルゴリズムの本格的解体が始まるのは時間の問題と言える。来月かもしれないし、来年かもしれない。だが、それがいつか必ずやってくることは、前例が教えている。たとえば、MD5は1991年に発表され、13年間生き長らえた。SHA1は1993年に発表され、12年後の現在、深刻な弱点をさらしつつある。余命がいくばくか、誰にもわからない。
では、どうしたらよいか。選択肢はいくつかあるが、絶対的な本命はない。いろいろな組み合わせが考案され、並行的に使われていくことになるだろう。
新しいハッシュアルゴリズムを書く
NISTが数年前に開催したAESコンテストにならい、新しいコンテストを実施したらどうかという案がある。AESコンテストからは、Twofish、Serpent、RC6、MARSなど、堅固な暗号方式がいくつも生まれてきた。新しいコンテストでも、優秀な新しいハッシュアルゴリズムが提案される可能性がある。高速で斬新、かつ安全なハッシュアルゴリズムが複数現れ、選択肢が大きく広がれば、それに越したことはない。
会議出席者のなかには、コンテスト前に何回かワークショップを行い、次世代ハッシュアルゴリズムの満たすべき要件をある程度具体化しておくのがよい、と考える人が少なくなかった。確かにうなずける考えである。これまで以上に長寿のアルゴリズムを目指すなら、何を作成し、それをどう使い、どのような特性を持たせるべきか、とことん考えておいたほうがよいだろう。だが、残念ながら、これを実施するにはかなりの時間がかかる。われわれに許されている時間は危険なほど短い。
新しいアルゴリズムを開発し、ベンダ製品に煮詰め、ユーザコミュニティに配備するまでに必要な時間は、4年から8年と見積もられている。暗号コミュニティでは、SHA1が2010年以降まで生き延びるのは難しいという意見が大勢を占めており、とすれば、急いでも間に合うかどうかぎりぎりのところである。コンテスト方式で行くなら、すぐにでも御輿を上げたほうがよい。やるとすれば、間もなく動きがあるだろう。
既存のアルゴリズムのなかから保護力のすぐれたものを探す
SHA系には、いくつかの兄弟アルゴリズムがある。たとえば、SHA1の兄とも言えるSHA256は、短期的には十分に代役を努められる力の持ち主である。設計上の保護レベルは2^128であり、解読実験でも堅固さが証明されていて、危機に瀕している弟よりセキュリティは強い。もちろん完璧ではないが、その保護力とほとんどの応用場面でのパフォーマンスから見て、当面の代役としては十分だろう。とくにパフォーマンスでは、競争相手があまり見当たらない。安全なハッシュアルゴリズムならほかにもいくつかあるが、それの高速化はなかなか難しい。
SHA256の欠点は、何よりもSHAファミリの一員だという事実である。暗号解読の進化で、SHA系の保護力は蚕食される一方である（すでの最初の24ラウンドは突破され、さらに蚕食は進みつつある）。ただし、よいニュースもある。SHA系アルゴリズムを破るのに現在使われているツールをSHA256に試したところ、多くは限定的な結果しか返せなかった。したがって、SHA1と同じ運命をたどるまでに、まだ多少の時間があるとは言える。ただ、新しいツールや解読手法は続々と生まれつづけており、SHA256も、もっと堅固なソリューションが得られるまでの時間稼ぎ以上のものにはなりえない。
SHA256を代役に立てる際の困難は、標準ハッシュ関数の変更に必要な時間と費用である。ベンダが新しいアルゴリズムの実装に費やす資金と時間は膨大である。SHA256に多大な投資をしても、それがすぐにだめになり、数年で再度同じことをしなければならないとしたら、はたしてベンダは動くだろうか。問題をさらに複雑にするのが、SHA256の256ビットというブロックサイズである。SHA1のブロックサイズは160ビットだった。当然、現在の暗号インフラストラクチャには、160ビット以下のハッシュを前提にしているものが多い。こう考えると、必然的に次の選択肢が浮上する……。
SHA1を補強する
SHA1アルゴリズムを補強するための方法についても、何人かの出席者から論文が発表された。そのほとんどは、既知の攻撃に対する防御戦略に工夫をこらす内容だったが、残念ながら、こうした補強策には、パフォーマンスが極端に低下するというデメリットがともなう。Ron Rivestからディザリング案が呈示され、Hugo Krawczykからはランダム化法の提案があって、どちらも有望と見なされたが、補強案の主流はトランケーションだった。
SHA256で256ビットのハッシュ文字列を作成し、うち96ビットを切り捨てて（トランケーション）160ビット文字列を得たらどうだろう。こうすれば、SHA1を前提としているすべての現行システムと整合するうえ、SHA1アルゴリズムで見つかったコリジョンも避けられる。何よりも最小の費用で急場をしのげるとあって、NISTはこのアイデアに強い関心を示していた。確かに悪い考えではない。とくに、もっと堅固なソリューションが得られるまでのつなぎとしては十分だろう。だが、このトランケーション法はほとんどテストされておらず、暗号強度への影響も未知数である。直感的にはよさそうだが、緻密な裏付けがなく、公的なレビューにもさらされていない方法とあって、NISTも承認には二の足を踏んでいる。現在、レビューが進行中であり、その結果しだいでは、トランケーションが暫定案として浮上するかもしれない。
開発者と管理者へのアドバイス
さて、いまシステムを開発していて、ハッシュアルゴリズムを選択しなければならないとしたら、どうするのが賢明だろうか。Niels Ferguson、Steve Bellovin、Hugo Krawczyk、Georg Illies、James Randellからなるパネルは、全員一致で「新しい罪を犯すな」と言う。いま何かを開発中なら、迷わずSHA256を選択しよう。さらに進んで、「アルゴリズム的に機敏」なアプリケーションにできればもっとよい。つまり、暗号化アルゴリズムの寿命が比較的短いことを踏まえ、アプリケーションの寿命よりアルゴリズムの寿命が先に尽きることを前提にしたアプリケーション作りをせよ、ということである。
既存のシステムについては、こんなアドバイスが与えられた。SHA1を使用しているレガシーシステムがあるなら、今後数年の間にシステムを入れ替えるための検討に入ろう。MD5を使用しているシステムがあるなら、もう救いようがない。尻尾を巻いて逃げ出そう。
原文
