RFC 9162: Certificate Transparency v2 証明の作成と検証の効率性

201x 年前半に認証局 (CA) の不正な証明書発行事件が相次ぎました。特に 2011 年にオランダの認証局 DigiNotar が攻撃を受けて大量の証明書を不正に発行した事件ではインターネットの信頼を大きく揺るがす脅威でした。これらの事件を受けて、2013 年に Google が CT (Certificate Transparency) ^[1] と呼ばれる、クライアントや監査者が発行された証明書を検証できるプロトコルを提案しました。

導入

CT は TLS サーバ証明書が発行されたり観測されたときに、その存在を公的に記録するために Google が開発したプロトコルです。これにより、誰でも認証局の活動を監査し、疑わしい証明書の発行に気づけるようにすることを目的としています。CT はマークルツリー (Merkle Tree) ^[2] 構造を動的に追記専用 (append-only) にしたバリアントである履歴ツリー (History Tree) ^[3] を実用的に定義して RFC として仕様化したものです。この構造により、特定の時点のログインスタンスが、以前のインスタンスを完全に含んでいることや、ログを管理するサーバの不正行為を効率的かつ暗号学的に安全に検出できます。

履歴ツリーおよび CT は効率的な監査に必要な 2 種類の証明を提供します。一つは特定のログエントリ (葉ノード) がツリーに含まれていることを証明する所属証明 (membership proof) または包含証明 (inclusion proof) です。もう一つは、ある時点の全ログエントリがそれ以降のツリーに完全に含まれている増分証明 (incremental proof) または一貫性証明 (consistency proof) と呼ばれるものです。所属証明は静的なマークルツリーの文脈では認証パス (authentication path) とも呼ばれます。

ハッシュ値の算出方法

$n$ 個のログエントリ (葉ノード) を持つツリーを想定し、ツリーに含まれる $0$ から $n-1$ までのデータ列を $D_{0:n}=\{d_0,d_1,\ldots,d_{n-1}\}$ と表記します。暗号学的ハッシュ関数を $h$ としたとき、このデータ列で構成されるツリーのルートハッシュは以下のように算出されます。

$$r(D_{0:n}) = \begin{cases} h() & \text{if } n = 0 \\ h({\tt 0x00} \parallel d_0) & \text{if } n = 1 \\ h({\tt 0x01} \parallel r(D_{0:k}) \parallel r(D_{k:n})) & \text{if } n > 1 \end{cases}$$

ここで $k$ は $k \lt n \le 2k$ を満たす最大の 2 のべき乗です (ビット演算を使って $k=1 {\tt \lt\lt} ({\rm bit\_length}(n-1)-1)$ とも書けます)。

この CT での記述はプログラミング言語の再帰呼び出しで部分配列 (スライス) を渡すことを意図した書き方となっていることに注意。再帰呼び出しの過程で暗黙的に $D_{i:j} \to D_{0:j-i}$ と置き換わります (つまり $n$ は常に再帰関数に渡された $D$ の部分配列の長さ $|D|$ を意味しています)。擬似コードで表すと以下のようになります。

${\bf function} \ r(D:{\rm Array}) \to {\rm Hash}$
$\hspace{14pt}{\bf if} \ |D| = 0 \ {\bf then} \ {\bf return} \ h()$
$\hspace{14pt}{\bf if} \ |D| = 1 \ {\bf then} \ {\bf return} \ h({\tt 0x00}\parallel D[0])$
$\hspace{14pt}k := \left\lceil\frac{|D|}{2}\right\rceil$
$\hspace{14pt}{\bf return} \ h({\tt 0x01}\parallel r(D[0:k])\parallel r(D[k:|D|]))$

ハッシュ関数の入力に追加されている 0x00 (葉ノード) と 0x01 (中間ノード) は第二原像攻撃への耐性を目的としたドメイン分離です。ある中間ノードのハッシュ値を $h({\rm lhash}\parallel{\rm rhash})$ のように算出すると、ログエントリ $d={\rm lhash}\parallel{\rm rhash}$ を追加することで、その中間ノードと同一のハッシュ値を持つ葉ノードを容易に発生させることができます。中間ノードと葉ノードのハッシュ値が衝突すると、攻撃者 (この場合サーバ) がログエントリ $d$ を変更したり削除しても、衝突した中間ノードへの所属証明をクライアントに提供し続けるすることで、あたかも $d$ が依然としてツリー内に存在しているかのようにクライアントや監査者を騙すことができます。

