Hatena::ブログ(Diary)

ぼちぼち日記

2016-08-04

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2016-07-29

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

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証明書から残り1年で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期限です。3ヶ月弱有効のもの。

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で報告


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に該当します。
f:id:jovi0608:20160729154144p:image:w640
これを見ると、EV対応によって認証局内部の証明書発行業務も従来のフローから変更せざる得なかったのではないかと思われます。

3. 障害発生原因の推測

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

3.1 2つのミスが重なったのか?

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

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

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

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

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

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

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

もし今回の障害がCT対応証明書の発行処理際のプレ証明書の扱いに関連するのであれば、漆嶌さんが見事に予想されていました。
f:id:jovi0608:20160729154145p:image:w640
(漆嶌さんのスライドより引用)
現実的にCTによって誤発行の発見などブラウザベンダ側にメリットをもたらしましたが、その副作用で別のリスクが増えてしまったのはなんとも残念です。

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




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

2016-07-06

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

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 へのリンクが貼ってあります 。
f:id:jovi0608:20160706182052p:image:w640
リンクを辿って /client_auth にアクセスするとFirefoxにクライアント証明書を全く入れてないのでエラーになります。クライアント認証はちゃんと効いています。
f:id:jovi0608:20160706182051p:image:w640
せっかく再試行ボタンが見えているので、再読み込みしてみましょう。
f:id:jovi0608:20160706182050p:image:w640
あらー、/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接続を共有しているので困ってしまいます。
f:id:jovi0608:20160706182047p:image:w640
HTTP/2上でHTTP/1.1と同じように renegotiation を行うと、クライアント認証が必要のないリクエストまで巻き添えを食らってしまいます。

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

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

このままではHTTP/2を使うとWebのリソースの一部をクライアント認証することができずに困ってしまいます。そこで、あまりスマートなやり方ではありませんが、クライアント認証が必要なリクエストをHTTP/1.1に逃がすことでまぁなんとか対応可能に落とし込みました。
f:id:jovi0608:20160706182048p:image:w640
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の青い稲妻状態でアクセスできていることからもわかります。
f:id:jovi0608:20160706182049p:image:w640
先の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の2つのドラフトが提出されていましたが、先の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. 短いまとめ

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

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

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

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

  4. 今年の夏のセキュリティ・キャンプ全国大会では、「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は次のようなフレームで生成されます。
f:id:jovi0608:20160524033037j:image:w640
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の共通鍵を使って2つ鍵HとSを使って計算します。
f:id:jovi0608:20160524103103j:image:w640
GCMの安全性は、この2つの鍵(HとS)によって担保されます。すなわちAESが破られない限りGCMは十分安全です。

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

もし同じIVを持つ2つのAES-GCMのAEADデータがあったらどうなるでしょうか? 両者のデータをXORすれば、鍵Sのマスク効果は消えてしまいます。
f:id:jovi0608:20160524103104j:image:w640
結果、鍵Hだけの1変数剰余多項式になり、因数分解によって解を求めることができます。一般的に複数の解を持ちますが、鍵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のプロトコル仕様に起因する実装の問題

さらなる調査結果から、7万以上のサーバが乱数を使って初期ベクトルを毎回生成しているのがわかりました。この方式では、大量のデータの通信を行うと過去使った乱数値と同じ乱数を生成してしまう確率が格段に上昇します。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が再利用されるまで待ち続けます。
f:id:jovi0608:20160524033038j:image:w640

4.2 再利用されたIVの発見

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

4.3 GHASHのMAC鍵Hの計算

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

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

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

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

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

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

4.5 実際にやってみた。

実際にPoCコードを試してみました。自前のTLS実装を細工して同一IVを送信するように変更します。中間者攻撃を担うGoで書か れた gcmproxy は port 8443から443へのTCPリレーを行います。ここでIVや他のTLSのデータを収集し、同一のものが見つかれば NTL(Number Theory Library)を使って鍵Hを求め、偽造したデータのタグ値を再計算します。通常鍵Hは複数候補が見つかるの で1発で成功することはなかなかないのですが、何回か繰り返すと成功しました。
f:id:jovi0608:20160524033042j:image:w640
この画像のようにブラウザ上の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を生成しているのか見てみます。
f:id:jovi0608:20160524033043j:image:w640
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(月)まで、興味のある方の応募を待っています。

2016-04-04

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

f:id:jovi0608:20160404114901p:image:w240

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. 短いまとめ

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

  1. 新しいTLSの暗号方式 ChaCha20-Poly1305 が仕様化されます。
  2. 新仕様版はChrome49/Firefox47/OpenSSL-1.1.0(beta)などで既に利用可能です。
  3. AES-GCMより転送サイズが小さくなり、AES-NIのないARM環境では3倍程度性能が高くなります。
  4. 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 さんより情報を頂きました。ありがとうございます。




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のこれまでの歩みをざっと表にしました。
f:id:jovi0608:20160404114842p:image:w640
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仕様化されるのは以下の7つの 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認証の2つ、残る1つはDHE/RSAのものです。master secretを生成するPRFにはすべてSHA256を利用します。個人的には Chrome49, Firefox47, OpenSSL-1.1.0-beta1 で既に実装されていること確認していますが、LibreSSLやその他のTLS実装はどの程度対応しているのかまで見ていません。各実装がサポートしているCipherSuiteを表の2カラム目(O, F, C)として記載しておきます。

2. ChaCha20とは何か?

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

2.1 AESとChaCha20の比較

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

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

2.3 2種類のChaChaラウンド

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

2.4 ChaCha20 Stream State

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

