数理解析研究所講究録1106 巻 1999 年 66-80

66

ハッシュ関数の構成法に関する $-$ 考察

A
$+$

井上徹、

$\mathrm{M}\mathrm{S}\mathrm{L}+$Toru INOUE(高度移動通信セキュリティ技術研究所)

現在使われているハッシュ関数には$\mathrm{S}\mathrm{H}$A,$\mathrm{S}\mathrm{H}$A–l,$\mathrm{M}\mathrm{D}4$.

$\mathrm{M}\mathrm{D}5$

などがある。 これらのハッシュ関数用の特定のアルゴリズムを用いる方式には演算スピードはそれなりに高速であるが、 いくつかのアタック (攻撃) が発表されている方式もある。 1)2) 3)$-$ 方、

ブロック暗号を圧縮関数として繰

4) 5)
り返し用いてハッシュ関数を得る方法に Dav es-Meyer の方法がある。
$\mathrm{i}$安全性改善策として 2 次元 Cellular Automaton を使う方法も報告されてい7)
しかし $-$ 般の 64 ビッ ト
る。 6) また種々の解析結果も報告されている。

ブロック暗号をそのまま用いるとバースデーアタックにより平均 232 の試行で衝突 (coll言$\overline{\mathrm{D}}$$\mathrm{i}\mathrm{s}\mathrm{i}$on) が生じてしまい、 これは今日では安全性が高いとはえない。 ブロック暗号をハッシュ関数に用いる利点としてブロック暗号の$\mathrm{s}$

安全性が保証されていればそれを用いたハッシュ関数も安全性が保証されると言われている。 8)9)

また、 単 $-$ のハッシュモー ドを多重の($\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}$iple)

ハッシュモードに拡張しても安全性は保たれる。 9) さらにデータの暗号化部で使う暗号アルゴリズムのハードウェアまたはソフトウェア資源が共用で

67

きるメリットがある。 本稿では Knud$\mathrm{s}$en らの方法を大幅に改良し、 効率の良いハッシュ値を得る方法を提案する。

1.

はじめに

本稿では安全性が保証されたブロック暗号を用いることとし、 以下の仮定をおくことにする。
1)

単 $-$ のハッシュモードは安全$(\mathrm{s}\mathrm{e}\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{e})$2)

単 $-$ のハッシュモードを解読$(\mathrm{b}_{\Gamma}\mathrm{e}\mathrm{a}\mathrm{k})$

である。

する短絡

$(\mathrm{s}\mathrm{h}\mathrm{o}\mathrm{r}\mathrm{t} \mathrm{c}\mathrm{u}\mathrm{t})$

が存在

しない。
3)

ブロック暗号の安全性が保証されていればそれを用いたハッシュ関数も安全性が保証される。

4)

文書は十分に長いとする。

しかしながら、 一般の 64 ビット暗号をそのまま用いたのでは衝突 (バースデーアタックまたは$\mathrm{c}\mathrm{o}11\mathrm{i}\mathrm{S}\mathrm{i}$on )が平均 232 回の試行で生じ、 これは今日の暗号事情ではけっして安全性が高いとはいえない。 9)

誤り訂正符号を用いて衝突耐性を向上させる手法に Knud en L. and$\mathrm{s}$B. の手法がある。 8) 9) 彼らの手法は 4 元
衝突を 2$\mathrm{m}/2$(non-b nary)$\mathrm{i}$から2$(\mathrm{d}-1)\mathrm{m}/2$($\mathrm{n},$$\mathrm{k}$,d)$\mathrm{p}_{\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{e}\mathrm{e}}1$

線形符号を用いてに改善している。 しかし彼らは非 2 元

符号しか構成に用いておらず、 安全性の面でもハードウェア

構成の面でも改良の余地がある。 筆者はた構成法を試み,$\mathrm{B}\mathrm{C}\mathrm{H}$

符号のような 2 元符号を用いその有用性を示す。 更に畳み込み符号を用いた手法も考察し、 ブロック符号と同じ性能条件で設計するとき、 拘束長$\mathrm{N}$の畳み込み符号68はブロック符号を用いた時の 1$/\mathrm{N}$の数の Dav es-Meye$\mathrm{i}$関数で装置化でき$\mathrm{r}$ることを示す。

2. ハッシュ関数

任意の長さの文書をある決められた長さに圧縮するためには暗号論的ハッシ
ュ関数がもちいられる。 衝突とは’$\mathrm{x}\neq \mathrm{X}$なる場合に$\mathrm{h}$(X).

$=\mathrm{h}$$(\mathrm{x}$’$)$となることである。 衝突に対するハッシュ関数の耐性の定義には、 弱い耐性