所属証明

所属証明 (membership proof) は特定のログエントリがサーバの管理するマークルツリーに含まれていることをクライアント側で検証できるようにするための小さなデータです。マークルツリーでは認証パス (authentication path)、CT のではマークル包含証明 (Merkle inclusion proof) と知られているものであり、その操作は CT や履歴ツリーの文脈に限らず一般的な静的マークルツリーでも使われている手法と同じです。

所属証明は、ある時点でマークルツリーのルートノードから特定の葉ノードへの検証可能な経路が存在し、葉ノードに対応するログエントリがルートハッシュによって固定されていることを検証できるようにします。所属証明 $\pi$ の実体は、ルートノードから目的の葉ノードまでの経路から枝分かれした中間ノードの集合です。したがって、その空間計算量/時間計算量は $O(\log N)$ と小さなものです。

ここで、サーバが $n$ 個のログエントリを含むマークルツリー $T_n$ を保持しており、クライアントは $T_n$ の検証済みルートハッシュ $r_n$ と (真偽が確かでない) ログエントリ $m$ を保持していると仮定します。クライアントは、サーバに要求して得た $m$ の所属証明 $\pi_m$ を使って、ログエントリ $m$ から検証済みルートハッシュ $r_n$ を算出できるかを確認します。算出したハッシュ値が一致した場合、クライアントが保持しているデータエントリ $m$ はサーバの管理しているマークルツリーに含まれていることが暗号論的に証明されたことになります。

所属証明の作成

所属証明は、ルートノードから目的の葉ノードまでを再帰的に探索し、その経路の左右に存在する中間ノードを収集することで行われます (経路上の中間ノードではないことに注意)。木構造を再帰的に探索して経路近傍の中間ノードを収集する関数を以下のように定義します。

$${\rm path}(m,D_n) \to {\rm NodeList}$$

再帰ケース: $n \gt 1$ の場合、目的の葉ノードが左枝側にある場合は右枝側のノードを証明に追加し、右枝側にある場合は左枝側のノードを追加します。

$${\rm path}(m,D_{0:n}) = \begin{cases} {\rm path}(m, D_{0:k}) : r(D_{k:n}) & \text{if } m \lt k \\ {\rm path}(m-k, D_{k:n}) : r(D_{0:k}) & \text{if } m \ge k \end{cases}$$

前述の通り、この記述もプログラミング言語の再帰呼び出しで部分配列を渡すことを意図した書き方となっていることに注意。

基底ケース: $n=1$ の場合、つまり葉ノードに到達した場合は空の集合を返します。所属証明において、葉ノードに対応するログエントリはすでにクライアントが保持しているため、証明に含める必要がないためです。

$${\rm path}(0, \{d_0\}) = \emptyset$$

所属証明の検証

所属証明には、クライアントが保持しているログエントリ $m$ からルートハッシュ $r(D_{0:n})$ を算出するために必要な中間ノードが含まれています。クライアントは、証明からルートハッシュ $r(D_{0:n})$ を算出し、自身が保持している (検証済みの) ルートハッシュ $r_n$ と一致するかを確認します。

暗号学的ハッシュ関数 $h$ では、意図したハッシュ値を生成する入力を見つけることが非常に困難であるため (原像攻撃耐性)、実際には $m$ がツリーに含まれないにもかかわらずルートハッシュが一致するようなログエントリを選択することは現実的に不可能です。したがって、もしそれらのハッシュ値が一致すれば、クライアントの保持しているログエントリ $m$ は $r_n$ をルートハッシュとするマークルツリーに含まれていることが暗号学的に証明されます。

例 1: 所属証明の作成と検証

