SHA256でデータが混ざる様を”混色”してみた

暗号学的ハッシュ関数、使ってますか。わたしはよく使ってます。たとえば、このブログでは画像のファイル名として、その中身をMD5ハッシュに掛けたものを使っています(そういうWordPressプラグインを作りました1

で、今日は暗号学的ハッシュ関数の中でもまだまだ現役のものの1つ、SHA256でデータが混ざり合う様を色を使って可視化してみました:

githubリポジトリはこちら:

今回はCanvas 2Dを使ってます。実際に動くデモサイト

入力は512ビット

SHA256は入力として512ビット( = 32bit × 16)の「ブロック」を単位としてを受け取りながら計算します。今回は便宜上、1ブロックだけ与えられた事にしました。左上の「input」の下にかかれている点々(512個あります)がその入力のビット列です。ビットには、それぞれに異なる色を塗って区別できるようにしてあります。

前準備

SHA256では、次の疑似コードにそって「w」と呼ばれる2048ビットの値を計算します:

create a 64-entry message schedule array w[0..63] of 32-bit words
(The initial values in w[0..63] don't matter, so many implementations zero them here)
copy chunk into first 16 words w[0..15] of the message schedule array

Extend the first 16 words into the remaining 48 words w[16..63] of the message schedule array:
for i from 16 to 63
    s0 := (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3)
    s1 := (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor (w[i-2] rightshift 10)
    w[i] := w[i-16] + s0 + w[i-7] + s1

真ん中にある「w」と書かれている下の点々の塊の部分がそれです(上から下に行くにつれてiが増える方向になっています)。計算式を見ると分かるのですが、すこし前(w[i-15]とw[i-2])の値を混ぜ合わせながら計算されているので、下の方に行けばいくほど色が似たりよったりになって、くすんでいきます。

圧縮関数

wの計算が終わったら、SHA256では「圧縮関数」と呼ばれる、次の64回のループを行います(h0〜h7は素数の平方根の小数部分だそうで、つまり定数です)。

Initialize working variables to current hash value:
a := h0
b := h1
c := h2
d := h3
e := h4
f := h5
g := h6
h := h7

Compression function main loop:
for i from 0 to 63
    S1 := (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
    ch := (e and f) xor ((not e) and g)
    temp1 := h + S1 + ch + k[i] + w[i]
    S0 := (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
    maj := (a and b) xor (a and c) xor (b and c)
    temp2 := S0 + maj
 
    h := g
    g := f
    f := e
    e := d + temp1
    d := c
    c := b
    b := a
    a := temp1 + temp2

この時に出てくる、a〜hまでの変数を右に並べました。それぞれ32ビットの値なので、32個の箱が上から下に並んでいます。ステップごとに最初はがやがやしてた色が、途中ぐらいからくすんだ紫一色になっていくのがわかります。

出力

で、64回のループが終わったら、次のコードでh0〜h7を更新して、h0〜h7を連結して256bit(=32bit ×8)の「ハッシュ」が得られる、という仕組みになっております:

    Add the compressed chunk to the current hash value:
    h0 := h0 + a
    h1 := h1 + b
    h2 := h2 + c
    h3 := h3 + d
    h4 := h4 + e
    h5 := h5 + f
    h6 := h6 + g
    h7 := h7 + h

Produce the final hash value (big-endian):
digest := hash := h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7

虹色が紫になった

そんなこんなで、無事SHA256というポテトミキサーで混ぜ合わせたビット列は、元の虹色を失って、よくわからんくすんだ紫色の256個のビットとなりまあしたとさ。

なぜ紫色になるのか?

オリジナルの512個のビットの色を平均したら(80, 80, 80)になっているのは確かめたのですが、SHA256にかけてみたら(149, 81, 145)というくすんだ紫色になってしまいました。doubleの誤差のせいとかなのか、彩色ルール(後に書く)のせいなのか、そもそもそういうもんなのか、何か実装がバグってるのか、…それはよくわかりませんw

(一応、空っぽの入力を入れた時にWikipediaに書かれてるのと同じ値が得られる事は確認してあるので、バグではないと思うのですが…)

追記:色の塗り方の縦横を入れ替えると灰色になった

わからん、全然わからん。でもこっちのほうが見ていて楽しいですね。

参考:彩色ルール

二項演算子に関するルール

ビット同士で下記の演算が起こった時は、結果のビットの色はそれぞれの平均とする:

  • add(繰り上がりが有るときは、色は3ビットの平均)
  • xor
  • and

ただし、定数やゼロクリアされた後のビットなどは「無彩色」とし、これらと演算するときは平均する時には考慮しない

例:

  • 無彩色のビット同士で演算が行われたら結果は無彩色のビットになる
  • 無彩色のビットと赤色のビットをandしたら、同じ赤色のbitになる
  • 赤色のビットと青色のビットをxorしたら、結果は紫のbitになる

単項演算子に関するルール

not演算(1の補数)や単項マイナス演算(-x)、シフト演算が行われた時はビットの色の情報は変化しない。

  1. MD5はもはや暗号学的には全く安全ではないそうですが、べつに改ざんの検出を行いたいわけではなく、単に重複しないファイル名を考えるのを自動でやってほしいだけなのと、出てきた結果が20バイトと大変短いことから採用しています。 []