誤り訂正符号を用いたハッシュ関数の構成法

全文

(1)Vol. 41. No. 9. Sep. 2000. 情報処理学会論文誌. 誤り訂正符号を用いたハッシュ関数の構成法井. 徹†. 上. ハッシュ関数の構成法には SHA，SHA-1，MD4，MD5 などの特定のハッシュ関数のアルゴリズムによらず，一般的な DES，FEAL，MISTY などのブロック暗号を用いてハッシュ関数を構成する Davies-Meyer の方法がある．しかし一般の 64 ビットブロック暗号をそのまま用いるとバースデーアタックにより平均 232 の試行でコリジョンが生じてしまい，これは今日では安全性が高いとはいえない．Knudsen and Preneel は誤り訂正符号を用いて攻撃の耐性を強化した方式を発表した．この論文では彼らの方法を改良し，2 元の符号を用いてより単純な構成でより効果的にハッシュ関数を実現できることを示す．また，畳み込み符号を用いるとブロック符号に比べて 1/N（ N は畳み込み符号の拘束長の段数）の数の Davies-Meyer の関数で構成でき装置の規模を小さくできることを示す．. A Construction for Hash Function Using Error Correction Codes Toru Inoue† This paper describes hash functions not using specific function such as SHA, SHA-1, MD-4 and MD-5, but the methods based upon m-bit block cipher algorithm, such as DES, FEAL, MISTY, etc. Constructions for hash function based on block cipher use Davies-Meyer compression function. However, if one use so to speak 64 bit block cipher, collision occurs by average 232 trials through birthday attack. Nowadays, it is not secure enough to protect document. Knudsen and Preneel proposed a method strengthen security utilizing non-binary error correction codes. This paper modifies their method using simple binary code and obtained efficient method avoid using Galois field. Also the method using convolutional codes reduce hardware 1/N (where N is a constraint length of the block) times of the number of Davies-Meyer functions compared with the case using block error correcting codes under the same functional conditions.. 号の安全性が保証されていればそれを用いたハッシュ. 1. はじめに. 関数も安全性が保証されるといわれている7),8) ．また，. 現在使われているハッシュ関数には SHA，SHA-1， MD4，MD5 などがある．これらのハッシュ関数用の特定のアルゴリズムを用いる方式には演算スピードは. モードに拡張しても安全性は保たれる8) ．さらにデー. 単一のハッシュモードを多重の（ multiple ）ハッシュタの暗号化部で使う暗号アルゴリズムのハードウェア. それなりに高速であるが，いくつかのアタック（攻撃）. またはソフトウェア資源が共用できるメリットがある．. が発表されている方式もある1),2),9) ．一方，ブロック. 本稿では安全性が保証されたブロック暗号を用いるこ. 暗号を圧縮関数として繰り返し用いてハッシュ関数を. ととし，以下の仮定をおくことにする．. 得る方法に Davies-Meyer の方法がある3),14) ．安全性. (1) (2). 単一のハッシュモードは安全（ secure ）である．. (3). ブロック暗号の安全性が保証されていればそれ. 改善策として 2 次元 Cellular Automaton を使う方法 5). 単一のハッシュモードを解読（ break ）する短絡（ short cut ）が存在しない．. も報告されている．また種々の解析結果も報告されている18) ．しかし一般の 64 ビットブロック暗号をそのまま用いるとバースデーアタックにより平均 232 の試. を用いたハッシュ関数も安全性が保証される．. い，これは今日では安全性が高いとはいえない．ブロッ. 行でコリジョン（衝突または collision ）が生じてしま. ( 4 ) 文書は十分に長いとする．しかしながら，一般の 64 ビット暗号をそのまま用. ク暗号をハッシュ関数に用いる利点としてブロック暗. いたのでは衝突（バースデーアタックまたはコリジョン）が平均 232 回の試行で生じ，これは今日の暗号事. † 高度移動通信セキュリティ技術研究所 Advanced Mobile Telecommunications Security Technology Research Laboratories Co. Ltd.. 情ではけっして安全性が高いとはいえない8) ．誤り訂正符号を用いて衝突耐性を向上させる手法に 2475.