collと強い耐性がある。 弱い耐性 (Weakジ耐性 ($\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{i}$$\mathrm{p}\mathrm{r}\mathrm{e}-\mathrm{i}$

mage

mage

$\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{s}\iota$$\mathrm{r}$anes$\mathrm{c}\mathrm{e}$$\mathrm{i}\mathrm{s}\mathrm{t}$)$\mathrm{i}\mathrm{s}\mathrm{i}$’$\mathrm{x}$$\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{s}\mathrm{t}$とはプレイメー(2nd-と呼ばれるものである。
$\mathrm{H}=\mathrm{h}$$(\mathrm{x})$に対して$\mathrm{h}(\mathrm{x}$’$)$を見つけることがどのくらい困難かということである。

セカンドプレイメージ耐性とは与えられた文書入力$=\mathrm{h}$)ance) あるいはセカンドプレイメージ耐性

プレイメージ耐性とは与えられたハッシュ値
なる

on

(x)

$=\mathrm{h}$$(\mathrm{x}$’$)$を持つ第 2 の文書入力

度困難かということである。 つまり、 文書があったとき、 同じハッシュ値

ことがいかなる文書

ばそのハッシュ関数$\mathrm{x}$$\mathrm{h}$$\mathrm{H}=\mathrm{h}$$\mathrm{x}$(X)’$\mathrm{x}$$\mathrm{x}$に対してハッシュ値を見つけることがどの程とそのハッシュ値になる別の文書に対しても困難であり、 平均$\mathrm{H}$$\mathrm{W}$のセカンドプレイメージ耐性は$\mathrm{H}=\mathrm{h}$

’

(X)

を見つける

$\mathrm{x}$回の試行を必要とすれ$\mathrm{W}$であるという。 本稿

では以後プレイメージとセカンドプレイメージとは数値として同じであるので同等に扱い区別しない。
強い耐性 ($\mathrm{s}\mathrm{t}\mathrm{r}$ong$\mathrm{c}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{i}$on$\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{S}\mathrm{t}$) とは、衝突耐性 ($\mathrm{c}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{i}_{\mathrm{S}}$on$\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{S}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{e}$またはバースデーアタックに対する耐性と呼ばれるものである。

$\mathrm{h}$

(X)

)

$=$

69

(X’ )

$\mathrm{h}$となるいかなる文書入力ペアー$(\mathrm{X}\text{、} \mathrm{x} ’ ;\mathrm{x}\neq \mathrm{x} ’ )$を見つけることがどの程度困難かということである。 すなわち、 ハッシュ値が同じになる異なる文書の組を見つけるために、平均$\mathrm{W}$回の試行を必要とするならば、そのハッシュ関数のバースデーアタックに対する耐性は$\mathrm{W}$であるという。 通常単に衝突耐性と言うときはこの強い耐性を言う。
$\mathrm{m}-$ビットブロック暗号 ($\mathrm{D}\mathrm{E}\mathrm{S}$などは 64 $-$ ビットブロック暗号である)に基くハッシュ関数のハッシュレート (たは復号化で処理される$\mathrm{E}\mathrm{k}$$\text{ッ}$を$(\cdot)$

ト鍵を$\mathrm{m}-$$\mathrm{h}$$\mathrm{F}\mathrm{E}$A$\mathrm{L}$$\mathrm{h}$に対するコリジョン ($\mathrm{m}-$$\mathrm{t}\mathrm{e}$)とは、 1 回の暗号化まの暗号化が必要である。

$8$

)

$9$

を Dav

$\mathrm{i}\mathrm{e}\mathrm{s}$$\mathrm{c}\mathrm{o}1\iota \mathrm{i}_{\mathrm{S}\mathrm{i}}$

-Meye

on)

$\mathrm{r}$$\mathrm{m}-$ビ関数と呼ぶ。

を見つけるには安全なビットブロックの) 約 2に対するプレイメージ ($\mathrm{h}$aのように 64 ビッ トブロック暗号で 64 ビット

ブロック暗号を用いている限り (化が、 又関数$\mathrm{h}\mathrm{r}$ビットメッセージブロックの数で定義される。

鍵を用いる暗号が該当する。 圧縮関数
『仮定 1: 関数asビッ トブロック暗号の暗号アルゴリズムとし、 そのとする。

$\mathrm{K}$$\mathrm{m}-$$\mathrm{h}$$\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{i}$mage)$\mathrm{m}/2$回の暗号を見つけるには約 2$\mathrm{m}$回)$\mathrm{B}$

メッセージ

ッシュ値
$\mathrm{H}1=\mathrm{h}$$\mathrm{M}1\text{、}$$\mathrm{H}\mathrm{i}-1$

ハッシュ

