2016-08-04

JPNICの証明書失効の障害とCertificate Transparency(正解編)

前回のエントリーでJPNICの証明書失効の障害事故について事実認定と推測記事を書きましたが、本日報告書が公開されました。

サーバ証明書が意図せずに失効されたことによるJPNIC Webの閲覧不可についてのご報告

文面自体は短いのですが、正解は

新たに発行された３ヶ月弱の期間の証明書は正式に再発行を受けたものであった。
失効の連絡がJPNICに来ず、再発行の証明書を入れ替える前に失効手続きが取られてしまった。

ということであったようです。

前回のエントリーで書いた、期限設定のミスなどはなかったようです。プレ証明書によるシステム的な問題は考えすぎでした。

再発行後、以前の証明書の失効を行う際に事前に連絡確認を怠ったというのが障害発生理由です。

発行からちょうど２週間後に失効されてしまったのは、下記に書いてある規定によるものではないかと思われます。

担当者変更／再発行／解約について

利用中の証明書失効期間について
再発行を行うために利用中の証明書を失効する期限を選択いただきます。発行手続きが完了した後に変更することはできませんので、お間違いないようご注意ください。

後日失効
証明書の入れ替えする期間を考慮し、証明書を再発行した日から2週間後に前証明書が失効されます。
即日失効
証明書の失効と再発行が同時に行われます。

なぜ3ヶ月弱の残り期間で更新を待たず再発行が必要だったのか（かつそんな状況で再発行後２週間経っても入れ替えをしなかったのか）というのは書かれていないのですが、いろいろ事情があったのでしょう。

以上、推測記事の訂正と正解？について書きました。

2016-07-29

JPNICの証明書失効の障害とCertificate Transparency

PKI

0. Disclaimer

先日JPNICのサイトの証明書が誤って失効してしまったという障害が発生しました。

「障害報告：サーバ証明書が意図せずに失効されたことによるJPNIC Webの閲覧不可について(第一報)」

週末にもかかわらず迅速に復旧対応を行った関係者の方々のご尽力は大変なものであったろうと察します。

筆者は本件と全く関わりはありませんが、公開されている情報から推測すると障害の発生経緯に Certificate Transparency とその周辺のPKI技術に深い関連があるように思えました。
正式な報告書が公開される前ですが、twitterで中途半端に推測をツイートしてしまい拡散されてしまったので、事実認定と推測をちゃんと分けて書いたほうが良かったかなと少々後悔しています。

そこで、正式な報告書が公開されたら記述を追記する予定ですが、現時点で自分が把握している客観的な事実と個人的な推測を分けて書いておきます。

2016年8月4日 20:49(JST)追記: JPNICより正式な報告書がリリースされました。

サーバ証明書が意図せずに失効されたことによるJPNIC Webの閲覧不可についてのご報告

取り急ぎそちらを参照してください。
あわせて正解記事を書きました。そちらもお読みください。
追記終わり

もし関係者の方で、内容が不適切であると思われた場合は、その旨ご連絡をお願いします。記載内容の修正、もしくは全面的に削除を行います。

1. 外部公開されている情報からの事実認定

1.1： 2015/9/30 09:15 GMT (18:15 JST)

JPNIC利用していた証明書発行
https://crt.sh/?id=9952316

シリアル: 17:87:31:52:fa:44:cd:a8:00:00:00:00:53:fa:f1:c5
Validity
            Not Before: Sep 30 09:15:05 2015 GMT
            Not After : Sep 29 14:59:59 2016 GMT

その前に2年あったSHA1証明書から残り１年でSHA2への入れ替えを行ったようです。これが今回誤失効されてしまった証明書です。

1.2： 2016/7/7 2:05 GMT (11:05 JST)

プレ証明書発行、CTログに登録
https://crt.sh/?id=24044898

シリアル: 34:f7:fc:ef:84:24:28:76:00:00:00:00:53:fb:1a:85
Validity
            Not Before: Jul  7 02:05:21 2016 GMT
            Not After : Sep 29 14:59:59 2016 GMT

なんと1.1と同じExpire期限です。３ヶ月弱有効のもの。

1.3： 2016/7/22 3:00 GMT (12:00JST)

1.1で発行されたJPNIC利用中の証明書が失効

    Serial Number: 17873152FA44CDA80000000053FAF1C5
        Revocation Date: Jul 22 03:00:22 2016 GMT
        CRL entry extensions:
            X509v3 CRL Reason Code:
                Unspecified

これが障害発生の直接的な原因です。

1.4： 2016/7/23 9:19 JST

ユーザが発見, twitterで報告

JPNICの証明書、revokeってことは失効してる？ pic.twitter.com/a2LzIetmLn
— タモ㌠は日陰おひるね作戦ですっ！ (@tamosan) 2016年7月23日

1.5： 2016/7/23 10:49(JST)

復旧
JPNICの障害報告書による復旧時間です。

1.6： 2016/7/24 11:06 GMT (20:06 JST)

正式発行証明書がCTログに登録される。
https://crt.sh/?id=25317179
2016/7/29現在JPNICのサイトが利用している証明書がこれです。

2. CT(Certificate Transparency)対応EV証明書発行の流れ

JPNICが利用しているEV証明書は、CT(Certificate Transparency)に対応した証明書です。CTについては漆嶌さんの資料が非常に詳しいです。

Certificate TransparencyによるSSLサーバー証明書公開監査情報とその課題の議論

今回1.2に書かれているプレ証明書というのはCT対応の証明書の発行手続きで必要なものです。漆嶌さんの資料からスライドを引用すると図中の丸1に該当します。

これを見ると、EV対応によって認証局内部の証明書発行業務も従来のフローから変更せざる得なかったのではないかと思われます。

3. 障害発生原因の推測

(注意) ここからはあくまで個人的な推測の範囲での記載になります。正式な報告書がリリースされたらそちらを参照して下さい。

3.1 ２つのミスが重なったのか？

1.2で発行されたプレ証明書の期限が3ヶ月弱で以前から利用している証明書と同じExpireの期日で、更新が数ヶ月後に迫っているのに非常に不自然です。
また、誤失効がプレ証明書の発行後で正式証明書がCTログに登録される前です。障害対応後に正式証明書がCTログに登録されています。

このことから推測するに、

何らかの理由でプレ証明書の期限設定を間違えて発行してしまったのではないか。
期限設定を間違えたプレ証明書を失効しようとして何らかの理由で利用中の証明書を間違えて失効してしまったのではないか。

といった可能性が考えられます。繰り返しますが第１報以降が公開される前ですのであくまで個人的な推測です。この推測が当たっているかどうか次の報告を待ちたいと思います。

なお、一度失効されてしまった証明書の失効を取り消すことは現実的に難しいようです。EV証明書の運用ポリシーを定めた規定CA/Browser Forum Baseline Requirements Certificate Policyの4.10.1には
「CRLやOCSPの失効エントリは失効された証明書の有効期限以前に削除してはいけない」
と記載されています。

今回誤失効された証明書はExpireするまで削除することはできないため、おそらく今回発行したプレ証明書から作った正式登録証明書に入れ替えて復旧対応したものと推測されます。本当にご苦労様でした。

3.2 Certificate Transparency の闇(プレ証明書)

もし今回の障害がCT対応証明書の発行処理際のプレ証明書の扱いに関連するのであれば、漆嶌さんが見事に予想されていました。

（漆嶌さんのスライドより引用）
現実的にCTによって誤発行の発見などブラウザベンダ側にメリットをもたらしましたが、その副作用で別のリスクが増えてしまったのはなんとも残念です。

今回、漆嶌さんと少し議論して最後に的確なコメントをいただきました。

@jovi0608 CTは思いつきで作って、結果実装や運用を無駄に複雑にしてしまった仕組みなので、この手の実装上の不備で運用に問題が発生するケースは今後もあるでしょうね。
— Kenji Urushima (@kjur) 2016年7月29日

2016/7/29 20:14 漆嶌さんの漢字が間違ってましたので修正しました。ごめんなさい。ごめんなさい。指摘していただいた林さんありがとうございました。

2016-07-06

HTTP/2とTLSの間でapacheがハマった脆弱性(CVE-2016-4979)

http2 TLS

0. 短いまとめ

昨晩apache2.4でHTTP/2利用時にTLSクライアント認証をバイパスする脆弱性(CVE-2016-4979)が公表され、対策版がリリースされました。
実際に試すと Firefoxで認証バイパスができることが確認できました。
HTTP/2でTLSのクライアント認証を利用するには仕様上大きな制限があり、SPDY時代から長年の課題となっています。
この課題を解決するため、Secondary Certificate Authentication in HTTP/2という拡張仕様が現在IETFで議論中です。

1. はじめに

ちょうど昨晩、apache2.4のhttpdサーバの脆弱性(CVE-2016-4979)が公開され、セキュリティリリースが行われました。

CVE-2016-4979: X509 Client certificate based authentication can be bypassed when HTTP/2 is used

リリース文を読んでみると、なにやらapache-2.4でHTTP/2の利用時にTLSクライアント認証がバイパスされる脆弱性とのこと。CVSS3スコアも7.5でHIGH。
はてさてHTTP/2仕様(RFC7540)ではTLSクライアント認証の利用は非常に限定的であまり実用的ではないと思っていましたが、得てして脆弱性とはあまり利用されないところで起こるものです。修正パッチもわずか1行でした。

実はちょうど今IETFのhttpbis WGでクライアント認証を可能にする新しい拡張仕様ドラフトが議論中です。この分野はまさにホットなトピック。HTTP/2 やTLSの仕様と照らしあわせなら実装を見てみると、この脆弱性は新しい仕様の背景の説明ネタとしてはピッタリです。

実際に試すとHTTP/2利用時にクライアント認証をバイパスする脆弱性も再現できました。ということで、この脆弱性通じてTLSとHTTP/2の仕様と課題を理解できないか、新しいエントリーを書いてみます。

2. TLSクライアント認証をバイパスするapache-2.4の脆弱性(CVE-2016-4979)とは？

この脆弱性の中身は、実際に見てみるのが一番でしょう。脆弱性のあるapache-2.4.20でHTTP/2のサーバをたててみます。

