ぼちぼち日記

おそらくプロトコルネタを書いていることが多いんじゃないかと思います。

ハッシュ衝突でTLSを破るSLOTH攻撃(CVE-2015-7575)とは何か

TLS

0. 簡単なSLOTH攻撃のまとめ

最初に簡単なまとめを書いておきます。長文になりそうなので、読むのが大変な方はここだけ見ておいてください。

  • MD5ハッシュは既に安全ではなく、証明書の署名方式での利用は停止されていたが、後方互換のためハンドシェイクデータの署名方式にRSA-MD5が今でも利用できるTLS実装が幾つか存在していた(Firefox NSS, Java等)。
  • 先週、INRIAグループからハッシュ衝突を利用して実際にTLSを破る攻撃(SLOTH)が公開された。それを受け、いくつかの実装でRSA-MD5を完全に利用不能にする修正が行われた(CVE-2015-7575)。
  • SLOTHでは、SHA1やTLS、IKE、SSHに対する攻撃についても評価を行い、幾つかは全く現実的に不可能なレベルではないことが示された。MD5とSHA-1でTLSハンドシェイクの完全性を担保しているTLS1.0/1.1への脅威は大きくなった。

1. SLOTHとは何か？

これまでFREAKやTriple Handshake, Logjam 攻撃などTLSに対する様々な攻撃を発見してきたINRIAグループが、先週また新たなTLSの攻撃手法(SLOTH)を公開しました。

Security Losses from Obsolete and Truncated Transcript Hashes (CVE-2015-7575)

タイトルを日本語訳すると、「古く廃止されたTruncated Transcriptハッシュによるセキュリティ低下」でしょうか？ 何を言っているのかわかりませんね。この攻撃を受ける脆弱性には、CVE-2015-7575も割り当てられており、今のところ先月に対応されたNSS(Firefox)のセキュリティアップデート情報が掲載されています。幸いOpenSSLは、２年ほど前に Don't use RSA+MD5 with TLS 1.2で修正を行っていたため、難を逃れました。OpenSSL-1.0.1f以降なら問題ありませんが、古いRHELで影響を受けるようです。JavaやGnuTLS等その他のTLSライブラリの状況に関しては、INRIAのサイトでまとめられています。
この攻撃の概要は、先週行われたReal World Cryptography Conference 2016で発表されましたが、この論文が採択された来月のNDSS Symposium 2016でもさらに詳細が発表されるでしょう。

このSLOTH攻撃は、TLS実装がRSA-MD5等既に安全でない署名方式が有効になっている場合に、あるハンドシェイクデータと同一のハッシュ値を持つ別のデータを計算し、それを偽造データにして中間者攻撃を仕掛けてTLSの安全性を破る攻撃です。

今回攻撃で使われたMD5は、かなり前から安全ではないことがわかっていましたが、現実的な攻撃としてMD5のハッシュ衝突を利用した偽造証明書の作成に成功したのは2008年末のことでした(MD5 considered harmful today)。これが非常にセンセーショナルな出来事だったため、その反省からブラウザベンダーや認証局は、現実的な攻撃が世に出る前に急いでSHA-1の証明書の移行・廃止を現在進めているわけです。

証明書の署名方式が、このような素早い廃止対応を進めているにもかかわらず、これまでTLSは全面的にMD5を利用不能にしていませんでした。それは静的な証明書データの攻撃に比べ、TLSハンドシェイクは接続時に毎回データ異なるため、現実的にハッシュ衝突の攻撃は難しいだろうと考えられていたからです。しかもMD5は、TLS1.0や1.1でmaster secret等を生成するPRF(擬似乱数生成関数)にも使われているので、完全にMD5のアルゴリズムを実装から削除するためには、TLS1.2への全面移行が必要です。これは非常に大変な作業です。

しかし、ついにMD5ハッシュ衝突の計算処理の効率化とTLS仕様の隙間を組み合わせることによって、TLSのハンドシェイクに対する現実的で具体的な攻撃手法が編み出されました。