(

$\mathrm{h}$

ash)

値

$\mathrm{H}1$

およびひとつ前の ($(\mathrm{M}1 , \mathrm{H}1-1)$

1 までのハシュ値と時刻
を、

ouS)

ハ

の間には
$=\mathrm{E}\mathrm{M}1$$(\mathrm{H}1-1)$が成り立つ。 ここで $+$ は法 2 加算である。

$\mathrm{E}_{\mathrm{K}’}(\cdot)$$\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{v}\mathrm{i}$$\mathrm{i}$$+\mathrm{H}1-1$$\mathrm{H}\mathrm{i}$は文書の始まりから時刻$\mathrm{i}-$のメッセージとの累積加算値である。

a $>0$ なる aX$\mathrm{m}-$ビッ ト鍵$\mathrm{K}$を使う$\mathrm{m}-$

ビッ トブロック暗70号アルゴリズムとする。

とにより互いに異なる Dav($\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{i}$Pl$\mathrm{e}$Davィン変換して$\ldots$$\mathrm{H}2\text{、}$($\mathrm{P}^{\mathrm{r}\mathrm{e}\mathrm{i}}$.

$\mathrm{i}\mathrm{e}$$\mathrm{i}\mathrm{e}$s-Meyes-Meyer) 関数は$\mathrm{h}\mathrm{n}$$\text{、}$個の)$\mathrm{Y}\mathrm{i}$$\mathrm{m}-$ビッ トメッセージ入力をアフへ写像して入力する。 出力はの連接となる。 コリジョン ($\mathrm{H}_{\mathrm{n}}$を鍵を互いに異なる値を取るこ関数にする。 多重デヴィスマイヤ一$\mathrm{r}$$\mathrm{r}$個のペアー (X 1 ,$\mathrm{n}$...

$\mathrm{h}2^{\text{、}}$$\mathrm{h}1^{\text{、}}$$\mathrm{c}\mathrm{o}11\mathrm{i}\mathrm{s}\mathrm{i}$on)またはプレイメージ(X 1 ,mage) アタックにおいて入力ブロックを構成する

ペアーと異なるなら

2 つの関数(X$\mathrm{h}\mathrm{i}$(X$\mathrm{h}$$\mathrm{i}$,$\mathrm{Y}\mathrm{i}$)

攻撃可能という時は、 関数
も、 関数$\mathrm{h}\mathrm{j}$,$\mathrm{i}$)$\mathrm{Y}\mathrm{i}$

と

は積極的
(X

$\mathrm{h}\mathrm{j}$$\mathrm{j}$,$\mathrm{Y}$(Xの変数パラメータ$\mathrm{j}$.

$\mathrm{Y}$$\mathrm{Y}\mathrm{i}$)が元のと呼ばれる。 又、$(\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e})$は独立に ( ndependen:)$\mathrm{i}$(Xの変数パラメータ$\mathrm{h}\mathrm{i}$$\mathrm{H}1\text{、}$$\mathrm{i}$.

$\mathrm{Y}\mathrm{i}$)$\mathrm{t}\mathrm{l}\mathrm{y}$

)

が変わって

: ) は変わらないような関数をいう。

仮定 2: 多重デヴィスマイヤー (するコリジョン

(ったとする。

を$\mathrm{P}$$\mathrm{c}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{i}_{\mathrm{S}\mathrm{i}}$$\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{i}$on)$\mathrm{m}\mathrm{u}\mathrm{l}\uparrow \mathrm{i}\mathrm{p}\mathrm{l}\mathrm{e}$$\mathrm{p}\mathrm{r}\mathrm{e}$ve な関数の数とし、s-Meyer)($\mathrm{P}-\mathrm{V}$$\mathrm{c}\mathrm{o}11\mathrm{i}_{\mathrm{S}}\mathrm{i}$image) が起こるためには少なくとも 2号化がそれぞれ必要である。

$\mathrm{i}\mathrm{e}$あるいはプレイメージ (の最大数とする。 このコリジョン
(

Dav

$8$

)

$9$

on)

$\mathrm{v}\mathrm{m}/2$$\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{i}$の圧縮関数に対mage) が見つかを独立に攻撃可能な関数
あるいはプレイメージ,

あるいは 2$\mathrm{v}\mathrm{m}$回の暗)$\mathrm{H}$

3. 誤り訂正符号を用いた構成法
3. 1. Knudsen
Knud en$\mathrm{s}$$\mathrm{L}$, and$\mathrm{L}$, and Preneel$\mathrm{p}_{\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{e}\mathrm{e}}1\mathrm{B}$[定理 3]: 長さ$\mathrm{n}\text{、}$$\mathrm{B}$による構成法による誤り訂正符号を用いた構成法を紹介しよう。