/client_auth にアクセスするとクライアント認証が必要なようにapacheのconfigを設定し、アクセスするブラウザはクライアント証明書を何も入れてないFirefox47を使いました。後述するようChromeではこの脆弱性は再現しません。

まずトップページ / を見てみます。青いイナズマが出てちゃんとHTTP/2でページが見えます。コンテンツは、/client_auth へのリンクが貼ってあります。

リンクを辿って /client_auth にアクセスするとFirefoxにクライアント証明書を全く入れてないのでエラーになります。クライアント認証はちゃんと効いています。

せっかく再試行ボタンが見えているので、再読み込みしてみましょう。

あらー、/client_auth のページが見えちゃいました。こりゃアカンです。一度認証エラーになっても再読み込みをするとアクセスできてしまう、それがこの脆弱性の正体です。

apache httpdの修正コミットは、

--- a/modules/ssl/ssl_engine_kernel.c
+++ b/modules/ssl/ssl_engine_kernel.c
@@ -727,6 +727,7 @@ int ssl_hook_Access(request_rec *r)
                      * on this connection.
                      */
                     apr_table_setn(r->notes, "ssl-renegotiate-forbidden", "verify-client");
+                    SSL_set_verify(ssl, verify_old, ssl_callback_SSLVerify);
                     return HTTP_FORBIDDEN;
                 }
                 /* optimization */

のわずか一行。mod_sslの処理においてサーバのSSL インスタンスがクライアントの認証が必要かどうか判断するフラグ verify_mode の処理にバグがあったようです。

3. HTTP/2のTLSクライアント認証の課題

HTTP/2の大きな特徴は、一つのTCP/TLS接続で複数のHTTPリクエスト・レスポンスを多重化してやりとりできることです。これによって、HTTP/1.1で性能のボトルネックになり得る HTTP Head of Line Blocking の解消を実現します。

一方、TLSクライアント認証は、あるリソースへのアクセスをサーバが指定したクライアント証明書を持つ端末に制限する機能です。HTTPサーバは、クライアント認証が必要なリクエストが来るとクライアントにHelloRequestを送ってRenegotiation(TLSの再ハンドシェイク)を発生させます。サーバは、Renegotiationを通じてクライアント証明書と署名データを検証し、正当であればアクセスを許可します。TLSクライアント認証の詳しい解説は、「パンドラの箱？TLS鍵交換の落とし穴、KCI攻撃とは何か」に記載していますので、あまり馴染みのない方は一度お読みください。

HTTP/1.1時代は、一つのTCP/TLS接続を一つのリクエストが専有していたのでこのやり方で問題なかったのですが、HTTP/2では複数のHTTPリクエストが一つのTCP/TLS接続を共有しているので困ってしまいます。

HTTP/2上でHTTP/1.1と同じように renegotiation を行うと、クライアント認証が必要のないリクエストまで巻き添えを食らってしまいます。

そのためHTTP/2仕様では、HTTPリクエストが発生する前の初期接続時のみクライアント認証を許可し、それ以降では禁止しています。従って接続始めからHTTP/2接続全体に認証を行うケースでしかクライアント認証を利用できませんでした。

4. HTTP/2接続後のTLSクライアント認証

このままではHTTP/2を使うとWebのリソースの一部をクライアント認証することができずに困ってしまいます。そこで、あまりスマートなやり方ではありませんが、クライアント認証が必要なリクエストをHTTP/1.1に逃がすことでまぁなんとか対応可能に落とし込みました。

HTTP/2のリクエストがクライアント認証が必要なリソースへアクセスしたらサーバ側は、そのストリームをHTTP1.1 requiredのエラーコードでリセットします。クライアントはHTTP/1.1 requiredのリセット通知を受けると新たにHTTP/1.1の接続を張り、そのハンドシェイクを通じてサーバはクライアント証明書の検証を行ってアクセスを判断します。これでなんとか回避可能です。

5. CVE-2016-4979の原因

CVE-2016-4979は、このHTTP/1.1の接続に逃がす際に verify_mode を元に戻すことを忘れてしまったのが原因です。

サーバのSSL インスタンスに保持されているverify_modeは、クライアント認証するかどうかの状態を保持しています。最初はサーバ認証だけなので SSL_VERIFY_NONE が入っています。mod_sslでは一度既存の接続の verify_mode を verify_old にバックアップしておき、新しいリクエストが verify_modeの変更が入るかどうか検証します。変更があれば verify_mode を新しい値(SSL_VERIFY_PEER|SSL_VERIFY_FAIL_IF_NO_PEER_CERT:クライアントの証明書を検証してダメならエラー)に置き換えて renegotiation を強制させる処理を行います。

しかしHTTP/2では途中での renegotiation は禁止されているので、代わりにRST_STREAMが送信してHTTP/2のTLS接続を維持します。SSLのインスタンスとverify_modeは、新しい値に更新されたままです。これが脆弱性を引き起こしました。
先の修正パッチのちょっと前の部分（下記）が該当します。

        /* remember old state */
        verify_old = SSL_get_verify_mode(ssl);
        /* configure new state */
        verify = SSL_VERIFY_NONE;
        (中略)

        /* TODO: this seems premature since we do not know if there
         *       are any changes required.
         */
        SSL_set_verify(ssl, verify, ssl_callback_SSLVerify);
        SSL_set_verify_result(ssl, X509_V_OK);

        /* determine whether we've to force a renegotiation */
        if (!renegotiate && verify != verify_old) {
        (中略)
        }

まさに TODO に書いてある通り、この処理が不十分になってしまい脆弱性を引き起こしたのは皮肉なことです。

FirefoxはHTTP/2ストリームのリセット通知を受け、新たにHTTP/1.1接続を試みますが、正当なクライアント証明書を持ってないため、接続はエラーになります。

再現試験のように続けて再読み込みを行うと、Firefoxは既存の維持されているHTTP/2接続を使って /client_auth にアクセスします。その際サーバのSSL インスタンスの verify_mode が同じであるため、サーバは既にクライアント認証済と判断し /client_auth へのアクセスを許可してしまいました。認証バイパスの成功です。先の試験でもHTTP/2の青い稲妻状態でアクセスできていることからもわかります。

先の1行修正パッチは、HTTP/2接続で renegotiationをHTTP/1.1の新規接続に逃がす際に verify_mode を以前の値SSL_VERIFY_NONEに戻す処理を加えたものです。これによって再読み込み時でもHTTP/1.1の新規接続への退避が繰り返し行われることになり、認証バイパスの脆弱性は回避されました。

Chrome(51のStable)ではこの脆弱性は発生しません。調べてみるとChromeは、http/1.1 requiredのRST_STREAMを受け取ると既存のHTTP/2接続を切断してしまうようです。そのため認証エラー後の再読み込みに新規のHTTP/1.1接続を張るため、この脆弱性の影響を受けなくなっていました。この辺の処理は実装依存なのでまぁ良かったということでしょう。

6. Secondary Certificate Authentication in HTTP/2

HTTP/2上でのクライアント認証の課題は、TLSとHTTP/2の両方の仕組みに関連する本質的なものです。実はSPDY時代からこのことは課題認識されており、SPDY/3ではクライアント認証に対応するためCREDENTIALというクライアント証明書と署名データをやり取りするフレームが規定されていました。

しかしGoogleは実際にクライアント認証を利用していなかったため、結局一度もChromeにCREDENTIALが実装されることはありませんでした。HTTP/2でも当初はスコープ外として早々に機能削除されました。

HTTP/2の仕様完了後、本格的なクライアント認証の機能が欲しいというユーザの声を受け、クライアント認証の拡張仕様の検討が始まりました。当初MSとMozillaの２つのドラフトが提出されていましたが、先のBAのIETFで一本化する方針が決まり、先日Secondary Certificate Authentication in HTTP/2 というドラフトが提出されました。今月のベルリンのIETFでも議論される予定です。

話が長くなるので新しいドラフトの解説は止めておきますが、クライアント認証に限らずこれまでTLSのレイヤで行ってきた証明書のやり取りと検証をHTTP/2のレイヤでも追加で行えるよう拡張するもので、なかなかしびれる機能になりそうです。

こうやって一つの脆弱性から技術プロトコルの仕組みと課題、その解決に向けての検討状況が見えてくるのは非常に楽しいですね。

2016-05-24

本当は怖いAES-GCMの話

Disclaimer

本エントリーは、この夏 blackhat usa 2016で行われる予定の講演「NONCE-DISRESPECTING ADVERSARIES: PRACTICAL FORGERY ATTACKS ON GCM IN TLS」のネタバレを含んでいます。現地で直接聞く方は読まないよう気をつけて下さい。

0. 短いまとめ

今回は短めにと思ったのですが、やっぱりそれなりの分量でした。なので短いまとめを書いておきます。

4千万以上のサイト対してAES-GCM使ったTLS通信の初期ベクトル(IV)データのサーベイが行われ、7万程のサイトでIVの値が再利用される可能性があることがわかりました。IVが再利用された場合、AES-GCMの安全性は致命的な影響を受けます。IVの再利用が判明した幾つか実装から既に脆弱性のアナウンスが出ています。

IVが再利用された場合、現実的にHTTPSサーバのコンテンツが改ざんできる実証(PoC)コードが公開されました。試してみたらホント見事にHTTPSサイトのコンテンツの改ざんができました。

この脆弱性の根本的な解決方法として、IVの再利用を避けるAEADの生成方式が幾つか検討されています。直前のエントリーで解説したChaCha20-Poly1305の方式は、既にTLSの通信でIVの再利用されることが原理的に不可能な仕組みになっています。現在仕様策定中のTLS1.3でも同じ対策が取られており、将来的にはIV再利用の問題は解決する方向になるでしょう。

今年の夏のセキュリティ・キャンプ全国大会では、「TLS徹底演習」という講義でChaCha20-Poly1305を扱います。来週5/30(月)が応募締め切りです。TLSに興味がある学生の方々は、ぜひ応募してください。

1. はじめに