SLOTHは、TLSハンドシェイクで中間者攻撃が自由に改変できる部分を利用します。攻撃者はハッシュ衝突が起こる偽造データを途中で計算し、エンドポイントのTLSデータの署名検証を欺きます。その結果、中間攻撃者によるTLS通信のなりすましや改ざんなどTLSの認証を破ることに成功しました。

SLOTHの論文では、TLSだけでなくIKE, SSHに対してハッシュ衝突を利用した様々な種類の攻撃を検証しています。TLSに対する攻撃として、

  1. RSA-MD5が有効になっているエンドポイント間のTLSクライアント認証への攻撃
  2. RSA-MD5が有効になっているTLSサーバ認証への攻撃
  3. TLS1.3のサーバ認証やクライアント認証への攻撃
  4. TLS1.0/1.0のハンドシェイクデータを改ざんして弱い暗号方式にDowngardeする攻撃
  5. TLSのハンドシェイクハッシュ値を偽造してアプリが利用するチャネルバインディングに対する攻撃

の５つが挙げられています。

論文を読むとまぁいつものごとく、見事な攻撃なのでホント感心させられます。ここで自分の理解を残しておくために、この中で一番計算量が少なく(2^39)、現実的に攻撃ができることを実証した1のTLSクライアント認証に対する攻撃について詳しく書いてみます。

2. Chosen-Prefix 衝突とは？

前述の通り、SLOTHはハッシュ衝突を計算して偽造データ作成するのがキモの一つです。しかも改変できるのは任意の部分でなく、主に頭の部分でデータ構造や書式の制限がついています。このような条件の元でハッシュ衝突を求めることを Chosen-Prefix 衝突と呼びます。

Chosen-Prefix 衝突でどのように偽造するか、MD5の攻撃で使われた本物と偽造証明書の比較を見てみるとわかりやすいでしょう。

同一の署名データをもつ偽造証明書は、正当なX509証明書としての構造を持っていないといけません。グレーの部分は一部本物のデータと一致していたり、偽造用に変更されたりする部分ですが、その書式や構造は仕様に合ったもので証明書の偽造目的に応じて固定化される部分です。公開鍵や拡張情報は比較的改変できる自由度が高いため、攻撃者はこの部分を調整して計算を行い、両者のハッシュ値が同一になるよう仕組みます。

頭の固定化されている部分を持っていることから Chosen-Prefix 衝突と呼びます。この Chosen-Prefix衝突の計算方式はこれまでいろいろ研究されていますが、まだかなりの計算リソースが必要です。SLOTHでは過去に開発された衝突探索ツールを改良して性能向上を図ったということです。

3. TLS1.2クライアント認証の復習

今回、SLOTHでTLS1.2のクライアント認証を破ることを解説しますので、TLSクライアント認証の復習です。細かいところは過去のエントリーを読んでください。
TLSのハンドシェイクではClientHelloからFinishedまでクライアント・サーバ間で様々なハンドシェイクデータのやり取りを行います。

TLSのハンドシェイクで利用する署名方式は、ClientHello/ServerHello で signature extension をやり取りして決めます。このTLS拡張によって、サーバ・クライアント間で共通に利用する署名方式が合意されます。現在多くのTLS実装では、明示的にRSA-MD5を有効になっていませんが、後方互換のため安全でないRSA-MD5署名方式で合意してしまうようなTLSサーバが数多く残っています。論文のサーベイでは、30%程度のTLSサーバがRSA-MD5署名を受け入れるようです。

ClientHello/ServerHelloでやり取りするTLS拡張は、signature以外にも様々なものがあります。各実装でサポートしている拡張機能はバラバラなので、サポートしていない拡張フィールドが送られてきてもエンドポイントは無視することになっています。皮肉なことに、この拡張フィールドの自由さに攻撃者がハッシュ値を調整できる余地が隠されていました。

TLSクライアント認証は、CertificateRequest/ClientCertificate/ClientCertificateVerify の３つで実現します。

