あけましておめでとうございます。

ビットコインの基盤技術であるブロックチェーンではSHA-256というハッシュ関数が使用されており、強力な改竄耐性を実現するために重要な役割をはたしています。
ブロックチェーンに限らずITの分野ではSHA-256は頻繁に登場します。
SHA-256の説明として、データを決まったサイズの文字列(ハッシュ値)に変換し、またハッシュ値からもとのデータを復元することが困難という特性はよく聞きます。実際どのようにそれが実現されているのか気になったので調べてみました。

SHA-256の概要

sha256は暗号学的ハッシュ関数のSHA-2シリーズの一つです。
ハッシュ関数とは元のデータからダイジェスト(要約)を得る関数のことで、そこに

  • 一方向性
  • 衝突困難性

が追加されたものを暗号学的ハッシュ関数と呼びます。

sha256の仕様と実装

sha256の仕様はアメリカ国立標準技術研究所 (NIST) が発行しているFIPSという標準規格にあります。
FIPS 180-2, Secure Hash Standard (superseded Feb. 25, 2004)

仕様が公開されているので誰でも作ることが可能です。

wikiに擬似実装コードが掲載されています。
SHA-2 - Wikipedia

またgithubにもちらほら実装が上がっています。

SHA-256の仕組み

初期値

SHA-256では最終的に32byteのデータが出力されますが、これと同じサイズのハッシュ値が初期値として与えられています。

(初期ハッシュの16進数表記)
6a09e667 bb67ae85 3c6ef372 a54ff53a 510e527f 9b05688c 1f83d9ab 5be0cd19

この32byteの初期ハッシュを入力データを用いて変化させます。
どうやってこの初期値を決めているかというと、小さい方から8個目までの素数の平方根の少数部分の最初の32bit部分です。

パディング処理とブロックへの分割

SHA-256ではMerkle-Damgård構造と呼ばれる繰り返しの構造が用いられています。
メッセージを固定長のブロックへ分割して一つずつ処理していきます。


Merkle–Damgård construction - Wikipedia

SHA-256では入力メッセージを64byteずつのブロックに分割しますが、最後のブロックは端数となるため64byteになるまで埋めてきっちり64byteにします。
例えばこのような50byteのデータがあるとします。

これにパディング処理を施して64byteにすると↓こうなります。

  • 赤:入力データの末尾に差し込む1bit
  • 緑:0bitの必要な分だけのパディング
  • 青:末尾8byteを用いた入力データの長さ
  • この場合50byteの入力データ長は400(bit)、16進数で190