情報シンボル数$\mathrm{k}\text{、}$最小距離$\mathrm{d}\text{、}$(a $+1$ )$\mathrm{k}>\mathrm{n}$但71

し a $\geqq 1$ 且つ $\mathrm{m}>>1\mathrm{o}\mathrm{g}2\mathrm{n}$ なる$\mathrm{G}\mathrm{F}$$(2 \mathrm{a}+1)$(

上の$\mathrm{n}\text{、}$d) 符号$\mathrm{k}\text{、}$で入力ブロックを符号化したとする。 すると仮定 2 が成り立つ限り圧縮関数に対するコリジョン (collision)を見つけることは少なくとも 2

2 回の暗号化が、 あるいはプレイメ一
とも 2

(証明)

$(\mathrm{d}-1)\mathrm{m}$$\mathrm{H}\mathrm{i}-1\mathrm{n}$$\mathrm{k}$までとブロックからなる。 ここで1)(preimage) を見つけるには少なく回の暗号化が必要である。 9) 9

: 入力は (a+1)

値 $\mathrm{H}1-11\text{から}$ .

$\sqrt[\backslash ]{}\backslash \backslash ^{\backslash }$$(\mathrm{d}-1)\mathrm{m}/$個の引き続くビッ トは個の$\mathrm{r}$ビッ トブロックからなる。

個のメッセージブロック$\mathrm{r}=2\mathrm{k}$$\mathrm{G}\mathrm{F}$$\mathrm{m}$–$\mathrm{n}>0$$(2 \mathrm{a}+1)$$\mathrm{M}1$か日$\mathrm{n}$個の連鎖$\mathrm{M}\mathrm{r}$である。 入力ブロックのの$\mathrm{k}$までの(a $+$

個の要素を与えるように構成される。

これら要素は ($\mathrm{n}$$\mathrm{n}$,$\mathrm{k}$

,

d)

符号を使い

$\mathrm{G}\mathrm{F}$$(2 \mathrm{a}+1)$の$\mathrm{n}$個の元となる。

個の関数の 1 つに対して (a+1) ビットの入力を表す。 個々のビッ トは$\mathrm{G}\mathrm{F}$$(2 \mathrm{a}+1)$の上のベク トル空間として$\mathrm{G}\mathrm{F}$$(2 \mathrm{a}+1)$ .

の元を表している。

この構成は $\mathrm{v}=\mathrm{d}-1$ なる値に対して仮定 2 に対する条件が満足される。
(a+1)$\mathrm{k}$個の入力の線形変換によって圧縮関数を得ることが可能となる。

ここで最初の$\mathrm{k}$個の関数がお互いに独立である。 符号語は最後の関数の少なくとも $\mathrm{d}-1$ 個が最初の関数の入力に依存している。

$\mathrm{n}-\mathrm{k}$個の$\mathrm{n}-\mathrm{k}\geqq \mathrm{d}$$-1$ だから定理 3 はおのずと証明される。 (証明終)このhash 関数は

1)$(\mathrm{k}/\mathrm{n})$$\mathrm{n}$$\mathrm{m}$ビッ トの内部メモリーが必要で hash rate は (a $+$$-1$ である. すなわち、 例えば距離 3 の誤り訂正符号を使う

72

ことによってコリジョン (collision)
メージ(preimage)

$-$

を2

$\mathrm{m}$から 22$\mathrm{m}$を2$\mathrm{m}/2$

から 2$\mathrm{m}$に、 あるいはプレイに改善し、 安全な hash 関数を簡単に構成できる。

3.2.

ブロック符号による構成法

また新たに$\mathrm{m}$$\mathrm{B}\mathrm{C}\mathrm{H}$符号などの 2 元符号を用いる方式 10) が提案され、 1 つのの 2 つの符号語を割り当てる構成

ビッ ト入力に 2 元符号 (binary code)にして 2 元符号を使えるような構成にしている。

4. 提案方式
前項 (3.

2.

項)の改善策はガロア体の符号を 2 元の符号に置き換えてはいるものの、 初期値を除くと 1 単位時間前のハッシュ値だけで構成される個の$\mathrm{m}-$ブロックから構成されている 1 列目の$\mathrm{B}\mathrm{C}\mathrm{H}$$\mathrm{n}$

符号語は前の時刻のハッシュ値だけを符号化する事になり、 ここには新しいメッセージの情報は入力されない。 従って、 この列が攻撃 (アタック)