(2) 2476. 情報処理学会論文誌. Sep. 2000. Knudsen and Preneel らの手法がある7),8) ．彼らの手法は 4 元 (n, k, d) 線形符号を用いて衝突を 2m/2 から 2(d−1)m/2 に改善している．なお m はブロック暗号での 1 ブロックのビット数，n は誤り訂正符号の符号長，k は情報記号数，d は最小距離である．しかし彼らは非 2 元（ non-binary ）符号しか構成に用いておらず，安全性の面でもハードウェア構成の面でも改良の余地がある．本稿では BCH 符号のような. 2 元符号を用いた構成法を試み，その有用性を示す． Knudsen らの構成のままでは BCH 符号などの 2 元符号は構成できない．本稿では 2 つの m ビット入力の各々に 2 元符号を割り当てる構成とし，2 元符号が. 図1. ブロック暗号に基づくハッシュ関数（ Davies-Meyer) Fig. 1 Hash function based on block cipher. (Davies-Meyer). 構成できるようにした．これによりガロア体の計算が不要となりハードウェア構成は簡単になったが，2 元符号を使うことによる効率の低下をメッセージベクト. x に対してハッシュ値 H = h(x) = h(x ) を持つ第 2 の文書入力 x を見つけることがどの程度困難かとい. ル入力だけを誤り訂正符号化することによりハッシュ. うことである．つまり，文書 x とそのハッシュ値 h(x). 率（ hash rate ）を符号比率の k/n まで改善した．. があったとき，同じハッシュ値 h(x) になる別の文書. 畳み込み符号はブロック符号を用いたときの 1/N の. x を見つけることが平均 W 回の試行を必要とすればそのハッシュ関数 h のセカンドプレイメージ耐性は W であるという．本稿では以後プレイメージとセ. 数のデビスマイヤー（ Davies-Meyer，以下 DM と略. カンドプレイメージとは数値として同じであるので同. さらに畳み込み符号を用いた手法も考察し，ブロック符号と同じ性能条件で設計するとき，拘束長 N の. 記）関数で装置化できることを示し，回路規模の大い. 等に扱い区別しない．なおセカンドプレイメージ耐性. なる減少が可能なことを示す．. は汎用一方向性ハッシュ関数とほぼ同等であり，文献. 2. ハッシュ関数. 19) にはしかるべき一方向性関数が存在するならば汎用一方向性ハッシュ関数（ Universal One-Way Hash. 通信におけるメッセージ，データ，などの機密保護のため暗号化して暗号文として通信を行うシステムに. Function ）が構成できること，また trap-door 一方向性関数が存在するならば証明安全な署名 scheme が存. おいてメッセージを圧縮して署名するための圧縮関数. 在することが述べられている．. であるハッシュ関数が使われる．任意の長さの文書を. 強い耐性（ strong collision resistance ）とは，衝突. ある決められた長さに圧縮するためには暗号論的ハッ. 耐性（ collision resistance ）またはバースデーアタッ. シュ関数を用いる．一例として DSS（ Digital Signa-. クに対する耐性と呼ばれるものである．h(x) = h(x ). ture Standard ）を使って署名をするには任意の長さ. となる文書入力ペア (x, x ; x = x ) を見つけること. の文書をハッシュ関数を使いいったん 160 ビットのブ. がどの程度困難かということである．すなわち，ハッ. ロックのハッシュ値に変換してこれに署名を施し，た. シュ値が同じになる異なる文書の組を見つけるために，. とえば 160 ビットに対し 320 ビットの署名を付加する．. 平均 W 回の試行を必要とするならば，そのハッシュ. ハッシュ関数は衝突のないように工夫する必要がある．. 関数のバースデーアタックに対する耐性は W である. 衝突とは x = x なる場合に h(x) = h(x ) となるこ. という．通常単に衝突耐性というときはこの強い耐性. とである．衝突に対するハッシュ関数の耐性の定義に. をいう．. は，弱い耐性と強い耐性がある．弱い耐性（ Weak col-. m-ビットブロック暗号（ DES などは 64-ビットブ. lision resistance ）とはプレイメージ耐性（ pre-image resistance ）あるいはセカンドプレイメージ耐性（ 2ndpreimage resistance ）と呼ばれるものである．プレイ. ロック暗号である）に基づくハッシュ関数のハッシュ. メージ耐性とは与えられたハッシュ値 H = h(x) に対 . . . 率とは，1 回の暗号化または復号化で処理される mビットメッセージブロックの数で定義される．図 1 に m-ビットブロック暗号を用いたハッシュ関. して H = h(x ) なる x (x = x ) を見つけることがど. 数を示す．これは DM（ Davies-Meyer ）の方法と呼ば. のくらい困難かということである．. れる．Ek ( · ) を m-ビットブロック暗号の暗号アルゴ. セカンドプレイメージ耐性とは与えられた文書入力. リズムとし，その m-ビット鍵を K とする．FEAL.