次にChaCha20の鍵データ、32バイトが続きます。その後に通常1から始まるカウンター値、12バイトのNonceが入ります。これを 列ラウンド+対角ラウンドの演算を10回繰り返します。結果1/4ラウンドを20回繰り返すことから ChaCha20 ということになります。20はラウンド数を表しています。
f:id:jovi0608:20160404114846p:image:w640
ChaCha20は、20ラウンドの演算を経て最終的に生成した ChaCha20 State を使って平文から暗号文を生成します。

2.5 ChaCha20による平文の暗号化

平文から暗号文の生成は簡単です。平文を64バイトのブロックに分割します。それぞれのブロックに対してカウンター値を上げながら、それぞれのChaCha20 Stateを計算します。出来上がった ChaCha20 State と64バイトブロックの平文との XOR をとり、暗号文を作ります。
f:id:jovi0608:20160404114847p:image:w640
暗号文から平文に戻す手順もほぼ 同一手順です。同じ鍵, Nonce, カウンター値からChaCha20 Stateを作り、暗号文とXORを作れば平文が生成できます。このようにChaCha20ではEncrypt/Decrypt が全く同じ処理でできます。これはソフトウェア処理がシンプルになる大きなメリットです。

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

3. Poly1305とは何か?

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

3.1 GHASHとPoly1305の比較

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

仕様的にGHASHは明示的な鍵長制限を持ってなさそうですが(間違っていたら誰か教えて下さい)、AESと組み合わせたAES-GCMの場合は、128bitsの鍵を利用 します。Poly1305は、256bit長の鍵を使います。後で説明しますが、256bit長の鍵を2つの鍵に分割して利用します。
GHASHとPoly1305、ともに生成するMACデータ長はどちらも128bitsです。ただしGHASHの方は、用途に合わせて小さく切り詰めて利用され、AES-GCMでは96bit128bit長にしています。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次の定数項がないのが特徴です。もし定数項があるとメッセージ評価値の差分を取ることによって鍵情報が部分的に漏洩してしまうからです。多項式評価を使うメリットは、ホーナー法によって高次の乗算計算を減らして加算の再帰として計算できるからです。ホーナー法を 利用することによって高次の事前計算を避けることができ、ソフトウェア実装がし易くなっています。
f:id:jovi0608:20160404114849p:image:w640

3.3 Wegman-Carter Construction

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

3.4 Poly1305のアルゴリズム

Poly1305のアルゴリズムも単純です。tweet(140字以内)で表現可能といわれるぐらいです。
f:id:jovi0608:20160404114851p:image:w640
Poly1305のMAC計算は、認証するデータを16バイト長で分割し、頭に0x01を付加して17バイト長のブロックにします。16バイトに満たないブロックは頭に0x01をつけた後0パディングして17バイト長に揃えます。

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

f:id:jovi0608:20160516130128j:image:w640
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として利用します。こうすることによって、わざわざ8 バイトのIVを明示的に送信することがなくなり、その分通信データ量を削減することができます。またバグなどでIVが再利用されてしまうといった間違いも避けることができるので、より安全な実装になることが期待されています。

4.2 ChaCha20-Poly1305のAEAD処理フロー

AES-GCM仕様のフローに似せてChaCha20-Poly1305によるAEAD生成(暗号化)のフローを書くとこのようになります。
f:id:jovi0608:20160404114854p:image:w640
初期カウンター0でPoly1305用の鍵(r,s)を作り、初期カウンター1に増加させてChaCha20 Key Streamを生成し、平文から暗号文に変換させます。
認証を行うデータと暗号文それぞれを0でパディングして16バイト長に揃えます。平文(8バイト長)と暗号文の長さ(8バイト長)を結合して、全体のデ ータのMACをPoly1305で計算し、128bitのMACデータ(認証タグ)を取得します。TLS1.2では認証を行うデータは、TLSレコード層のデータとシーケンス番号を合わせたデータです。最後に暗号文に認証タグをつけて暗号化されたTLSのアプリケーションデータとして相手に送信します。

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

AES-GCMとChaCha20-Poly1305で1バイトの平文をAEADで暗号化した場合の比較をしてみましょう。
f:id:jovi0608:20160516130129j:image:w640
どちらもストリーム暗号として機能するので暗号文は1バイトです。タグのサイズは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上での比較から。
f:id:jovi0608:20160404114859p:image:w640
うん、AES-GCMはやっぱり速いです。3.1Gbpsのスループットを叩き出しています。ChaCha20-Poly1305はAES-GCMのおよそ半分 1.6Gbpsのスループットがでます。逆にいうとAES-NIという強力なハード処理の助けがなくてもここまで性能が出せるのは健闘でしょう。

ARM上ではどうなる?
f:id:jovi0608:20160404114900p:image:w640
おぉ! 確かに 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とリストとサーバ側が決めているリストとを比べ、1つの暗 号方式を選択します。サーバ・クライアントともに独立して優先度付きリストを持っているので、選択する方法はクライアントの優先度に従うか、サーバ の優先度に従うか2通りしかありません。クライアントが常にサーバ側のポリシーにあった正しい優先リストで送られてくるのかわかりません 。
f:id:jovi0608:20160404114856p:image:w640
一般的なTLSサーバの推奨設定では、サーバ側でセキュリティポリシーで暗号選択を行う設定(Cipher Server Preference)を入れる場合が多いです。

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

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つのリストでどちらが選択されるのか、試してみました。
f:id:jovi0608:20160404142953j:image:w640
結果から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の導入と共に使いたいところです。
f:id:jovi0608:20160404114858p:image:w640
実は、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の運用を目指しましょう。