SHA-256 algorithm

2022-10-10

こんにちは

どうも、僕です。

今週猫がきます。

猫の名前について、友人と雑談をしていて、

名前なんて記号なんだから呼びやすくて聞こえが良ければなんでもいいよ

と言われたので、記号だなんてそんなのハッシュではないかと思ったと同時に、ハッシュという名前はとてもいいなと思いました。

ハッシュという名前にしっくりきたので名前はハッシュにしようと思ったものの、筆者はコンピュータサイエンスの学部を出ているのにも関わらずハッシュ化アルゴリズムを自前実装した経験がありません。

そのため、今回は [Secure Hash Standard (SHS)](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf) を参考にしながら SHA-256 のアルゴリズムを書いてみました。

SHA-256 とは

SHA-256 は 2001 年に NIST によって FIPS 180-4 として国際標準化されたハッシュ化アルゴリズムです。

暗号学的ハッシュ関数として設計されており、ある原文を元に同じ値になる別の原文を効率よく探索することは難しいとされています。

SHA-2

に分類され、SHA-256 は 256 ビットのハッシュ値を生成します。

他にも SHA-224, SHA-384, SHA-512 などがあり、SHA-224 と SHA-384 は、それぞれ SHA-256 と SHA-512 を単純に切り詰めたバージョンであり、初期値のみが異なるという特性があります。

実装

実装をするにあたって、[Secure Hash Standard (SHS)](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf) を参考にしながら行ったため、アルゴリズムや定数は SHS に準拠しています。

また、一部外部の記事や書籍を参考にしてる部分がありますが、おおむね SHS の仕様に則っています。

定数

まずは定数を定義します。SHA-256 では 64 個の定数が必要です。

この定数は SHS の 4.2.2 SHA-224 and SHA-256 Constants に記載されています。

// 4.2.2 SHA-224 and SHA-256 Constants
const K: [u32; 64] = [
    0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
    0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
    0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
    0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
    0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
    0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
    0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
    0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2,
];

また、初期値も定義します。

この初期値は SHS の 5.3.3 SHA-224 and SHA-256 Initial Hash Values に記載されています。

初期値は 8 個あり、それぞれ 32 ビットの値です。

// 5.3.3 SHA-256
const H0: [u32; 8] = [0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19];

関数

SHA-256 では 6 個の関数を使用します。

これらの関数は SHS の 4.1.2 SHA-256 Functions に記載されています。

Rust での命名規則はスネークケースがデフォルトですが、ここでは関数名を SHS に準拠して一部キャメルケースで記載します。そのため、`#[allow(non_snake_case)]` を付与しています。

SHA-224 and SHA-256 both use six logical functions, where each function operates on 32-bit

words, which are represented as x, y, and z. The result of each function is a new 32-bit word.

とある通り、これらの論理関数は 32 ビットの値を引数に取り、32 ビットの値を返します。

// 4.1.2 SHA-224 and SHA-256 Functions
#[allow(non_snake_case)]
fn Ch(x: u32, y: u32, z: u32) -> u32 {
    (x & y) ^ (!x & z)
}

#[allow(non_snake_case)]
fn Maj(x: u32, y: u32, z: u32) -> u32 {
    (x & y) ^ (x & z) ^ (y & z)
}

#[allow(non_snake_case)]
fn Sigma0(x: u32) -> u32 {
    x.rotate_right(2) ^ x.rotate_right(13) ^ x.rotate_right(22)
}

#[allow(non_snake_case)]
fn Sigma1(x: u32) -> u32 {
    x.rotate_right(6) ^ x.rotate_right(11) ^ x.rotate_right(25)
}

#[allow(non_snake_case)]
fn sigma0(x: u32) -> u32 {
    x.rotate_right(7) ^ x.rotate_right(18) ^ (x >> 3)
}

#[allow(non_snake_case)]
fn sigma1(x: u32) -> u32 {
    x.rotate_right(17) ^ x.rotate_right(19) ^ (x >> 10)
}

padding

padding とは前処理のことで、入力されたメッセージを 512 ビット（64 バイト）のブロックに分割するために必要です。SHS の 5.1.1 Padding the Message に記載されています。

SHA-256 では 512 ビットのブロックに分割するために、メッセージの末尾に 1 ビットの 1 と 0 ビットの 0 を追加します。

注目すべき点は以下で、メッセージが 512 ビットのブロックに収まる場合は 1 ビットの 1 と 0 ビットの 0 で 64 バイトになるように padding します。

