🤸‍♂️

SHA-256を書いてみようううううう

2022/04/05に公開

初心者

hash

tech

始球式

なんとなく使ってきたsha-256ですが、256が出力bitなんだろうなーとしか今まで思ってきませんでした。しかしあるときふと、 $1/2^{256}$ の確率でぶつかるじゃん！！と思ったので、どのあたりから事実上衝突しないと保証されているのかについて調べてみようと思いました。その過程で意外と自分でも書けそうだなと思ったので、勉強も兼ねて書いてみました！！（でもうまくはいかなかったです涙）

Hash functonのHistory（1回表）

最も古いハッシュ関数の一つとして、MD4が挙げられます。1991年にMITから発表された入力によらず128ビットのハッシュを出力するものです。Wikipediaによると、1991年に脆弱性が実証され、2004年にはハッシュ衝突の可能性が報告されたらしいです。どうやるんでしょうか。。。トライしてみたいですね。。。ちなみにMDはMessage Digestの略で、MDファミリーには他にもMD5、MD6, RIPEMDなどがあるようです。

またMDファミリーとは別のファミリーの一つとして、SHAファミリーが挙げられます。SHAはSecure Hash Algorithmの略です。SHA-0から始まり、修正や更新が行われて現在ではSHA-0, SHA-1, SHA-2, SHA-3の４つのアルゴリズムがあるようです。しかしながら、SHA-0はセキュリティホールが見つかってしまい、SHA-1に移行したものの、SHA-1にも脆弱性とハッシュ衝突の可能性が見つかり、SHA-1は非推奨となりました。（sha-1の脆弱性の読み物としてはこちらの記事が面白かったです）
そこで現在は主にSHA-2とSHA-3が使われるようになりました。

乱闘（試合の中断）

ここで、単純で純粋無垢な僕は、「せやったら、SHA-2とSHA-3の違いはなんやねん。SHA-2でいいんやったら、SHA-3いらんのんちゃうん」という疑問を感じました。（関西人ではないです。気分です。憧れです。たこ焼きと焼きそば好きです。お好み焼きはあまり好きじゃないです。食べにくいからです。だから挟みすぎなサンドイッチとか、ハンバーガーも好きじゃないです。なんでこぼす前提なんですかあれ。フォークとナイフが置かれていても、問題なのは幅ではなく高さだろといつも思います。しかも切ったら食べやすくなるかなと思って切ろうとすると、挟まれている肉とか野菜とかがパンとの挟まっているソースによって、滑ってはみ出てきて余計に食べづらくなるというあれ、受け入れ難いです。そう考えるとお好み焼きはまだ食べやすい部類な気がしてきました。）
おおっと、この辺りで乱闘が収まったようです。
今回の乱闘は中島が危険球を投げられて起きてしまいました。お詫び致します。
またこれも関係ないですが、あれは実は、「磯野〜野球しようぜ」のオマージュとしてやっているんじゃないかなと思っているんですが違うんですかね。。

Hash functonのHistoryの続き（1回表の再開）

すいません乱闘が長くなりました。SHA-2とSHA-3の違いでしたね。。。それは、hashの生成構造（構成？）にあります。Hash functionは任意の長さの入力に対して、出力の長さは一定なことが求められます。そのことが起因して、Hash functionは、rawな入力値に対して処理するのではなく、入力値を固定長に分けて、それぞれに対して処理を行う構成をとられています。その構成がSHA-2とSHA-3では違います。代表的な構成は以下の3つです。

マークル・ダンガード構造
（Merkle-Damgårdと書くらしいので、正式にはマークル・ダンオングストローマードかもしれません。嘘です。多分Damgårdさんが北欧とかオランダあたりをルーツに持つ人なのかな？）
スポンジ構造
ツリー構造

SHA-1とSHA-2はマークル・ダンガード構造でSHA-3はスポンジ構造です。なぜ違うのかといえば歴史的な背景が理解の役に立ちます。マークル・ダンガード構造を持っている限り、多重衝突の可能性を秘めているということで、別の構造をSHA-3として採用するとNISTが決めたので、構造が異なります。
それに加えて、リスク分散的な意味合いもあったのかなーとも個人的には思ってます。