(3) Vol. 41. No. 9. 誤り訂正符号を用いたハッシュ関数の構成法. 2477. のように 64 ビットブロック暗号で 64 ビット鍵を用い. るメッセージによる攻撃であるので元のメッセージ. る暗号が該当する．圧縮関数 h を DM 関数と呼ぶ．. の長さ情報をハッシュする前にデータとして埋め込. 長さ m の 2 入力の 2 元シーケンスにより繰り返し. むことによって避けられる．これを MD 強化（ MDstrengthening ）という．ハッシュ値 Hash(IV, M ) を hash round 関数と関. 計算によってハッシュ値を得る圧縮関数 h( · ，· ) を考える．メッセージは m ビットごとに分割されて，入力される．M = (M1 , M2 , · · · , Mn ) となる．もし M. 連付けるため，入力系列の MD 強化をした付加的な. が m の倍数でないときは確定的にパディング規則に. ブロックを付けて次のような結果が得られる．. 則ってパディングする．長さ m のハッシュ値 Hn は. ：h( · ) を MD 強化を施した繰返定理 1（ MD 強化）. 繰り返し計算によって累積値が計算される．. しハッシュ関数とする．圧縮関数 h( · ，· ) に対するプ. Hi = h(Hi−1 , Mi ). i = 1, 2, · · · , t. (1). ここで H0 は初期値 IV である．H0 = IV となる．関. レイメージ（ preimage ）とコリジョン攻撃は対応する. round function における攻撃とほぼ同じ複雑度を持（定理終）. 数 h( · ，· ) は hash round 関数と呼ばれる．ハッシュ値. つ4),15) ．. h(IV, M ) (2) が式 (1) の計算結果として得られる．DM 法に対する以下のような攻撃が考えられる10) ．. される．このことは評価を安全なサイドに導くので定. 実際の応用ではハッシュ関数の初期値は仕様が固定理は h(IV, · ) の下界を与える9) ．. ハッシュ関数 H( · ) が 2 つのバイナリー系列 x，y を. 仮定 1：h に対するコリジョンを見つけるには安全な. 入力して round 関数 h(x, y) を繰り返し計算して得ら. ブロック暗号を用いている限り（ m-ビットブロック. れるものとする．メッセージを M = (M1 , M2 , · · · Mn ). の）約 2m/2 回の暗号化が，また h に対するプレイ. とし Mi は長さ m とし，式 (3) を繰り返して計算し，. メージを見つけるには約 2m 回☆ の暗号化が必要であ. 最終的にハッシュ値 Hn を H = Hn として計算する．. る7),8) ．. Hi = H(Hi−1 , Mi ) H0を初期値とする．. i = 1, 2, · · · , n. (3). メッセージ Mi ，ハッシュ（ hash ）値 Hi および 1 つ前の（ previous ）ハッシュ値 Hi−1 の間には. H = H(H0 , M ) (4) と書ける．明らかに H は H0 に依存する．メッセージ長が m の倍数でないときはパディングして m の. Hi = h(Mi , Hi−1 ) = EMi (Hi−1 ) ⊕ Hi−1 (5) が成り立つ．ここで ⊕ は法 2 加算である．Hi は文書. 倍数にする．. の始まりから時刻 i − 1 までのハッシュ値と時刻 i の. 攻撃例 1 ）（ Long Mesage attack ）. メッセージとの累積加算値である．. n > 2(m/2)とする．順次ストアされるパターンは H1 , H2 , · · · , H2m/2 通りとなる．するとランダムに選. 定義〔多重デビスマイヤー（ multiple Davies-Meyer ）. ∗. ばれたメッセージ M がこれのどれかと一致する確率は概算で 0.63 となり無視できない10) ．攻撃例 2 ）（ Trivial free-start attacks ）. 圧縮関数〕：Ek ( · ) を，a > 0 なる a × m-ビット鍵. K を使う m-ビットブロック暗号アルゴリズムとする． h1 , h2 , · · · , hn を鍵を互いに異なる値をとることにより互いに異なる DM 関数にしている．多重デヴィス. 初期値 H0 でハッシュ値 H となる M = (M1 , M2 ). マイヤー関数は r 個の m-ビットメッセージ入力をア. なるメッセージを考える．H1 = h(H0 , M1 ) なる初期. フィン変換して n 個のペア (Xi , Yi ) へ写像して入力. 値に対して，メッセージ M2 は H = H(H1 , M2 ) と. する．出力は h1 , h2 , · · · , hn の連接となる．. なってやはり同じハッシュ値を持つ．つまり 1 ブロッ. 入力ベクトル X ，出力ベクトル Y とするとき，係. ク以上の round ではつねにアタックがありうる10) ．. 数行列 A，と定数行列 B が与えられたときのアフィ. 攻撃例 3 ）（ Trivial semi-free-start collision attack. ン変換を. Y =A·X +B. based on a “fixed point” ）. (6). もし round 関数 h が明らかな “固定点”を持つならば. と表すと B はフィードバックされたハッシュ値，X. つまりもし H = h(H, M ) なるようなある (H, M ) を. はメッセージ入力または鍵入力，A は DES などの暗. 見つけられたら，そのときは初期値 H が H0 に等しい. 号アルゴリズムによる変換マトリクス，Y は得られ. 値でスタートしても “異なった” メッセージ M (= M ) と M (= (M, M )) が両方とも同じハッシュ値 H を持つことになる．以上のアタックはすべてもとのメッセージ長と異な. ☆. ここで約 2m 回と約を付加したのはコリジョンが起こるまで比較したハッシュ値の数は得られたハッシュ値が完全にランダムになっていると仮定したうえで平均して約 2m 回の暗号化でコリジョンが起こっているという意味．以下同じ．.

(4) 2478. Fig. 2. 情報処理学会論文誌. Sep. 2000. 図3. コリジョン（またはプレイメージ）したハッシュ値におけるパラメータ相互関係 Fig. 3 Relations among parameters P , v, and n when collision or preimage happens.. 図 2 多重デビスマイヤー圧縮関数 Multiple Davies-Meyer compression function.. たハッシュ値 h1 , h2 , · · · , hn となる．コリジョンまたはプレイメージが生じたとき入力ブロックを構成する. りで攻撃せねばならない．P − v = 1 で 1 ブロックが. (Xi , Yi ) が元のペアーと異なるなら h(Xi , Yi ) は能動. 独立に攻撃可能．しかしこれは攻撃全体から見ると無. 的（ active ）と呼ばれる．また，コリジョンまたはプレ. 視できる7) ．したがって，総当りを行うパターンの数. イメージが生起している状態で 2 つの関数 hi (Xi , Yi ). は 22m となる．. と hj (Xj , Yj ) は独立に（ independently ）攻撃可能というときは，コリジョンまたはプレイメージが生起し. 3. 誤り訂正符号を用いた構成法. ている状態で関数 hi の変数パラメータ (Xi , Yi ) が変. 3.1 Knudsen and Preneel による構成法（ KP. わっても，関数 hj の変数パラメータ (Xj , Yj ) は変わ. 法） Knudsen and Preneel による誤り訂正符号を用い. らないような関数をいう．図 2 に多重デビスマイヤー関数を示す．. た構成法をこの論文では KP 法と呼ぶ．. 仮定 2：多重デヴィスマイヤーの圧縮関数に対するコリジョンあるいはプレイメージが見つかったとする．. P を能動的（ active ）な関数の数とし，P −v を独立に攻撃可能な関数の最大数とする．このコリジョンあるいはプレイメージが起こるためには少なくとも 2. vm/2. 定理 2：長さ n，情報シンボル数 k ，最小距離 d， (a + 1)k > n ただし a ≥ 1 かつ m log2 n なる GF (2a+1 ) 上の (n, k, d) 符号で入力ブロックを符号化したとする．すると仮定 2 が成り立つ限り圧縮. ，. 関数に対するコリジョンを見つけるには少なくとも. あるいは 2vm 回の暗号化がそれぞれ必要である7),8) ．. 2(d−1)m/2 回の暗号化が，あるいはプレイメージを見つけるには少なくとも 2(d−1)m 回の暗号化が必要で. なおコリジョン（またはプレイメージ）したハッシュ値におけるパラメータ P, v, n の相互関係を図 3 に. ある8) ．. 示す．図で n · m ビットがハッシュ値の長さとなる．. このハッシュ関数は n · m ビットの内部メモリが必. n は ECC（ Error correction coding ）符号語の長さで，Hamming 符号 (7, 4, 3) の例では n = 7 となる． v = d − 1 で d = 3 であるから v = 2 となる．P = 3. 要でハッシュ率は (a + 1)(k/n) − 1 である．すなわち，たとえば距離 3 の誤り訂正符号を使うことによってコ. とすると能動的でない残り 4 ブロックでは 2 つのハッ. を 2m から 22m に改善し，安全なハッシュ関数を簡. シュ値のなかでパターンが一致しているブロックがそ. 単に構成できる．Knudsen らの構成を図 4 に示す．. れぞれ 4 ブロックあることになる．v = 2 であるので. 3.2 ブロック符号による構成法定理 2 を Binary BCH 符号に適用しよう．KP 法. 2 ブロック互いに従属なため攻撃するにはここを総当. リジョンを 2m/2 から 2m に，あるいはプレイメージ.