サーバは 7 個のログエントリを含むマークルツリー $T_7$ を保持しており、クライアントはそのルートハッシュ $r_7$ を保持していると仮定します。またクライアントは、(信頼できない経路で取得したなどの理由で) 正しいかどうか確証の持てないログエントリ $d_3$ を保持しており、これがサーバの管理するマークルツリーに含まれているかを知りたいとします。

証明の作成

$$\begin{align*} \pi_3 & = {\rm path}(3, D_{0:7}) \\ & = {\rm path}(3,D_{0:4}) : r(D_{4:7}) & (k=4) \\ & = ({\rm path}(3-2,D_{2:4}) : r(D_{0:2})) : r(D_{4:7}) & (k=2) \\ & = (({\rm path}(0,D_0) : r(d_3)) : r(D_{0:2})) : r(D_{4:7}) & (k=1) \\ & = ((\emptyset : r(d_3)) : r(D_{0:2})) : r(D_{4:7}) \\ & = \{ r(d_3), r(D_{0:2}), r(D_{4:7})\} \end{align*}$$

証明の検証

$$\begin{align*} r_7 & \stackrel{?}{=} r(D_{0:7}) \\ & = h({\tt 0x01}\,\parallel\,r(D_{0:4})\,\parallel\,r(D_{4:7})) \\ & = h({\tt 0x01}\,\parallel\,h({\tt 0x01}\,\parallel\,r(D_{0:2})\,\parallel\,r(D_{2:4}))\,\parallel\,r(D_{4:7})) \\ & = h({\tt 0x01}\,\parallel\,h({\tt 0x01}\,\parallel\,r(D_{0:2})\,\parallel\,h({\tt 0x01}\,\parallel\,r(d_2)\,\parallel\,r(d_3)))\,\parallel\,r(D_{4:7})) \\ & = h({\tt 0x01}\,\parallel\,h({\tt 0x01}\,\parallel\,r(D_{0:2})\,\parallel\,h({\tt 0x01}\,\parallel\,h({\tt 0x00}\,\parallel d_2)\,\parallel\,r(d_3)))\,\parallel\,r(D_{4:7})) \\ \end{align*}$$

最終的に $r_7 = r(D_{0:7})$ が成り立てば、サーバの管理するツリーに $d_3$ のログエントリが含まれていることが証明されます。

以下の図は $n=7, m=3$ での所属証明の作成と検証を表しています。

増分証明

増分証明 (incremental proof) とは、マークルツリーが $T \to T'$ と成長したときに、サーバの管理している $T'$ が $T$ の構造に基づいているかをクライアント側で検証するための小さなデータです。CT の文脈では整合性証明 (consistency proof) とも呼ばれます。所属証明と同様に経路近傍の中間ノードの集合で構成されているため、$O(\log N)$ と小さな空間計算量/時間計算量になります。

クライアントが $T$ 時点での信頼できるデータ数 $n$ とルートハッシュ $r$ を保持していると想定します。マークルツリーに含まれるデータ数が $n$ から $n'$ に増えた時、クライアントは増分証明 $\pi_{n,n'}$ を用いて以下の 2 点を検証することができます:

1. $T'$ の先頭の $n$ 個のデータが $T$ 時点でのデータと同一。
2. $T'$ のルートハッシュ $r'$ が $T$ のルートハッシュ $r$ に基づいている。

増分証明は、所属証明と同じ理屈で、ある時点のツリー構造が過去の任意の時点のツリー構造を「完全に」含んでいて、過去のエントリが一切変更・削除されていないことを検証可能にするための暗号学的な仕組みといえます。これは履歴ツリーや CT の追記専用特性に対する検証機構でです (つまり静的なマークルツリーには増分証明はありません)。

増分証明の作成

$n_1$ 個のデータを含むマークルツリー $T_{n_1}$ から、$n_2$ 個のデータを含むマークルツリー $T_{n_2}$ へ成長したとき、クライアントは信頼できる $n_1$ と $r_1$ を保持していると仮定する。増分証明 $\pi_{n_1,n_2}$ は、直感的には、$T_2$ のルートノードから $T_1$ 時点の最右データへの経路近傍の中間ノードの集合となります。