されることはなく、 攻撃に対する符号化をする必要もない。 符号化は 2 列目のを行い攻撃から守ればよい。 ベク トル X
みなせる)$\mathrm{i}$$\mathrm{n}$個の$\mathrm{m}-$ブロックだけは暗号器が完全 (乱数オラクルとであれば乱数と見徹せる。 関数$\mathrm{h}\mathrm{i}$の$\mathrm{Y}\mathrm{i}$だけ誤り訂正符号化する。

このように構成しても圧縮関数に対するコリジョン (collision) を見つける
ことは少なくとも

2$(\mathrm{d}-1)\mathrm{m}/2$回の暗号化が、 あるいはプレイメージ(preimage) を見つけるには少なくとも 2る。

$(\mathrm{d}-1)\mathrm{m}$回の暗号化が必要であ73

4.1. ブロック符号を用いた方法:[定理 4]$\mathrm{k}$個のメッセージブロックを

トブロックを作り、 それを
2 個の$\mathrm{m}-$るとする。

個の Dav$\mathrm{i}\mathrm{e}$ベク トル$\mathrm{n}$個のビッ トブロックにして$\mathrm{n}$個のブロックにs-Meye$\mathrm{Y}\mathrm{i}$$\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{v}\mathrm{i}$ous$\mathrm{c}\mathrm{o}11\mathrm{i}\mathrm{S}.\mathrm{i}$

符号化して

ashe

$\mathrm{h}$$\mathrm{n}-\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{i}_{\mathrm{P}}[\mathrm{e}$on または関数が積極的ならば$\mathrm{r}$$\mathrm{E}\mathrm{C}\mathrm{C}$$\mathrm{d}$

Dav

value

$\mathrm{i}\mathrm{e}$$\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{i}$s-Meye個の$\mathrm{m}-$と並べて、$\mathrm{r}$ビッ$\mathrm{n}\cross$

関数に入力すmage が起こったとし$(\mathrm{d}-1)$$\mathrm{P}-$$\mathrm{s}$$\mathrm{n}$$\mathrm{P}$

個のメッセージ入力

が独立で $\mathrm{d}-1$ 個のメッセージ入力ベク トル$\mathrm{Y}1$

が従属であ

る。
』

(証明)

: ベク トル立である。 最後の$\mathrm{Y}\mathrm{i}$の$\mathrm{n}-\mathrm{k}$$\mathrm{n}$ビッ トは少なくとも最初の$\mathrm{k}$ビッ トが互いに独

ビッ トの少なくとも $\mathrm{d}-1$ 個が最初の入力に依存している。 $\mathrm{n}-\mathrm{k}\geqq \mathrm{d}-1$ だから定理 4 はおのずと証明される。 (証明終)以上の議論は定常状態で入力ベクトル X1 が乱数オラクルの出力とみなせる
限り成り立つ。 しかし、 初期状態においては鍵入力、 メッセージ入力ともに任意の値を取りうる。従って、初期入力ベクトルについては Knudsen, L. andPreneel, B. に基づいて入力せねばならない。
[仮定 2 の拡大 (extension)] : 初期状態 :Multiple-Davies-Meyer の圧縮関数に対するコリジョンあるいはプレイメージが見つかったとする。
active な関数の数、$\mathrm{f}\mathrm{n}$$\mathrm{P}-\mathrm{V}$を独立に攻撃可能な関数の数とする。

$\mathrm{f}1$,$\mathrm{P}$$\cdots$

を,を同時に衝突が起こっている Davies-Meyer 関数とする。 個々の関数には$\mathrm{f}$:(X 1 ,$\mathrm{Y}1$)$=\mathrm{E}\mathrm{x}1$$(\mathrm{Y}\mathrm{i})$$+\mathrm{Y}$:74が成り立つ。 これらは異なる値を個の$\mathrm{m}$$\ulcorner\log_{2}\mathrm{n}^{\urcorner}$

個の鍵を固定して得られる。 2

ピット初期値入力をもつ圧縮関数を考えそれがアフィン変換により個のペアー (X 1 ,: ) に写像されるすべての圧縮関数の出力が 2$\mathrm{Y}$ブロックに依存する。 すなわち変換マトリクスは階数 2定常状態 :. 個の$\mathrm{m}$$\mathrm{k}$個の$\mathrm{m}$ち変換マトリクスは階数$\{\mathrm{Z}1’\}$

この時数$\mathrm{f}1$,$\cdots$,$\mathrm{f}\mathrm{n}$’$\{\mathrm{f}\mathrm{j}\}$で$\mathrm{Z}1\neq \mathrm{Z}\mathrm{i}$$\mathrm{n}$個のブロックに依存する。 すなわ$\mathrm{v}\mathrm{m}/2$個の関数の組をとなる。 これら$\mathrm{Y}0$

態のメッセージビットは$\mathrm{r}=\mathrm{k}$のうち$\{\mathrm{Z}\mathrm{i}\}$と$\mathrm{n}$$\mathrm{P}$とする。 関個の関数$\mathrm{m}$$\{\mathrm{f}\mathrm{j}\}$

ビッ トのうちビットにして初期値 X$\mathrm{n}-\mathrm{k}$$\mathrm{r}=2\mathrm{k}-\mathrm{n}$$\{\mathrm{f}\mathrm{j}\}$回の暗号化が、 また、 pre-image に回の暗号化が必要である。 従って鍵入力ビットを初期値

ジビットは$\mathrm{P}$$\mathrm{P}-\mathrm{V}$ットを予め誤り訂正符号で符号化し$\mathrm{n}-\mathrm{k}$:$\mathrm{Y}$個の関数に等しい出力を与えるとする。

に依存するに対する同時衝突は少なくとも 2$\mathrm{v}\mathrm{m}$個のベクトルに起こった時、 すなわち 2 つの入力値のマトリクスの階数は対しては 2$\mathrm{k}$$\mathrm{n}$$\mathrm{k}$を持つ。

$\mathrm{k}$の異なった組がすべての$\mathrm{P}\leqq \mathrm{n}$個のビット入力を持つ初期値状態を除く定常状態においてに写像されるすべての圧縮関数の出力が$\mathrm{n}$を持つ。

$\mathrm{k}$ビット入力を持つ圧縮関数のアフィン変換により同時衝突が$\mathrm{k}$$\mathrm{k}$$0$$\mathrm{k}$ビを与え、 残りビットに配置する。 すなわち初期状

ビットとなる。 2 番目以降のメッセ一ビットとなる。

すなわち $\mathrm{d}-1$ 個の$\mathrm{Y}1$

ベク トルだけが従属であることが要求されるので定常状態においてはベクトル[補題 5]: 符号長$\mathrm{n}\text{、}$$\mathrm{Y}\mathrm{j}$だけを誤り訂正符号化すればよい。

情報記号数$\mathrm{k}\text{、}$最小距離$\mathrm{d}$の 2 元符号を考える。 デ75

ビスマイヤー (Davの時刻の$\mathrm{n}$$\mathrm{i}-1$個の$\mathrm{m}-$ブロック数はの$\mathrm{n}$$\mathrm{i}\mathrm{e}$s-Meye r) の段数を個のハッシュ値 (とする。 時刻を$\mathrm{n}$$\mathrm{i}$ou$\mathrm{s}\mathrm{h}$asva$\mathrm{h}$$\mathrm{l}\mathrm{u}\mathrm{e}$$\mathrm{i}$)と仮定すると前はすべて 1 列目

ブロックに戻されるから、 メッセージブロックのため使われる$\mathrm{k}$となる。 Has$\mathrm{h}$$\mathrm{r}$a$\mathrm{t}\mathrm{e}$(ハッシュ率)は$\mathrm{k}/\mathrm{n}$となる。

$\ovalbox{\tt\small REJECT}$

これは元々誤り訂正符号の持っている符号化率に等しい。 すなわち効率が大幅に改善されることになる。 運用上の注意としては初期値に’n$\mathrm{X}\mathrm{m}$ビットの鍵の初期値が必要である。

新しい構成法は 2 元符号の 1 つの符号語によってある$\mathrm{m}$$\mathrm{n}$個のペアー入力の片側でビッ トブロックに入力される。

2 元符号を使った例と Knudsen らの結果とを比較のため表でしめす。
表12 元の符号による方法と従来法との比較

Non-binary の符号は Knudsen L. and Preneel B. 8)らの結果による。

$9\rangle$

この方法は Knudsen L. and Preneel B. と比べてフィードバックされたハッシ

ュ値を誤り訂正符号化しない分だけ効率$\mathrm{B}\mathrm{C}\mathrm{H}$($\mathrm{h}$as$\mathrm{h}\mathrm{r}$符号などの 2 元符号を使うため既存の高速a$J\backslash$$\mathrm{t}\mathrm{e}$)が改善されており、

一ドウェアなどが流用で76きる。 更に$\mathrm{c}\mathrm{o}11\mathrm{i}\mathrm{s}\mathrm{i}$る要望があればon を $\mathrm{m}=64$ として 22 $\mathrm{m}=2128$ に $-$ 回の割合に抑えの$\mathrm{d}=5$$\mathrm{B}\mathrm{C}\mathrm{H}$

符号を選べば良い。

以上の説明からわかるように本稿によれば 2 元符号を使うため、 ガロア体の演算をしなくてすみ、 且つ、 より安全性の高いハッシュ値を得ることができる。

畳み込み符号を用いた構成法 11)