(5) Vol. 41. No. 9. 誤り訂正符号を用いたハッシュ関数の構成法. 2479. 4. 提案方式 3.2 節の改善策はガロア体の符号を 2 元の符号に置き換えてはいるものの，1 単位時間前のハッシュ値だけで構成され，n 個の m-ブロックから構成される 1 列目の BCH 符号語は前の時刻のハッシュ値だけを符号化することになり，ここには新しいメッセージの情報は入力されない．したがって，この列がアタックされることはなく，攻撃に対する符号化をする必要もない．符号化は 2 列目の n 個の m-ブロックだけを行い攻撃から守ればよい．ベクトル Xi は暗号器が完全（乱数オラクルと見なせる）であれば乱数と見なせる．関数 hi の Yi だけ誤り訂正符号化する．図 4 Knudsen and Preneel 法 Fig. 4 Knudsen and Preneel’s method.. 3.1 節の定理 2 において，符号化は 2 列目の n 個の m-ブロックだけを行い，フィードバックされてくる 1 単位時刻前だけのブロックから構成される 1 列は符号化せず，2 列目だけを 2 元符号で符号化する．このよ. では a ≥ 1 としているがそれは能率の良い MDS. うに構成しても圧縮関数に対するコリジョンを見つけ. （ maximum distance separable=最大距離分離）符号. るには少なくとも 2(d−1)m/2 回の暗号化が，あるいは. を使う意図からであると考えられる．KP 法では a ≥ 1. プレイメージを見つけるには少なくとも 2(d−1)m 回. ではあるが，a = 0 と仮定すれば Binary BCH 符号. の暗号化が必要である．. となる．GF(2) の (n, k, d) 符号で k > n なる入力ブ. 本稿ではフィードバックされてくる 1 単位時刻前だ. ロックを構成することになる．つまり，GF(2) すなわ. けのブロックから構成される 1 列は符号化せず，2 列. ち BCH 符号などの 2 元符号には k > n が成り立た. 目だけを 2 元符号で符号化するので新しいメッセー. ないのでこのままではこの構成法を適用できない．誤. ジをその分多く入力でき，より効率的な構成で実現で. り訂正符号として構成するには k < n が必要となる. きる．. ので結果的に 2 個の BCH 符号で構成すれば a = 0. 4.1 ブロック符号を用いた方法. でも 2k > n なる構成に作れ，構成可能となる．す. 定理 3：n 個の 1 単位時刻前のハッシュ値（ previous. なわち，入力ブロックの各ビットがそれぞれ BCH 符. hashed values ）と，k 個のメッセージブロックを ECC. 号の k 個の要素を与えるように構成すれば，BCH 符. 符号化して n 個の m-ビットブロックを作り n × 2 個. 号などの 2 元の符号にも構成できる．その方式はデビ. の m-ビットブロックを n 重 DM（ n-multiple Davies-. スマイヤーの基本構成である 2 つの m ビット入力に. Meyer 関数）に入力するとする．n 個のブロックにコ. ガロア体のシンボルエレメントを割り当てることをせず，1 つの m ビット入力に 2 元符号（ binary code ）. リジョンまたはプレイメージが起こったとし，P 個の DM 関数が能動的ならば，P − (d − 1) 個のメッセー. の 1 ビットを割り当てる構成にして 2 元符号を使え. ジ入力ベクトル Yi が独立で，d − 1 個のメッセージ. るようにする．2 個の BCH 符号を 1 つは previous. 入力ベクトル Yi が従属である．仮定 2 が成り立つ限. hashed value をもう 1 つはメッセージブロックをそ. り圧縮関数に対するコリジョンを見つけるには少なく. れぞれ符号化して，つまり 2 個の符号語にして n × 2. とも 2(d−1)m/2 回の暗号化が，あるいはプレイメージ. の入力 array を m 個作る．しかしながらこのように. を見つけるには少なくとも 2(d−1)m 回の暗号化が必. 構成しても non-binary 符号が Reed-Solomon 符号な. 要である8) ．. どの MDS 符号を利用できるのに対して，2 元の符号. （証明）：ベクトル Yi の n ビットは少なくとも最初の. は MDS 符号になる符号のクラスがないので符号比率. k ビットが互いに独立である．最後の n − k ビット. が悪く，効率が非常に悪くなる．この効率を改善する. の少なくとも d − 1 個が最初の入力に依存している．. ためメッセージ部分だけを誤り訂正符号化する構成を. Singleton 境界13) より n − k ≥ d − 1 だから定理 3 は. 考えよう．. おのずと証明される．. （証明終）. 以上の議論は定常状態で入力ベクトル Xi が乱数オ.