末尾に入力データの長さを入れることでハッシュが更に強力になる(らしい・・Merkle-Damgård強化だとか

この繰り返し構造では初期ハッシュと分割されたメッセージブロックを用いてハッシュ処理して、またそのハッシュと次のメッセージブロックを用いてハッシュしてまた・・・と全てのブロックを消化するまで続きます。この各処理で入力ハッシュとメッセージの長さが固定であることが必要です。なので最初にパディング処理をして64byteの倍数にしています。

ちなみに入力データの長さが元々64byteの倍数だったり、最後のブロックの末尾の8byte分を足すと64byte超えてしまう場合はもう1ブロック足します。

64回のラウンド(ローテーション)でハッシュ

メッセージブロック一つにつき1回ハッシュ処理を行っているが、その内部では64回のラウンドが行われています。

  • 先程の初期ハッシュ32byteを4byteずつ8個に分けます。これを仮にA,B,C,D,E,F,G,Hとします。
  • これらを図のように一つずつずらしてローテーションします。ただし、4番目と8番目はただずらしただけではなく特別な処理で変化させます。
  • これが64回繰り返されます。

ラウンドの計算式の紹介と実装コードの引用紹介

計算式は FIPS 180-2を見て下さい。
9ページと18ページです。

pysha2/sha256.py at master · thomdixon/pysha2


""""""""""""""""""""""""""""""""""""
ラウンド部分抜粋
""""""""""""""""""""""""""""""""""""
def _rotr(self, x, y):
    return ((x >> y) | (x << (32-y))) & 0xFFFFFFFFL 

def _sha256_process(self, c): 
    w = [0]*64
    w[0:16] = struct.unpack('!16L', c)
    for i in range(16, 64):
        s0 = self._rotr(w[i-15], 7) ^ self._rotr(w[i-15], 18) ^ (w[i-15] >> 3)
        s1 = self._rotr(w[i-2], 17) ^ self._rotr(w[i-2], 19) ^ (w[i-2] >> 10)
        w[i] = (w[i-16] + s0 + w[i-7] + s1) & 0xFFFFFFFFL

a,b,c,d,e,f,g,h = self._h

for i in range(64):
    s0 = self._rotr(a, 2) ^ self._rotr(a, 13) ^ self._rotr(a, 22)
    maj = (a & b) ^ (a & c) ^ (b & c)
    t2 = s0 + maj
    s1 = self._rotr(e, 6) ^ self._rotr(e, 11) ^ self._rotr(e, 25)
    ch = (e & f) ^ ((~e) & g)
    t1 = h + s1 + ch + self._k[i] + w[i]

    h = g
    g = f
    f = e
    e = (d + t1) & 0xFFFFFFFFL
    d = c
    c = b
    b = a
    a = (t1 + t2) & 0xFFFFFFFFL

    self._h = [(x+y) & 0xFFFFFFFFL for x,y in zip(self._h, [a,b,c,d,e,f,g,h])]

・・・何をやっているの・・?

メッセージ拡張

64byteの1ブロックを256byteに拡張します。
その方法は、まず4byteずつ16ブロックに分割して、その16個を用いてさらに48個を生成します。前述の式(1),(2)
合わせて4byte×64個=256byteとなります。
これを64回のラウンドで1ブロックずつ変化を与える材料として使います。

非線形に発散

SHA-256には初期ハッシュに加えもうひとつ定数があります。4byteハッシュ×64個の定数kです。
FIPS 180-2に書いてあります。
どうやって導き出しているかというと、最小から64個目までの素数の立方根の少数部分の最初の32bit部分です。

ラウンド1回につき
* 定数kの一つ
* メッセージ拡張ブロック1つ
* 右シフト、巡回ビットシフト、排他的論理和などのビット演算

を用いて初期ハッシュの1番目(A)と5番目(B)を変化させつつ全体を一つずらしていきます。
この処理の意図は要するに元の平文をできるだけぐちゃぐちゃにすることです。

MD5やSHA-1の内部ブロック暗号はARX型と呼ばれ、算術加算でのけた上がり(Addition)と巡回ビットシフト演算(Rotation)と排他的論理和(XOR)との組み合わせによって非線形性を導入している
暗号学的ハッシュ関数 –安全神話の崩壊と新たなる挑戦

SHA-2はSHA-1と構造が似ているのでこれはSHA-2にも当てはまると思います。
通常入力データは統計的に偏っています。例えば文章だと頻出単語とそうでない単語があるでしょう。その偏りが最終的なハッシュ値にあらわれてしまうと攻撃者にとってヒントを与えてしまします。この部分の演算を繰り返すことで影響を拡散させ全体に波及させています。ハッシュ関数は入力データが少し変わるとまったく違うハッシュ値になるというのはこういった仕組みで実現されています。

ラウンド中のハッシュの変化

FIPS 180-2の付録に「abc」という3文字をSHA-256でハッシュ化する様子が紹介されています。
具体的に64回のラウンド中のハッシュの変化の最初と最後を抜粋します。

はじめのt=0Aのハッシュに着目すると1ラウンドごとに右にずれていき、Eの場所でまったく違うハッシュに変換されています。これを64回繰り返した結果t=63の列のハッシュはどれも最初のハッシュとは異なります。

前の結果のハッシュを次のブロック処理の初期ハッシュとして渡す

前の結果のハッシュと、今回のメッセージブロックを用いてまた64回のラウンドを行います。
すべてのメッセージブロックをハッシュし終えたら最後に8つのハッシュを一つにして完成です。

といった感じで実装自体はそんなに難しくありませんでした。実装の簡易さもその普及の一要因のようです。

おまけ

定数kを求めてみる

定数kは最小から64個目までの素数の立方根の少数部分の最初の32bit部分でした。
素数の導出はおいといて立方根の少数部分の先頭から32bitを取り出す関数


"""
立方根の少数部分のうち先頭から32bit分をhexで取り出す
"""
def convert_cube_root_fractional_part_to_hex(n,hex_chars=8):
    cube = n**(1/3)
    flac_part = cube - floor(cube)
    c = int(floor(flac_part*(16**8)))
    return '0x{:x}'.format(c)

print(convert_cube_root_fractional_part_to_hex(2)) """0x428a2f98"""
print(convert_cube_root_fractional_part_to_hex(11)) """0x3956c25b"""

FIPS180-2記載の定数値と一致。
立方根じゃなく平方根にしたら初期ハッシュ値も求まる。

Maj,ch・・?

ラウンド処理で使ったMaj()やCh()は調べてみると多数決関数、選択(?。違うかも?)関数と呼ばれる論理代数の分野の概念らしい。
ここで用いられているのは適当にひっぱってきたのではなく、何かそれ相応の数学的背景があると予想しますがよくわかりません・・。

質問:SHA2はなぜ安全?

答え:SHA2に対する有効な攻撃が発見されていないから

SHA2を調べはじめる前は安全であることが論理的に証明されていると勘違いしていたのですが、調べているうちにどうやら違うということがわかりました。
実際にSHA2の前身のSHA1に対して、総当り(2^80)よりもはるかに少ない計算量(2^63)で解く攻撃手法が見つかっています。SHA2もこの先ずっと安泰とはいえないようです。

参考

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です