先週5/20(金)の日本時間未明に、Bulletproof TLS Newsletterの著者で有名なHanno Böck氏らのグループが「Nonce-Disrespecting Adversaries: Practical Forgery Attacks on GCM in TLS」という脆弱性情報を公開しました。ここで公開されている論文と実証(PoC)コードによって、TLSのAES-GCMに対して初期ベクトル(IV)が再利用されると実用的な攻撃が可能であることが示されました。AES-GCMは、現在最も信頼されている暗号方式であり、これが影響を受けるとしたらホントに一大事です。

2. 実は危ないTLS1.2のAES-GCM

いつものごとく長文になるので、今回はAES-GCMのあまり細かい解説はやめます。前回のChaCha20-Poly1305のエントリーにAES-GCMとChaCha20-Poly1305を比較して特徴をまとめていますので、まだ見ていない方はそちらを読んで下さい。ちなみに学問的なGCMの安全性の評価は、日本の研究者の方々の業績*1による貢献が非常に大きいです。このようにAES-GCMの安全性がちゃんと数学的に証明されていることが、現在普及が進んでいる要因の一つと言えるでしょう。

数学的に安全が保証されているGCMですが、それはGCMが使うIV(初期ベクトル)が再利用されないこと、すなわちIVがNonce(Number used once)であることが大前提となっています。この前提が崩れるとAES-GCMの安全性は大きく損なわれます。

今回の調査で、幸いこの脆弱性の影響を受けるのは一部実装に限られており、(素のままの)OpenSSLは問題ありません。Nonceには決して再利用する値を使わない、ある意味暗号実装の世界では常識的に言われていることですが、その現時的なリスクがこれまで十分理解されていたとは言えません。今回実際に手元でPoCを試してみて、ブラウザから何のアラートもなくTLSのコンテンツの改ざんが成功しました。ホント見事です。頭でわかっていることですが、実際に行えることの知るギャップは非常に大きいです。そのリスクを現実的に示したことが、この論文の主題の一つじゃないかなと思います。

2.1 TLS1.2のAES-GCM

TLS1.2のAES-GCMは次のようなフレームで生成されます。

AES-GCMの初期ベクトルとして12バイト必要ですが、TLSでは頭の4バイト分はPrefixとしてハンドシェイク毎に固定して利用します。この部分は、鍵交換で生成した master secret から4バイト分を使います。残りの8バイトは、Nonceであることが必要です。TLSで暗号化されたデータの頭に明示的に8バイト分のIVが付与されています。当然この部分は暗号化されていないので攻撃者からはHTTPSサーバがどのようなIVを使っているのか丸見えです。

2.2 TLS1.2のGCMのMAC(タグ値)の求め方

GCMのMAC(タグ値)は、このIVとAESの共通鍵を使って２つ鍵HとSを使って計算します。

GCMの安全性は、この２つの鍵(HとS)によって担保されます。すなわちAESが破られない限りGCMは十分安全です。

2.3 IVの再利用はGCMの安全性に致命的

もし同じIVを持つ２つのAES-GCMのAEADデータがあったらどうなるでしょうか？両者のデータをXORすれば、鍵Sのマスク効果は消えてしまいます。

結果、鍵Hだけの１変数剰余多項式になり、因数分解によって解を求めることができます。一般的に複数の解を持ちますが、鍵Hが判明すればGCMのMAC値を再計算することが可能になります。これはAES-GCMの安全性を致命的に損なうことにつながります。本当に怖い話です。

3. 現実のHTTPSサーバへの調査

Hanno Böck氏らのグループは、今回インターネット上の4800万以上のHTTPSサーバをスキャンしてAES-GCMのIVが実際どのように生成されているのか調査を行いました。その結果、7万以上のHTTPSサーバでIVの値が再利用される可能性があることがわかりました。対象サーバへの調査を進めたところ、大きく2つの原因によるものでした。

3.1 AES-GCMの実装上の問題に起因するIVの再利用

一番致命的なのは184のサーバで、文字通り初期ベクトルがホントに再利用されているのが観測されました。これはダメです。脆弱なサイトには、大手のクレジットカード会社や金融機関のサイトのサイトが含まれていました。大きく4種類の実装が該当しており、いずれもCavium社のチップを使っていました。どうも OpenSSLに手を加えてHSM(Hardware Security Module)の実装をしているのではないかと見られています。実は以前のOpenSSLでは、IVの生成を RAND_bytes() 関数から取得していましたが、その返り値をちゃんと見ていませんでした。1.0.1系では「Fixed missing return value checks.」でエラー判定をするよう修正されています。

おそらくHSMを組み込む際にこの部分の処理がそのままになっており、乱数生成がエラーになってもIVが未初期化の変数のまま値を送信してしまう、そんなバグがIV再利用の原因だったのではないかと想定されています。

3.2 TLSのプロトコル仕様に起因する実装の問題

さらなる調査結果から、７万以上のサーバが乱数を使って初期ベクトルを毎回生成しているのがわかりました。この方式では、大量のデータの通信を行うと過去使った乱数値と同じ乱数を生成してしまう確率が格段に上昇します。TLSの仕様では8バイト分がNonceなので、試算では2^33の乱数を生成すると誕生日パラドックスで80％の確率で衝突するようです。これではテラバイト級のデータを通信すると危ないです。4バイトのPrefixと8バイトのNonceでIVを作成するのは、FIPS-140の規定から来ているようですが、乱数でNonceを生成するには時代的にもう合わなくなってきました。そのため他の実装では、通常IVにカウンター値を利用します(Nonceは再利用されなければ予測可能であっても構わない）。この場合、IVは2^64まで一意に生成できるのでまぁ大丈夫でしょう。OpenSSLでは一番最初の値を乱数で決め、それ以降はカウンターとしてインクリメントしていく実装になっています。

今回の調査で、Radware と IBM Domino Webサーバの脆弱性が公表されています。他にA10や中国のSangforの脆弱性についても論文で指摘されています。また、MicrosoftのIISサーバに対してもいくつか見つかったらしいですが、MicrosoftからはSChannelはカウンターを初期ベクトルに使っているとの回答があり、途中経路上のLBやFWがTLS通信を行っているかもしれず原因不明のままです。中国のベンダーSangfor からは、報告しても全く返答がなかったようです。もし使っているなら気をつけましょう。

4. Nonce再利用の脆弱性をついたMiTM攻撃を試してみる

繰り返しになりますが、数学上はGCMのNonceが再利用されると危ないのはわかっていたのですが、TLSは毎回ハンドシェイクを行って write_IVが変わるし、現実的にどれだけ危険なのかはこれまでそれ程明確ではありませでした。今回Hanno Böck氏らのグループは、実際にNonceが再利用された場合にHTTPSサーバのコンテンツを偽造する PoC コードを公開しました。ここでその方法を見てみます。

このPoCは、中間者(MITM)を使ってNonce再利用の脆弱性をついた攻撃を行います。試験ではネットワーク経路をタップするのは大変なので一旦 port 8443 で受け、443にリレーする形式で擬似的に中間者攻撃をテストします。クライアントとHTTPSサーバとは port 8443 を経由して End-to-EndでTLS接続しており、port 8443上の攻撃者がデータの盗聴や改ざんを行うことは不可能です。

4.1 IVの収集

まず攻撃者は、クライアントを悪意のあるコンテンツに誘導し、クライアントから攻撃者経由でサーバへの数多くのTLSアクセスを仕掛けます。そして攻撃者は、そのTLSデータ収集します。PoCコードでは、

<html>
  <head>
    <meta http-equiv=refresh content=1>
  </head>
  <body>
    <script>
      var img = new Image();
      img.src = 'https://noncerepeat.com:8443/';
    </script>
  </body>
</html>

のようなコンテンツをクライアントに踏ませ、keep-aliveでTLS接続を維持したままイメージを攻撃者経由で取りにいかせます。攻撃者はTLSフレームを収集・解析し、じっとIVが再利用されるまで待ち続けます。

4.2 再利用されたIVの発見

攻撃者はついに、別のTLSフレームで同じIVを使われていることを発見しました。暗号文、タグ値は別のデータです。
この同一のIVで異なる暗号文、タグ値を持つ２つのフレームデータを使い、GCMのMAC鍵Hを直ちに計算を始めます。

4.3 GHASHのMAC鍵Hの計算

GCMはPoly1305と同様に多項式を使った剰余値を鍵Hを使って計算しハッシュを求めます。
同一のIVの暗号データから生成した２つの剰余方程式の論理的排他和(XOR)を取ると、IVを暗号化してマスクしたハッシュ値の効果は消えてしまいます(同一データのXORは0になる)。そのためGCMの多項式は0を暗号化したMAC鍵Hの単独多項式になり、それを因数分関して解のMAC鍵Hを求めることが可能になります(鍵候補が複数になることもあり)。

4.4 HTTPSサーバのコンテンツの改ざん

さあ攻撃者はMAC鍵Hを入手しました。悪意のあるコンテンツを変更して

window.location = 'https://noncerepeat.com:8443/"

を差し込み、クライアントの接続先を攻撃者の宛にリダイレクトさせます。

この際、データを暗号する鍵はまだわかりません。そのためTLSの暗号文を解くことはできませんが、データのMACを計算する鍵を持っているので、もし通信のデータが判明していればXORを使ってその値を改ざんすることが可能です。攻撃者はGHASHのMAC鍵Hを持っているので、タグ値を再計算します。データを改ざんした攻撃者は、新しいタグ値にTLSデータを入れ替え、クライアントに送信します。クライアントはMAC値が合っているのでコンテンツの改ざんに気づきません。

4.5 実際にやってみた。

実際にPoCコードを試してみました。自前のTLS実装を細工して同一IVを送信するように変更します。中間者攻撃を担うGoで書かれた gcmproxy は port 8443から443へのTCPリレーを行います。ここでIVや他のTLSのデータを収集し、同一のものが見つかれば NTL（Number Theory Library)を使って鍵Hを求め、偽造したデータのタグ値を再計算します。通常鍵Hは複数候補が見つかるので1発で成功することはなかなかないのですが、何回か繰り返すと成功しました。

この画像のようにブラウザ上のHello World の文字列の一部が Cracked! に変更されているのがわかります。あらかじめHello Worldの文字列がわかっていれば、Hello Cracked!とのXORを取ったデータをTLSデータに差し込めば、タグ値を再計算して改ざんが成功です。