4. 2.

ブロック符号では誤り訂正能力を大きくするには符号長が $-$ 般に大きくなり演算が複雑になる傾向があった。 又、 符号長分だけのデビスマイヤーの段数が必要になるため多くのデビスマイヤー関数を装置化しておく必要がある。
本稿ではデビスマイヤー (Dav

み込み符号の小ブロック長$\mathrm{n}0$$\mathrm{i}\mathrm{e}$s-Meyer)の基本構成である段数入力を畳に選ぶことにより又、 拘束長$\mathrm{N}$とするとき$\mathrm{N}$段に分けて入力することによりデビスマイヤーのサイズをブロック符号を使った時の符号長$\mathrm{n}$から畳込み符号の小ブロック長法を示す。 すなわち、 デビスマイヤー (Dav数は 1$/\mathrm{N}$$\mathrm{i}\mathrm{e}$$\mathrm{n}0$まで小さくできる構成

s-Meyer) 関数の基本構成の段まで減少する。

構成は畳み込み符号器と多段デビスマイヤーハッシュ関数とたハッシュ値を蓄積する$\mathrm{F}$I$\mathrm{F}\mathrm{O}$$\mathrm{N}$段に連接されメモリーによって特徴付けられる。 畳み込

み符号は大きく分けて 2 種類の符号器がある。 例で説明しよう。 畳み込み符
号の小ブロック長き($\mathrm{n}0$

しよう。

,

$\mathrm{k}0$,$\mathrm{n}0$N)

