メインコンテンツまでスキップ

5. 有限体へのハッシュ (Hashing to a Finite Field)

hash_to_field 関数は、任意長のバイト列 msg を、体 F の 1 個以上の元へとハッシュします。この関数は 2 つの段階で動作します。まず入力バイト列をハッシュして一様ランダムなバイト列を生成し、次にそのバイト列を F の 1 個以上の元として解釈します。

第 1 段階のために、hash_to_field は補助関数 expand_message を呼び出します。本文書は expand_message の 2 つの変種を定義します。一方は SHA-2 [FIPS180-4] や SHA-3 [FIPS202] のようなハッシュ関数に適したもの、もう一方は SHAKE128 [FIPS202] のような拡張可能出力関数に適したものです。各 expand_message 変種に関するセキュリティ上の考慮事項は以下（第 5.3.1 節および第 5.3.2 節）で論じます。

実装者は、hash_to_field 関数が定数時間実装に適したものであることを保証するため、F の一様ランダムな元を生成するのに棄却サンプリングを用いてはなりません (MUST NOT)。その理由は、棄却サンプリングの手続きは定数時間で実装することが難しく、また後になって善意で行われた「最適化」が、実装を気付かないうちに非定数時間にしてしまう可能性があるためです。これは、棄却サンプリングに基づく hash_to_field 関数はいずれも定数時間実装と両立しないことを意味します。

hash_to_field 関数は、スカラーへの安全なハッシュにも適しています。たとえば、素数位数 r を持つ楕円曲線の（部分）群に対応するスカラー体へハッシュする場合、対象の体を GF(r) として hash_to_field を実体化すれば十分です。

hash_to_field 関数は、expand_message（第 5.3 節）がランダムオラクルとしてモデル化されるとき、ランダムオラクル [MRH04] から識別不可能となるように設計されています（その識別不可能性の詳細については第 10.5 節を参照）。識別不可能性を保証するには注意が必要です。その理由を理解するため、3/4 * 2^256 に近い素数 p を考えてみましょう。ランダムな 256 ビット整数をこの p で剰余簡約すると、得られる値はおよそ 1/2 の確率で範囲 [0, p / 3] に入ります。これは、この値が [0, p - 1] における一様分布から統計的に大きく離れていることを意味します。

偏りを制御するため、hash_to_field はその代わりに、長さが少なくとも ceil(log2(p)) + k ビットであるランダム整数を使用します。ここで k はそのスイートに対する目標セキュリティ強度（ビット単位）です。そのような整数を p で剰余簡約すると、任意の p について偏りは高々 2^-k となります。この偏りは、k ビットのセキュリティを目標とする場合に適切です。そのような整数それぞれについて、hash_to_field は expand_message を用いて L バイトの一様なバイト列を得ます。ここで

L = ceil((ceil(log2(p)) + k) / 8)

です。これらの一様なバイト列は、次いで OS2IP によって整数として解釈されます。たとえば 255 ビットの素数 p と k = 128 ビットのセキュリティに対しては、L = ceil((255 + 128) / 8) = 48 バイトとなります。

k は対応する曲線のセキュリティ強度の上界であることに注意してください。詳細は第 10.8 節を、また所与の曲線に対する k の選び方の指針は第 8.9 節を参照してください。

5.1. 拡大体における効率性の考慮 (Efficiency Considerations in Extension Fields)​

本節で述べる hash_to_field 関数は、ある種の拡大体に対しては非効率です。具体的には、拡大体 GF(p^m) の元へハッシュする場合、hash_to_field は msg を m * L バイト（L は上で定義したもの）へ拡張することを必要とします。log2(p) がセキュリティ強度 k よりも著しく小さい拡大体では、このアプローチは非効率です。すなわち、これは expand_message におよそ m * log2(p) + m * k ビットを出力させることを要求しますが、偏りが高々 2^-k である GF(p^m) の元を生成するには m * log2(p) + k バイトで十分だからです。そのような場合、応用は、以下のセキュリティ要件を満たすことを条件として、代替の hash_to_field 関数を使用してもかまいません (MAY)。

  • 当該関数は、偏りが高々 2^-k である点を除いて一様ランダムな体の元を 1 個以上出力しなければなりません (MUST)。

  • 当該関数は棄却サンプリングを用いてはなりません (MUST NOT)。

  • 当該関数は直線的な実装に適したものであるべきです (SHOULD)。