5. IVを再利用させない対策は？

この脆弱性は、いずれも実装上の問題です。IVがNonceである限りAES-GCMの安全性は確保されます。しかし実装上の問題で今回のような脆弱性が発生するとAES-GCMの安全性に致命的な影響を受けることになります。
そのためIVを再利用させない対策が2つ進められています。

5.1 AES-GCM-SIV

現在IETFのCFRG(Crypto Forum Research Group)では、AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryptionの仕様化の議論が進んでいます。これは多項式生成の方式を変更してIVが再利用されても影響が出ないようにする仕組みをGCMに組み込んだ仕様です。素のGCMより若干(10%程度)オーバヘッドが入りますが、実装上のIV再利用のバグに耐性があることからより安全な暗号方式と言えるでしょう。でもこれが仕様化されても、次の方式があることからTLSの暗号方式として採用されるかまだわからないところです。

5.2 暗黙的に両者で共有するIV(ChaCha20-Poly1305の方式)

まっとうな実装は、IVとしてカウンターを使います。TLSには、暗号を開始してからどれだけ暗号フレームを送受信したのかわかるよう、クライアント・サーバ間で sequence number を内部で共有しています。これをIVに流用すれば万事解決です。
前回解説したChaCha20-Poly1305のAEAD生成方式では、まさにこの方式が採用されています。そのためサーバ・クライアント間で明示的に8バイトのIVをやり取りする必要がなく、全体のフレームサイズの節約にも貢献しています。

では ChaCha20-Poly1305ではどうIVを生成しているのか見てみます。

8バイトのsequence numberの頭に4バイト分0を付与し、master secretから導出した12バイトのwrite IVをXORを取ってIVとしています。このためIVはNonceに必ずなります。この方式は、別にChaCha20-Poly1305固有のものではありません。TLS1.3では全てのAEADの暗号方式のIVはこの方式で生成されます。TLS1.2のAES-GCMは既に今の方式で仕様化されているため、もしこの方式にするためには新しくAES-GCMのCipherSuiteのエントリーが必要となるでしょう。

6. 今年のセキュリティ・キャンプはChaCha20-Poly1305

ということで、ここからは宣伝です。今年の8月に行われるセキュリティ・キャンプ全国大会に講師として参加する予定です。「TLS徹底演習」という講義を、なんとまる一日、集中講義として8時間行います。

当日どこまでできるかわかりませんが、内容は

本講義では、2016年にTLSに新しく追加される暗号方式ChaCha20-Poly1305を使って実際にTLSのプロトコルを実装し、自らが手を動かす事によってインターネット通信のセキュリティを実現しているTLSの理論と実践を徹底的に学びます。

を予定しています。他にもTLSの djb 三部作(AEAD:ChaCha20-Poly1305, 鍵交換：x25519/448, 署名：eddsa25519/448)の一つChromeに先行実装されている x25519 もやりたいのですが、やっぱり時間的に難しいかなと思ってます。今回は、とにかくTLSに関して徹底的に演習を行います。

去年に続いて2回めの全国大会の講師としての参加ですが、全国からトップクラスのスキルを持つ若者エンジニアが集まるセキュリティ・キャンプで講義ができるのは本当に楽しみです。受講者を普通の学生とは思わず、海外でも通用するガチな最先端エンジニアだと思って講義・演習を行うつもりです。応募の締め切りは来週5/30(月)まで、興味のある方の応募を待っています。

*1:「国際標準暗号GCMの新たな安全性評価結果〜従来の安全性保証に欠陥が発見されるも、修復に成功〜」

2016-04-04

新しいTLSの暗号方式ChaCha20-Poly1305

TLS

Disclaimer

本エントリは、近々IETFで標準化される予定の新しいTLSの暗号方式 ChaCha20-Poly1305 について解説したものです。

本来なら、新しい暗号方式を紹介するいうことは、その暗号の安全性についてもちゃんと解説しないといけないかもしれません。しかし一般的に暗号の安全性評価はとても難しく、専門家でない者が暗号の安全性について軽々しく書くわけにはいかないなとも思いました。いろいろ悩みましたが、結局無用な誤解を避けるため、本エントリーでは ChaCha20-Poly1305 の安全性に関する記載を最小限に留めています。

今回紹介する ChaCha20-Poly1305 は、これまでも様々な暗号研究者の評価を受けている暗号方式ですが、まだNISTの標準や某国の推奨暗号リストに掲載されるといった、いわゆる特定機関のお墨付きをもった暗号方式ではありません。記載内容が中途半端で申し訳ありませんが、ChaCha20-Poly1305 の暗号利用の安全性について心配な方は、本エントリーをお読みにならないようお願い致します。またこういった内容を留意していただいた上で、本記事をお読みくださるようお願いします。

2016年6月23日追記:
RFC7905「ChaCha20-Poly1305 Cipher Suites for Transport Layer Security (TLS)」が発行されました。

0. 短いまとめ

記事が長いです。長文を読むのが苦痛な方は、この短いまとめだけ読んでください。

新しいTLSの暗号方式 ChaCha20-Poly1305 が仕様化されます。
新仕様版はChrome49/Firefox47/OpenSSL-1.1.0(beta)などで既に利用可能です。
AES-GCMより転送サイズが小さくなり、AES-NIのないARM環境では３倍程度性能が高くなります。
OpenSSLなどでcipher server preferenceと両立して運用するには現時点で課題があります。equal preference cipher groups機能待ちです。

(2016年5月16日訂正: 記事中 TLSのAES-GCMのタグ長が12バイトと記載されていましたが、16バイトの誤りです。図表と記載を修正しました。id:kazuhooku さんのご指摘ありがとうございました。)

1. TLSに新しい暗号方式が必要となった背景

常時HTTPS化は、これからのWebには避けられない流れです。その中核となる通信プロトコル TLSには、現在いろいろなリスクや課題が存在します。

1.1 AESがTLSのSPOFになっている

その課題一つに現在広く利用されているAESを使った暗号方式に関するものがあります。

現在実用的に広く使えるTLSの対称暗号が実質AESの一択しかない。

AES以外の暗号で普及しているという意味ではまだ3DESも健在ですが、性能がAESに比べて1/4〜1/10に落ちてしまいます。AES/3DES以外にも性能的に見劣りしない対称暗号もありますが、世界的に広く使われているとは言い難いです。

こんな状況でもし今、AESに重大な問題が見つかったらとしたらどうなるか？ TLSの運用者は非常に厳しい選択に迫られます。対称暗号以外ではTLS1.2において、認証は RSA/ECDSA, 鍵交換は DHE/ECDHEと2つ以上の仕組みが存在します。リスク管理の観点から、現実的に代用できるAESのバックアップを持つことが今のTLSに必要です。

1.2 AES-NIのないARM環境でも安全で高速な暗号が欲しい

AESはハードウェア処理(AES-NI)が使える環境では非常に高性能だが、ソフトウェア処理だけではそれほど性能がでない。またAESはキャッシュタイミングなどサイドチャネル攻撃を避ける必要がある。そのため実装が複雑になりがちである。

IntelやAMDのCPUで実装されているAES-NIは、非常に強力な機能です。AES-NIを使うだけで暗号処理能力は数倍に跳ね上がります。しかしモバイルやIOTの環境でよく利用されるARMにはAES-NIなど入っておらず、非力なCPUの上でソフトウェアで頑張らないといけません。その上、やみくもな最適化はキャッシュタイミングによるサイドチャネル攻撃を受ける可能性があります。

シンプルな実装で、なおかつAES-NIのない環境でも十分に性能が確保できる暗号方式が求められています。

1.3 新しい暗号方式 ChaCha20-Poly1305 の導入

ChaCha20はストリーム暗号、 Poly1305はメッセージ認証(MAC)の機能を実現します。共に著名な D. J. Bernstein (djb)氏が考案しました。djbは当初SalSa20という暗号を公開し、後にChaCha20という改良版を発表しました。いずれもラテンダンスの名前にちなんでいるようですが、はっきりと名付け由来が書いてある記述を探し当てることはできませんでした。どなたか由来を知っている人がいらっしゃいましたら教えて下さい。

4/5追記： id:bottomzlife さんより情報を頂きました。ありがとうございます。

https://t.co/34OXqKuhit
Salsaの由来は4カウント（正確には8拍だけど）のベースステップがクオーターラウンドに似てるからだね。djbにしては楽しい命名 id:jovi0608
https://t.co/kuURgqniyu
— bottomzlife (@bottomzlife) 2016年4月4日

Poly1305に関しては、最初 ~~dbj~~ djb はhash127という2^127-1の素数を使ってMACを計算する方式を発表していましたが、後により計算効率が良い2^130-5の素数を使ったPoly1305を2005年に発表しました。どちらも鍵の生成に対称暗号と組み合わせることが必要で、論文ではAESと組み合わせたPoly1305-AESが使われていました。Poly1305の仕組み上、AES以外の対称暗号とも組み合わせられることが可能です。

RFC7539では、Poly1305がChaCha20と組み合わせた形で仕様化されました。ChaCha20/Poly1305のどちらも知的財産権などの問題もないと言われています。ChaCha20とPoly1305は、ともに非常に簡潔なアルゴリズムで規定されており、ソフトウェア処理に向いています。これを使って先に述べたTLSの課題を解決できるものと期待されています。

1.4 ChaCha20-Poly1305のこれまでの歩み

ChaCha20-Poly1305のこれまでの歩みをざっと表にしました。

TLSに関連する動きが出てきたのが2013年から。このあたりで、Chacha20とSHA1を組み合わせたり、Salsa20とUMAC(RFC4418)と組み合わせたドラフトなどが公開されていました。動きが本格化したのは、2013/09 にGoogleのセキュリティ専門家 Adam Langlay (agl)氏が、ChaCha20とPoly1305を組み合わせた暗号方式のドラフトを提出してからです。

ちょうど2013/06にEdward Snowden事件でNSAによる広範囲の盗聴・改ざん行為が明らかになり、Dual_EC_DRBGのバックドア問題などNSAが関与しているNIST標準の暗号方式に対する疑義が高まった時分でした。過去米国政府と暗号技術に関して何回も法廷闘争を繰り広げたdjbの暗号は、安全性に対する信頼は他とは違うぞと、この時期の新しい暗号方式の提案にはそんな象徴的な意味合いを個人的に感じてしまいます。