ビッ ト、 小情報記号ビッ ト$\mathrm{k}0^{\text{、}}$

拘束長$\mathrm{N}$段とすると畳み込み符号と呼ぶ。 定理 4 を畳み込み符号にも適用

77[定理 6]:$\mathrm{n}_{0}$個の prev

を畳み込み符号化してビットブロックを束長$\mathrm{N}$

とするとき

こったとし

$\mathrm{P}$ous hashed values と$\mathrm{n}0$個の$\mathrm{m}-$$\mathrm{n}0-\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{i}\mathrm{p}\mathrm{l}\mathrm{e}$$\mathrm{N}\cross \mathrm{n}0$

個の Dav

クトルが独立で$\mathrm{i}$$\mathrm{d}-1$

運用上の注意としては$\mathrm{i}\mathrm{e}$$\mathrm{r}$個のメッセージブロック

ビッ トブロックを作りDav$\mathrm{i}\mathrm{e}$s-Meye個のブロックにs-Meye$\mathrm{k}0$$\mathrm{r}$$\mathrm{n}0\cross 2$$-$ タの最後に$\mathrm{N},$$\mathrm{c}\mathrm{o}11\mathrm{i}\mathrm{S}\mathrm{i}$on または関数が積極的ならば$\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{i}$$\mathrm{P}-\mathrm{d}+1$

mage が起個の入力ベ個の入力ベクトルが従属である。]$\mathrm{n}0\cross \mathrm{m}$ビッ トの鍵初期値が必要である。

. 全長$(\mathrm{N}-1)$$\mathrm{N}\cross \mathrm{n}0\cross \mathrm{m}$$\cross \mathrm{k}0\cross \mathrm{m}$$/\mathrm{N}$倍と小さく

ビッ トのハッシュ値を得るためにはデ

ビッ トの

$0$

を入力してデータを完全に符号器から出力させる必要がある。 したがって符号化のため$\text{ッ}$$\mathrm{m}-$関数に入力するとする。 拘

畳込み符号を用いると多重デビスマイヤー関数のサイズは 1なるが、 拘束長個の$(\mathrm{N}-1)$$\cross \mathrm{m}$ビトの遅延が起こる。

提案方式による $-$ 般的なハッシュ関数は多重デビスマイヤー関数の入力側で$\mathrm{n}0\cross 2$の 2 次元配置を構成して第 1 の列の単位時刻前の個の$\mathrm{m}-$$\mathrm{n}0$$\mathrm{n}0$の$\mathrm{m}-$

ビッ トブロックに 1個のハッシュ値をフィードバックし新しいメッセージ

ビットブロックを符号化して$\mathrm{n}0$個の$\mathrm{m}-$$\mathrm{k}0$

ビットブロックにしたの

ち、 入力する方式となる。

ワイナーアッシュ符号13)を使った場合と$\mathrm{C}\mathrm{S}\mathrm{O}\mathrm{C}$

Self-Orthogonal Codes : 自己直交畳込み符号)
に示す。

13)

符号