CertificateRequestは、サーバからクライアントへ証明書を送付を要求するハンドシェイクタイプです。ここでは、後にクライアントが利用する署名方式やサーバが必要とするクライアント証明書の認証局情報(dn)などを指定してクライアント側に送ります。
このdn情報は、複数記載することが可能であり、該当するものがなければクライアントはデータ内容を無視します。ということは、悪意のあるエンドポイントがこの部分を自由に使い、データを埋め込むことができます。ここにもハッシュ衝突攻撃につけ入れられるTLS仕様の隙間が隠されていました。

最後のClientCertificateVerifyは、TLSクライアント認証の重要な部分です。クライアント証明書は秘匿されているものではなく、外部に公開されても構わないものです。そのため第３者がクライアント証明書を流用して成りすますことを防止しなければなりません。

クライアントは、ClientCertificateで証明書をサーバに送付した後に、ClientCertificateVerifyでそれまでサーバとやり取りした全ハンドシェイクデータのハッシュ値を秘密鍵で署名してサーバに送付します。サーバはClientCertificateVerifyを受け取ったら、クライアント証明書の公開鍵を利用して相手側のハッシュ値を求め、自身が持つ全ハンドシェイクデータのハッシュ値と比較し署名検証を行います。このステップを踏むことで、サーバはクライアントが正当な証明書と秘密鍵のペアを持つエンドポイントであることを確認します。

4. SLOTHによるRSA-MD5を使ったTLSクライアント認証への攻撃

SLOTHは、中間攻撃者がTLSハンドシェイクデータを細工して正当なクライアントになりすまし、TLSのハンドシェイクに成功する攻撃です。驚くことにこの攻撃によって、攻撃者はクライアントの秘密鍵の情報を盗む必要はありません。攻撃者は、秘密鍵情報にアクセスすることなく署名検証を成功させ、なりすましを行うことが可能になります。この攻撃は、サーバ・クライアント間で交換する一連のTLSハンドシェイクデータ(Transcript)のハッシュ衝突を突く攻撃であるため、Transcript Collision Attackとも呼ばれています。

SLOTHによるTLSクライアント認証の攻撃が成功するには、以下の条件が必要です。

  • クライアント・サーバの両者でRSA-MD5署名方式を利用できる。
  • サーバがTLSクライアント認証を行い、対象サーバ以外(攻撃者のサーバ)にも同一のクライアント証明書を送付している。
  • クライアントがDHE鍵交換をサポートしており、クライアントが素数でないDHパラメータも受け入れてしまう。
  • サーバ側から送られてくるTLSハンドシェイクの長さが予測できる(データの中身ではない)。

ではSLOTH攻撃をステップ毎に見ていきます。

4.1 ステップ1: クライアント・攻撃者間でTLSハンドシェイク(途中まで)

まず攻撃者は、なんらかの方法でクライアントを誘導して中間攻撃者向けにTLSハンドシェイクを開始させます。この際ターゲットサーバへのDNSの改ざんしてサーバIPを偽造する必要はなく、攻撃者自身のドメインと証明書によるTLS接続で構いません。

攻撃者は、クライアントと攻撃者間の鍵交換はDHEで行います。サーバからクライアントに送るDHパラメータp, gは、p=g^2-g を指定します(gは普通2を使う)。pは本来素数であるべきですが、p=g^2-g=g*(g-1)なので素数ではありません。クライアントが厳密にチェックしなければ使えてしまいます*1。この仕込みがどう生きてくるか後のステップ7で説明します。

攻撃者は、CertificateRequestの前でハンドシェイクを一旦ストップさせます。

4.2 ステップ2: ハッシュ衝突の計算

次に攻撃者は、これまでクライアントとやり取りしたハンドシェイクデータと、次に送信する CertificateRequest のデータ、そしてそこに追加されるCertificateRequestのパラメータの一部(dn情報長さ)を予測してデータAを決めます。この長さ情報の予測が後のステップで生きてきます。

攻撃を成功させるために、このデータAと、中間攻撃者がサーバ側とのTLSハンドシェイクするデータのハッシュ値が一致するよう、データBを計算して探し当てます。