たとえば Pornin [P20] は、GF(9767^19) へハッシュする方法を記述しており、これはこれらの要件を満たしつつ、その体に対して hash_to_field が用いるよりも少ない出力ビット数を expand_message から使用します。

5.2. hash_to_field の実装 (hash_to_field Implementation)​

以下の手続きは hash_to_field を実装します。

この関数への expand_message パラメータは、第 5.3 節に示す要件に適合しなければなりません (MUST)。第 3.1 節では、ドメイン分離タグである DST を構成するために要求される (REQUIRED) 方法について論じます。expand_message が失敗した場合、hash_to_field も失敗する (ABORT) ことがある点に注意してください。

hash_to_field(msg, count)

パラメータ (Parameters):
- DST, ドメイン分離タグ（第 3.1 節を参照）。
- F, 標数 p かつ位数 q = p^m の有限体。
- p, F の標数（直上を参照）。
- m, F の拡大次数, m >= 1（直上を参照）。
- L = ceil((ceil(log2(p)) + k) / 8), ここで k はスイートの
  セキュリティパラメータ（例: k = 128）。
- expand_message, バイト列とドメイン分離タグを
  一様ランダムなバイト列へ拡張する関数
  （第 5.3 節を参照）。

入力 (Input):
- msg, ハッシュ対象のメッセージを含むバイト列。
- count, 出力する F の元の個数。

出力 (Output):
- (u_0, ..., u_(count - 1)), 体の元のリスト。

手順 (Steps):
1. len_in_bytes = count * m * L
2. uniform_bytes = expand_message(msg, DST, len_in_bytes)
3. for i in (0, ..., count - 1):
4.   for j in (0, ..., m - 1):
5.     elm_offset = L * (j + i * m)
6.     tv = substr(uniform_bytes, elm_offset, L)
7.     e_j = OS2IP(tv) mod p
8.   u_i = (e_0, ..., e_(m - 1))
9. return (u_0, ..., u_(count - 1))

5.3. expand_message​

expand_message は一様ランダムなバイト列を生成する関数です。これは 3 つの引数を取ります。

  1. msg, ハッシュ対象のメッセージを含むバイト列、

  2. DST, ドメイン分離タグとして働くバイト列、および

  3. len_in_bytes, 生成すべきバイト数。

本文書は expand_message の次の 2 つの変種を定義します。

  • expand_message_xmd（第 5.3.1 節）は、SHA-2 [FIPS180-4]、SHA-3 [FIPS202]、BLAKE2 [RFC7693] などを含む幅広いハッシュ関数とともに使用するのに適しています。

  • expand_message_xof（第 5.3.2 節）は、SHAKE [FIPS202] や BLAKE2X [BLAKE2X] 系列の関数を含む拡張可能出力関数 (extendable-output functions, XOFs) とともに使用するのに適しています。

これらの変種は大多数のユースケースにとって十分なはずですが、他の変種も可能です。第 5.3.4 節ではその要件を論じます。

5.3.1. expand_message_xmd​

expand_message_xmd 関数は、b ビットを出力する暗号学的ハッシュ関数 H を用いて一様ランダムなバイト列を生成します。セキュリティのため、H は以下の要件を満たさなければなりません (MUST)。

  • H が出力するビット数は b >= 2 * k でなければなりません (MUST)。ここで k はビット単位の目標セキュリティ強度です。また b は 8 で割り切れなければなりません (MUST)。第 1 の要件は k ビットの衝突耐性を保証し、第 2 の要件は expand_message_xmd の出力の一様性を保証します。

  • H は SHA-2 のような Merkle-Damgaard ハッシュ関数であってもかまいません (MAY)。この場合、基礎となる圧縮関数がランダムオラクルとしてモデル化されるとき、安全性が成り立ちます [CDMP05]。（議論は第 10.6 節を参照。）

  • H は SHA-3 や BLAKE2 のようなスポンジ構造に基づくハッシュ関数であってもかまいません (MAY)。この場合、内部関数がランダム変換またはランダム置換としてモデル化されるとき、安全性が成り立ちます [BDPV08]。

  • それ以外の場合、H は、妥当な暗号学的仮定の下でランダムオラクル [MRH04] から識別不可能であることが証明されたハッシュ関数でなければなりません (MUST)。

