MMH-バジャーMAC

Badger はユニバーサルハッシュのアイデアに基づいたメッセージ認証コード(MAC)であり、 Boesgaard、Scavenius、Pedersen、Christensen、Zenner によって開発されました^{[いつ? ] 。 [1]}これは、ENH (下記参照) を適用した後、ϵ ほぼ強くユニバーサル (ASU) ハッシュ関数族を使用して ∆-ユニバーサルハッシュ族 MMH を強化することによって構築されます。ここで、ϵ の値は です。^{[2] Badger は}ユニバーサルハッシュ関数アプローチに基づく MAC 関数であるため、Badger のセキュリティに必要な条件は、UMACなどの他のユニバーサルハッシュ関数の条件と同じです。 ${\displaystyle 1/(2^{32}-5)}$

Badger MAC は、最大ビットの長さのメッセージを処理し、長さビットの認証タグを返します。ここで、 です。セキュリティのニーズに応じて、ユーザーは の値、つまりBadger の並列ハッシュツリーの数を選択できます。 uにさらに大きな値を選択することもできますが、それらの値は MAC のセキュリティにそれ以上影響を与えません。アルゴリズムは128 ビットのキーを使用し、このキーで処理されるメッセージの長さは に制限されています。^[3]${\displaystyle 2^{64}-1}$${\displaystyle u\cdot 32}$${\displaystyle 1\leq u\leq 5}$${\displaystyle u}$${\displaystyle 2^{64}}$

特定のキーで Badgerアルゴリズムを実行するには、キー設定をキーごとに 1 回だけ実行する必要があります。これは、結果として得られる MAC の内部状態を保存して、後で処理される他のメッセージで使用できるためです。

ハッシュ ファミリを組み合わせることで、新しいハッシュ ファミリを作成できます。ϵ-AU、ϵ-A∆U、および ϵ-ASU ファミリの場合、後者は前者に含まれます。たとえば、A∆U ファミリは AU ファミリでもあり、ASU は A∆U ファミリでもあります。一方、パフォーマンスの向上が達成できる限り、より強力なファミリをより弱いファミリに縮小できます。∆-ユニバーサル ハッシュ関数をユニバーサル ハッシュ関数に縮小する方法については、以下で説明します。

定理2 ^[1]

集合Aから集合Bへの ϵ-AΔU ハッシュ族を とします。メッセージ を考えます。すると関数から成る族Hは ϵ-AU です。 ${\displaystyle H^{\triangle }}$${\displaystyle (m,m_{b})\in A\times B}$${\displaystyle h(m,m_{b})=H^{\triangle }(m)+m_{b}}$