下の図はマークルツリーが $n_1=3$ から $n_2=7$ へ成長したケースでの増分証明を表しています。

増分証明の構築は、所属証明と同様に、ルートノードから目的のノードまでの経路近傍の中間ノードを収集します。これは経路を再帰的にたどって (つまり部分木を再帰的に評価して) 行うことができます。

$n$ 個の葉ノードを持つ部分木に対して、その先頭の $m$ 個の共通接頭辞データで構成される部分木との増分を証明するために必要最低限のノード集合を計算する以下の関数を導入します。

$${\rm subproof}(m, D_{0:n}, b) \to {\rm NodeList}$$

CT の文書に現われる完全性フラグ $b$ の意味はヒューリスティックでやや解釈が難しいところです。これは、再帰の基底で $b={\tt true}$ になっていた場合、クライアントはその部分木のルートハッシュ $r(D_{0:m})$ を既に知っているはず、つまり、そのノードは要求のあった増分証明の元の木構造 $T_1$ のルートノードなので、その位置以下のノードは証明に含める必要はないことを意味います。

${\rm subproof}$ は目的の葉ノードに向かって木構造を下りながら経路近傍のノードを収集します。増分証明 $\pi_{n_1,n_2}$ は以下のように表すことができます。

$$\pi_{n_1,n_2} = {\rm subproof}(n_1,D_{0:n_2},{\tt true})$$

再帰ケース: $m \lt n$ の場合、$k$ を $k \lt n \le 2k$ を満たす最大の 2 のべき乗とします。目的のツリー $B$ をカバーしているのは左右どちらの部分木かで分岐します。

$${\rm subproof}(m, D_{0:n}, b) = \begin{cases} {\rm subproof}(m, D_{0:k}, b)\ \oplus\ {r(D_{k:n})} & \text{if } m \leq k\\ {\rm subproof}(m - k, D_{k:m}, {\tt false})\ \oplus\ r(D_{0:k}) & \text{if } m > k \end{cases}$$

ここで $\oplus$ をリスト連結演算子とします。また、所属証明と同様にプログラミング言語で部分配列を渡すことを意図した書き方となっていることに注意。

基底ケース: $n=m$ の場合 (評価位置が現在の部分木の最右の葉ノードとなった場合) は次のようになります。

$$\begin{cases} {\rm subproof}(m,D_{0:m},{\tt true}) = \emptyset \\ {\rm subproof}(m,D_{0:m},{\tt false}) = \{r(D_{0:m})\} \end{cases}$$

結果として得られる証明に含まれる中間ノードは高々 $\lceil\log_2 n_2 \rceil+1$ となるため、$n_2$ が極めて大きい場合でも現実的な空間および時間計算量となります。

増分証明の検証

データ数が $n_1$ 時点でのルートハッシュ $r_1$ を持っているクライアントが、サーバから現在のデータ数 $n_2$、ルートハッシュ $r_2$、および増分証明 $\pi_{n_1,n_2}$ を受け取ったと仮定します。ここでクライアントは、増分証明 $\pi_{n_1,n_2}$ を使って $r_1$ から $r_2$ へ到達できることを確認する必要があります。それぞれでルートハッシュが一致すればツリーは $n_1$ から $n_2$ の過程で追記のみ (append-only) であり、前方の $n_1$ 個のデータの変更や削除は行われていないことが証明されます。

増分証明には、1) $n_1$ 時点のルートハッシュ $r_1$ を計算するのに必要なノード、および 2) $n_2$ 時点のルートハッシュ $r_2$ を計算するのに必要なノードを含む必要があります。クライアントは、これらを計算して自身が認識している $r_1$ と $r_2$ とそれぞれ一致していることが検証されれば、CT の整合性は証明されたことになります。

例 2: 一般的な増分証明の生成と検証

例えば $n_1=3$, $n_2=7$ の場合、増分証明の生成は目的の葉ノードまでの経路近傍のノードを収集します。

証明の生成