実際どのような Chosen-Prefix のデータ列になるのか、TLSハンドシェイクデータを並べて見てみるとわかりやすいです。

上図のグレー領域が固定化された(Chosen-Prefix)部分、赤い部分がハッシュ衝突を調整するために計算されたデータの部分です。dn lenの部分は今後サーバから送られてくるハンドシェイクデータ長を予測して決めます。TLSデータは書式が固定化されている部分が多いので、データ長だけを予測するのは難しくないと思います。
攻撃者・サーバ側のデータは、ClientHelloの拡張領域に衝突を発生させるデータを埋め込みます。前述したようにTLSサーバは知らない拡張は無視するため、攻撃者にとって自由なデータを埋め込むことができ、ハッシュ衝突を調整するには都合が良くなっています。

サーバ側に送り込むClientHelloには、明示的にRSA-MD5署名方式のみでサーバ側とハンドシェイクを行うようにsignature extensionを埋め込みます。前述した通り、後方互換重視のサーバはこの署名方式でハンドシェイクを受け入れてしまいます。

最後にここまでの両者のデータ長をハッシュ方式のバイト長境界(MD5なら16バイト)に合わせます。これによって一度２つのデータのハッシュ値を一致させると、次に同じデータをそれぞれに結合してもハッシュ値が同一に保たれます。

このChosen-Prefixの衝突計算は、効率化による省メモリ化や並列処理の改善によって現在48コアで１時間程度で計算が可能なようです。その１時間の間、攻撃者はクライアントにアラートを送り続けてハンドシェイクセッションを維持しておきます。

4.3 ステップ3: 攻撃者・サーバ間でTLSハンドシェイクの開始

MD5(A)=MD5(B)となるChosen-Prefix衝突の計算が完了したら、攻撃者はサーバ向けにTLSハンドシェイクを開始します。

攻撃者・サーバ間でRSA-MD5署名方式で合意できたら、ここまで中間攻撃者を介した２つのTLSハンドシェイクデータのハッシュ値は一致することになります。

4.4 ステップ4: 攻撃者のハンドシェイクデータの偽造

攻撃者からのClientHelloと偽造用の拡張データを受け取ったサーバは、それに応える一連のTLSハンドシェイクの応答(ServerHello,Certificate,CertificateRequest)を返します。

攻撃者は、このデータ結合したもの(ServerHello|Certificate|CertificateRequest)をクライアント側に偽のdn情報と見せかけ、CertificateRequestのパラメータの最後に付加してクライアントに送付します(|はデータ結合を表します)。

両者のハッシュ MD5(A|C) は MD5(B|C) と同一のままです。

Chosen-Prefix中のdn len には、あらかじめ青色のCのデータ長まで含んだ長さを予測して含んでいたため、単純に最後に結合することが可能となりました。

4.5 ステップ5: クライアント・攻撃者・サーバ間でハンドシェイクの同期

この後攻撃者は、ハンドシェイクデータを素通しします。


素通ししたハンドシェイクデータDは、どちらの接続にも追加されるため、両者のハッシュ値 MD(A|C|D) と MD(B|C|D) は同一のままです。

4.6 ステップ6: 中間者攻撃下の署名検証の成功

いよいよSLOTHの攻撃のクライマックスです。クライアントは自身の正当性を証明するためにそれまでやり取りしたTLSのハンドシェイクデータ A|C|D のハッシュ MD(A|C|D) を自身の秘密鍵で署名し、ClientCertVerifyとして送付します。

攻撃者は、これまでと同様にクライアントからのClientCertVerifyをサーバへ素通しで転送します。

ClientCertVerifyを受け取ったサーバは、クライアント証明書の公開鍵を使ってクライアントのハンドシェイクデータのハッシュ値MD(A|C|D)を取得します。 続いて、これまで攻撃者とやり取りしたハンドシェイクデータ B|C|D のハッシュ値MD5(B|C|D)の値と比べます。