(6) 2480. Sep. 2000. 情報処理学会論文誌. ラクルの出力と見なせる限り成り立つ．しかし，初期. ジョンを見つけるには少なくとも 2(d−1)m/2 回の暗号. 状態においては鍵入力，メッセージ入力ともに任意の. 化が，あるいはプレイメージを見つけるには少なくと. 値をとりうる．したがって，初期入力べクトルについ. も 2(d−1)m 回の暗号化が必要である．また，時刻を i. ては Knudsen and Preneel に基づいて入力しなけれ. と仮定すると前の時刻 i − 1 の n 個のハッシュ値は. ばならない．. すべて 1 列目の n 個の m-ブロックに戻されるから，. 仮定 2 の拡張. メッセージブロックのため使われるブロック数は k と. 初期状態：Multiple-Davies-Meyer の圧縮関数に対す. なる．ハッシュ率は k/n となる．. るコリジョンあるいはプレイメージが見つかったとす. （証明）仮定 2 の拡張により定常状態においてはメッ. る．P を能動的な関数の数，P − v を独立に攻撃可能. セージのため使われるビットは k ビットとなりベク. な関数の数とする．h1 , · · · , hn を同時に衝突が起こっ. トル Yi の n ビットは少なくとも最初の k ビットが独立である．最後の n − k ビットは少なくとも d − 1. ている DM 関数とする．個々の関数には. hi (Xi , Yi ) = Exi (Yi ) ⊕ Yi. (7). ビットが最初の入力に依存するので n − k ≥ d − 1 ゆ. が成り立つ．これらは log2 n ビットを異なった固定. え，コリジョンを見つけるには少なくとも 2(d−1)m/2. 値にして異なった鍵が得られる．KP 法に基づき 2k 個. 回の暗号化が，またプレイメージを見つけるには少な. の m ビット初期値入力を持つ圧縮関数を考え，それ. くとも 2(d−1)m 回の暗号化が必要である．なお初期. がアフィン変換により n 個のペア (Xi , Yi ) に写像さ. 状態ではすべての圧縮関数の出力は入力 2k のブロッ. れ，すべての圧縮関数の出力は入力の 2k 個のブロッ. クに依存し，ベクトル Yi の n ビットは少なくとも最. クに依存する．すなわち式 (6) の変換マトリクス A は. 初の 2k ビットに依存するので初期ベクトルはそれぞ. 階数 2k を持つ．. れ k ビットずつ 2 個に分け，それぞれを ECC 符号化. 定常状態：初期値状態を除く定常状態において k 個. することにより n − k ≥ d − 1 となり定常状態と同じ. の m ビット入力を持つ圧縮関数のアフィン変換によ. 衝突耐性を得る．. （証明終）. り n 個のベクトル Yi に写像されるすべての圧縮関数. このハッシュ率は元々誤り訂正符号の持っている符. の出力が入力の k 個のブロックに依存する．すなわ. 号化率に等しい．すなわち効率が大幅に改善されるこ. ち変換マトリクス A は階数 k を持つ．同時衝突が h1 , · · · , hn に起こったとき，すなわち. とになる．運用上の注意としては初期値に n × m ビットの鍵の初期値が必要である．図 5 に本稿の 2 元符号. 2 つの入力値 {zi } と {zi } の異なった組がすべての n 個の関数に等しい出力を与えるとする．このとき. を使った例を示す．. Zi = Zi となる P 個 (P ≤ n) の関数の組を {hi } とする．関数 {hi } のマトリクスの階数は仮定 2 より. n 個のペア入力の片側である m ビットブロックに入力される．その構成を説明の便宜上簡単な (7, 4, 3). 新しい構成法は 2 元符号の 1 つの符号語によって. P − v となる．これら P 個の関数 {hi } に対する同時衝突は少なくとも 2vm/2 回の暗号化が，また，プレイメージに対しては 2vm 回の暗号化が必要である．したがって，入力ベクトル X0 のうち k 個の m ビットブロックをあらかじめ誤り訂正符号で符号化し. n ビットブロックにして初期値 X0 とし，残り n − k ビットブロックを初期値 Y0 のうち n − k ビットブロックに配置する．すなわち初期状態のメッセージ m ビットブロックは Y0 の残りビットである r = 2k − n ビットブロックとなる．2 番目以降のメッセージビットブロックは r = k ビットブロックとなる．すなわち d − 1 個の Yi ベクトルだけが従属であることが要求されるので定常状態においてはベクトル. Yj だけを誤り訂正符号化すればよい．定理 4：符号長 n，情報記号数 k ，最小距離 d の 2 元符号を考える．デビスマイヤーの段数を n とする．仮定 2 の拡張が成り立つ限り，圧縮関数に対するコリ. Fig. 5. 図 5 2 元符号を用いた構成 Construction for hash function using binary codes..

