鍵導出アルゴリズム

2023年10月4日 #鍵導出 #KDF #HKDF

概要

鍵導出 (key derivation) は 1 つの秘密から複数の秘密を導出する手法である。より具体的には、ある鍵素体 (key material) から暗号論的強度を持つ 1 つ以上の秘密鍵を決定論的に導出するために用いられる。このような鍵導出を行うための関数を鍵導出関数 (key derivation function; KDF) と呼ぶ。

KDF が取る鍵素体はエントロピーが十分であれば必ずしも一様に分散している必要はなく、生成される鍵は決定論的で一様にランダムである。したがって DH 鍵交換の共有シークレットから一つまたは複数の秘密鍵を生成するようなケースで有用である [2]。

1 つ以上の秘密を生成することのできる疑似乱数生成器 (PRNG) は KDF と類似しているが、シードが一様に分散している必要がある点と、決定論的な結果を保証していない (例えば後方秘匿性のために生成途中に再シードを行うことができる) という点で KDF とは異なる。また一般に KDF は PRNG のように一度に大量の秘密を生成するようには設計されていない。

概要
HMAC ベースの鍵導出関数
1. HKDF-Extract
2. HKDF-Expand
Keccak ベースの鍵導出関数
参考文献

HMAC ベースの鍵導出関数

広く使われている HMAC ベースの鍵導出関数 (HKDF; HMAC-based key derivation function) は HMAC 上に構築された KDF である。ここでは RFC 5869 [1] で規定されている HKDF を前提とする。

HKDF は抽出 (extract) と展開 (expand) の 2 ステップで構成されている。アプリケーション設計者は鍵素体が同じであっても異なるドメインで同じ秘密が導出されないように Salt 値と \({\sf info}\) を注意深く選択する必要がある。

HKDF-Extract

抽出ステップでは偏りが想定される任意の長さの鍵素体 \(s\) から一様にランダムな秘密 \(S\) を生成する。この変換には HMAC 関数 \(h\) と Salt 値 \(t\)、および鍵素体 \(s\) を使用する。\[ \begin{equation} S = h(t, s) \end{equation} \] Salt は同じ HKDF プロトコルを使う上でのドメイン分離として機能する。鍵素体 \(s\) と異なり Salt 値 \(t\) は秘匿されていなくても良い (敵対者にも知られて良い) が、Salt 値を秘匿することで HKDF はより強力なセキュリティを提供することができる。また Salt 値は省略することができる。この場合、Salt 値 \(t\) には値がすべてゼロの長さ \(|S|\) のバイト列を指定する。HKDF は Salt 値のサイズが短かったり低エントロピーあっても十分なセキュリティを提供するが、セキュリティの大幅な向上を期待できることから有効な Salt 値を指定することが推奨される。理想的な Salt 値は長さが \(|S|\) バイトの一様にランダムなバイト列である [1]。

なお、鍵素体 \(s\) が十分に一様なランダム値である保証があれば \(S = s\) としてこの HKDF-Extract ステップを省略しても良い。ただしそのような場合でもアプリケーションは手順の統一や秘密のサイズをそろえる目的で HKDF-Extract ステップを行うことができる。

HKDF-Expand

展開ステップでは一様にランダムな秘密 \(S\) から任意長 (ただし上限がある) の秘密 \(S'\) を生成する。この変換には HMAC 関数 \(h\) とアプリケーション指定のコンテキスト情報 \({\sf info}\)、出力バイト長 \(L\) を指定する。基本的な考え方は、繰り返し適用した HMAC 関数の出力を \(L\) の長さとなるまで連結することである。

出力 \(S'\) を得るためにまず式 (\(\ref{seq}\)) のような MHAC 関数 \(h\) の出力列 \(T_0, T_1, \ldots\) を生成する。\[ \begin{equation} \left\{ \begin{array}{rcl} T_0 & = & \emptyset \ \ \ \mbox{(zero-length byte sequence)} \\ T_1 & = & h(S,\, T_0 \, || \, {\sf info} \, || \, {\tt 0x01}) \\ T_2 & = & h(S,\, T_1 \, || \, {\sf info} \, || \, {\tt 0x02}) \\ \vdots \\ T_N & = & h(S,\, T_{N-1} \, || \, {\sf info} \, || \, N) \\ \end{array} \right. \label{seq} \end{equation} \] ここで連結末尾の定数 \({\tt 0x01}\), \({\tt 0x02}\), ..., \(N\) は 1 バイトである。したがって \(N = \lceil\frac{L}{|T|}\rceil \le 255\) であり、出力長 \(L\) は上限 \(L \le 255 \times |T|\) を持つ。例えば HMAC 関数 \(h\) のハッシュアルゴリズムに SHA-512 を使用するのであれば、その上限は \(255 \times 512/8 = 16,320\) バイトとなる。

次にすべての \(T_i\) を連結し \(L\) バイトで切り詰めを行って目的の長さの秘密 \(S'\) を得る。\[ \begin{equation} S' = {\rm truncate}_{L}(T_1 \, || \, T_2 \, || \, \cdots \, || \, T_N) \end{equation} \] 出力された秘密 \(S'\) は一様なランダム値であることから、目的の長さに分割することで複数の秘密を生成することができる。

コンテキスト情報 \({\sf info}\) は Salt 値と同様にドメイン分離として機能する。Salt が目的としての区分 (例えば "ユーザ鍵" など) だったのに対して、\({\sf info}\) は生成する鍵のインスタンス固有の区分 (例えばその鍵を所有するユーザ ID など) として利用することが推奨される。特に抽出されたある鍵 \(S\) から複数の鍵 \(S'\) を生成する場合は \({\sf info}\) を変更することで同じ鍵の導出を防ぐことができる。\({\sf info}\) を使用する場合は元の鍵素体 \(s\) や \(S\) から独立している必要があり、省略する場合は長さ 0 のバイト配列を指定することができる。

HKDF を一様にランダムな値を生成する機能として見たとき、HKDF-Expand は HMAC 関数を繰り返し呼ぶことから疑似乱数生成より著しく効率が悪く、また出力長 \(L\) に上限があることで大量の乱数生成には不向きである。大量の乱数列を高速に生成するケースでは HKDF-Extract で抽出した秘密 \(S\) から (決定論的な結果を妥協するか、決定論的な動作が保証されている) 疑似乱数生成器を使用して乱数を生成する方法を検討する方が良い。