また、メッセージの末尾にはメッセージのビット長を 64 ビットの整数として追加します。

padded = match len % 64 < 56 {
    true => {
        padded.extend_from_slice(&tmp[..56 - len % 64]);
        padded
    },
    false => {
        padded.extend_from_slice(&tmp[..64 - len % 64 + 56]);
        padded
    },
};

上記の match 式で値を整えたあと、メッセージのビット長を 64 ビットの整数として追加し、最終的な padding されたメッセージを返します。

// 5.1 Padding the Message
fn padding(message: &[u8]) -> Vec {
    let len = message.len();
    let mut tmp: Vec = Vec::new();
    tmp.push(0x80); // バイトで扱う
    tmp.extend_from_slice(&[0; 63]);

    let mut padded = message.to_vec().iter().map(|&x| x as u32).collect::>();

    padded = match len % 64 < 56 {
        true => {
            padded.extend_from_slice(&tmp[..56 - len % 64]);
            padded
        },
        false => {
            padded.extend_from_slice(&tmp[..64 - len % 64 + 56]);
            padded
        },
    };

    let bits = (len as u64) * 8; // バイトの長さをビットに変換
    let mut size = vec![0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00];
    size[4] = ((bits & 0xff) >> 24) as u32;
    size[5] = ((bits & 0xff) >> 16) as u32;
    size[6] = ((bits & 0xff) >> 8) as u32;
    size[7] = (bits & 0xff) as u32;

    padded.append(&mut size.clone());
    padded
}

compute

前処理が終わったため、ハッシュ値計算を行います。compute は SHS の 6.2.2 SHA-256 Computation に記載されています。

SHA-256 のハッシュ値計算は、N 個のメッセージブロック M に対して、1 ≤ i ≤ N の順に以下の処理を行います。

最初に、関数と必要な定数を定義します。

// 6.2.2 SHA-256 Hash Computation
fn compute(message: Vec) -> [u32; 8] {
    #[allow(non_snake_case)]
    let N = message.len() / 64; // メッセージの長さ
    #[allow(non_snake_case)]
    let W = &mut [0u32; 64]; // メッセージスケジュール
    #[allow(non_snake_case)]
    let mut H = H0; // 初期値
}

メッセージ拡張

まず、メッセージ拡張を行います。メッセージ拡張とは、メッセージブロック M から 64 個の 32 ビットのワード W を生成する処理です。

SHA-256 では、メッセージ拡張は W が 16 個のワードの場合とそれ以外の場合で分けられます。

まず、W が 16 未満の場合は、メッセージブロック M の 32 ビットのワードを渡します。

M の 32 ビットのワードを 32 ビットのワードに変換するために、以下のように 4 バイトずつに分割します。

let chunk = &message[(i - 1) * 64..i * 64];
for t in 0..16 {
    W[t] = (chunk[t * 4] as u32) << 24
        | (chunk[t * 4 + 1] as u32) << 16
        | (chunk[t * 4 + 2] as u32) << 8
        | (chunk[t * 4 + 3] as u32);
}

次に、W が 16 個のワードではない場合は、以下の処理を行います。

for t in 16..64 {
    W[t] = sigma1(W[t - 2]) + W[t - 7] + sigma0(W[t - 15]) + W[t - 16];
}

圧縮

次に、圧縮を行います。

8 個のバッファを用意し、初期値として H0 を設定します。

let mut a = H[0];
let mut b = H[1];
let mut c = H[2];
let mut d = H[3];
let mut e = H[4];
let mut f = H[5];
let mut g = H[6];
let mut h = H[7];

次に、0 から 63 の順に以下の処理を行い、ハッシュ化をします。

正直ここは Rust 力不足を感じますが、単に足し算をするとオーバーフローをしてしまうので計算は `u32::wrapping_add` 関数を用いています。

for j in 0..64 {
    let s1 = Sigma1(e);
    let ch = Ch(e, f, g);
    #[allow(non_snake_case)]
    let T1 = h.wrapping_add(s1).wrapping_add(ch).wrapping_add(K[j]).wrapping_add(W[j]);

    let s0 = Sigma0(a);
    let maj = Maj(a, b, c);
    #[allow(non_snake_case)]
    let T2 = s0.wrapping_add(maj);

    h = g;
    g = f;
    f = e;
    e = d.wrapping_add(T1);
    d = c;
    c = b;
    b = a;
    a = T1.wrapping_add(T2);
}

そして、最後に上で生成した値を用いて、H を更新します。