(7) Vol. 41. No. 9. 誤り訂正符号を用いたハッシュ関数の構成法. Table 1. 2481. 表 1 2 元の符号による方法と従来法との比較 Comparison of a method using binary codes and a conventional method.. Hamming 符号で説明しよう．パリティマトリクスは次のようになる．. 参考までに符号長 63 ビット以下の原始 BCH 符号による構成した設計パラメータを表 2 に示す．. H =（ α6 , α5 , α4 , α3 , α2 , α1 , α0 ） 1110100 =0111010 1101001 原始多項式は X 3 ⊕ X ⊕ 1 である．. この方法は Knudsen and Preneel と比べてフィードバックされたハッシュ値を誤り訂正符号化しない分だけ効率（ hash rate ）が改善されており，BCH 符号. (8). などの 2 元符号を使うため既存の高速ハードウェアなどが流用できる．さらにコリジョンを m = 64 とし. H 1 = h1 (G1 , M1 ) H 2 = h2 (G2 , M2 ). て 22m = 2128 に 1 回の割合に抑える要望があれば. H 3 = h3 (G3 , M3 ) H 4 = h4 (G4 , M4 ) H 5 = h5 (G5 , r3 ). 以上の説明から分かるように本稿によれば 2 元符号. H 6 = h6 (G6 , r2 ) H 7 = h7 (G7 , r1 ). d = 5 の BCH 符号を選べばよい．を使うため，ガロア体の演算をしなくてすみ，かつ，より安全性の高いハッシュ値を得ることができる．しかしながらこの構成には DM 関数は多数必要であり，. (9). ここで r3 ，r2 ，r1 は Hamming 符号のチェックビットのブロックである．これらは次式で与えられる．. r3 = M1 ⊕ M2 ⊕ M3 r2 = M2 ⊕ M3 ⊕ M4 r1 = M1 ⊕ M2 ⊕ M4. この点を次節において，畳み込み符号を導入して改善する．. 4.2 畳み込み符号を用いた構成法ブロック符号を用いる KP 法では衝突耐性を高めるため誤り訂正能力を大きくすると符号長が一般に大き. (10). くなり演算が複雑になる傾向があった．また，符号長. シンボル Gi ，Mi ，ri は m-ビットブロックを表す．. 分だけのデビスマイヤーの段数が必要になるため多く. Gi は 1 つ前の時刻のハッシュ値を表す．Mi はメッ. のデビスマイヤー関数を装置化しておく必要がある．. セージブロックを表し，ri は Hamming 符号のチェックビットをそれぞれ表す．なお今は説明の便宜上 Hamming 符号で示したが，. 本稿では DM の基本構成である段数入力を畳み込み符号の小ブロック長 n0 に選ぶことにより，また拘束長 N とするとき N 段に分けて入力することによ. 距離を大きくとるため 2 重誤り訂正 BCH 符号で考え. りデビスマイヤーのサイズをブロック符号を使ったと. よう．これによりより安全性の高いハッシュ関数を構. きの符号長 n から畳み込み符号の小ブロック長 n0 ま. 成できる．(31, 21, 5) BCH 符号を (30, 20, 5) BCH 符. で小さくできる構成法を示す．すなわち，DM 関数の. 号に短縮する．すると r = 20 となる．ハッシュ率は. 基本構成の段数は 1/N まで減少する．. 20/30 = 0.66 · · · となる．. 構成は畳み込み符号器と多段デビスマイヤーハッシュ. 2 元符号を使った例と Knudsen らの結果とを比較のため表 1 に示す．. 関数と N 段に連接されたハッシュ値を蓄積する FIFO. Non-binary の符号は Knudsen and Preneel7),8)らの結果による．. く分けて 2 種類の符号器がある．Massey によって導. メモリによって特徴付けられる．畳み込み符号は大き入されたタイプ 1 とタイプ 2 の符号器である16) ．例.

(8) 2482. Sep. 2000. 情報処理学会論文誌. Table 2. 表 2 符号長 63 ビット以下の原始 BCH 符号による構成 Parameters using primitive BCH codes whose length are up to 63 bits.. で説明しよう．畳み込み符号の小ブロック長 n0 ビット，小情報記号ビット k0 ，最小距離 d，拘束長 N 段とするとき本稿では (n0 , k0 , d; N ) 畳み込み符号と呼ぶ．定理 4 を畳み込み符号にも適用しよう．定理 5：n0 個の 1 時刻前のハッシュ値と k0 個のメッセージブロックを畳み込み符号化して n0 個の m-ビットブロックを作り n0 × 2 個の m-ビットブロックを. n0 -multiple Davies-Meyer 関数に入力するとする．拘束長 N とするとき N × n0 個のブロックにコリジョンまたはプレイメージが起こったとし P 個の DM 関数が能動的ならば P − d + 1 個の入力ベクトルが独立で d − 1 個の入力ベクトルが従属である．仮定 2 の. Fig. 6. 図 6 (2, 1, 3; 3) Type 1 畳み込み符号器 A (2, 1, 3; 3) Type 1 convolutional encoder.. 拡張が成り立つ限り圧縮関数に対するコリジョンを見つけるには少なくとも 2(d−1)m/2 回の暗号化が，ある. 鍵入力としてハッシュ側入力とし，それぞれを ECC. いはプレイメージを見つけるには少なくとも 2(d−1)m. 符号化することにより (n0 − k0 ) · N ≥ d − 1 となり，. 8). 回の暗号化が必要である．. 定常状態と同じ衝突耐性を得る．. （証明終）. （証明）仮定 2 の拡張により定常状態のとき，衝突が起. 運用上の注意としては k0 × m ビットの鍵初期値が. きた拘束長において，メッセージのため使われるビッ. 必要である．図 6 は (2, 1, 3; 3) 畳み込み符号器のタ. トは k0 · N ビットとなりベクトル Yi の n0 · N ビット. イプ 1 の符号器である．. は少なくとも k0 · N ビットが独立である．検査ビットの (n0 −k0 )·N ビットは少なくとも d−1 ビットがメッセージの入力に依存するので (n0 − k0 ) · N ≥ d − 1 ゆえ，コリジョンを見つけるには少なくとも 2(d−1)m/2 回の暗号化が，またプレイメージを見つけるには少なくとも 2(d−1)m 回の暗号化が必要である．なお初期状態ではすべての圧縮関数の出力は入力 2k0 のブロッ. 部分生成子（ sub-generator ）は. g(1, 1) = 110. (11). で与えられる12) ．各生成子のエレメントは. g0 (1, 1) = 1 g1 (1, 1) = 1 g2 (1, 1) = 0. (12). であり，これらより構成すると図 6 の符号器を得る16) ．. クに依存し，ベクトル Yi の n0 ビットは少なくとも. Massey により与えられた (3, 2, 3; 3) CSOC 符号タイ. 最初の 2k0 ビットに依存するので，初期ベクトルはそ. プ 2 の構成は図 7 の符号器となる16) ．図 8 にタイプ. れぞれ k0 ビットずつ 2 個に分け，1 ブロックだけは. 1 で構成したワイナーアッシュ符号器の例を示す12) ．.