これまでのステップによるデータの偽造により両者のハッシュ値は一致するため、見事に署名検証成功です。

4.7 ステップ7: MAC偽造によるハンドシェイク完了、なりすまし成功

署名検証の成功でクライアントの正当性が確認されると、クライアント・サーバ間でChangeCipherSpecをトリガーにして暗号化通信が開始されます。
このままでは、中間攻撃者は自身を介した２つのハンドシェイクの完了を成功させることはできたけれども、共通鍵がわからないので暗号化されたデータの中身を見ることができなくなります。ここでステップ１で仕込んだDHEの不正な素数パラメータがようやく生きてきます。

ステップ1で攻撃者は、DHEのパラメータをp=g^2-gで送付しました。その場合、クライアントが秘密鍵 x を使って公開鍵を作成しても g^x mod p = (g^(x-2)+...+1)*(g^2 -g) + g) mod p = g なので、クライアントの公開鍵は秘密鍵xによらず g のままです。ClientKeyExhangeでそのクライアントの公開鍵はサーバと交換されており、サーバから送られた公開鍵が g^y とすると、共有鍵は g^xy mod p = (g^x mod p)^y = g^y となり、サーバ側の公開鍵だけで共通鍵を計算できてしまうことになります。従って中間攻撃者に共有鍵がバレバレな状態に持っていくことができます。
この仕込みのおかげで攻撃者も同一の共有鍵の計算を行い、暗号化データの操作や交換するFinishedのHMACデータと一致させることも可能となります。

これで、攻撃者とサーバ間のTLSクライアント認証を伴ったTLSのハンドシェイクの完了です。

無事、攻撃者はTLSクライアントのなりすましに成功しました。
実際書いてみると、いろいろ大変な手続きが必要な攻撃ですが、秘密鍵の漏洩がなくてもなりすましが成功するとは、いやぁー見事です。

5. 危なかったTLS1.3

論文ではTLSサーバのなりすます攻撃も記述しています。TLS1.2のサーバ認証では、ServerKeyExchangeの署名検証を偽造させて成功させないといけませんが、中間攻撃者が自由にいじれるのはClientHelloの乱数値(32バイト分)だけです。この様な制限下ではハッシュ衝突攻撃を行うのはまだ大変困難です。まずは一安心。

TLS1.3では、サーバ認証をクライアント認証と同様のServerCerticateVerifyをTranscriptハッシュの署名を利用するよう仕様変更が行われました。これはクライアント認証同様の手法でサーバのなりすましができるようになり大問題になります。TLS1.3では、INRIAグループからの指摘を受け、仕様からMD5とSHA-1のアルゴリズムを全面的に削除し、該当パラメータをReservedに変更しました。サーバ認証が破られるとその影響は多大なものになるので、TLS1.3は本当に危ないところでした。

6. TLS1.0やTLS1.1はどうなる？

SLOTHの公開を受けてIETFのTLS WGでもMD5をどうするか、TLS1.0/1.1をどうするか、の議論が始まりました。
SHA-1衝突を見つける計算量はまだまだ膨大で、MD5とSHA-1と組み合わせたPRFに対する具体的な衝突がまだ見つかっていません。また、ChromeやIEの統計からTLS1.0/1.1の利用率は現在でも3〜5%存在するため、現時点ではTLS1.0/1.1を直ちに deprecate するという話にはならないようです。

でも確実にSHA-1に対する攻撃の脅威は大きくなってきています。RC4の危殆化とBEAST攻撃でTLS1.0は崖っぷちです。いつまたPOODLEのようなプロトコル上の脆弱性が見つかり、プロトコル自体の廃止が早急に進められる可能性も否定できません。来るべき将来のX-Dayのために、日頃からTLSサーバの構成を注意して備えておきましょう。

*1:多くの実装では使えることが多いそうです。偶数・奇数のチェックを行っているのもあるようですが、その場合は p=g^2-1を利用することができます。ただ g^x mod p が 1 か g^2 のいずれかになるため、確率1/2で当てることになりそうです。