誕生日のパラドクス(1回裏）

さてそんなハッシュ関数達ですけど、実は $\frac{1}{2}$ の確率でハッシュの衝突を起こす試行回数は、nをハッシュ長としたときに $2^{(n/2)}$ 回となります。なので始球式で僕が投げたボール（ $1/2^{256}$ の確率でぶつかるじゃん！！）はすっぽ抜けのボールとなってました。なぜかは、余事象を考えることでとてもシンプルに説明できていて面白かったので載せておきます。

\\ n人の人間がいるとき、同一誕生日のペアが一組以上いる確率は\\ \begin{aligned} 1 - p &= \frac{364}{365} * \frac{363}{365} * ... * \frac{365-(n-1)}{365}\\ p &= 1 - \frac{364Pn−1}{365^{n-1}}\\ &=1 - \frac{365Pn}{365^{n}}\\ \end{aligned}

これで、nを動かして計算すると23で0.5を超えるので、23人いる場合は、その中に同じ誕生日の二人組は、1/2の確率で存在することになります。これは誕生日のパラドックスと呼ばれるものです。
これと衝突可能性の関係を探るためにも、さらにこれを一般化してみましょう。

\\ N個の要素の中から無作為に１個を選択する試行を繰り返すことを考える。\\ q回目の試行にて2回以上選ばれる要素が存在する確率をPとすると\\ \begin{aligned}\\ 1 - P &= \frac{N-1}{N} * \frac{N-2}{N} * ... * \frac{N-(q-1)}{N}\\ 1 - P &= \displaystyle\Pi_{i=1}^{q-1}(1 - \frac{i}{N})\\ \end{aligned}

ここで、 $e^{-x}$ をマクローリン展開すると

\\ \begin{aligned} e^{-x} &= 1 - \frac{x}{1!} + \frac{x^{2}}{2!} - \frac{x^{3}}{3!} + \frac{x^{4}}{4!} ... \\ e^{-x} &\approx 1-x\\ \end{aligned}

つまり

\\ \begin{aligned} 1 - P &\approx \displaystyle\Pi_{i=1}^{q-1}(e^{\frac{-i}{N}})\\ 1 - P &\approx e^{-\displaystyle\sum_{i=1}^{q-1}(\frac{i}{N})}\\ 1 - P &\approx e^{-\frac{q(q-1)}{2N}}\\ 1 - P &\approx e^{-\frac{q^{2}}{2N}}\\ \end{aligned}

エイピア数のマクローリン展開を当てはめた際に、Nが十分に大きいとしてます。
また、それから試行回数も十分に大きいだろうということで-qを消してます。
ここから、試行回数qに関して解いていくと

\\ \begin{aligned} e^{-\frac{q^{2}}{2N}}&\approx 1 - P \\ -\frac{q^{2}}{2N} &\approx ln(1 - P) \\ \end{aligned}

ここで、 $P=\frac{1}{2}$ となる場合を考えると

\begin{aligned} -\frac{q^{2}}{2N} &\approx -ln(2) \\ q^{2} &\approx 2Nln(2) \\ q &\approx \sqrt{2Nln(2)} \\ q &\approx 1.1774\sqrt{N} \\ \end{aligned}

となります!試しに、N=365を入れるとわかると思いますが、大体22.5くらいなので23人集めると誕生日が重なる確率は $\frac{1}{2}$ ということがわかると思います。
さて、そんな試行回数を計算する際に物理的に効いているのは $\sqrt{N}$ ということで
$q \approx \sqrt{N}$ と言われています。シンプルで面白いですね!!
一応確認しておくと、SHA-256の場合であれば $N=2^{256}$ なので試行回数は $2^{128}$ となります。SHA-1であれば出力が160bitなので試行回数は $2^{80}$ 回ですね。

マークル・ダンガード構造とSHA-256の処理(2回表）

そろそろ、具体的にSHA-256の構造を紐解いていきましょう。
マークル・ダンガード構造はざっくりと以下のような通りです。

与えられた入力値を512 bitに分解するので、入力値を512の倍数にする必要があります。その処理がPaddingを与えている箇所です。
なのでまずは、512の倍数bitに入力値を合わせる必要がありそうです。

と思っていたら、最後の64 bitは長さを格納するために空けないといけないんですね。
$l + k + 1 \equiv 448 mod 512$ を満たす最小の、負ではないk個分だけ０を入れ込んで、
長さを最後の64bitに格納するという感じなんですね。
なるほど、だからsha-256はmessageの長さは $2^{64} bit$ 未満にしないといけないんですね。

さて大体の大筋はこんな感じなので、次は関数と書かれたところの中身を見ていきましょう。

SHA-256のラウンド関数とは(2回裏）

先程の図で表らした関数に関して、なんかの本だったかネット記事だったか忘れましたが、ラウンド関数という表現がされているのを見たことがあります。その時はなんとも思わなかったですが、今回真面目に調べてみて、分かる気がしました。というのも似たような処理を64回するからです。
今現時点で、送られてきたMessaggeに対してpaddingして、512 bitずつに分けていると思います。
この512 bitをさらに、 $32 bit * 16$ に分けます。その上で、以下のループを回します。（各演算子については本家のpaperでご確認ください。また＋は $mod 2^{32}$ ということもお気をつけください。）

その後、a,b,c,d,e,f,g,hの8つの変数を初期ベクトル（こちらも本家のpaperで。。。）
で初期化します。

そして、以下のようにa,e以外は一つずつ値をずらしていきます。（a,eはなんでこんなことをしているのでしょうか。）

そして最後に、Hashを計算します。

これを512 bitずつに対して実行していきます。

SHA-256の実装(3回表）

やっている理由はちょこちょこ分からずともやっていることは意外とシンプルなんだなーと思い僕も実装してみたんですが、うまいこといかずに諦めつつあります。とはいえなんとか完成へと持っていきたいです。。。一応github

また、今回はbit演算子というものがほぼです。
JSならこの辺を見ると実装しやすいです。こういった演算子を使いながら、bit単位で右へ左へシフトさせたり入れ替えたりしながらbinaryを変えて変えて変えまくってるんですね。ふーん、なるへそ。

SHA-256の安全性(3回裏）

実はここが本題ということにしたかったんですがgoogle sholarで論文を調べた感じあまり、どのあたりから衝突発見（計算）困難性が保証されるラインなのかはわかりませんでした。。。
正確にいうと裏が取れなかったんですが、衝突発見（計算）困難性を担保するのは160bit以上というのは見かけました。ただ、出力bit数が256以上と推奨されているといった記事も見ました。
NISTが出してるんですかね、そういうの。どこにあるんだろう。。。
まあでも、無難にSHA-2系もしくは3系を使っておくと、そんなの気にしなくてもすみますからね。
大人しくベーシックにしといた方が無難ですね。

また、2009年時点でのこちらの論文によると、とりあえずまだ大丈夫だったらしいです。この時点で41 -stepのSHA-256であれば $2^{253.5}$ のtime complexityがかかっているということらしいです。ただなぜそのような操作を行うのかに関してはひとつもわからず、どういう操作をやっているのに関しては途中で迷子になりました。誰か一緒に読んでくれる人募集中です。

さらに2009年から7年ほどたった2016年には、こちらの論文が出ています。
こちらの論文では27 -stepのSHA-256であれば衝突させることができたそうです。
これ以降は見つけられませんでしたが、どれだけ進化しているのでしょうか。（あと気になったのが41 -stepという-をstepの前に持ってくるのはなんでなんでしょうか。マイナスの単位ということでしょうか。最初読んでて驚きました。）

そんなこんなで、おそらくまだ計算量が $2^{128}$ よりも格段におちる明確な方法論は確立されていないのですかね。仮に見つかったとしても、用途によっては急な対応が必要ではないとかありそう（その逆も）ですし、これからも見守っていきましょうかね。

雨天中断（後攻のチームが優勢だった模様）

さて、最後になりましたが、結構疲れました。色々と調べていくと面白いですね。Rainbow Tableを使って平文を解読してみた！とかしてみたいです。