セキュリティ
\( \def\vector#1{\boldsymbol{#1}} \)

ハッシュベース暗号

Takami Torao #WOTS #MSS
  • このエントリーをはてなブックマークに追加

概要

ハッシュベース暗号 (hash-based cryptography) は素因数分解や離散対数のような数学的な問題の困難性を利用するのではなく、暗号論的ハッシュ関数によって確立されるセキュリティに基づいている。量子計算機を使用して暗号論的ハッシュ関数の衝突と見つけることが困難であると同様に、ハッシュベースの暗号も量子計算耐性を持つと考えられている。一般に電子署名スキームとして使用されているハッシュベース暗号には XMSS (extended Merkle signature scheme), LMS (Leighton-Micali Signature), BPQS (blockchained post-quantum signature), SPHINCS, SPHINCS+ などがある。

Table of Contents

  1. 概要
  2. Winternitz ワンタイム署名
    1. ワンタイム特性
    2. パフォーマンス問題
  3. マークル署名スキーム

Winternitz ワンタイム署名

ハッシュベース暗号の最も単純な例として 1979 年に Winternitz が開発した Winternitz ワンタイム署名 (WOTS; Winternitz one-time signature) を挙げる。ここで "one-time" とは 1 つの秘密鍵で 1 つのメッセージにのみ署名できることを意味している (2 つ以上の署名から別の署名を偽造できるため)。ただし WOTS を後述する MSS などと組み合わせることで複数のメッセージに署名することができる。

WOTS は IOTA で使用されている。

\(\mathbb{W} = \{0, 1, \ldots, w-1\}\) のハッシュ値を生成する暗号論的ハッシュ関数 \({\rm hash}\) を想定する。ここで \(w\) は署名スキームのパラメータである。

鍵生成
まず秘密鍵 \(S = (S_1, S_2)\) を構成する 2 つのランダムな値 \(S_1, S_2 \in \mathbb{W}\) を選択する。公開鍵 \(P=(P_1, P_2)\) の構成要素はこの秘密鍵に対して \({\rm hash}\) を \(w\) 回繰り返して適用した値である。\[ \begin{eqnarray*} P_1 & = & {\rm hash}({\rm hash}(\ldots {\rm hash}(S_1) \ldots)) = {\rm hash}^w(S_1) \\ P_2 & = & {\rm hash}({\rm hash}(\ldots {\rm hash}(S_2) \ldots)) = {\rm hash}^w(S_2) \end{eqnarray*} \]
署名の生成
あるメッセージ \(m \in \mathbb{W}\) に対して、秘密鍵 \(S\) の 2 値をそれぞれ \(m\) 回と \(w-m\) 回繰り返してハッシュ関数 \({\rm hash}\) に適用した値を署名 \(\sigma\) とする。\[ \sigma = (\sigma_1, \sigma_2) = \left( {\rm hash}^m(S_1), \ {\rm hash}^{w-m}(S_2) \right) \]
署名の検証
検証者は与えられたメッセージ \(m\) と署名 \(\sigma\) の構成要素 \(\sigma_1, \sigma_2\) に対してハッシュ関数 \({\rm hash}\) をそれぞれ \(w-m\) 回と \(m\) 回適用し、それが公開鍵 \(P\) の構成要素と等しければメッセージ及び署名が有効であることを確かめることができる。\[ \begin{array}{llll} {\rm hash}^{w-m}(\sigma_1) & = {\rm hash}^{w-m}({\rm hash}^m(S_1)) & = {\rm hash}^w(S_1) & = P_1 \\ {\rm hash}^m(\sigma_2) & = {\rm hash}^m({\rm hash}^{w-m}(S_2)) & = {\rm hash}^w(S_2) & = P_2 \end{array} \]

ワンタイム特性

ハッシュ関数 \({\rm hash}\) が署名スキームとして公開されていることから、第三者は \({\rm hash}^m(S)\) から \({\rm hash}({\rm hash}^m(S))\) = \({\rm hash}^{m+1}(S)\) を容易に算出ことができることに注意。

単一の署名であれば \({\rm hash}^{m}(S_1)\) から \({\rm hash}^{m+1}(S_1)\) を算出できたとしても \({\rm hash}^{w-m}(S_2)\) から \({\rm hash}^{w-m-1}(S_2)\) を算出することはできないため安全である。しかし、同一の秘密鍵で 2 つのメッセージ \(m_x\), \(m_y\) の署名 \(\sigma_x\), \(\sigma_y\) を生成した場合、攻撃者はある範囲: \[ \min(m_x,m_y) \le m \le \max(m_x,m_y) \] の任意のメッセージ \(m\) に対する署名を秘密鍵なしに生成することができるようになる。これが WOTS が "one-time" である理由である。

例としてパラメータ \(w=16\) の設定で 2 つのメッセージ \(m_x=3\) と \(m_y=11\) に署名した場合について考えてみよう。それぞれの署名 \(\sigma_x\), \(\sigma_y\) は以下のように表される。\[ \left\{ \begin{eqnarray*} \sigma_x & = & \left( {\rm hash}^3(S_1), \ {\rm hash}^{16-3}(S_2) \right) \\ \sigma_y & = & \left( {\rm hash}^{11}(S_1), \ {\rm hash}^{16-11}(S_2) \right) \end{eqnarray*} \right. \] この 2 つの署名を入手した攻撃者は、前述の方法で \(3 \le m \le 15\) 範囲の \({\rm hash}^m(S_1)\) と、\(5 \le 16-m \le 15\) 範囲、つまり \(1 \le m \le 11\) 範囲の \({\rm hash}^{w-m}(S_2)\) を計算することができる。したがって、結果的に攻撃者は \(m \in \{3,4,\ldots,11\}\) 範囲の任意のメッセージに対する署名を秘密鍵なしに作成することができる。

8-bit 程度の大きさでは、たかだか 256 回の試行で \({\rm hash}^m(S) = {\rm hash}(x)\) となるような \(x={\rm hash}^{m-1}(S)\) が見つかるのではないか? これを最大でも 256 回試行すれば \(S\) が求まり、さらに 32 回繰り返せば 256-bit 全ての秘密鍵 \(S\) が特定できるのではないか?

パフォーマンス問題

WOTS は 8-bit のように非常に短い鍵や署名を生成するケースでもハッシュ値の計算を少なくとも 256×2 回計算する必要がある。このスキームは非常に短いメッセージや署名に対しては機能するが、256-bit のような比較的長いメッセージに対して適用することは現実的ではない。回避策は、このような長いメッセージをより短いメッセージに分割することである。

例えば 256-bit のメッセージに署名を行うとき、8-bit 単位の \(n=32\) 個の値に分割してそれぞれに秘密鍵を作成したとき、\(2^{256}\) ではなく \(2^8\times 32\) のハッシュ計算で公開鍵を作成することができる (この処理は SIMD で並列化できるかもしれない)。このような手法のさらなる拡張は後述のマークル署名スキームとなる。

マークル署名スキーム

マークル署名スキーム (MSS; Merkle signature scheme) は WOTS をマークルツリーと組み合わせて \(N\) 個のメッセージに署名できるように拡張した署名スキームである。ただし、実際には WOTS だけではなく任意のワンタイム署名 (OTS) スキームを使用することができる。

鍵生成
  1. 対象とするワンタイム署名スキームに基づいて \(N=2^n\) 個の OTS 鍵ペア \((s_i,p_i)\) を作成する。
  2. すべての OTS 公開鍵 \(p_i\) に対してハッシュ値 \(h_i={\rm hash}(p_i)\) を計算してマークルツリーを作成する。
  3. すべての OTS 鍵ペア \((s_i,p_i)\) を MSS における秘密鍵 \(S\)、マークルルートを MSS における公開鍵 \(P\) とする。
署名生成
  1. 署名者はまだ署名に使用していない OTS 鍵ペア \((s_i,p_i)\) を選択する。
  2. メッセージ \(m\) に対してワンタイム署名スキームを適用して OTS 署名 \(\sigma_i\) を作成する。
  3. また \(h_i\) からマークルルートまでの認証パスとなる \(n\) 個のノードのハッシュ値 \(a_1,\ldots,a_n\) を取得する
  4. OTS 署名、OTS 公開鍵、認証パスのタプル \((\sigma_i, p_i, a_1, \ldots, a_n)\) を MSS における署名 \(\sigma\) とする。
署名検証
検証者は公開鍵 (マークルルート) \(P\)、メッセージ \(m\)、署名 \(\sigma=(\sigma_i, p_i, a_1, \ldots, a_n)\) の情報を持っている。以下の 2 つの検証が成功すれば署名 \(\sigma\) はメッセージ \(m\) に対して有効である。
  1. \(h_i={\rm hash}(p_i)\) を算出し認証パス \((a_1,\ldots,a_n)\) とのハッシュ値を計算して \(P\) と等しいこと、つまり \(p_i\) が正しいことを検証する。
  2. ワンタイム署名スキームに従って OTS 署名 \(\sigma_i\) が正しいことを OTS 公開鍵 \(p_i\) を使用して検証する。

MSS はワンタイム署名用の \(N\) 個の鍵ペアを予め作成しておき順番に使用する。したがってそれぞれの署名処理は独立しておらず、どの鍵ペアまで使用したかという状態を記憶しておかなければならないことからステートフル署名スキーム (stateful signature scheme) である。単純に OTS で \(N\) 個の鍵ペアを作成する場合と比較して、配布する公開鍵がマークルルートの値一つだけで済むという利点がある。