ハクソク

世界を動かす技術を、日本語で。

インターネットを迅速かつ安全に保つ：マークルツリー証明書の導入

209日前原文(blog.cloudflare.com)

概要

  • 量子コンピュータの登場による既存暗号の脆弱化リスク
  • CloudflareによるPost-Quantum（PQ）暗号への移行推進
  • WebPKIの複雑さとPQ証明書導入時のパフォーマンス課題
  • Merkle Tree Certificates（MTCs）による効率的なPQ認証提案
  • 実験的導入とChrome Securityとの協業

量子コンピュータ時代のインターネット暗号課題

  • 量子コンピュータは 従来の暗号方式 を突破可能な計算能力を持つ脅威
  • 「 今収集し、後で解読 （harvest now, decrypt later）」攻撃への対応が急務
  • Cloudflareは トラフィックの約50% をPQ暗号で保護
  • TLS証明書自体も量子耐性が必要となる新たな課題
  • PQ署名と公開鍵のサイズが 従来の約20倍 に増大し、TLSパフォーマンスに深刻な影響

WebPKIの現状と課題

  • クライアントはサーバ公開鍵を事前に知ることが非現実的なため 証明書 を利用
  • 証明書は CA（認証局） によって発行され、信頼の連鎖を形成
  • WebPKIの進化により、TLSハンドシェイクで 複数の署名・公開鍵 が必要
    • 例：サーバ署名、証明書署名、CAキー更新用証明書、Certificate Transparency署名等
    • 一般的なTLSハンドシェイクでは 5つの署名と2つの公開鍵 が含まれる

Post-Quantum証明書導入の難しさ

  • PQ証明書は Q-day（量子コンピュータ到来日） 以前はセキュリティ向上効果が限定的
  • しかし、証明書サイズ増大により パフォーマンス劣化 が顕著
  • 移行には WebPKI全体の設計見直し が不可欠

Merkle Tree Certificates（MTCs）による新提案

  • MTCsは TLSハンドシェイクで必要な署名・公開鍵数を最小化 する仕組み

  • クライアントが最新情報を保持していれば、 1つの署名・公開鍵・Merkle tree証明 のみで検証可能

  • 各CAが自身の発行証明書ログを管理し、 Certificate Transparency を標準機能化

  • PQアルゴリズム利用時でも 通信コストを大幅削減 可能

    • MTCの例：PEM形式証明書にMerkle tree情報を組み込み
    • opensslなどで デコード・検証 が容易

実験的導入と今後の展望

  • Cloudflareは Chrome Security と協力し、MTCsを実験導入予定
  • 実験を通じて パフォーマンス・安全性・実装課題 を検証
  • 量子耐性WebPKIへの 円滑な移行計画 策定を目指す

まとめ：次世代WebPKIへの道

  • 量子時代に向けて WebPKIの根本的刷新 が必要
  • MTCsなどの新技術で パフォーマンスとセキュリティの両立 を追求
  • 早期実験と業界連携による 安全なインターネットの持続的確保

Hackerたちの意見

来週のIETF 124では、標準化プロセスを始めるためのBirds-of-a-Featherセッションがあるよ。Merkle Tree Certificatesは有望な選択肢だと思う。私も標準化の取り組みに参加する予定。Chromeは、いくつかの場面でこれがポスト量子証明書の好ましい（または唯一の）選択肢になると予想しているって言ってるから、今後数年でこれを導入する可能性はかなり高いと思う。私はLet's Encryptで働いてるけど、これは公式な声明や実装の約束じゃないからね。それについてはニュースレターを購読してね :)

Merkle Tree Certificateを検証するためにクライアントが必要な情報は、バンド外で配信できる。この記事では触れてなかったけど、素朴に考えるとプライバシーの問題になりそうじゃない？

└

Cloudflareがプライバシーの問題について語るなんて、ありえないよね。;-)

└

なんとなくね。基本的に各CAはこれを運用することになる。信頼する側（ブラウザ）は、ユーザーが閲覧するサイトの証明書に署名するCAのメルクルツリーのヘッダーを定期的に取得する必要があるんだ。もしかしたら、訪問したサイトの証明書に署名するCAだけじゃなくて、WebPKIの全CAから取得することになるかも。全体で約100のCAがあるから、例えばブラウザが5つのCA、あるいは1つのCAのMTヘッダーを取得したとしても、ユーザーが訪れている特定のサイトについてはあまり情報が漏れないと思う。ただ、もしユーザーが中国のサイトだけを訪れているなら、CNのMTヘッダーだけを取得するのが見えるかもしれない。そうなると「お、これは中国のユーザーだな」って思うかもしれないけど…それでも漏れる情報は少ないし、あまり役に立たないよね。

└