早速ChaCha20-Poly1305は、2013/11にChromeに先行実装され、現在まで既にGoogleのサービスで利用されています。この時期の先行実装は、現在のLastCall 版の仕様と若干異なっており、互換性はないものでした(Googleは既に最新仕様に移行しています)。

Google以外の実装では、2014/04に発覚したHeartBleed脆弱性の余波でLibreSSL/BoringSSLがOpenSSLからフォークされたことを受け、これらのフォークが直ちにChaCha20-Poly1305をサポートし始めました。これらの実装の広がりを受け、IETFのTLS WGの要請を受けCFRG(Crypto Forum Research Group)で議論が進み、2015/05にChaCha20-Poly1305の仕様がRFC7539として発行されました。

このRFC7539で規定されたChaCha20-Poly1305をTLSで使えるようにするのが、 draft-ietf-tls-chacha20-poly1305-04 です。2016/3/22にIETF Last Callが開始され、ちょうど明日(4/5)に終わります。IESGとIANAのレビューが無事通れば、近いうちに晴れてRFCになる予定です。この仕様はTLS/DTLSの両方の利用を規定していますが、本エントリーはTLS向けの仕様だけを解説します。

1.5 TLSで使えるChaCha20-Poly1305の種類

今回新たにTLS仕様化されるのは以下の７つの CipherSuiteです。いずれもAEAD(認証付き暗号)であるため、AEADの規定がないTLS1.0/1.1では仕様上利用できません。使うにはTLS1.2以上が必要です。

TLS_ECDHE_RSA_WITH_CHACHA20_POLY1305_SHA256	O, F, C
TLS_ECDHE_ECDSA_WITH_CHACHA20_POLY1305_SHA256	O, F, C
TLS_DHE_RSA_WITH_CHACHA20_POLY1305_SHA256	O, Fコメント欄参照
TLS_PSK_WITH_CHACHA20_POLY1305_SHA256	O
TLS_ECDHE_PSK_WITH_CHACHA20_POLY1305_SHA256	O
TLS_DHE_PSK_WITH_CHACHA20_POLY1305_SHA256	O
TLS_RSA_PSK_WITH_CHACHA20_POLY1305_SHA256	O

(O: OpenSSL-1.1.0, F: Firefox, C: Chrome)

PSK(PreSharedKey)のCipherSuiteが4つ。ECDHEの鍵交換はRSA/ECDSA認証の２つ、残る１つはDHE/RSAのものです。master secretを生成するPRFにはすべてSHA256を利用します。個人的には Chrome49, Firefox47, OpenSSL-1.1.0-beta1 で既に実装されていること確認していますが、LibreSSLやその他のTLS実装はどの程度対応しているのかまで見ていません。各実装がサポートしているCipherSuiteを表の２カラム目(O, F, C)として記載しておきます。

2. ChaCha20とは何か?

先述した通りChaCha20は非常にシンプルなアルゴリズムを使った暗号です。せっかくだからその仕組みを解説したいと思います。まずはAESと比較してみてChaCha20の特徴を見てみます。

2.1 AESとChaCha20の比較

AESはブロック暗号、ChaCha20はストリーム暗号と分類されます。しかしAES-GCMなどカウンターモードでのAESの利用は、実質ストリーム暗号として機能します。AEADの観点から比較するとストリーム/ブロックでの両者の暗号の違いはほとんどありません。ChaCha20は、入力にNonceと初期カウンター値が必要なのが特徴です。暗号の安全性を確保するため、Nonceは同じ値が使われないことが必要です。Nonceサイズはオリジナルの djb の論文と異なっています。これはAEADの仕様(RFC5116)の推奨サイズに合わせたためです。

暗号実装では両者は大きく違います。AESでは、剰余計算を高速に行うために事前計算テーブルを作成したり、要素を非線形に変換するSBOX処理が必要ですが、ChaCha20は後述する通り加算剰余、XOR、ビットローテーションという単純な計算処理だけです。ChaCha20は、SIMDを使うとより高速なソフトウェア処理が可能になります。

2.2 ChaCha 1/4ラウンド演算

先程から繰り返し書いている通り、ChaChaの暗号化を担う処理は非常にシンプルなものです。この処理を行う中心的な関数を1/4ラウンド演算(QuarterRound)と呼びます。ChaChaは内部に4バイトx16個の状態を持っています。このQuarterRoundを使って内部状態の中の4つの要素(a, b, c, d)を混ぜあわせ、新しい要素の値に更新します。

QuarterRoundは、上図の通り４つの演算から成り立っています。 x + y は (x+y) mod 2^32, ^ は XOR, <<< n はnビット左ローテションを表します。注目すべきは乗算がないことです。一般的に暗号技術は、乗算処理が含まれることが多いのです。ChaChaは乗算処理がないため、演算中の桁上り伝搬を心配する必要がほとんどありません。ビットローテーションも固定長なので、容易に Constant Time の演算処理が実現できます。これがサイドチャンネル攻撃を受けにくい理由です。

ChaChaのQuarterRoundは、１回の処理で４つの要素が２回ずつ更新されています。ここはSalsa20から改良された点で、ChaChaがSalsaより安全性が高くなっていると見られている点です。

2.3 2種類のChaChaラウンド

ChaCha20は、４バイトx１６個の初期状態をQuaterRoundを使って状態を変えていきます。QuaterRoundを適応させるやり方として、列の要素４つ対する列ラウンドと、対角的に並ぶ要素に対する対角ラウンド、この２種類のChaChaラウンドを規定しています。これを使い16個の要素全部に対して偏りなく演算を行っています。

2.4 ChaCha20 Stream State

ChaChaの初期の状態はどうやって決まるでしょうか？最初の４バイトｘ４は定数値です。これは expand 32-byte k という固定文字列が入っています(このmagic wordの由来もわかりませんでした)。

次にChaCha20の鍵データ、３２バイトが続きます。その後に通常１から始まるカウンター値、１２バイトのNonceが入ります。これを列ラウンド＋対角ラウンドの演算を10回繰り返します。結果1/4ラウンドを20回繰り返すことから ChaCha20 ということになります。20はラウンド数を表しています。

ChaCha20は、20ラウンドの演算を経て最終的に生成した ChaCha20 State を使って平文から暗号文を生成します。

2.5 ChaCha20による平文の暗号化

平文から暗号文の生成は簡単です。平文を64バイトのブロックに分割します。それぞれのブロックに対してカウンター値を上げながら、それぞれのChaCha20 Stateを計算します。出来上がった ChaCha20 State と64バイトブロックの平文との XOR をとり、暗号文を作ります。

暗号文から平文に戻す手順もほぼ同一手順です。同じ鍵, Nonce, カウンター値からChaCha20 Stateを作り、暗号文とXORを作れば平文が生成できます。このようにChaCha20ではEncrypt/Decrypt が全く同じ処理でできます。これはソフトウェア処理がシンプルになる大きなメリットです。

AES単体のDecryptは、Encryptの逆関数を用意しなければならず、ChaChaほど簡単にいきません。

3. Poly1305とは何か?

次はPoly1305です。まずは AES-GCMで使われているメッセージ認証GHASHと比較してみます。

3.1 GHASHとPoly1305の比較

GHASHとPoly1305のどちらも Wgman-Carter Constructionという方法でメッセージ認証データを生成します。GHASHはガロア拡大体、Poly1305は素体の有限体上で演算を行います。

仕様的にGHASHは明示的な鍵長制限を持ってなさそうですが(間違っていたら誰か教えて下さい)、AESと組み合わせたAES-GCMの場合は、128bitsの鍵を利用します。Poly1305は、256bit長の鍵を使います。後で説明しますが、256bit長の鍵を2つの鍵に分割して利用します。
GHASHとPoly1305、ともに生成するMACデータ長はどちらも128bitsです。ただしGHASHの方は、用途に合わせて小さく切り詰めて利用され、AES-GCMでは~~96bit~~128bit長にしています。GHASHの利用は、セキュリティの観点から64bits以上であることが求められています。

GHASHの特徴はなんとってもハードウェア処理。Intel/AMDが提供するPCLMULQDQ命令セットを使うと非常に高速に演算できます。
Poly1305の方はChaChaと同様、非常にシンプルなアルゴリズムを持ち、ソフトウェア処理が得意です。
しかも2^130-5という128bitsを少し超えた素数上での演算であるため、計算効率が非常に高くなります。また8bitから64bitまでのサイズの変数を使った最適実装を作ることができ、様々なアーキテクチャ上で高速に動作させることができます。さらにPoly1305は、剰余算を高速化させるために通常行う事前計算テーブルの作成が不要です。ただし剰余を求める際にタイミング攻撃に合わないよう Constant timeな実装が求められます。

3.2 Polynomial evalation(多項式評価)

Poly1305のPolyは、Polynomialの略です。MACによって任意の長さのメッセージが改ざんされていないか認証するためには、認証するメーッセージを何かの形で評価することが必要です。
Poly1305は、メッセージを128bits長のブロックに分割します。各ブロックを係数とした多項式f(x)を作成し、xの値が鍵データrの時のf(r)の値でメッセージを評価します。この多項式には0次の定数項がないのが特徴です。もし定数項があるとメッセージ評価値の差分を取ることによって鍵情報が部分的に漏洩してしまうからです。多項式評価を使うメリットは、ホーナー法によって高次の乗算計算を減らして加算の再帰として計算できるからです。ホーナー法を利用することによって高次の事前計算を避けることができ、ソフトウェア実装がし易くなっています。

3.3 Wegman-Carter Construction

GCMとPoly1305、ともにメッセージ認証コードの生成は、Wegman-Carter Constructionという方式を利用します。