H[0] = a.wrapping_add(H[0]) & 0xffffffff;
H[1] = b.wrapping_add(H[1]) & 0xffffffff;
H[2] = c.wrapping_add(H[2]) & 0xffffffff;
H[3] = d.wrapping_add(H[3]) & 0xffffffff;
H[4] = e.wrapping_add(H[4]) & 0xffffffff;
H[5] = f.wrapping_add(H[5]) & 0xffffffff;
H[6] = g.wrapping_add(H[6]) & 0xffffffff;
H[7] = h.wrapping_add(H[7]) & 0xffffffff;

全てまとめると、`compute` 関数は以下のようなコードになります。

戻り値は上の処理で更新をした H になります。

fn compute(message: Vec) -> [u32; 8] {
    #[allow(non_snake_case)]
    let N = message.len() / 64;
    #[allow(non_snake_case)]
    let W = &mut [0u32; 64];
    #[allow(non_snake_case)]
    let mut H = H0;

    for i in 1..N + 1 {
        let chunk = &message[(i - 1) * 64..i * 64];
        for t in 0..16 {
            W[t] = (chunk[t * 4] as u32) << 24
                | (chunk[t * 4 + 1] as u32) << 16
                | (chunk[t * 4 + 2] as u32) << 8
                | (chunk[t * 4 + 3] as u32);
        }
        for t in 16..64 {
            let s0 = sigma0(W[t - 15]);
            let s1 = sigma1(W[t - 2]);
            W[t] = W[t - 16].wrapping_add(s0).wrapping_add(W[t - 7]).wrapping_add(s1);
        }

        let mut a = H[0];
        let mut b = H[1];
        let mut c = H[2];
        let mut d = H[3];
        let mut e = H[4];
        let mut f = H[5];
        let mut g = H[6];
        let mut h = H[7];

        for j in 0..64 {
            let s1 = Sigma1(e);
            let ch = Ch(e, f, g);
            #[allow(non_snake_case)]
            let T1 = h.wrapping_add(s1).wrapping_add(ch).wrapping_add(K[j]).wrapping_add(W[j]);

            let s0 = Sigma0(a);
            let maj = Maj(a, b, c);
            #[allow(non_snake_case)]
            let T2 = s0.wrapping_add(maj);

            h = g;
            g = f;
            f = e;
            e = d.wrapping_add(T1);
            d = c;
            c = b;
            b = a;
            a = T1.wrapping_add(T2);
        }

        H[0] = a.wrapping_add(H[0]) & 0xffffffff;
        H[1] = b.wrapping_add(H[1]) & 0xffffffff;
        H[2] = c.wrapping_add(H[2]) & 0xffffffff;
        H[3] = d.wrapping_add(H[3]) & 0xffffffff;
        H[4] = e.wrapping_add(H[4]) & 0xffffffff;
        H[5] = f.wrapping_add(H[5]) & 0xffffffff;
        H[6] = g.wrapping_add(H[6]) & 0xffffffff;
        H[7] = h.wrapping_add(H[7]) & 0xffffffff;
    }

    H
}

ハッシュに変換

ここまでくると、ハッシュ化の処理は終わりなので、最後にハッシュのリストに対して変換関数を噛ませてあげてハッシュ値を生成します。

fn to_hex(bytes: &[u32]) -> String {
    let mut s = String::new();
    for &byte in bytes {
        s.push_str(&format!("{:02x}", byte));
    }
    s
}

fn gen_sha256(message: &[u8]) -> String {
    let padded = padding(message);
    let hash = compute(padded);
    to_hex(&hash)
}

最後に、`main.rs` に以下のようなコードを追加して、実行してみると以下のような結果が得られます。

fn main() {
    let input = b"I wanna be cat.";
    let hash = gen_sha256(input);
    println!("{}", hash);
}

% cargo run
   Compiling sha256 v0.1.0 (/path/to/sha256)
    Finished dev [unoptimized + debuginfo] target(s) in 0.22s
     Running `target/debug/sha256`
40d8f0c6dc3c31421913513e66a534560d4a3929acd1113f9123fdbfc28ee86

まとめ

SHA-256 のアルゴリズムの実装を仕様を見ながらしてみましたが、これがどうして安全で、どうしてこのように標準化されているのかまではまだあまり踏み込めていません。

また、他の暗号化アルゴリズムとの比較や、使い分け、具体的なユースケース等についてもまだまだ理解できていない点が多いです。

自分自身が疎い領域というのもありますが、今後はこのような領域にも積極的に手をつけていき、安全で堅牢なアプリケーションを書けるようにしていきたいです。