(Convolutionalを使った例を表 2,

3

78

表2

表3

5.

ワイナーアッシュ (Wyner-Ash) 符号による構成例$\mathrm{C}\mathrm{S}\mathrm{O}\mathrm{C}$

符号による構成例

まとめ

誤り訂正符号を用いてハッシュ関数を構成する Knudsen L. and Preneel B.
を改良して2 元の符号を用いる方法、

畳み込み符号を用いる方法を開発し、 その構成を示した。 近年ブロック暗号の鍵長の安全性が真剣に議論されるようになり、 128 ビット以上の鍵を持つ暗号が主流となりつつある。

14)

このような要請と合わせ既存の手法を組み合わせて安全なハッシ

ュ関数を求める研究がもっと活発になされるべきである。
参考文献$1)\mathrm{D}\mathrm{o}\mathrm{b}\mathrm{e}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{n}$H., ”Cryptanarysis of$\mathrm{M}\mathrm{D}4,$: Fast Software Encryption, LNCS 1039,

D. Goldman, Ed., Spring-Verlag, 1996, pp.53-69.
$2)\mathrm{D}\mathrm{o}\mathrm{b}\mathrm{e}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{n}$H., :Cryptanarysis of$‘ \mathrm{M}\mathrm{D}5$

compress, Presented at the rump session

79of EUROCRYPT’96, May 1996.
$3)\mathrm{K}\mathrm{u}\mathrm{w}\mathrm{a}\mathrm{k}\mathrm{a}\mathrm{d}\mathrm{o}$Hidenori and Tanaka Hatsukazu,” On the One-wayness of the reduced

MD4 compression function”, The 1999 Symposium on Cryptography andInformation Security”, pp.247-250. Kobe, Japan, January 26-29, 1999.
$4)\mathrm{D}\mathrm{a}\mathrm{v}\mathrm{i}\mathrm{e}\mathrm{s}$D.W. and Price W.L.,: Digital Signature-An Update,: Proceedings ofInternational Conference on Computer Communications, Sydney,$\mathrm{O}\mathrm{c}\mathrm{t}$

’

1984,

North Holland: Elsevier, 1985, pp.843-847.
$5)\mathrm{M}\mathrm{a}\mathrm{t}\mathrm{y}\mathrm{a}\mathrm{s}\mathrm{S}.\mathrm{M}.$, Meyer C. H.

and Oseas J.,: Generating Strong One-Way

Functions with Cryptgraphic Algorithm, IBM Technical Disclosure Bulletin,$\mathrm{v}$. $27,$ .
$\mathrm{n}$$6)\mathrm{H}\mathrm{i}\mathrm{r}\mathrm{o}\mathrm{s}\mathrm{e}$$10\mathrm{A}$, Mar. 1985, pp.5658-5659.

Shouichi and Yoshida Susumu,” A one-way hash function based on a

two-dimensional

cellular automaton”, The 20-th Symposium on

Information Theory and Its Applications (SITA97)

pp.213-216, Matsuyama,

Japan, December 2-5, 1997.( In Japanese)$7)\mathrm{M}\mathrm{o}\mathrm{r}\mathrm{i}\iota$a Hikaru, Odagi Hideo and Ohta Kazuo,” Collision search of a hashfunction by using random mapping”, IEICE Trans. Fundamentals, vol. E81A,No. 1, pp.35-40, January 1998.
8) Knudsen L.R.,and Preneel B.,: Hash functions based on block ciphers andquaternary codes, Advances in Cryptology, Proc. Asiacrypto’96, LNCS 1163,
K. Kim, T. Matsumoto, Eds., Springer-Verlag, 1996, pp.77-90$9)\mathrm{K}\mathrm{n}\mathrm{u}\mathrm{d}\mathrm{s}\mathrm{e}\mathrm{n}$L.

and Preneel B. “Fast and secure hashing based on codes,

80

Crypto’97, LNCS1294. pp.485-498, 1997.
$10)\mathrm{I}\mathrm{N}\mathrm{O}\mathrm{U}\mathrm{E}$Toru and TANAKA Hatsukazu, :A Note on Hash Functions Based on

Block Ciphers and Error Correction Code, International Symposium on

Information Theory and its Applications, pp. 127-129., Mexico City
MEXICO, October 14-16,1998“

11) 井上徹、 畳み込み符号を用いたハッシュ関数の法”、 信学技報 I $\mathrm{T}98-55$ , pp. $1- 6,(1999- 01)$$12)\mathrm{L}\mathrm{i}\mathrm{n},$1970,$\mathrm{S},$

–

構成

。

: An Introduction to Error Correction Codes, Englewood Cliffs., N., J.,$\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{p}\mathrm{t}\mathrm{e}\mathrm{r}$10.

13) 川村信–: A
November$\mathrm{E}\mathrm{S}$1998.

参加報告、、 信学会技術報告、ISEC98-41,$\mathrm{p}\mathrm{p}.39\cdot 43$,