Webman-Carter Constructionとはメッセージのユニバーサルハッシュに一時鍵を加えた値をメッセージ認証値とする方法です。数学的に強度が証明できていることが特徴です。なにより高速です。ユニバーサルハッシュは、暗号だけでなく誤り訂正などにでも利用される高速なデータハッシュ手法ですが、SHA-1/2のような原像攻撃に耐性があるようなわけではなく、暗号ハッシュほどの強度はありません。しかし Wegman-Carter Construction によってメッセージ改ざんを検知するに十分な強度を得ることができるためTLSのAEADでの利用が進んでいます。

3.4 Poly1305のアルゴリズム

Poly1305のアルゴリズムも単純です。tweet(140字以内)で表現可能といわれるぐらいです。

Poly1305のMAC計算は、認証するデータを16バイト長で分割し、頭に0x01を付加して１７バイト長のブロックにします。16バイトに満たないブロックは頭に0x01をつけた後0パディングして17バイト長に揃えます。

16バイト長の鍵を２つ r と s を用意し、鍵rの方は128bit全部利用せず、途中のビットを0にして22bit分間引きます(ここがdjbのすごいところです)。
生成したメッセージを多項式評価として鍵rの値で評価し、素数2^130-5の剰余をユニバーサルハッシュを求めます。一時鍵sを加えれば、強度の高いWgman-CarterのMACデータが出来上がりです。しかしこのままだと最大130ビット長となって扱いにくいので、頭の2bit分を取り除き16バイト長のメッセージ認証データにします。

Poly1350で利用する鍵 r, s は ChaCha20を使って生成します。カウンター0のChaCha20 Stateを求め、上位16バイトをs 下位16バイトをrに割り当てます。

2^130-5という128bitよりちょい大きい絶妙なサイズの素数を利用しているため16バイトという大きいブロックでメッセージ分割した多項式評価が行える。22bit分間引いた鍵rを使用しているため部分剰余のサイズが一定の範囲に納まり、ホーナー法を使いながら各ブロック毎に逐次計算がしやすくなります。

4. ChaCha20-Poly1305とは何か?

これまでChaCha20とPoly1305を別々に見てきましたが、TLSではChaCha20とPoly1305を組み合わせてAEAD(認証つき暗号)として利用します。従来のMac-then-Encrypt(平文のMACを取ってから暗号化を行う方法)では過去いろいろな脆弱性の影響を受ける可能性があるため、ChaCha20-Poly1305はAEAD一択です。

AES-GCMとChaCha20-Poly1305を比較してみます。

4.1 AES-GCMとChaCha20-Poly1305の比較

AES-GCMとChaCha20-Poly1305の大きな違いは、ChaCha20-Poly1305の鍵交換はECDHE/DHEだけしかサポートしないことです。TLS1.2といえでも、もはやForward Securecyのない鍵交換はサポートしません。

またChaCha20-Poly1305では明示的なIV(Nonce)データを必要としません。明示的IVは、TLS1.0でBEAST攻撃に対応するためTLS1.1に導入された項目ですが、次期TLS1.3では廃止される予定です。ChaCha20-Poly1305は、そのTLS1.3仕様を部分的に先取りしたものになっています。

ChaCha20-Poly1305はTLSの暗号化通信を行う際に双方で持つシーケンス番号(8バイト)のデータをNonceに利用します。シーケンス番号を0でパディングし、master secret から生成される12バイト分のWriteIVとXORを取ってNonceとして利用します。こうすることによって、わざわざ８バイトのIVを明示的に送信することがなくなり、その分通信データ量を削減することができます。またバグなどでIVが再利用されてしまうといった間違いも避けることができるので、より安全な実装になることが期待されています。

4.2 ChaCha20-Poly1305のAEAD処理フロー

AES-GCM仕様のフローに似せてChaCha20-Poly1305によるAEAD生成(暗号化)のフローを書くとこのようになります。

初期カウンター0でPoly1305用の鍵(r,s)を作り、初期カウンター１に増加させてChaCha20 Key Streamを生成し、平文から暗号文に変換させます。
認証を行うデータと暗号文それぞれを0でパディングして１６バイト長に揃えます。平文(８バイト長)と暗号文の長さ（８バイト長)を結合して、全体のデータのMACをPoly1305で計算し、128bitのMACデータ(認証タグ)を取得します。TLS1.2では認証を行うデータは、TLSレコード層のデータとシーケンス番号を合わせたデータです。最後に暗号文に認証タグをつけて暗号化されたTLSのアプリケーションデータとして相手に送信します。

4.3 ChaCha20-Poly1305とAES-GCMのサイズ

AES-GCMとChaCha20-Poly1305で１バイトの平文をAEADで暗号化した場合の比較をしてみましょう。

どちらもストリーム暗号として機能するので暗号文は１バイトです。~~タグのサイズはChaCha20-Poly1305が16バイト、AES-GCMが12バイトです。~~ タグのサイズはChaCha20-Poly1305とAES-GCMともに16バイトです。
ただAES-GCMは明示的IVの8バイト分先頭に必要です。レコード層の5バイト分は共通ですからChaCha20-Poly1305は22バイト、AES-GCMは~~26バイト~~30バイト。TLS1.2ではChaCha20-Poly1305の方が、AES-GCMより小さいサイズに収まります。

5. ChaCha20-Poly1305 vs AES-GCMの性能比較

本当に ChaCha20-Poly1305 は、ARM環境では速いのか？ AES-GCMと性能比較してみます。

EC2 c3.large (Intel Xeon E5-2666 Haswell)とRaspberry Pi2 (ARM Cortex-A7)上で openssl speed コマンドによるベンチマークを行いました。ベンチを行った時期がちょっと前だったのでOpenSSLは 3/1 時点での master head( OpenSSL-1.1.0-pre4-dev master HEAD on 2016/03/01)を使っています。その後ChaCha20-Poly1305のアセンブラ関連のバグ修正などされていますが、性能自体はそれほど変わっていないはずです。

Haswellを搭載するc3.largeは、現時点でのEC2の最速CPUで、AES-NI/AVX/AVX2とハードウェアの力で暗号処理を高速化させる機能が満載です。OpenSSLもAES-NI/AVX/AVX2に対応するようビルドしています。Raspberry Pi2 の ARM の Cortex-A7 には、 NEON によるベクトル処理がサポートされています。しかし2016/04/04時点でまだopenssl-1.1.0にバグが残っており、正常に Raspi でビルドできませんので、実際にベンチを試される方は注意して下さい。

グラフでは 8Kバイトのスループットを比較してみます。

まずは Intel Haswell上での比較から。

うん、AES-GCMはやっぱり速いです。3.1Gbpsのスループットを叩き出しています。ChaCha20-Poly1305はAES-GCMのおよそ半分 1.6Gbpsのスループットがでます。逆にいうとAES-NIという強力なハード処理の助けがなくてもここまで性能が出せるのは健闘でしょう。

ARM上ではどうなる？

おぉ！確かに ChaCha20-Poly1305の方がAES-GCMより3倍程度速いです。絶対的なスループット性能は Intel Haswellには全くかないませんが、AES-NIのないARM環境では AES-GCMより ChaCha20-Poly1305 の暗号方式を利用するのが性能的に良いことが明らかです。

6. TLSの運用はどうなる？現状の問題点とは。

6.1 ブラウザは ChaCha20-Poly1305 をどう使う？

TLSで利用する CipherSuite は、TLSのハンドシェイクで決まります。クライアントがハンドシェイクの最初に送信する ClientHello に CipherSuite リストが含まれ、そのリストからサーバが暗号方式を決定し ServerHello で返します。ClientHelloのCipherSuiteのリストは、クライアントが優先して欲しい順番で記載されています。実は ChaCha20-Poly1305の導入に合わせ、Chromeは動作環境によってサーバに送信するCipherSuiteリストを変えるように機能が追加されています。。

Chrome は、端末がAES-NIとAVXをサポートしている時のみChaCha20-Poly1305よりAES-GCMを優先します。

Issue 91913002: net: boost AES-GCM ciphers if the machine has AES-NI.

つまりdefaultは、ChaCha20-Poly1305が最優先で、AES-GCMの性能が高いと判断できるときのみAES-GCMをCipherSuiteのリストの先頭に持ってきています。

Firefoxは、ARM環境の場合の時のみ AES-GCMより ChaCha20-Poly1305を優先させる予定です。

Bug 1126830 - Prioritize ChaCha20/Poly1305 ciphers over AES-GCM for ARM builds

ただこのパッチ、一度 Land されてましたがリリース直前だったため差し戻しを受け、2016/04/04時点でまだ未適応です。

6.2 サーバ側の暗号選択の難しさ

このようにブラウザ側がクライアントの環境に合わせて ChaCha20-Poly1305と AES-GCM のCipherSuiteリストの優先度を変えてTLSのハンドシェイクを開始してくれます。サーバ側はクライアントの環境を直接わからないのでこれは嬉しいことです。

サーバ側はクライアントから送られてくるCipherSuiteリストの順番を見て、単純に優先しているのを決めれば良いかというとそう単純ではありません。通常サーバは、サーバ側のセキュリティポリシーに従い、優先度付きのCipherSuiteリストを保持しています。これと相性が悪いのです。

先ほど述べた通り、TLSのハンドシェイクではサーバはクライアントから送られたCipherSuiteとリストとサーバ側が決めているリストとを比べ、１つの暗号方式を選択します。サーバ・クライアントともに独立して優先度付きリストを持っているので、選択する方法はクライアントの優先度に従うか、サーバの優先度に従うか2通りしかありません。クライアントが常にサーバ側のポリシーにあった正しい優先リストで送られてくるのかわかりません。

一般的なTLSサーバの推奨設定では、サーバ側でセキュリティポリシーで暗号選択を行う設定(Cipher Server Preference)を入れる場合が多いです。

nginxでは、 ssl_prefer_server_ciphers on 、 apacheでは、 SSLHonorCipherOrder on といった設定に該当します。しかしこの場合、 ChaCha20-Poly1305とAES-GCMの選択に問題が生じます。サーバ側の優先度だけで判断してしまうので、せっかくブラウザがクライアント側の環境に応じて変えた暗号方式の優先度情報が生かされなくなってしまいます。サーバが ChaCha20-Poly1305の方を優先する設定にすると、ARMやAES-NIのどちらのクライアントも ChaCha20-Poly1305を選択してしまいます。

6.3 OpenSSL-1.1.0に足りないequal preference cipher groups機能