SHA-2 [FIPS180-4] と SHA-3 [FIPS202] は典型的かつ推奨される (RECOMMENDED) 選択肢です。一例として、128 ビットのセキュリティ強度に対しては b >= 256 ビットであり、SHA-256 または SHA3-256 のいずれかが適切な選択となります。

ハッシュ関数 H は、固定長のデータブロックを繰り返し取り込むことによって動作すると想定されています。これらのブロックのビット単位の長さは入力ブロックサイズ (input block size, s) と呼ばれます。例として、SHA-512 [FIPS180-4] では s = 1024、SHA3-512 [FIPS202] では s = 576 です。正しく動作するために、H は b <= s を必要とします。

以下の手続きは expand_message_xmd を実装します。

expand_message_xmd(msg, DST, len_in_bytes)

パラメータ (Parameters):
- H, ハッシュ関数（上記の要件を参照）。
- b_in_bytes, H の出力サイズをビット単位で b としたときの b / 8。
  たとえば b = 256 の場合、b_in_bytes = 32。
- s_in_bytes, H の入力ブロックサイズをバイト単位で測ったもの
  （上記の議論を参照）。たとえば SHA-256 の場合、s_in_bytes = 64。

入力 (Input):
- msg, バイト列。
- DST, 高々 255 バイトのバイト列。
  より長い DST の使用については下記の情報を参照。
- len_in_bytes, 要求される出力の長さ（バイト単位）。
  (255 * b_in_bytes) と 2^16-1 のうち小さい方を超えないこと。

出力 (Output):
- uniform_bytes, バイト列。

手順 (Steps):
1.  ell = ceil(len_in_bytes / b_in_bytes)
2.  ell > 255 または len_in_bytes > 65535 または len(DST) > 255 ならば ABORT
3.  DST_prime = DST || I2OSP(len(DST), 1)
4.  Z_pad = I2OSP(0, s_in_bytes)
5.  l_i_b_str = I2OSP(len_in_bytes, 2)
6.  msg_prime = Z_pad || msg || l_i_b_str || I2OSP(0, 1) || DST_prime
7.  b_0 = H(msg_prime)
8.  b_1 = H(b_0 || I2OSP(1, 1) || DST_prime)
9.  for i in (2, ..., ell):
10.    b_i = H(strxor(b_0, b_(i - 1)) || I2OSP(i, 1) || DST_prime)
11. uniform_bytes = b_1 || ... || b_ell
12. return substr(uniform_bytes, 0, len_in_bytes)

文字列 Z_pad（手順 6）は、b_0 を計算する（手順 7）前に msg の前に付加されることに注意してください。これは H が SHA-2 などの Merkle-Damgaard ハッシュである場合に、セキュリティ上必要です（第 10.6 節を参照）。この追加データをハッシュするということは、b_0 を計算するコストが、単に H(msg) を計算するコストよりも高くなることを意味します。ほとんどの状況において、このオーバーヘッドは無視できます。H の評価コストは、曲線へのハッシュに関わる他のコストよりもはるかに小さいからです。

しかしながら、Z_pad が H のみに依存し、expand_message_xmd への引数には依存しないという事実を利用することで、このオーバーヘッドを完全に回避することも可能です。そのためには、まず Z_pad を取り込んだ後の H の内部状態を事前計算して保存しておきます。そして b_0 を計算する際に、保存した状態を用いて H を初期化します。さらなる詳細は実装依存であり、本文書の範囲外です。

5.3.2. expand_message_xof​

expand_message_xof 関数は、拡張可能出力関数 (XOF) H を用いて一様ランダムなバイト列を生成します。セキュリティのため、H は以下の基準を満たさなければなりません (MUST)。

  • H の衝突耐性は少なくとも k ビットでなければなりません (MUST)。

  • H は、妥当な暗号学的仮定の下でランダムオラクルから識別不可能であることが証明された XOF でなければなりません (MUST)。

SHAKE XOF 系列 [FIPS202] は典型的かつ推奨される (RECOMMENDED) 選択肢です。一例として、128 ビットのセキュリティに対しては SHAKE128 が適切な選択となります。

