「原理的に」とは
一方向ハッシュ関数hについて，衝突に対する2つの性質を次のように定義します．
- 弱衝突耐性とは，与えられたh(m)から，h(m)=h(n)を満たすnを求めることができないこと．
- 強衝突耐性とは，m≠nかつh(m)=h(n)を満たすm,nを求めることができないこと．
そして上記の「〜できないこと」の否定は，それぞれの耐性を破る攻撃が存在することを意味します．
弱衝突耐性を破る攻撃は，原理的に示せます．強衝突耐性を破る攻撃は，hが単射でないという条件のもとで---実用的な一方向ハッシュ関数ではこれを満たします---，原理的に示せます．
これからそのそれぞれを示していくことにしますが，そのためには今からいう2つのことを，準備しておきます．
まず「原理的に」というのは，「いくらでも時間をかければ」「有限時間で」ということだと，理解してください．いくら時間をかけても，解くことができない問題を「原理的に決定不能」もしくは「一般に決定不能」と言います．チューリング機械の停止性問題がその一例です．直接的に背理法で示すか，既知の原理的に決定不能な問題をそれに帰着させる*1ことになります．いやこれは，脱線でした，ここでは「原理的に〜できる」だけを考えれば十分です．
さてその「原理的に〜できる」とはどういうことか，なのですが，計算理論ではこれを「帰納的加算」と呼びます．枚挙可能，とも言います．ある条件を満たす値を，漏れなく，すべて書き出す---枚挙する---ことができることにちなんでいます．
ただし，その枚挙されることになる値は，無限に存在すると思ってください．言い方を変えると，無限個の解を列挙していく，そんなアルゴリズムを示せたら，「原理的に解ける」ことになるのです．
とはいえ，そういう枚挙を試みて，最初の一つを発見したら，それで「見つかった，おしまい」としてプログラムを終了させる，という使い方もあります．最初の一つを発見するのに，何億年もかかるかもしれませんが，「解けるか解けないか」で言うと，「解ける」の側になります．
もう一つの準備は，列挙するための集合です．計算機で扱うための，一方向ハッシュ関数の入力---数学的には定義域---になるのは，任意のビット列です．長さは任意ですが，常に有限長とします．このとき，そのビット列を，次の順番で書き出すことができます．
"", 0, 1, 00, 01, 10, 11, 000, 001, ...
どんな規則かというと，長さが短いものを先に，同じ長さどうしだったら，0＜1の辞書順で並べてできる，ビット列の列です．0, 00, 000, などなどはいずれも異なるビット列であることに注意してください．
このようにしてできる系列は，自然数と一対一の対応をとることができます．まあ，自然数は0から始まるものとして，先頭の空列を，0としますか，1ビットの0は1，1は2，00は3です．10101010がどんな整数に対応付けられるか，また10000番目のビット列が何になるのか，というのはともに，高校の数学の範囲で求めることができますし，プログラムを書くのも，決して難しくありません*2．
弱衝突耐性を破るためのアルゴリズム
これでやっと，弱衝突耐性を破るためのアルゴリズムを言うことができます．入力となるのは，一方向ハッシュ関数のhと，ハッシュ値h(m)ですね．
アルゴリズムとしては，まず，変数iを用意します．その初期値を0とします．あとで示すように，カウントアップしていきます．
そして，「ここがループの先頭」とラベルをつけておきまして…
iという自然数の値に対応するビット列bを，先ほどの対応付けをもとに，求めます．そうすると，bに対してhを適用することで，ハッシュ値h(b)が得られます．これをh(m)と比較し，等しければ，bは弱衝突耐性のところで書いた，「h(m)=h(n)を満たすn」に当たりまして，これが弱衝突耐性を破る根拠の一つですよと，出力すればいいのです．
一つだけ，そのようなビット列を求めればいいのであれば，ここでプログラムを終了します．すべて出したいだとか，h(m)≠h(b)なのであれば，iを1増やしてから「ループの先頭」に戻ります．
このようにして，少なくとも1回，条件を満たすbを出力するということは，iを0から順に増やしていけば，いつかは，その自然数に対応するビット列がmに一致することから，確認できます．
しかし「h(m)=h(b)を満たすb」を出力したからといって，そのときのbが，mに一致するかどうかは，わかりません．ビット列mよりも，先に書いた順序で前にあるbが，当たりとなったかもしれないからです．
強衝突耐性を破るためのアルゴリズム
次は，強衝突耐性を破るためのアルゴリズムですが，もう一つ準備が必要になります．それは，自然数のみからなる2次元平面のそれぞれの点が，自然数に対応付けられることです．
並べてみますか．(0,0), (1,0), (0,1), (2,0), (1,1), (0,2), (3,0), (2,1), ...と，2次元座標上の点を見ていきます．
こうすると，x，yともに0以上の格子点のすべてが，この点の列のどこかに，ちょうど1回だけ出現します．これが，N×NとNの対応付けの一つです*3．これもプログラムを作って，自然数の値から座標を，逆に座標から自然数の値を，求めることができます．
ではアルゴリズムです．今回の入力は，一方向ハッシュ関数hだけです．
変数としてi, j, k, m, nの5つを用意します．変数iは，0をスタートとして1ずつ増えていきます．その変数iの値に対応する，2次元平面の点が，(j,k)となるよう，変数jとkに代入します．それから，先ほど言った，自然数とビット列の対応付けを使用して，変数jの値に対応するビット列をm，kに対応するものをnとします．
ああ，思い出しました．j=kだと，後の処理をする必要がありませんので，スキップすなわち，iの値を1増やして次のケースに行っちゃってください．
それで，h(m)とh(n)を計算し，比べます．h(m)=h(n)ならば，「m≠nかつh(m)=h(n)を満たすm,n」の1組を得たことになります．あとの処理は，弱衝突耐性を破るためのアルゴリズムと同様です．
*1:問題Aが原理的に決定不能であることを証明したいときに，原理的に決定不能である問題Bを選び，問題Bから問題Aへの写像を作ります．細かいことをいうと，その写像の定義域は問題B全体ですが，値域は問題Aの部分集合（問題A全体でもよい）となります．もし，問題Aが原理的に決定可能ならば，問題Bは問題Aに帰着して解くことができ，したがって問題Bも原理的に決定可能であることになります．しかしすでに，問題Bは原理的に決定不能であることが示されています．したがって，問題Aも原理的に決定不能であるという次第です．
*2:ちょうどnビットで表せるビット列の最初が，先頭を0としたとき何番目に現れるかを求めておけば，あとは労せずコードにできると思います．
*3:他の対応付けは，尺取り虫プログラム〜保持する情報を減らす, 尺取り虫プログラム〜経路のバリエーション