ブラウザやOSからのThe Approved Set™を使うことにはプライバシーの問題はないよ：それはただ、あなたのマシンが定期的に他の人と一緒に母艦からダウンロードするちょっとしたデータに過ぎないから。そこであなたを他の誰かと区別するものはないよ。あなたのマシンが信頼するものに含めるために、The Approved Set™外のCAからランドマークを取得したいかもしれないけど、そうなると定期的に他の場所からデータが必要になるね。どこから何を取得するかに関する通常のプライバシーの懸念は適用されるよ。ウェブ取引を行っている場合、第三者があなたのDNSルックアップやポート443への接続、交換するトラフィックの量を見ることができるかもしれないけど、あなたが何をリクエストしたかや、何を受け取ったかは見えないはず。あなたのOSやブラウザは普通にあなたを密告することができるけどね。新しいプライバシーの脅威は特に見当たらないけど、すべての角度を考慮していないかもしれないな。

└

SNIとOCSPの間で、TLSは訪問するウェブサイトを覗き見から隠すことに関しては決して関係ありません。

除外証明についてのセクションが欠けてるし、クライアントが具体的に何を受け取るのかも不明だね。私の理解が正しければ、各CAは一定の間隔（週ごと）でランドマークの署名リストを公開するんだよね。証明書を取得すると、ランドマーク（256ビットのハッシュ）と、葉証明書のハッシュまでのメルクルパスのハッシュを受け取ることになる。N個の証明書を含むランドマークの場合、log2(N) * hash_lenバイトを含めて、log2(N)回のハッシュ計算を行う必要がある。256ビットのハッシュを使ってN=100万のMTC署名だと、だいたい20*32=620バイトくらいになる。これが要点かな？最適なランドマークサイズと公開間隔を決めるための数学にすごく興味があるんだ。

└

そうだね。RFCドラフトから: > 新しいランドマークが毎時間割り当てられると、署名なしの証明書サブツリーは約4,400,000の証明書を含むことになり、包含証明には23のハッシュが必要で、包含証明のサイズは736バイトになる。署名はなし。 https://davidben.github.io/merkle-tree-certs/draft-davidben-... これは、ランドマークごとに440万の証明書を想定していて、あなたの見積もりよりちょっと大きいね。最新のランドマークを持っていないクライアント向けには署名を含む「フル証明書」もあるよ。それはまだ大きいけど、たまに「curl」コマンドを使うだけなら、多くのクライアントにとっては大したことじゃないよ。

MTCは、証明書に署名するための新しい署名アルゴリズムとして説明するのが一番いいと思う。そこに価値があるのはメルクルツリーの包含証明だね。これはかなり賢いアイデアだと思う。好きだな。

TLSハンドシェイク中、クライアントはサーバーに自分が持っているツリーヘッドを伝えます。TLS経由で接続するすべてのサーバーに、最近（またはそうでない）MTCツリーヘッドを取得したことで私をフィンガープリンティングできる能力を与えるのはあまり好きじゃないです。特にクライアントハローにこれが含まれている場合、ネットワーク経路上の誰でも接続ごとに、または私のDoHリクエストを通じて暗号化されたクライアントハローをブートストラップするために見ることができるのはさらに悪いです。

TLSハンドシェイク中、クライアントはサーバーに自分が持っているツリーヘッドを伝えます。クライアントが最初にサーバーの証明書がどのルートにチェーンされるかを知らない場合、サーバーに自分のツリーヘッドを伝えないことになります。そうすると、クライアントはフル証明書を取得し、それをキャッシュして後の接続のために覚えておくことができます。これでも動くかもしれませんが、少しメタデータが漏れることになります。代わりに、クライアントが信頼するすべてのルートのツリーヘッドを送信することもできます。それだとClientHelloが膨れ上がってしまいますし、CA/ブラウザフォーラムやChromeルートプログラムによって認められたすべてのルートを信頼すると主張する以外のことをしない限り、少しメタデータが漏れることになります。

ちょっとざっくりとメモを取って、言葉を減らしました。この提案は、証明書機関のようなWebPKIにPQ証明書を導入することです。問題はPQ署名が大きいことです。証明書チェーンが小さい場合は許容できるかもしれませんが、チェーンが大きいと、TLSハンドシェイク中の帯域幅や計算において高コストになります。つまり、多くの証明書を送信し、それには署名と大きな（PQ）公開鍵が埋め込まれています。Merkle Tree Certificatesは、最新のクライアントが1つの署名、1つの公開鍵、1つのMerkleツリーの証人だけで済むことを保証します。MTC生成の証明書を見ると、従来の署名アルゴリズムと署名が証人に置き換えられています。つまり、クライアントが必要なのは、MTCA（Merkle Tree CA）によって署名された拡張Merkle Treeからの署名されたMerkleルートだけです。これは何らかの方法でバンド外で配信されます。要するに、TLSクライアントは新しい署名アルゴリズムを含む証明書を受け取ります。これは署名の代わりに証人を埋め込んでいます。ルートは（ハッシュか署名されたハッシュかはわかりませんが、前者だと思います）です。クライアントはバンド外で署名されたルートを受け取り、事前に検証できます。つまり、証人を検証するのは単に証人をチェックすることです。編集：私の質問は、これは本当に対処すべき懸念ですか？TLSキー交換のためのPQは、HNDL（Harvest Now Decrypt Later）という差し迫った脅威に対処します。少なくとも今のところ、WebPKIがPQ署名を使う必要があるとは思えません。

