中身に入る前に...

グループワークとしてリレーブログを続けていたら、セキュリティキャンプフォーラム2022で発表させていただけることになりました

www.ipa.go.jp

他の内容もおもしろそう2

こんな機会はなかなかないので、楽しんできたいと思います〜

例によってリレーブログの時間です*1！前の僕の記事はこれ、前回の方のブログはこちらになります。

potaxyz.hatenablog.jp

bigdrea6.hatenablog.com

今回のテーマはハッシュ、ということでハッシュ関数の1つであるSHA256を実装してみようかなと思います。

※色々あって記事の内容が前の方と被ってしまいましたが、書いてしまったのでせっかくなので投稿します

ハッシュ関数の概要

ハッシュ関数とは

ハッシュ関数とは、任意の長さの入力データ（メッセージ）を一定の手順で計算し、あらかじめ決められた固定長の出力（ハッシュ値）を得る関数です。

とくに、セキュリティのために使われるのは一方向ハッシュ関数とか、暗号学的ハッシュ関数とか言われて、（条件がゆるいものから厳しいものの順に）次の3つの暗号学的性質を持ちます。

衝突困難性（衝突発見困難性）：同じ出力値を生成するような2つの入力値を発見することが困難であること。すなわち、H(m1)=H(m2)となるような異なるメッセージm1とm2を探すことが困難であること。
第2原像計算困難性：ある入力値と同じハッシュ値となるような別の入力を求めることが困難であること。すなわち、m1があたえられたときH(m1)=H(m2)となるようなm2（ただしm1とは異なる）を探すのが困難であること。
原像計算困難性（一方向性）：出力値から入力値を発見することが困難であること。すなわち、あるハッシュ値hが与えられた時、h=H(m)をみたす任意のメッセージmを探すことが困難であること。

ちなみに、ハッシュってのは、ハッシュドポテトとかのハッシュで、切り刻んでごちゃごちゃにして混ぜるみたいな意味です。

利用例

ハッシュ関数は、

パスワード認証
- 平文パスワードではなく、平文のハッシュ値をシステムに保存しておき、ログインするときには入力されるたびにハッシュ値を計算してシステム内のハッシュ値と比較する）
ワンタイムパスワードの生成
- S/Key方式
改竄検知
- ファイルの中身が変わっていないならハッシュ値を計算したら前に計算したハッシュ値と完全に一致するはず
デジタル署名
- 送信者から送るデータDとする。受信者は、データDを受け取り、ハッシュ値[X]を計算する。また、送信者から「署名」として、暗号化されたDのハッシュ値が送られてくる。これを受信者側で復号する[Y]。XとYが等しければ署名の検証に成功したことになる

などに利用されています。

上で述べた性質から、めっっちゃ長いデータでもハッシュ関数を通してハッシュ値を得れば、短いデータにしてやることができます。大きな本体のデータそのものを扱って確認するよりも、小さい値を確認するだけで正真性（改竄などがされていないこと）を確かめることができます。

種類

ハッシュ関数にはMD5、SHA-1、SHA-256など、色々な種類があります。MD5やSHA-1はすでに衝突困難性が破られているため、使用は非推奨とされていますが、セキュリティが必要とされていないところでは今でも使うとかなんとかどこかで見たことがある気がします（うろ覚え）。

SHA-256

ハッシュ関数について簡単にまとめたところで、今回はSHA-256をピックアップして実装してみようと思います。

ちなみに、ここで実装するのは自分の理解を深めるという目的あってのことです。セキュリティ的にはここにあるコードを利用することはせず、SHA-256の機能を提供してくれるライブラリ等を使う方がいいです。

なお、SHA-256の簡単なしくみの概要は前回のブログを参照してください。

あと、アニメーションでわかりやすくSHA-256の仕組みを説明してくれるものもあるので、興味があれば見てみるのもいいかも。

github.com

実装

実装にはNISTの論文を参考に、他の実装されている方のものも参考にしつつ、という感じで実装しました。

使用する定数の定義

Kには小さい方から64個の素数の立方根
Hには小さい方から8個の素数の平方根

の、小数点以下32bitが格納されています。

なんでこんな定数が使われているのかはどこにも書いていないので謎です。が、私見と調べてみた感じとして、2つ理由を考えてみました。私は専門家でもなんでもないので、1つの考えとして受け取ってください！真に受けないこと！

恣意的な数を選んでバックドアを作ったりはしていないということ。
素数の平方根や立方根を用いているというのは、あまり恣意的な感じがしない。他の疑似的にランダムな数字を定数に使用してもよさそうな気がするが、それが確実にランダムであるという保証はどこにもない。他人からはすぐにはわからないが、実際には仕様を定めた人にしかわからないような脆弱性がある定数かもしれない。
素数の平方根や立方根が正規数であることが（未解決だが）予想されているため。
正規数とは、無限小数表示において数字が一様に分布しており、数字の列が現れる頻度に偏りがないという性質を持つ実数のこと（wikipedia）。素数の平方根は正規数であることが予想されており、小数点以下の数字の並びが一様に分布しているとエントロピーが最大になってくれるのでうれしいのかもしれない。

羅列したところであまり意味はないと思うので、雰囲気だけコードを載せます

K = (
    0x428A2F98,
    0x71374491,
    ...,
    0xC67178F2,
) # 実際には64個の数字が格納されている
H = (
    0x6A09E667,
    0xBB67AE85,
    ...,
    0x5BE0CD19,
) # 実際には8個の数字が格納されている

使用する関数の定義