$$\begin{aligned} \pi_{3,7} & = {\rm subproof}(3, D_{0:7}, {\tt true}) \\ & = {\rm subproof}(3, D_{0:4}, {\tt true}) \ \oplus \ r(D_{4:7}) & (k = 4) \\ & = ({\rm subproof}(3-2, D_{2:4}, {\tt false}) \ \oplus \ r(D_{0:2})) \ \oplus \ r(D_{4:7}) & (k = 2) \\ & = (({\rm subproof}(1, D_{2:3}, {\tt false}) \ \oplus \ r(D_{3:4})) \ \oplus \ r(D_{0:2})) \ \oplus \ r(D_{4:7}) & (k = 1) \\ & = \{ r(D_{2:3})\} \ \oplus \ r(D_{3:4}) \ \oplus \ r(D_{0:2}) \ \oplus \ r(D_{4:7}) \\ & = \{ r(d_2), r(d_3), r(D_{0:2}), r(D_{4:7})\} \end{aligned}$$

証明の検証

クライアントは証明 $\pi_{3,7}$ から以下を算出し、自身が知っているルートハッシュ $r_3$、サーバから得た $r_7$ とそれぞれ一致していれば、サーバの現在のデータ $D_{0:7}$ がルートハッシュ $r_7$ を持つこと、またそれは $D_{0:3}$ から追加のみで成長したツリーであることが証明されます。

$$\begin{aligned} r_3 & \stackrel{?}{=} r(D_{0:3}) = h({\tt 0x01}\,\parallel\,r(D_{0:2})\,\parallel\,r(d_2)) \\ r_7 & \stackrel{?}{=} r(D_{0:7}) = h({\tt 0x01}\,\parallel\,h({\tt 0x01}\,\parallel\,r(D_{0:2})\,\parallel\,h({\tt 0x01}\,\parallel\,r(d_2)\,\parallel\,r(d_3))))\,\parallel\,r(D_{4:7})) \end{aligned}$$

例 3: クライアント既知のルートハッシュ以下を省略するケース

一方、$n_1=4$, $n_2=7$ のケースでは、増分証明の生成過程でクライアントが既に保持しているルートハッシュ $r_4$ のノードで探索を終了します。これは証明のデータサイズを削減することを目的としています。

証明の生成

$$\begin{aligned} \pi_{4,7} & = {\rm subproof}(4, D_{0:7}, {\tt true}) \\ & = {\rm subproof}(4, D_{0:4}, {\tt true}) \ \oplus \ r(D_{4:7}) & (k = 4) \\ & = \emptyset \ \oplus \ r(D_{4:7}) \\ & = \{ r(D_{4:7})\} \end{aligned}$$

証明の検証

クライアントは証明 $\pi_{4,7}$ から $r(D_{0:7})$ を算出し、自身が知っているルートハッシュ $r_7$ と一致していれば増分の一貫性が証明される。ここで $r(D_{0:7})$ の算出にはクライアントが既に知っている $r_4$ を使用することに注意。これにより、$r_7=r(D_{0:7})$ であれば $r_3$ の時点から追加のみで成長したデータであることが確証できる。

$$r_7 \stackrel{?}{=} r(D_{0:7}) = h({\tt 0x01}\,\parallel\,r_4\,\parallel\,r(D_{4:7}))$$

まとめ: 改ざん防止を実現する追記専用のデータ構造

Certificate Transparency (CT) の基盤となるマークルツリー (履歴ツリー) は、CA や証明書に依存するインターネットの信頼性を確保するための、監査可能な改ざん防止ログ機構として効率的な設計です。この構造の最も重要な特徴は、ログのサイズ $N$ に対数的なサイズと時間で証明を生成/検証できる点にあります。これらはネットワークコストを抑えつつ、迅速に検証プロトコルを完了することができるため、所属証明と増分証明の現実的な適用に寄与しています。

脚注

1. RFC 9162 Certificate Transparency

2. MERKLE, Ralph C. A certified digital signature. In: Conference on the Theory and Application of Cryptology. New York, NY: Springer New York, 1989. p. 218-238.

3. CROSBY, Scott A.; WALLACH, Dan S. Efficient data structures for tamper-evident logging. In: USENIX security symposium. 2009. p. 317-334.