└

IPv6がこの標準化を完了し、インターネットやIoTのほとんどの部分に展開されるまでに時間がかかるかもしれません。2050年に最後の非PQ安全なTLSデバイスをシャットダウンできるようにしたいなら、今やった方がいいかもしれませんね。

量子コンピュータが現代の暗号を破るとは考えられない理由はありません。ショアのアルゴリズムは、因数分解する整数に量子フーリエ変換を適用する必要があります。QFTは、通常のバイナリを反映した表現を持つ量子データを取り、それを量子位相（角度）で情報をエンコードする表現にマッピングします。正確なQFTを実行するために必要な位相の精度は、変換しようとしているキュービットの数に対して指数関数的にスケールします。私の鍵を因数分解できる量子コンピュータを開発できた？いいよ、鍵の長さに11ビット追加するから、2000倍の位相精度を持つコンピュータを開発したら戻ってきて。

└

あなたに同意しますが、少なくともハイブリッドアルゴリズムを推進する理由はよくわかります。量子コンピュータがどのように実際にスケールするかはまだわからないですからね。既存の暗号システムを物理的な理由で破ることが本当に不可能であると確信できるまで、追加のセキュリティ層を提供するハイブリッドシステムを使うのは明らかに良い実践のように思えます。

└

規制当局は量子安全なアルゴリズムへの移行を求めています。EUでは、「非常に重要」とラベル付けされたシステムは2030年までに移行を完了しなければならないので、量子コンピュータがどのように進化するかに関係なく、実施する必要があります。

└

いいよ、鍵の長さに11ビット追加するよ。2000倍の位相精度を持つコンピュータが開発されたら戻ってきてね。実はこれが本当じゃないっていうのが本当に変なんだ。すでに量子コンピュータのO(1)エラーをO(exp(-k))エラーに修正できる量子誤り訂正の仕組みがあって、ポリログ(k)の不正確なキュービットでエラーを修正できるっていう実証もあるんだよ。鍵に11ビット追加すると、約12の論理キュービット、または約100の物理キュービットが量子コンピュータに追加されることになる。

└

量子コンピュータが現代の暗号を破る理由はないよ。誰もそれを必要としていない。5つの目はすでにルート証明書やインターネットノードにアクセスできるから。大事なのは、あなたが安全で、テロリストや児童ポルノ犯が何もできないことだよ。理論上はね。 /s

ブラウザベンダーがTLSエコシステムの重要な部分になっていくのが心配だよね。最初はCRLブルームフィルター、今は署名付きマークルツリー。もちろん、彼らはルートストアも管理してるし。常に更新されるエバーグリーンブラウザを使ってるなら便利だけど、他の人たちはどうすればいいの？CurlやカスタムアプリケーションのHTTPライブラリでどう使うの？メールクライアントは？埋め込みデバイスで使えるのかすら怪しいよ。「インターネット」は「Google Chromeのあるウェブサイト」よりずっと大きいから、他の使い方を不可能にしないように気をつけないと。

└

主要なOS（WindowsやMacなど）には「プラットフォームバリファイア」があって、これが一部を処理できるんだ。バンド外データの取得や共有も含めてね。ブラウザに縛られる必要はないと思う。Linuxも多分必要だろうけど、誰がその取り組みをリードするのかは分からない。その間、ブラウザはOSが整うのを待ってくれないし、それは妥当だよ。規制やユーザー（特に企業や政府）がポスト量子ソリューションを早く求めてるから、実際に展開できるソリューションを探してるんだ。ブラウザはこの分野で常にリードしてきたし、最初にSSLを導入したのもNetscapeだった。

ウェブPKIを完全に廃止することもできるんじゃない？でもTLSには公開鍵が必要だよね？じゃあ、それをDNSに入れればいいじゃん！DNSレスポンスがDNSSECで検証されていると仮定すれば、さらに安全になるよ。IPハイジャックやサーバーサイドのAitM、CAの妥協からたくさんの攻撃ベクターを閉じることができる。実際、最初からCAを使う必要もなくなる。信頼のチェーンは、レジストラからウェブサーバーに直接つながるようになるんだ。 （もしレジストラやウェブサーバーがハッキングされたら、もっと大きな問題になるけど…）