ではGoogleはどうしているのでしょうか？実は、ChaCha20-Poly1305を実装する際 BoringSSLには equal preference cipher groups機能を実装していました。

Equal preference cipher groups

これは、[]で複数のCipherSuiteをグループ化し、この中の CipherSuiteはクライアントからの優先順に従うというものです。

Googleのサービス GFE(Google Front End)に対して cipher1:cipher2 の2つのリストでどちらが選択されるのか、試してみました。

結果からGoogleは、

[ECDHE-RSA-AES128-GCM-SHA256:ECDHE-RSA-CHACHA20-POLY1305]:ECDHE-RSA-AES128-SHA:ECDHE-RSA-AES256-GCM-SHA384:ECDHE-RSA-AES256-SHA384:ECDHE-RSA-AES128-SHA256:ECDHE-RSA-AES128-SHA256

なリストで運用しているのではないかと予想が付きます。

この equal preference cipher groups機能は便利ですし、是非ChaCha20-Poly1305の導入と共に使いたいところです。

実は、OpenSSLでは今年の1月ぐらいに同様のリクエストが issue で登録されていました。

Support bracketed equal-preference groups in SSL_CTX_set_cipher_list

今回もうすぐOpenSSL-1.1.0がリリースされるので、どうなんだろうと要望を書き加えたところ、OpenSSLチームの一人から「私も欲しいけど、もう時間切れ」とのこと。あぁ OpenSSL-1.1.0はもう feature freeze に入っています。時すでに遅し。パッチ出したとしても1.1.1 以降まで待たないといけないでしょう。

結局今のところ OpenSSLで ChaCha20-Poly1305 をAES-NI/ARMのクライアント環境で共に最適に利用するには Cipher Server Preference を利用しないようにするしかないです。この設定が受け入れられないところも多いでしょうね。うぅ、なんともったいない・・・

ということで、今後普及が見込まれるTLSの新しい暗号方式 ChaCha20-Poly1305 について解説しました。まだまだ課題はありますが、次期TLS1.3では AES-GCMとChaCha20-Poly1305 がMTI(Must To Implement)として規定されています。この2つのデファクトはこれからしばらく続く可能性が高いので、きちんとした理解を持ってより安全なTLSの運用を目指しましょう。

2016-01-13

ハッシュ衝突で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に対する攻撃として、

RSA-MD5が有効になっているエンドポイント間のTLSクライアント認証への攻撃
RSA-MD5が有効になっているTLSサーバ認証への攻撃
TLS1.3のサーバ認証やクライアント認証への攻撃
TLS1.0/1.0のハンドシェイクデータを改ざんして弱い暗号方式にDowngardeする攻撃
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で当てることになりそうです。

2015-08-21

パンドラの箱？TLS鍵交換の落とし穴、KCI攻撃とは何か

TLS

1. 初参加のセキュリティキャンプ

先週ですが、講師としてセキュリティキャンプに初めて参加しました。
担当したのは高レイヤーのセッションで、TLSとHTTP/2の講義を合計6時間、まぁ大変でした。講義の時間配分、分量などの検討が十分でなかったため、本番では事前に準備していた講義内容の一部しかできず、ホント反省しきりです。せめての救いは、今回作った講義資料にたくさんのfavを頂いたことです。ありがとうございました。

講義では、学生の方々が短い時間ながら難しい演習に真面目に取り組んでくれました。質疑なども皆受け答えがしっかりしていて、技術的にもレベルが高い回答も多く、非常に驚きました。これだけ優秀な10代、20代の若者が、全国各地から毎年50人も集まるのを実際に見ると、彼らの将来が楽しみです。これまで10年以上継続してこのような活動を続けきた成果でしょう。私自身、とても良い経験をさせていただきました。セッションオーナーの西村さん、はせがわさん、講義を手伝っていただいたチューター、運営スタッフの方々、本当にありがとうございました。

2. TLSに対するKCI(Key Compromise Impersonation)攻撃とは何か？

講義準備に追われていた8月10日、ワシントンでセキュリティに関するワークショップ USENIX WOOT'15 が開かれていました。
その会議では、一つ面白い発表と論文「Prying Open Pandora's Box: KCI Attacks against TLS （開いたパンドラの箱を覗く： TLSに対するKCI攻撃）」が公開されました。パンドラの箱を覗くとは、何やら意味深なタイトルです。

https://www.usenix.org/conference/woot15/workshop-program/presentation/hlauschek

KCI攻撃は、 Key Compromise Impersonation攻撃の略です。日本語で「危殆化鍵による成りすまし攻撃」と訳すのでしょうか。このKCI攻撃の論文、読んでみるとなかなか非常に面白い。一つ穴を踏ませることに成功すれば、見事にTLSの中間者攻撃が成功します。幸いこの攻撃で使われる機能をサポートしているTLSクライアントが現状少ないため、今のところ世間であまり大騒ぎになっていません（古いMacOSのSafariが影響受けます)。これまで気づかれていなかったTLSの鍵交換仕様のすき間を突いた攻撃であることから、「パンドラの箱を覗く」というタイトルがついたのではないかと個人的に思っています。

この攻撃を理解すると、TLSクライアント認証とはどういうものか、TLS鍵交換とはどういうものなのか、その仕組みが明確になります。そこで今回「SSL/TLSの基礎」講義の補習エントリーとして、このKCI攻撃がどういうものなのか、解説を書いてみたいと思います。

2.1 TLSクライアント認証のしくみ

セキュリティキャンプでの講義「SSL/TLSの基礎と最新動向」では、説明が複雑になるのでTLSクライアント認証は説明の対象外にしていました。

一般的に広く使われているhttpsサーバのTLS通信は、サーバ証明書を使ってTLSサーバの正当性を検証する一方向のものです。この場合、どのクライアントから接続を許すかどうかTLSレイヤーでは認証・認可を行っていません。一方TLSのクライアント認証は、サーバ・クライアント双方向でTLS接続の認証・認可を行う方法です。

TLSクライアント認証は、非常に強力なセキュリティ通信ですが、証明書の発行・更新手続きが煩雑であったり、クライアント環境（OS・ブラウザ）で証明書管理の仕組みが統一されていないなど導入や運用のハードルが高く、現状それほど広く利用されていません。また、TLSの接続途中でクライアント認証に移行するような場合、TLSハンドシェイクのrenegotiationが必要となり、複数のTLS接続を集約するSPDYやHTTP/2の通信とはあまり相性が良くありません。
ただ、SSL3.0からある古い機能であるため、基本的な機能はどのブラウザー環境でも使えるようになっています。

2.2 クライアント認証時のTLSハンドシェイク

通常のサーバ認証だけのTLS通信と、クライアント認証をする通信とではどう違うのでしょうか？
TLSハンドシェイクのシーケンスを見てみると違いがわかります。クライアント認証を行う前提として、TLS通信を行う前にクライアント側に認証局から発行されたクライアント証明書と秘密鍵の鍵ペアがクライアントにインストールされていることが必要です。
クライアント認証時に必要なTLSハンドシェイクメッセージを赤字で示します。

サーバ側は、クライアント証明書が必要であることをCertificateRequestでクライアントに伝えます。クライアントはその要求を受け、自身が持つ証明書をサーバに送信します。さらに送信した証明書が自身が保持する正当なものであることをサーバに示すため、それまでのハンドシェイクデータを秘密鍵で署名し、CertificateVerifyでサーバに送信します。サーバはクライアントの証明書とCertificateVerifyの値を検証し、クライアントが正当な鍵ペアを持つ通信相手であることを確認します。