(9) Vol. 41. Fig. 7. No. 9. 誤り訂正符号を用いたハッシュ関数の構成法. 2483. 図 7 (3, 2, 3; 3) Type 2 畳み込み符号器 A (3, 2, 3; 3) Type 2 convolutional encoder.. 図 9 提案方式による (2, 1, 3; 3) Type 1 畳み込み符号器 Fig. 9 An example of proposed construction using (2, 1, 3; 3) Type 1 convoultional encoder. 図 8 Wyner-Ash (4, 3, 3; 2) 畳み込み符号器 Fig. 8 Wyner-Ash (4, 3, 3; 2) convolutional encoder.. 次に動作を説明しよう．図 9 は Massey のタイプ 1 で図 6 の (2, 1, 3; 3) 畳み込み符号器を使って構成した例である．図 9 で Mi はメッセージで m-ビットブロック，Hj はハッシュの n0 × m-ビットブロック，Ci は畳み込み符号のチェックの m-ビットブロックである．Hj は多重デビスマイヤーハッシュ関数が D-ラッチ入力タイプの場合は 1 単位時刻の遅延回路（ Delay ）が不要でこのときは Hj = Hi である．多重デビスマイヤーハッシュ関数がワイアードロジックで構成されているときは Hj = Hi−1 である．また Ci は多重デビスマイヤーハッシュ関数入力側を Ci とするのでこの図では Ci−2 = Mi である．以下同じ．図 9 で初期値として多重デビスマイヤーハッシュ関数の入力例に H0（ Hi で i = 0 ）がまた，各チェックシンボルレジスター C1 ，C2 には初期値 C10 ，C20 が. 図 10 畳み込み符号を使ったハッシュ関数構成法 Fig. 10 Construction for hash function using convolutional codes.. 入っている．多重デビスマイヤーハッシュ関数の 1 回の動作で 2 × 64 = 128 ビットのハッシュ値 H1 が. ビットブロックが入力され，6 × 64 = 384 ビットハッ. 得られ，FIFO メモリへ入力されると同時に入力側へ. シュ値の演算は終了する．. フィードバックされ，次のメッセージとチェックシン. 畳み込み符号を用いると多重デビスマイヤー関数の. ボルとハッシュ値が入力され，次の動作で H2 が得ら. サイズは 1/N 倍と小さくなるが，拘束長 N ，全長. れる．このようにして次々に Hi が生成され，FIFO. N × n0 × m ビットのハッシュ値を得るためにはデー. メモリにはつねに最新の 2 × 3 = 6 個の m-ビットブ. タの最後に (N − 1) × k0 × m ビットの 0 を入力して. ロック分のハッシュ値 Hi−2 Hi−1 Hi が残る．デー. データを完全に符号器から出力させる必要がある．図. タが全部入力されたあと畳み込み符号化を終端させる. 10 は本構成による一般的な多重デビスマイヤーハッシュ関数を示す．. ため N − 1 すなわち 1 × 2 = 2 個のデータ値 0 の m-.

(10) 2484. 情報処理学会論文誌. Table 3. 表 3 提案方式における初期化時と最終時のダミーデータ数 Dummy data for proposed construction at initial and final stage.. Table 4. 表 4 ワイナーアッシュ（ Wyner-Ash ）符号による構成例 An example of a construction which uses Wyner-Ash codes.. Table 5. 表 5 CSOC 符号による構成例 An example of a construction which uses CSOC codes.. Sep. 2000.