ならば、 はϵ-A∆U 族なので、 が最大 ϵ である確率は である 。だが ならば、の確率は自明に 0 である。定理 2 の証明は^{[1]で説明されている。}${\displaystyle m\neq m'}$${\displaystyle h(m,m_{b})=h(m',m'_{b})}$${\displaystyle H^{\triangle }}$${\displaystyle m=m'}$${\displaystyle m_{b}\neq m_{b}'}$

ENH ファミリは、ユニバーサル ハッシュファミリ NH ( UMACでも使用される) に基づいて構築されます。

${\displaystyle NH_{K}(M)=\sum _{i=1}^{\frac {\ell }{2}}(k_{(2i-1)}+_{w}m_{(2i-1)})\times (k_{2i}+_{w}m_{2i})\mod 2^{2w}}$

ここで、は ' を法とする加算' を意味し、 です。これは-A∆U ハッシュ ファミリです。 ${\displaystyle +_{w}}$${\displaystyle 2^{w}}$${\displaystyle m_{i},k_{i}\in {\big \{}0,\ldots ,2^{w}-1{\big \}}}$${\displaystyle 2^{-w}}$

補題1 ^[1]

NH の次のバージョンは-A∆U です。 ${\displaystyle 2^{-w}}$

${\displaystyle NH_{K}(M)=(k_{1}+_{w}m_{1})\times (k_{2}+_{w}m_{2})\mod 2^{2w}}$

w=32 を選択し、定理 1 を適用すると、アナグマ MAC の基本的な構成要素となる -AU 関数ファミリ ENH が 得られます。${\displaystyle 2^{-32}}$

${\displaystyle ENH_{k_{1},k_{2}}(m_{1},m_{2},m_{3},m_{4})=(m_{1}+_{32}k_{1})(m_{2}+_{32}k_{2})+_{64}m_{3}+_{64}2^{32}m_{4}}$

ここで、すべての引数は 32 ビット長で、出力は 64 ビットになります。

Badgerは強力な普遍性ハッシュファミリーを使用して構築されており、次のように記述できます。

${\displaystyle {\mathcal {H}}=H^{*}\times F,}$^[1]

ここで、-AU ユニバーサル関数ファミリH*は、任意のサイズのメッセージを固定サイズにハッシュするために使用され、-ASU 関数ファミリF は、全体の構築の強いユニバーサル性を保証するために使用されます。NHとENH は、 H* の構築に使用されます。関数ファミリ H* の最大入力サイズはで、出力サイズは 128 ビットで、メッセージとハッシュごとに 64 ビットに分割されます。H *関数の衝突確率はからの範囲です。強いユニバーサル関数ファミリFを構築するには、∆ ユニバーサル ハッシュ ファミリ MMH* に別のキーを追加して、強いユニバーサル ハッシュ ファミリに変換します。 ${\displaystyle \epsilon _{H^{*}}}$${\displaystyle \epsilon_{F}}$${\displaystyle 2^{64}-1}$${\displaystyle 2^{-32}}$${\displaystyle 2^{-26.14}}$

すべてのメッセージに対して、処理フェーズと最終処理フェーズという2つのステップを実行する必要があります。^[3]

このフェーズでは、データは 64 ビットの文字列にハッシュされます。この処理フェーズでは、コア関数h  :が使用され、次のように 128 ビットの文字列が64 ビットの文字列にハッシュされます。 ${\displaystyle \left\{0,1\right\}^{64}\times \left\{0,1\right\}^{128}\to \left\{0,1\right\}^{64}}$${\displaystyle m_{2}\parallel m_{1}}$${\displaystyle h(k,m_{2},m_{1})}$

${\displaystyle h(k,m_{2},m_{1})=(L(m_{1})+_{32}L(k))\cdot (U(m_{1})+_{32}U(k))+_{64}m_{2}\,}$

任意のnについて、は を法とする加算を意味します。⁠ ⁠ビット文字列xが与えられた場合、⁠ ⁠ は最下位nビットを意味し、⁠ ⁠ は最上位nビットを意味します。 ${\displaystyle +_{n}}$${\displaystyle 2^{n}}$${\displaystyle 2n}$${\displaystyle L(x)}$${\displaystyle U(x)}$

この関数を使用してメッセージを処理できます。level_key[j][i]で示します。 ${\displaystyle k_{j}^{i}}$

処理フェーズの疑似コードは次のとおりです。

L = | M |
 L = 0
    の場合 ${\displaystyle M^{1}=\cdots =M^{u}=0}$
    最終決定へ進む
r = L mod 64
 r ≠ 0の場合 :
     i = 1からuの場合:
     j = 1からv ′の場合:${\displaystyle M=0^{64-r}\parallel M}$
  ${\displaystyle M^{i}=M}$
    ${\displaystyle v'=\max\{1,\lceil \log _{2}L\rceil -6\}}$
  ⁠ ⁠ を${\displaystyle M^{i}}$64 ビットのブロックに
    分割します。 ⁠ ⁠ ${\displaystyle M^{i}=m_{t}^{i}\parallel \cdots \parallel m_{1}^{i}}$
tが偶数の場合 :
     ⁠ ⁠そうでない場合⁠ ⁠ ${\displaystyle M^{i}=h(k_{j}^{i},m_{t}^{i},m_{t-1}^{i})\parallel \cdots \parallel h(k_{j}^{i},m_{2}^{i},m_{1}^{i})}$

    ${\displaystyle M^{i}=m_{t}^{i}\parallel h(k_{j}^{i},m_{t-1}^{i},m_{t-2}^{i})\parallel \cdots \parallel h(k_{j}^{i},m_{2}^{i},m_{1}^{i})}$

このフェーズでは、処理フェーズから得られた 64 文字列が目的の MAC タグに変換されます。このファイナライズ フェーズでは、Rabbit ストリーム暗号final_key[j][i]が使用され、ファイナライズ キーを としてキー セットアップと IV セットアップの両方が使用されます。 ${\displaystyle k_{j}^{i}}$

ファイナライズフェーズの疑似コード

ラビットキーセットアップ(K)
RabbitIVセットアップ(N)
 i = 1から uまで:
     27 ビットのブロックに分割し、S = 
    S ⨁ RabbitNextbit ( u ∙ 32)
 S
を返す${\displaystyle Q^{i}=0^{7}\parallel L\parallel M^{i}}$${\displaystyle Q^{i}}$${\displaystyle Q^{i}=q_{5}^{i}\parallel \cdots \parallel q_{1}^{i}}$
    ${\displaystyle S^{i}=(\sum _{j=1}^{5}(q_{j}^{i}K_{j}^{i}))+K_{6}^{i}{\bmod {p}}}$
${\displaystyle S=S^{u}\parallel \cdots \parallel S^{1}}$

上記の疑似コードでは、k はRabbit Key Setup(K) のキーを表し、これは 128 ビットのキーkで Rabbit を初期化します。M はハッシュされるメッセージを表し、 | M | はメッセージの長さをビット単位で表します。⁠ ⁠ は${\displaystyle q_{i}}$iブロックに分割されたメッセージMを表します。 ⁠ ⁠ビット文字列xの場合、L ( x )とU ( x )はそれぞれ最下位 n ビットと最上位nビットを表します。 ${\displaystyle 2n}$

Boesgard、Christensen、Zennerは、1.0GHz Pentium IIIと1.7GHz Pentium 4プロセッサで測定されたBadgerのパフォーマンスを報告しています。^[1]速度最適化バージョンは、Cでインライン化されたアセンブリ言語でプログラムされ、Intel C++ 7.1コンパイラを使用してコンパイルされました。

次の表は、さまざまな制限されたメッセージ長に対する Badger のプロパティを示しています。「Memory req.」は、キー マテリアルとRabbit ストリーム暗号の内部状態を含む内部状態を格納するために必要なメモリの量を示します。「Setup」はキーのセットアップを示し、「Fin.」は IV セットアップによる終了を示します。

MMH という名前は、Multilinear-Modular-Hashing の略です。マルチメディアでの応用としては、オンライン マルチメディア タイトルの整合性の検証などが挙げられます。MMH のパフォーマンスは、最新のマイクロプロセッサにおける整数スカラー積のサポートの向上に基づいています。

MMH は、最も基本的な演算として単精度スカラー積を使用します。これは、メッセージとキーの(修正された)内積 (素数を法 とする) で構成されます。MMH の構築は、ある素数整数 の有限体で機能します。 ${\displaystyle p}$ ${\displaystyle F_{p}}$${\displaystyle p}$

MMH* は、ある正の整数kに対する多重線型関数からなるハッシュ関数の族の構築を伴います。からまでの関数の族 MMH* は次のように定義されます。 ${\displaystyle F_{p}^{k}}$${\displaystyle F_{p}^{k}}$${\displaystyle F_{p}}$

${\displaystyle \mathrm {MMH} ^{*}=\{g_{x}:F_{p}^{k}\rightarrow F_{p}|x\in F_{p}^{k}\}}$

ここで、x、m はベクトルであり、関数は次のように定義されます。 ${\displaystyle g_{x}}$

${\displaystyle g_{x}(m)=mx{\bmod {p}}=\sum _{i=1}^{n}m_{i}\,x_{i}{\bmod {p}}}$

MAC の場合、mはメッセージ、x はキーです。${\displaystyle m=(m_{1},\ldots ,m_{k})}$${\displaystyle x=(x_{1},\ldots ,x_{k}),x_{i},m_{i}\in \!F_{p}}$

MMH* は MAC のセキュリティ要件を満たし、Ana と Bob が認証された方法で通信できるようにします。彼らは秘密鍵x を持っています。Charles が Ana と Bob の会話を聞いて、そのメッセージを Bob への自分のメッセージに変更し、Ana からのメッセージとして渡したいとします。そのため、Charles のメッセージm'と Ana のメッセージm は少なくとも 1 ビット異なります (例)。 ${\displaystyle m_{1}\neq m'_{1}}$

チャールズは関数が形式であることを知っており、アナのメッセージm を知っているが、キーxは知らないと仮定すると、チャールズがメッセージを変更したり、独自のメッセージを送信したりできる確率は、次の定理によって説明できます。 ${\displaystyle g_{x}(m)}$

定理1 ^[4] :MMH*族は∆普遍的である。

証拠：

を と取り、 を2 つの異なるメッセージとします。一般性を失うことなく と仮定します。すると、 の任意の選択に対して、 ${\displaystyle a\in F_{p}}$${\displaystyle m,m'}$${\displaystyle m_{1}\neq m'_{1}}$${\displaystyle x_{2},x_{3},\ldots ,x_{s}}$

${\displaystyle {\begin{aligned}{\Pr }_{x_{1}}[g_{x}(m)-g_{x}(m')\equiv a\mod p]&={\Pr }_{x_{1}}[(m_{1}x_{1}+m_{2}x_{2}+\cdots +m_{k}x_{k})-(m'_{1}x_{1}+m'_{2}x_{2}+\cdots +m'_{k}x_{k})\equiv a\mod p]\\&={\Pr }_{x_{1}}[(m_{1}-m'_{1})x_{1}+(m_{2}-m'_{2})x_{2}+\cdots +(m_{k}-m'_{k})x_{k}]\equiv a\mod p]\\&={\Pr }_{x_{1}}[(m_{1}-m'_{1})x_{1}+\textstyle \sum _{k=2}^{s}(m_{k}-m'_{k})x_{k}\equiv a\mod p]\\&={\Pr }_{x_{1}}[(m_{1}-m'_{1})x_{1}\equiv a-\textstyle \sum _{k=2}^{s}(m_{k}-m'_{k})x_{k}\mod p]\\&={\frac {1}{p}}\end{aligned}}}$

上記の定理を説明するために、素数を として体を表す。 の元を とすると、の確率 は${\displaystyle F_{p}}$${\displaystyle p}$${\displaystyle F_{p}=\underbrace {{\big \{}0,1,\ldots ,p-1{\big \}}} _{p}}$${\displaystyle F_{p}}$${\displaystyle 0\in F_{p}}$${\displaystyle x_{1}=0}$

${\displaystyle {\Pr }_{x_{1}\in \!{F_{p}}}(x_{1}=0)={\frac {1}{p}}}$

実際に計算する必要があるのは

${\displaystyle {\Pr }_{(x_{1},\ldots ,x_{k})\in \!{F_{p}^{k}}}(g_{x}(m)\equiv g_{x}(m')\mod p)}$

しかし、

${\displaystyle {\begin{aligned}{\Pr }_{(x_{1},\ldots ,x_{k})\in \!{F_{p}^{k}}}(g_{x}(m)\equiv g_{x}(m')\mod p)&=\sum _{(x_{2},\ldots ,x_{k})\in \!{F_{p}^{k-1}}}{\Pr }_{(x_{2}^{'}\cdots ,x_{k}^{'})\in \!{F_{p}^{k-1}}}({x_{2}=x_{2}^{'}},\ldots ,{x_{k}=x_{k}^{'}})\cdot {\Pr }_{x_{1}\in \!F_{p}}(g_{x}(m)\equiv g_{x}(m')\mod p)\\&=\sum _{(x_{2},\ldots ,x_{k})\in \!{F_{p}^{k-1}}}{\frac {1}{p^{k-1}}}\cdot {\frac {1}{p}}\\&=p^{k-1}\cdot {\frac {1}{p^{k-1}}}\cdot {\frac {1}{p}}\\&={\frac {1}{p}}\end{aligned}}}$

上記の証明から、は1 ラウンドの攻撃者の衝突確率であるため、平均してp 回の検証クエリで 1 つのメッセージが受け入れられることになります。衝突確率を下げるには、大きなp を選択するか、 n 個の独立したキーを使用してn個の MAC を連結して衝突確率] が になるようにする必要があります。この場合、キーの数はn倍に増加し、出力もn倍に増加します。 ${\displaystyle {\frac {1}{p}}}$ ${\displaystyle {\frac {1}{p^{n}}}}$

HaleviとKrawczyk ^[4]は、と呼ばれる変種を構築します。この構築は、32ビット整数と素数整数で機能します。実際には、素数pは、 を満たす任意の素数に選択できます。このアイデアは、素数またはを使用するというCarterとWegmanの提案から採用されました。 ${\displaystyle \mathrm {MMH} _{32}^{*}}$${\displaystyle p=2^{32}+15}$${\displaystyle 2^{32}<p<2^{32}+2^{16}}$${\displaystyle 2^{16}+1}$${\displaystyle 2^{31}-1}$

${\displaystyle \mathrm {MMH} _{32}^{*}}$は次のように定義されます。

${\displaystyle \mathrm {MMH} _{32}^{*}=\left\{g_{x}(\left\{0,1\right\}^{32})^{k}\right\}\to F_{p},}$

ここで、は（つまり、バイナリ表現） を意味します。${\displaystyle \left\{0,1\right\}^{32}}$${\displaystyle \left\{0,1,\ldots ,2^{32}-1\right\}}$

関数は以下のように定義されます。 ${\displaystyle g_{x}}$

${\displaystyle {\begin{aligned}g_{x}(m)&\ {\overset {\underset {\mathrm {def} }{}}{=}}\ m\cdot x{\bmod {(}}2^{32}+15)\\&=\textstyle \sum _{i=1}^{k}m_{i}\cdot x_{i}{\bmod {(}}2^{32}+15)\end{aligned}}}$

どこ

${\displaystyle x=(x_{1},\ldots ,x_{k}),\ m=(m,\ldots ,m_{k})}$

定理1により、衝突 確率は約 であり、 の族はϵ -ほぼ ∆として定義でき、 で普遍的です。 ${\displaystyle \epsilon =2^{-32}}$${\displaystyle \mathrm {MMH} _{32}^{*}}$${\displaystyle \epsilon =2^{-32}}$

メッセージとキーベクトルの長さを表すkの値には、いくつかの効果があります。

• k を超えるコストのかかるモジュラー削減は乗算と加算の演算であるため、 k が増加すると速度が低下するはずです。
• キーx はk 個の32 ビット整数で構成されているため、 kを増やすとキーが長くなります。
• システムを破壊する確率は k であり、k を増やすとシステムを破壊しにくくなります。${\displaystyle 1/p}$${\displaystyle p\approx 2^{k}}$

^{以下は、1997年にHaleviとKrawczykによって設計されたMMH [4]}のさまざまな実装のタイミング結果です。

• AIX が動作する150 MHz PowerPC 604 RISC マシン

• Windows NTが動作する 150 MHz Pentium-Pro マシン

• Linuxが動作する 200 MHz Pentium-Pro マシン

• ユーマック
• 仮想MAC
• ポリ1305-AES