サーバは、CertificateRequestを使ってクライアントに証明書を要求する際、鍵交換手法に応じて必要な証明書のタイプを指定します。TLS1.2では、図中の表の通り7種類規定されています。今回KCI攻撃で利用されるのは、fixed が含まれる証明書タイプです。このタイプを選択すると、サーバ・クライアント双方の証明書に含まれている(固定的で変わらない）公開鍵を用いて鍵交換を行います。その仕組みの詳細について次節で説明します。

2.3 fixed_ecdhによる鍵交換

前述した通りサーバがfixedタイプのクライアント証明書を要求すると、証明書に記載されている固定の公開鍵を利用して鍵交換(DH/ECDH)を行います。他方、最後にE(Ephemeral:一時的）が付くDHE/ECDHE は、セッション毎に毎回異なる鍵を共有する方式です(PFS:Perfect Forward Securecy)。

論文では、www.facebook.comを使った攻撃が例示されています。そこでfacebookの証明書で公開鍵の情報を見てみましょう。

この赤枠で囲った部分が、証明書の公開鍵の情報を表している部分です。楕円曲線の種類と65バイトの公開鍵情報が書かれています。これを見ると*.facebook.comは、楕円暗号を用いたECDSA証明書です。その公開鍵はECDHの鍵交換で利用可能です。本来この証明書を鍵交換に使うためには、 X509 KeyUsage のフィールドにKeyAgreementフラグが立ってないと使えません。しかし、現実にそこまで厳密にチェックするクライアントは少ないようです。論文では www.facebook.com の証明書にKeyAgreementのフラグが入っているとの指摘がありましたが、今回確認したところこの証明書にはそのフラグはたっていませんでした。

fixed_ecdhによる鍵交換では、下図の通りTLSハンドシェイクの途中で相互の証明書を交換し、証明書に掲載されている公開鍵とそれぞれが持つ秘密鍵を組み合わせて、同一のPreMasterSecretを生成します。

その後、この相互で共有されたPreMasterSecretとClient/ServerHelloで交換した乱数と合わせて、実際のアプリデータを暗号化する共通鍵やMAC、初期ベクトルで利用する鍵を作ります。
このPreMasterSecretをいかに安全に共有できているかが、TLS通信のセキュリティを確保するキモの部分であると言えるでしょう。

3. KCI攻撃の仕組み

KCI(危殆化鍵による成りすまし）攻撃は、文字通り危殆化されたクライアント認証鍵を利用してサーバに成りすまし、中間者攻撃を成功させる方法です。そのステップを見ていきましょう。

攻撃によって成りすましの対象となるサーバは、必ずしもクライアント認証を使っている必要はありません。ただしサーバ証明書はDSA/ECDSA証明書で、クライアント側は fixed の証明書タイプを利用したTLSクライアント認証をサポートしていることが条件です。

そして、悪意のある中間者(Evil)が生成したクライアント証明書を何らかの方法でクライアントにインストールするトラップが必要です（後述）。これが成功した時点で、攻撃者がクライアント証明書の秘密鍵を持っていることになるので、「危殆化された鍵」と名付けられているわけです。

次にステップ毎に見事なKCI攻撃を見ていきます。ここでは論文に合わせて https://www.facebook.com/ サーバを題材にしてみます。4つのステップで攻撃を成功させます。

3.1 攻撃者がサーバ証明書を入手

これは簡単です。公開されているサーバの証明書はTLS接続すればすぐ入手できます。

サーバの秘密鍵は、厳重に守られているので簡単に入手できませんが、今回の攻撃はサーバの秘密鍵が入手できなくても、公開されているサーバ証明書だけで正当なサーバに成りすまして中間者攻撃が成功するものです。

3.2 クライアント証明書の入れ込み

次に攻撃者は、あらかじめ攻撃用のクライアント証明書と秘密鍵のペアを生成しておきます。この証明書は、後で攻撃者が要求するものなので、特に正式な認証局から発行された証明書である必要はありません。ただし後で鍵交換で使うサーバ証明書と同じ形式(DSA/ECDSA)であることが必要です。

この攻撃用のクライアント証明書の鍵ペアを如何にクライアントに意識せずにインストールさせることができるのか、ここがハードル高いステップです。論文では、iOSではメールで簡単にインストールできたり、Androidアプリなどからも比較的容易にインストールできるトラップが紹介されています。クライアント証明書のインストールはあまり普段使わない機能なので、まだまだ未知の穴があるかもしれません。

この仕込みが成功し、中間者攻撃の前までになんらかの方法でクライアント証明書と秘密鍵がクライアントにインストールされていることが攻撃の条件になります。

3.3 正当なサーバに成りすましてTLSハンドシェイク

さぁ、ここから本番です。
クライアントは、攻撃者が作成した不正なクライアント証明書がインストールされているものとは知らず、https://www.facebook.com/にアクセスします。攻撃者はネットワーク経路途中で中間者攻撃を仕掛けます。

まず www.facebook.com に成りすましてTLSハンドシェイクを行います。その際サーバ側がServerHelloで選択する暗号方式は、証明書の固定鍵を使う DH または ECDH の鍵交換を行うものを選択します。後述する通り、DHE/ECDHEではサーバの秘密鍵が必要なため攻撃は成功しません。攻撃者は、事前に入手した www.facebook.com のサーバ証明書を送信し、fixed_ecdhタイプのクライアント証明書を要求します。通常 www.facebook.com はクライアント認証することはありませんが、この時点ではクライアントにはわかりません。

クライアントは、攻撃者からの要求に応じてクライアント証明書を送信し、その秘密鍵で鍵交換を行います。おそらくクライアントは、サーバの秘密鍵を持ってなければこの後のTLSハンドシェイクは失敗するはずだと思い込んでいることでしょう。

3.4 同一PreMasterSecretの生成

ところがどっこい、攻撃者はクライアントの秘密鍵を保持しています。
攻撃者は、クライアント証明書の公開鍵とサーバの秘密鍵を使って鍵交換を行うという真面目なことはせずに、既に保持しているサーバ証明書とクライアントの秘密鍵を使ってクライアントと同じ手順で全く同一のPreMasterSecretを生成します。

クライアントと攻撃者間で同一のPreMasterSecretが共有できていれば、後はいかようにもTLSハンドシェイクを偽造して完了することができます。結果、サーバの秘密鍵を使うことをせずに www.facebook.com の成りすまし、中間者攻撃に成功です。

いやぁー、見事できれいです。
前述の通り、危殆化されているクライアント証明書の鍵ペアをどういうトラップでクライアントに入れ込むかというのが課題ですが、TLSの鍵交換しているようでしていない、PreMasterSecretさえ共有できちゃえば勝ちというKCI攻撃の手法は、ホント目から鱗でした。

幸い fixed_ecdh/dhに対応したクライアントが現状ほとんどないので、この攻撃は現状それほど脅威として騒がれていません。論文では、Mac OS X 10.5.3 以前のSafariで攻撃に成功したと報告されていますが、現在は機能が無効化されています。しかし論文ではこの攻撃が知られていないと将来的に実装されて危なくなると警告しています。本当は攻撃を再現した状況を実際に試して載せたかったのですが、攻撃の影響を受けるクライアントが手元になく残念です。今後このような合わせ技攻撃の組み合わせによって思いっきりTLSの穴ができるような別の攻撃手法が出てくるかもしれません。

4. TLS1.3ではどうなる？

講義でも後半触れましたが、現在仕様策定中のTLS1.3ではどうなるでしょうか？

まず鍵交換は、一時鍵を使うDHE/ECDHEのPFSしかサポートされないのでKCI攻撃は無理です。PFSでは、ServerKeyExchangeで送信する公開鍵にサーバが署名するのでサーバの秘密鍵がないと署名検証でクライアントに攻撃がばれます。

またTLS1.3ではサーバ側も常に CertificateVerifyを送る Server Sign の要件が新たに入る予定です。これによって、ハンドシェイク途中でサーバ証明書の鍵ペア所有の検証が行われることになり、サーバの秘密鍵なしに中間者攻撃が成立するといった類似の攻撃がTLS1.2より困難になるでしょう。

個人的には、総当たりっぽく平文を判定するOracle攻撃なんかより、このような一つのほころびで全体のセキュリティを台無しにさせるこのKCI攻撃手法は、ある意味美しさを感じてしまいます。これで皆さんのTLSクライアント認証と鍵交換の仕組みの理解が少しでも深まれば幸いです。

5. 明日は YAPC

TLSとは全然関係ないですが、明日(8/22) YAPC Asia Tokyo 2015で「どうしてこうなった？ Node.jsとio.jsの分裂と統合の行方。これからどう進化していくのか？」のセッションの後半で古川さんと対談します。この半年余り、Node.jsプロジェクトの分裂と統合という流れの真っただ中にいた身として、今回の騒動でオープンソースのガバナンスの姿、その一つの形が見えてきた気がします。なかなか経験できない貴重な体験を皆さんにお伝えできたらと思っています。朝10時からと若干早い時間からのスタートですが、皆さんの参加をお待ちしています。

以上、セキュリティキャンプの補習講義でした。

0. Disclaimer

1. 外部公開されている情報からの事実認定

1.1： 2015/9/30 09:15 GMT (18:15 JST)

1.2： 2016/7/7 2:05 GMT (11:05 JST)

1.3： 2016/7/22 3:00 GMT (12:00JST)

1.4： 2016/7/23 9:19 JST

1.5： 2016/7/23 10:49(JST)

1.6： 2016/7/24 11:06 GMT (20:06 JST)

2. CT(Certificate Transparency)対応EV証明書発行の流れ

3. 障害発生原因の推測

3.1 ２つのミスが重なったのか？

3.2 Certificate Transparency の闇(プレ証明書)

0. 短いまとめ

1. はじめに

2. TLSクライアント認証をバイパスするapache-2.4の脆弱性(CVE-2016-4979)とは？

3. HTTP/2のTLSクライアント認証の課題

4. HTTP/2接続後のTLSクライアント認証

5. CVE-2016-4979の原因

6. Secondary Certificate Authentication in HTTP/2

Disclaimer

0. 短いまとめ

1. はじめに

2. 実は危ないTLS1.2のAES-GCM

2.1 TLS1.2のAES-GCM

2.2 TLS1.2のGCMのMAC(タグ値)の求め方

2.3 IVの再利用はGCMの安全性に致命的

3. 現実のHTTPSサーバへの調査

3.1 AES-GCMの実装上の問題に起因するIVの再利用

3.2 TLSのプロトコル仕様に起因する実装の問題

4. Nonce再利用の脆弱性をついたMiTM攻撃を試してみる

4.1 IVの収集

4.2 再利用されたIVの発見

4.3 GHASHのMAC鍵Hの計算

4.4 HTTPSサーバのコンテンツの改ざん

4.5 実際にやってみた。

5. IVを再利用させない対策は？

5.1 AES-GCM-SIV

5.2 暗黙的に両者で共有するIV(ChaCha20-Poly1305の方式)

6. 今年のセキュリティ・キャンプはChaCha20-Poly1305

Disclaimer

0. 短いまとめ

1. TLSに新しい暗号方式が必要となった背景

1.1 AESがTLSのSPOFになっている

1.2 AES-NIのないARM環境でも安全で高速な暗号が欲しい

1.3 新しい暗号方式 ChaCha20-Poly1305 の導入

1.4 ChaCha20-Poly1305のこれまでの歩み

1.5 TLSで使えるChaCha20-Poly1305の種類

2. ChaCha20とは何か?

2.1 AESとChaCha20の比較

2.2 ChaCha 1/4ラウンド演算

2.3 2種類のChaChaラウンド

2.4 ChaCha20 Stream State

2.5 ChaCha20による平文の暗号化

3. Poly1305とは何か?

3.1 GHASHとPoly1305の比較

3.2 Polynomial evalation(多項式評価)

3.3 Wegman-Carter Construction

3.4 Poly1305のアルゴリズム

4. ChaCha20-Poly1305とは何か?

4.1 AES-GCMとChaCha20-Poly1305の比較

4.2 ChaCha20-Poly1305のAEAD処理フロー

4.3 ChaCha20-Poly1305とAES-GCMのサイズ

5. ChaCha20-Poly1305 vs AES-GCMの性能比較

6. TLSの運用はどうなる？ 現状の問題点とは。

6.1 ブラウザは ChaCha20-Poly1305 をどう使う？

6.2 サーバ側の暗号選択の難しさ

6.3 OpenSSL-1.1.0に足りないequal preference cipher groups機能

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

1. SLOTHとは何か？

2. Chosen-Prefix 衝突とは？

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

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

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

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

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

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

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

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

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

5. 危なかったTLS1.3

6. TLSの運用はどうなる？現状の問題点とは。