以下の手続きは expand_message_xof を実装します。

expand_message_xof(msg, DST, len_in_bytes)

パラメータ (Parameters):
- H(m, d), 入力メッセージ m を処理して d バイトを返す
  拡張可能出力関数。

入力 (Input):
- msg, バイト列。
- DST, 高々 255 バイトのバイト列。
  より長い DST の使用については下記の情報を参照。
- len_in_bytes, 要求される出力の長さ（バイト単位）。

出力 (Output):
- uniform_bytes, バイト列。

手順 (Steps):
1. len_in_bytes > 65535 または len(DST) > 255 ならば ABORT
2. DST_prime = DST || I2OSP(len(DST), 1)
3. msg_prime = msg || I2OSP(len_in_bytes, 2) || DST_prime
4. uniform_bytes = H(msg_prime, len_in_bytes)
5. return uniform_bytes

5.3.3. 255 バイトを超える DST の使用 (Using DSTs Longer than 255 Bytes)​

本節で定義される expand_message の変種は、高々 255 バイトのドメイン分離タグを受け付けます。たとえば呼び出し元のプロトコルによって課される要件のために、応用が 255 バイトを超えるドメイン分離タグを必要とする場合、実装者は次のようにハッシュによって短いドメイン分離タグを計算しなければなりません (MUST)。

  • ハッシュ関数 H を用いる expand_message_xmd に対しては、DST は次のように計算されます。
DST = H("H2C-OVERSIZE-DST-" || a_very_long_DST)
  • 拡張可能出力関数 H を用いる expand_message_xof に対しては、DST は次のように計算されます。
DST = H("H2C-OVERSIZE-DST-" || a_very_long_DST, ceil(2 * k / 8))

ここで a_very_long_DST は長さが 255 バイトを超える DST であり、"H2C-OVERSIZE-DST-" は 17 バイトの ASCII 文字列リテラル、k はビット単位の目標セキュリティ強度です。

5.3.4. 他の expand_message 変種の定義 (Defining Other expand_message Variants)​

新しい expand_message の変種を定義する際に最も重要な考慮事項は、hash_to_field が expand_message をランダムオラクルとしてモデル化しているという点です。したがって実装者は、基礎となる暗号プリミティブに関する適切な仮定の下で、ランダムオラクルからの識別不可能性を証明すべきです (SHOULD)。さらなる情報は第 10.5 節を参照してください。

加えて、expand_message の変種は次を満たす必要があります。

  • 対象となる楕円曲線のセキュリティ強度に見合った衝突耐性を与えなければなりません (MUST)。

  • 暗号学的なランダム性を必要とする応用での使用を想定して設計されたプリミティブの上に構築されなければなりません (MUST)。例として、安全なストリーム暗号は適切なプリミティブですが、メルセンヌ・ツイスタ疑似乱数生成器 [MT98] はそうではありません。

  • 棄却サンプリングを用いてはなりません (MUST NOT)。

  • 相異なる (msg, DST, length) の入力に対して独立した値を与えなければなりません (MUST)。この要件を満たすのは微妙な問題です。簡略化した例として、msg || DST をハッシュする方法はうまくいきません。というのも、この場合、連結結果が等しくなるような相異なる (msg, DST) の組（たとえば ("AB", "CDEF") と ("ABC", "DEF")）が同じ出力を返してしまうからです。本文書で定義される変種は、この問題を避けるために DST のサフィックスフリーな符号化を用いています。

  • expand_message の内部での暗号プリミティブの呼び出しが、expand_message の外部での呼び出しからドメイン分離されることを保証するために、ドメイン分離タグ DST を使用しなければなりません (MUST)。たとえば、expand_message の変種がハッシュ関数 H を用いる場合、H の各呼び出しへの入力のプレフィックスまたはサフィックスのいずれかとして DST の符号化を追加しなければなりません (MUST)。DST をサフィックスとして追加する方法が推奨される (RECOMMENDED) アプローチです。

  • msg が長い場合の効率のため、msg をちょうど一度だけ読み取るべきです (SHOULD)。

加えて、各 expand_message 変種は、Suite ID においてその変種を識別する一意な EXP_TAG を規定しなければなりません (MUST)。さらなる情報は第 8.10 節を参照してください。

に最終更新