BLAKE2s

# はじめに

BLAKEは、SHA-3の最終選考まで残ったハッシュ関数です。
これを改良したものが、BLAKE2と呼ばれるもので、64ビットのBLAKE2bと32ビットのBLAKE2sがあります。
詳しくは、[BLAKE - Wikipedia](https://ja.wikipedia.org/wiki/BLAKE)を参照ください。

ここでは、[RFC-7693](https://tools.ietf.org/html/rfc7693)の手順で、BLAKE2sの実装をjavascriptで行いたいと思います。
（javascriptは64ビット演算が通常の整数で出来ない為）

# BLAKE2s

今回は、`BLAKE2s`クラスを作成します。

```javascript
class BLAKE2s {
    // ここに各処理を記述します。
}
```

## コンストラクタ

各値の初期化を設定して、インスタンスを返します。

- パラメータ
    - ハッシュサイズ（`nn`）
    - キー（`key`）
- リターン
    - BLAKE2sオブジェクト 


①キーサイズ　　　　：32バイトまでのキーを使う事が出来ます。なしでも可能です。
②ハッシュサイズ　　：1~32バイトが設定可能です。
③インプットサイズ　：入力されたメッセージのバイトサイズです。64ビットの為、32ビット2つとしています。
④初期ベクトル　　　：32バイトを8個です。SHA2と同じく素数の小数部分です。
⑤メッセージワードスケジュール
　　　　　　　　　　：メッセージを16バイト毎に処理するので、一行には0~15までが必ずあります。
⑥ハッシュ値　　　　：初期値は初期ベクトルです。
⑦パラメータブロック：ハッシュ値の0番目にパラメータブロックのXORを設定します。※１
⑧キャッシュ　　　　：キーがある場合、キャッシュに設定します。
⑨ゼロ埋め　　　　　：64バイトになるまでゼロで埋めます。

※１：パラメータブロックは32ビットでオフセット0にはハッシュサイズ、1にはキーサイズを設定します。

```
byte offset:    3 2 1 0     (otherwise zero)
      p[0] = 0x0101kknn     p[1..7] = 0
```

javascriptで実装します。

```javascript
    constructor(nn, key) {
        if (nn < 1 || 32 < nn) {
            throw new Error("blake2s: invalid hash size");
        }
        let kk = key.length;                       // ①
        if (32 < kk) {
            throw new Error("blake2s: invalid key size");
        }
        this.nn = nn;                              // ②
        this.ll = [0, 0];                          // ③
        this.IV = [
            0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
            0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19,
        ];                                         // ④
        this.SIGMA = [
            [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],
            [14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5, 3],
            [11, 8, 12, 0, 5, 2, 15, 13, 10, 14, 3, 6, 7, 1, 9, 4],
            [7, 9, 3, 1, 13, 12, 11, 14, 2, 6, 5, 10, 4, 0, 15, 8],
            [9, 0, 5, 7, 2, 4, 10, 15, 14, 1, 11, 12, 6, 8, 3, 13],
            [2, 12, 6, 10, 0, 11, 8, 3, 4, 13, 7, 5, 15, 14, 1, 9],
            [12, 5, 1, 15, 14, 13, 4, 10, 0, 7, 6, 3, 9, 2, 8, 11],
            [13, 11, 7, 14, 12, 1, 3, 9, 5, 0, 15, 4, 8, 6, 2, 10],
            [6, 15, 14, 9, 11, 3, 0, 8, 12, 2, 13, 7, 1, 4, 10, 5],
            [10, 2, 8, 4, 7, 6, 1, 5, 15, 11, 9, 14, 3, 12, 13, 0],
        ];                                         // ⑤
        this.h = this.IV.concat();                 // ⑥
        // Parameter block p[0]
        this.h[0] ^= 0x01010000 ^ (kk << 8) ^ nn;  // ⑦
        this.cash = [];
        if (kk > 0) {
            this.cash = key.concat();              // ⑧
            while (this.cash.length < 64) {        // ⑨
                this.cash.push(0);
            }
        }
    }
```

## ミキシング関数

- パラメータ
    - 作業ベクトル（`v`：16バイト）
    - ベクトルワードインデックス（`a`、`b`、`c`、`d`：4ワード）
    - インプットワード（`x`、`y`：2ワード）

2つのインプットワードを4つのベクトルワードでミキシングし作業ベクトルを更新します。

```javascript
    g(v, a, b, c, d, x, y) {
        v[a] = (v[a] + v[b] + x) >>> 0;
        v[d] = ((v[d] ^ v[a]) >>> 16) | ((v[d] ^ v[a]) << 16);
        v[c] = (v[c] + v[d]) >>> 0;
        v[b] = ((v[b] ^ v[c]) >>> 12) | ((v[b] ^ v[c]) << 20);
        v[a] = (v[a] + v[b] + y) >>> 0;
        v[d] = ((v[d] ^ v[a]) >>> 8) | ((v[d] ^ v[a]) << 24);
        v[c] = (v[c] + v[d]) >>> 0;
        v[b] = ((v[b] ^ v[c]) >>> 7) | ((v[b] ^ v[c]) << 25);
    }
```

## 圧縮関数

- パラメータ
    - メッセージブロック（`m`：16バイト）
    - 最終フラグ（`f`）

①　 ：ハッシュに初期ベクトルを連結します。（8バイト+8バイトの16バイト）
②②'：連結したベクトルのインデックス`12`、`13`にインプットサイズを`XOR`します。
③　 ：最終フラグが__真__の場合、インデックス`14`に`0xffffffff`を`XOR`します。
④　 ：10ラウンドミキシングします。（ChaCha20と同じように縦と斜めです。）
⑤　 ：ベクトルを16バイトから8バイトに`XOR`で圧縮します。

```javascript
    f(m, f) {
        let v = this.h.concat(this.IV);                // ①
        v[12] ^= this.ll[0];                           // ②
        v[13] ^= this.ll[1];                           // ②'
        if (f) {
            v[14] ^= 0xffffffff;                       // ③
        }
        for (let i = 0; i < 10; i++) {                 // ④
            let s = this.SIGMA[i % 10];
            this.g(v, 0, 4, 8, 12, m[s[0]], m[s[1]]);
            this.g(v, 1, 5, 9, 13, m[s[2]], m[s[3]]);
            this.g(v, 2, 6, 10, 14, m[s[4]], m[s[5]]);
            this.g(v, 3, 7, 11, 15, m[s[6]], m[s[7]]);
            this.g(v, 0, 5, 10, 15, m[s[8]], m[s[9]]);
            this.g(v, 1, 6, 11, 12, m[s[10]], m[s[11]]);
            this.g(v, 2, 7, 8, 13, m[s[12]], m[s[13]]);
            this.g(v, 3, 4, 9, 14, m[s[14]], m[s[15]]);
        }
        for (let i = 0; i < 8; i++) {
            this.h[i] ^= v[i] ^ v[i + 8];              // ⑤
        }
    }
```

## 更新関数（ダイジェスト計算）

- パラメータ
    - メッセージ（バイト配列）

①：パラメータのメッセージをバイト数分ループします。
②：キャッシュサイズが64であるかチェックします、64バイトであれば③〜⑥までの処理をします。
③：インプットサイズに64を加算します。
④：キャッシュをメッセージブロックに変換します。
⑤：メッセージブロックで圧縮関数を実行します。最終フラグは__偽__です。
⑥：キャッシュを空にします。
⑦：キャッシュにメッセージのバイトを追加します。

```javascript
    update(bs) {
        for (let i = 0; i < bs.length; i++) {          // ①
            if (this.cash.length == 64) {              // ②
                this.ll[0] += 64;                      // ③
                if (this.ll[0] > 0xffffffff) {
                    this.ll[1] += 1;
                    this.ll[0] >>>= 0;
                }
                let m = [0, 0, 0, 0, 0, 0, 0, 0,       // ④
                    0, 0, 0, 0, 0, 0, 0, 0];
                for (let i = 0; i < m.length; i++) {
                    m[i] = this.cash[i * 4 + 3] << 24 |
                        this.cash[i * 4 + 2] << 16 |
                        this.cash[i * 4 + 1] << 8 |
                        this.cash[i * 4];
                }
                this.f(m, false);                      // ⑤
                this.cash = [];                        // ⑥
            }
            this.cash.push(bs[i]);                     // ⑦
        }
    }
```

## 最終関数（ダイジェスト計算）

- リターン
    - ハッシュ値

①：最終のインプットサイズを設定します。
②：キャッシュサイズが64未満の場合は64バイトになるまで0で埋めます。
③：キャッシュをメッセージブロックに変換します。
④：メッセージブロックで圧縮関数を実行します。最終フラグは__真__です。
⑤：ハッシュをバイト配列にします。
⑥：指定のハッシュサイズ分、返します。

```javascript
    final() {
        let size = this.cash.length;                   // ①
        this.ll[0] += size;
        if (this.ll[0] > 0xffffffff) {
            this.ll[1] += 1;
            this.ll[0] >>>= 0;
        }
        while (this.cash.length < 64) {                // ②
            this.cash.push(0);
        }
        let m = [0, 0, 0, 0, 0, 0, 0, 0,               // ③
            0, 0, 0, 0, 0, 0, 0, 0];
        for (let i = 0; i < m.length; i++) {
            m[i] = this.cash[i * 4 + 3] << 24 |
                this.cash[i * 4 + 2] << 16 |
                this.cash[i * 4 + 1] << 8 |
                this.cash[i * 4];
        }
        this.f(m, true);                              // ④
        let out = [0, 0, 0, 0, 0, 0, 0, 0,            // ⑤
            0, 0, 0, 0, 0, 0, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0];
        for (let i = 0; i < this.h.length; i++) {
            out[i * 4 + 3] = this.h[i] >>> 24 & 0xff;
            out[i * 4 + 2] = this.h[i] >>> 16 & 0xff;
            out[i * 4 + 1] = this.h[i] >>> 8 & 0xff;
            out[i * 4 + 0] = this.h[i] & 0xff;
            if ((i * 4) > this.nn) {
                break;
            }
        }
        return out.slice(0, this.nn);                 // ⑥
    }
```

## ダイジェスト計算

- パラメータ
    - ハッシュサイズ（`nn`）
    - キー（`key`）
    - メッセージ（`in`、バイト配列）
- リターン
    - ハッシュ値

```javascript
    static blake2s(nn, key, in_) {
        let b2s = new BLAKE2s(nn, key);
        b2s.update(in_);
        return b2s.final();
    }
```

# さいごに

高速で強度の高いハッシュ関数ですが、案外簡単に実装できます。
自身の得意とする言語等で実装してみてください。
ソースコードは、[Github](https://github.com/tnakagawa/education/tree/master/blake2)にあります。

# 参考（Reference） 

- [RFC-7693 : The BLAKE2 Cryptographic Hash and Message Authentication Code (MAC)](https://tools.ietf.org/html/rfc7693)
- [BLAKE - Wikipedia](https://ja.wikipedia.org/wiki/BLAKE)
- [BLAKE2 — fast secure hashing](https://blake2.net/)
- [Github](https://github.com/BLAKE2/)