以下に使用する8つの演算を定義しておきます。なお、計算は全て$\bmod\,2^{32}$上で考えるので、それを超えてしまうことのある演算には& 0xFFFFFFFFとして、$\bmod\,2^{32}$をとるのに該当する操作をおこなっています。

def ROTR(x, n):
    return ((x >> n) | (x << (32 - n))) & 0xFFFFFFFF


def SHR(x, n):
    return x >> n


def Ch(x, y, z):
    return (x & y) ^ (~x & z)


def Maj(x, y, z):
    return (x & y) ^ (x & z) ^ (y & z)


def SIGMA0(x):
    return ROTR(x, 2) ^ ROTR(x, 13) ^ ROTR(x, 22)


def SIGMA1(x):
    return ROTR(x, 6) ^ ROTR(x, 11) ^ ROTR(x, 25)


def sigma0(x):
    return ROTR(x, 7) ^ ROTR(x, 18) ^ SHR(x, 3)


def sigma1(x):
    return ROTR(x, 17) ^ ROTR(x, 19) ^ SHR(x, 10)

padding処理

以下のようなフォーマットの512bitsの倍数の下図の赤枠にあたるデータを成形します。lbitsの長さのメッセージMとします。

f:id:potaxyz:20220228234036j:plain

仕様書にはbit単位で書いてありますが、実装にはbyte単位で考えることに注意します。つまり、下のようになります。

f:id:potaxyz:20220228234128j:plain

まず、ハッシュ関数にかけたいメッセージmessageをutf-8でエンコードしておきます（メッセージのbyte数を正確にはかりたいため）。

メッセージの長さをmessage_lenとしてbyte数で取得しておきます。

$56\leq (l'\,\bmod\, 64)\leq 63$ byteをみたす数 $l'$ になるとハッシュ関数に入れるデータの形に合わなくなってしまう（一番後ろに入れる元のメッセージの長さのbit数を格納できない）ので、その分1ブロック増やします。

一番後ろに元のメッセージ長のbit数を表現する8byteを入れるのですが、message_lenとして得られているのはbyte数なので、3つシフトさせてbit数表現に直しておきます。

最終的に成形して得られるデータは「元のメッセージ+区切りの0x80+0埋め0x00+元のメッセージ長のbit数を表現する8byte」となります（これをあらためてmessageとしてやります）。

今回はこのメッセージのハッシュ値を計算してみましょう。

message = "シャーっと実装するSHA256🐱"

message = message.encode("utf8")

message_len = len(message)
padding_len = 64 - 8 - 1 - message_len % 64
if message_len % 64 > 64 - 8 - 1:
    padding_len += 64
message = (
    message + b"\x80" + b"\x00" * padding_len + struct.pack("!Q", message_len << 3)
)
message_len += 1 + padding_len + 8

本処理

padding処理を行なったデータを64byteずつに分け、先頭からその64byteごとのブロックをハッシュ計算にかけていきます。上で設定していたHというのが初期ハッシュ値というやつで、それと64byteごとのブロックを順次演算させてやります。

while len(message) >= 64:
    message_block = struct.unpack("!16L", message[:64])
    H = sha256_hash_computation(message_block)
    message = message[64:]

本処理は以下のような形になっています。こうやってみると意外と単純？

def sha256_hash_computation(message_block):
    W = [0] * 64

    # 1. Prepare the message schedule, W[t]:
    W[0:16] = message_block
    for t in range(16, 64):
        W[t] = (
            sigma1(W[t - 2]) + W[t - 7] + sigma0(W[t - 15]) + W[t - 16]
        ) & 0xFFFFFFFF  # +はmod 2^32上の演算であることに注意

    # 2. Initialize the eight working variables, a-h with the (i-1)st hash value:
    a, b, c, d, e, f, g, h = H

    # 3.
    for t in range(64):
        T1 = h + SIGMA1(e) + Ch(e, f, g) + K[t] + W[t]
        T2 = SIGMA0(a) + Maj(a, b, c)
        h = g
        g = f
        f = e
        e = (d + T1) & 0xFFFFFFFF
        d = c
        c = b
        b = a
        a = (T1 + T2) & 0xFFFFFFFF

    # 4. Compute the ith intermediate hash value Hi
    return [(x + y) & 0xFFFFFFFF for x, y in zip(H, [a, b, c, d, e, f, g, h])]

結合

最後に、8つの数が入っている配列Hを結合します。

message_digest = b"".join([struct.pack("!L", i) for i in H])

これでbit表示が得られていますが、ハッシュ値の表示として16進数に直しておきます。

message_digest = message_digest.hex()

これでハッシュ値を表示してみると

print(message_digest)

43b682dc606a6321cd51a05268c60f93fe2694473d34650bfb1c093ee560f795

が得られました。他のSHA256を計算してくれるものを使うと同じ値が得られるので、正しい実装ができていそうです。

動かしてみる

google colaboratoryで作ってみました。興味がある人は中のmessageのところとか書き換えて遊んでみよう〜

おわりに

ハッシュ関数、特にSHA-256には詳しくなれた気がします！

次回はこちらです。

参考文献

[1] NISTの論文

[2] Software Design 2022年3月号｜技術評論社

[3] 『暗号技術入門第3版秘密の国のアリス』

[4] マスタリングTCP/IP 情報セキュリティ編 | Ohmsha

これまでのリレーブログ記事まとめ

ここにリレーブログ記事の履歴を載せておきます

*1:seccampのグループワークから生まれた企画。リレーブログのルール：前の人がが次の人のテーマを決める

ポタージュを垂れ流す。

マイペースこうしん（主に旅行）

ハッシュ関数について（後編？ + SHA-256を実装してみる）