(11) Vol. 41. No. 9. 2485. 誤り訂正符号を用いたハッシュ関数の構成法. 本構成は多重デビスマイヤー関数の入力側で n0 × 2. の鍵を使い，b × m ビットのハッシュ値を得る暗号を. の 2 次元配置を構成して第 1 の列の n0 の m-ビットブ. 考えると行方向は a + b となる．このような暗号方式. ロックに 1 単位時刻前の n0 個のハッシュ値をフィー. に適合するハッシュ関数合成技術が研究されるべきで. ドバックし新しいメッセージ k0 個の m-ビットブロッ. ある．. クを符号化して n0 個の m-ビットブロックにしたのち，入力する．表 3 は本構成の初期化時と終了時の必要なダミーデータ数を示す表である．. その結果，安全性が大幅に改善されることが期待される．謝辞全般にわたりディスカッションいただいた早. ワイナーアッシュ符号を使った場合と CSOC 符号. 稲田大学平沢教授，九州大学桜井幸一助教授に感謝し. （ Convolutional Self-Orthogonal Codes；自己直交畳. ます．DM 関数でご意見をいただいた埼玉大学佐藤孝. 12) を使った例を表 4，表 5 に示す．み込み符号）. 表 1，2 と表 4，5 を比べる距離 3 の場合，ハッシュ率をほぼ同じにとるとブロック符号は (15, 11, 3) Ham-. ming 符号が (4, 3, 3; 4) CSOC 符号とメモリ，安全性，ほぼ同等であるが，Hamming 符号が 15 段の DM 関数を要するのに CSOC 符号は 4 段の DM 関数で構成できることが分かる．距離 5 の場合，ハッシュ率を. 2/3 に選ぶと (31, 21, 5) BCH を短縮した (30, 20, 5) BCH 符号と (3, 2, 5; 14) CSOC 符号が対応し，BCH 符号は 30 m のメモリで済むのに CSOC 符号は 42 m と多くなっている．しかし DM 関数は 3 段で構成でき現実的である．. 5. まとめ誤り訂正符号を用いてハッシュ関数を構成する Knudsen and Preneel を改良して 2 元の符号を用いる方法，畳み込み符号を用いる方法を開発し，その構成を示した．近年ブロック暗号の鍵長の安全性が真剣に議論されるようになり，128 ビット以上の鍵を持つ暗号が主流となりつつある6) ．このような要請と合わせ既存の手法を組み合わせて安全なハッシュ関数を求める研究がもっと活発になされるべきである．アメリカの標準暗号 AES6) の選定作業と絡め，より長いブロック長，より長い鍵長のブロック暗号を用いてハッシュ関数を構成する方法を確立しておく必要がある．一方でハッシュ関数用の特定アルゴリズムも引き続き研究していく必要がある．ブロック暗号には a ≥ 2 すなわち MISTY17) ，. IDEA11) 暗号のように m = 64 ビットで入力，出力のデータビット数は 64 でも暗号化/復号化の鍵は 128 ビットすなわち a = 2 のものがある．また，タンデ 20) やアブレスト Dム D-M（ Tandem-Davies-Meyer ） 20) M（ Abreast Davies-Meyer ）は m-ビット鍵によっ. て 2m-ビットのハッシュ値を得る．ハッシュ関数の入力としては時刻 i − 1 のハッシュ値 2 m ビットと鍵入力 m-ビットとなる．今後の課題としては，a ≥ 2 の鍵長 a × m ビット. 和先生，有益な討論をいただいた神戸大学田中初一教授に感謝します．. 参考文献 1) Dobbertin, H.: Cryptanalysis of MD4: Fast Software Encryption, Goldman, D. (Ed.), LNCS, Vol.1039, pp.53–69, Spring-Verlag (1996). 2) Dobbertin, H.: Cryptanalysis of MD5 compress, rump session of EUROCRYPT’96 (May 1996). 3) Davies, D.W. and Price, W.L.: Digital Signature-An Update, Proc.International Conference on Computer Communications, Sydney, pp.843–847, Elsevier, North Holland (1985). 4) Damgard, I.B.: A design principle for hash functions, Advances in Cryptology, Proc. Crypto’89, Brassard, B. (Ed.), LNCS, Vol.435, pp.416–427, Springer-Verlag (1990). 5) 広瀬勝一，吉田進：二次元オートマトンに基づく一方向性ハッシュ関数，情報理論とその応用，松山，pp.213–216 学会シンポジウム（ SITA97 ） (Dec. 1997). 6) 川村信一：AES 参加報告，信学会技術報告， ISEC98-41, pp.39–43 (Nov. 1998). 7) Knudsen, L. and Preneel, B.: Hash functions based on block ciphers and quaternary codes, Advances in Cryptology, Proc. Asiacrypto’96, Kim, K. and Matsumoto, T. (Eds.), LNCS, Vol.1163, pp.77–90, Springer-Verlag (1996). 8) Knudsen, L. and Preneel, B.: Fast and secure hashing based on codes, Crypto’97, LNCS, Vol.1294, pp.485–498 (1997). 9) Kuwakado, H. and Tanaka, H.: On the Onewayness of the reduced MD4 compression function, The 1999 Symposium on Cryptography and Information Security, Kobe, pp.247–250 (Jan. 1999). 10) Lai, X. and Massey, J.L.: Hash Functions Based on Block Ciphers, Eurocrypt’92, LNCS, Vol.658, pp.55–70 (1993). 11) Lai, X. and Massey, J.L.: A Proposal for a New Block Encryption Standard, Proc..

(12) 2486. Sep. 2000. 情報処理学会論文誌. Advances in Cryptology-EUROCRYPTO’90, pp.389–404, Springer-Verlag (1991). 12) Lin, S.: An Introduction to Error Correction Codes, Chapter 10, Englewood Cliffs., N.J. (1970). 13) MacWilliams, F.J. and Sloane, N.J.A.: The Theory of Error-Correcting Codes, NorthHolland Publishing Company, Amsterdam (1978). 14) Matyas, S.M., Meyer, C.H. and Oseas, J.: Generating Strong One-Way Functions with Cryptographic Algorithm, IBM Technical Disclosure Bulletin, Vol.27, No.10A, pp.5658–5659 (1985). 15) Mercle, R.: One way hash functions and DES, Advances in Cryptology, Proc.Crypto’89, Brassard, G. (Ed.), LNCS, Vol.435, pp.428–446, Spring-Verlag (1990). 16) Massey, J.L.: Threshold Decoding, MIT Press (1963). 17) Matsui, M.: New structure of block ciphers with provable security against differential and linear cryptanalysis, 3rd international workshop of fast software encryption (1996). 18) Morita, H., Odagi, H. and Ohta, K.: Collision search of a hash function by using random map-. ping, IEICE Trans. Fundamentals, Vol.E81-A, No.1, pp.35–40 (1998). 19) Naor, M. and Yung, M.: Universal One-Way Hash Functions and their Cryptographic Applications, Proc. STOC, pp.33–43, ACM Press (1989). 20) Schneier, B.: Applied cryptography, pp.451– 452, John Wiley & Sons, New York (1996). (平成 11 年 5 月 7 日受付) (平成 12 年 7 月 5 日採録) 井上. 徹（正会員）. 昭和 44 年京都大学工学部電 II 卒業．同年三菱電機入社．昭和 50∼. 52 年米国コムサット研究所国際職員．平成 9 年 2 月より（株）高度移動通信セキュリティ技術研究所出向，現在に至る．符号理論，暗号理論およびその応用製品開発に従事．「実戦誤り訂正技術」（ 1996 年，トリケップス出版，監修），「先端技術の手ほどきシリーズディジタル放送」（ 1996 年，テレビジョン学会編，共著）．工学博士，電子情報通信学会，IEEE，情報理論とその応用学会各会員．.

(13)