つくって理解するストリーム暗号 ChaCha20 - ちりもつもればミルキーウェイ

はじめに

しかも math/rand/v2 トップレベルで利用されてる、かつシードがない math/rand でも使われるようになったらしい。一応議論を追った感じだと、暗号学的強度がある乱数をもとめてるのに math/rand つかっちゃうケースがちょいちょいあるらしく、そういうケースでリスクが少なくなるし生成コストも大したことないからいいんじゃね？みたいな雰囲気だった。

ぼくは RSAを完全理解しようとして途中で疲れた過去を持っており、このへんちょっとわかり手なのでホットな話題に乗っかって ChaCha 実装しながら完全理解しようというやつです。

はじめにやってる操作について説明し、そのあと実装する感じでやります。みんなで完全理解しよう

ChaCha 概要

ChaCha 自体の元ネタは Bernstein, D., "ChaCha, a variant of Salsa20", January 2008 で、ストリーム暗号の一種です。

めちゃめちゃざっくりいうと、入力とか定数から内部状態をつくって、それにround関数かけてかき回すことで擬似乱数つくり、最後にXORとって暗号化や！みたいなやつです。

Go 1.22 では、この擬似乱数を得る部分の処理が math/rand に採用された感じです。

かけるラウンド $r$ の数によって ChaCha $r$ みたいな言い方をしたりします。 ChaCha8 とか ChaCha20 とか。

なので ChaCha の理解にあたって着目すべき主要な観点としては、内部状態をどう初期化するかということと、それをround関数でどうかき回すかの2点です。

そのへん説明していきます。

内部状態の初期化

入力は

256bit key: $K = (key_0, key_1, key_2, ... key_7)$
32bit counter: $C = (counter_0)$
96bit nonce: $N = (nonce_0, nonce_1, nonce_2)$

です。(元ネタにある表だと counter と nonce は区別せず input として記載していますが、ここではわかりやすさのため別の性質であることを明示しています)

さらに以下の定数も保持しています。

$const_0 = 0x61707876$
$const_1 = 0x3320646E$
$const_2=0x79622D32$
$const_3=0x6B206574$

(余談だけどこの定数は特に意味のない値で expand 32-byte k ていう文字をそのままhexにとっただけ。なんかこういう意味のないことが自明な値を定数に使うとかよくあるらしい)

入力3つと定数を合わせて4つの要素から状態を構成しています。
状態は以下のような行列で表せます。

これが初期状態で、こいつをround関数かけてぶん回した出力が擬似乱数になるぞいという感じですね。

QuarterRound

次にround関数の詳細です。ChaCharでは QuarterRound という関数を使ってかき混ぜてるのでそのあたりを紹介します。

ある関数 QuarterRound(a, b, c, d) があったとき、その操作は以下

a += b; d ^= a; d <<<= 16;
c += d; b ^= c; b <<<= 12;
a += b; d ^= a; d <<<= 8;
c += d; b ^= c; b <<<= 7;

ここで + は $2^{32}$ を法とした演算であり <<< は回転シフトなので注意。

ようは各要素ごとに加算、XOR、回転シフトを順繰りに繰り返して値をガシャガシャにしているという感じ。

QuarterRound() っていうくらいなので、これを4回やって1ラウンドということになってるぽい。

QuarterRound を使って擬似乱数列を得る

以下のように column 方向と diagonal 方向ごとに1ラウンドごと、計2ラウンドをセットでまわすっぽい

/* column round */
QuarterRound( x0, x4, x8,x12)
QuarterRound( x1, x5, x9,x13)
QuarterRound( x2, x6,x10,x14)
QuarterRound( x3, x7,x11,x15)
/* diagonal round */
QuarterRound( x0, x5,x10,x15)
QuarterRound( x1, x6,x11,x12)
QuarterRound( x2, x7, x8,x13)
QuarterRound( x3, x4, x9,x14)

わかりやすく図字すると、column 方向の処理対象はこんな感じ。順にやっていって、要素を全て処理したら1ラウンド！

diagonal 方向はこんな感じ。おなじく全部処理したら1ラウンドなのは同じだけど、ななめ方向にかきまわすのが column round との違い

それぞれ合わせて2ラウンドで、これを何回繰り返すかがいくつかパターンがあるようす。 ChaCha20 はこのセットを10回繰り返す感じぽい。

最終的に期待回数のラウンドをこなしたあとに、初期状態 $X$ との和をとったものが key stream として出力されるぞ！ということらしい。

暗号化 & 復号

擬似乱数とXORするだけなので特に語ることなし！

しいていうとしたら平文 m を ChaCha の擬似乱数出力サイズである 512bit ごとのブロックにわけてXORとっていくくらいだけど、まあそれも説明不要だと思うので省略。このときブロックごとに counter を increment しながら key stream を作っていったりするんだけど、実装みればすぐわかりそうなのでそれも省略。

実装してみる

最終的な実装はこちらにあるので、まとめて見たい方はこちらを！

github.com

RFC8439 の appendix A.1 に ChaCha20 のテストスイートがあるのでこれをパスさせることを目指します。のでラウンドは20で実装するぞい！

(Go 1.22 math/rand に ChaCha8 実装入って気になったのがそもそものモチベなので、せっかくだからラウンド8でやりたい気持ちもあった。けどシュッといい感じのテストスイートを探せなかったので20ラウンドでやることにしまた！ラウンドかける数しか違いないしまあどっちでもいいよねという感)

勉強目的の実装なので、細かいハンドリングは考慮せず作っていきます。

あとせっかくなので、かっちょよく crypto/cipher.Stream interface を実装して使える感じにしていきましょう。

まずはノリで初期化を書く！初期状態周りはすでに説明してるのでそのまんまいきます。

type Cipher struct {
    constant [4]uint32
    key      [8]uint32
    counter  uint32
    nonce    [3]uint32
}

var _ cipher.Stream = (*Cipher)(nil)

func NewCipher(key [32]byte, count uint32, nonce [12]byte) *Cipher {
    c := new(Cipher)
    c.constant = [4]uint32{0x61707865, 0x3320646e, 0x79622d32, 0x6b206574}
    c.key = [8]uint32{
        binary.LittleEndian.Uint32(key[0:4]),
        binary.LittleEndian.Uint32(key[4:8]),
        binary.LittleEndian.Uint32(key[8:12]),
        binary.LittleEndian.Uint32(key[12:16]),
        binary.LittleEndian.Uint32(key[16:20]),
        binary.LittleEndian.Uint32(key[20:24]),
        binary.LittleEndian.Uint32(key[24:28]),
        binary.LittleEndian.Uint32(key[28:32]),
    }
    c.counter = count
    c.nonce = [3]uint32{
        binary.LittleEndian.Uint32(nonce[0:4]),
        binary.LittleEndian.Uint32(nonce[4:8]),
        binary.LittleEndian.Uint32(nonce[8:12]),
    }
    return c
}

func (c *Cipher) toState() [16]uint32 {
    return [16]uint32{
        c.constant[0], c.constant[1], c.constant[2], c.constant[3],
        c.key[0], c.key[1], c.key[2], c.key[3],
        c.key[4], c.key[5], c.key[6], c.key[7],
        c.counter, c.nonce[0], c.nonce[1], c.nonce[2],
    }
}

func (c *Cipher) XORKeyStream(dst, src []byte) {
    panic("implement me!")
}

いちおう test vector を定義してくれてる RFC8439 では little endian で取り扱う旨が記載されていたのでそれに従って取り扱っているけど、その部分以外で読んでわからないところはないはず！

つぎに QuarterRound(a,b,c,d) を作る。回転シフトは math/bits に準備されてるのでありがたく使いましょう。

func qr(a, b, c, d uint32) (uint32, uint32, uint32, uint32) {
    a += b
    d ^= a
    d = bits.RotateLeft32(d, 16)
    c += d
    b ^= c
    b = bits.RotateLeft32(b, 12)
    a += b
    d ^= a
    d = bits.RotateLeft32(d, 8)
    c += d
    b ^= c
    b = bits.RotateLeft32(b, 7)
    return a, b, c, d
}

加算は $2^{32}$ を法とする加算なのに普通に a += b していますが、これは uint32 での演算なので溢れたら勝手に捨てられるためです。

素材がそろったので、あとは column round & diagonal round を10回ずつぶんまわして最後に $2^{32}$ を法とする和をとれば key stream がとれる！

func (c *Cipher) keyStream() [64]byte {
    x := c.toState()
    for i := 0; i < 10; i++ {
        // column round
        x[0], x[4], x[8], x[12] = qr(x[0], x[4], x[8], x[12])
        x[1], x[5], x[9], x[13] = qr(x[1], x[5], x[9], x[13])
        x[2], x[6], x[10], x[14] = qr(x[2], x[6], x[10], x[14])
        x[3], x[7], x[11], x[15] = qr(x[3], x[7], x[11], x[15])
        // diagonal round
        x[0], x[5], x[10], x[15] = qr(x[0], x[5], x[10], x[15])
        x[1], x[6], x[11], x[12] = qr(x[1], x[6], x[11], x[12])
        x[2], x[7], x[8], x[13] = qr(x[2], x[7], x[8], x[13])
        x[3], x[4], x[9], x[14] = qr(x[3], x[4], x[9], x[14])
    }
    initial := c.toState()
    for i := range x {
        x[i] += initial[i]
    }
    var stream [64]byte
    for i, v := range x {
        stream[i*4] = byte(v)
        stream[i*4+1] = byte(v >> 8)
        stream[i*4+2] = byte(v >> 16)
        stream[i*4+3] = byte(v >> 24)
    }
    return stream
}

あとは↑のstreamと適当にXORをとる処理を実装すればよろし
(実用に耐えるものを作るならlenのエラーとか細かいハンドリングが本来必要だけど、今回は勉強目的なのでskip)

func (c *Cipher) XORKeyStream(dst, src []byte) {
    // NOTE: Skip error handling because this implementation is learning purpose.
    for len(src) > 0 {
        stream := c.keyStream()
        block := len(stream)
        if len(src) < block {
            block = len(src)
        }
        for i := range block {
            dst[i] = src[i] ^ stream[i]
        }
        c.counter++
        src, dst = src[block:], dst[block:]
    }
}

これでうごくはず！key stream size である 64byte ごとに処理していくんだけど、その際1回ごとにカウンタを increment するのを忘れずに(1敗, ここ忘れてると test vector が通りません)

実装とテストは playground にまとめてポン置きしたので、実際に動いてる姿を眺めることもできます。

https://go.dev/play/p/gp9lej-MBO6

これにて実装も完了！すべてを理解しましたね。

感想

やってる操作はそんな難しくないので完全に理解した。

ChaCha20 とか ChaCha8 とか数字違うのなんやねんと思ってたけど、単にラウンド数の違いでしかないというのもわかってよかった。

なんというかこんなに簡単そうな操作で計算量的安全性のある擬似乱数つくれるっていうのは面白かった。ChaCha は専用命令のってないハードウェアでもコスト軽いって紹介されることがおおいけど、そら軽いわという感想になった。

あと TLS 1.3 では AEAD (Authenticated Encryption with Associated Data) として ChaCha20-Poly1305 が定義されてたりするので、Poly1305 を理解していい感じに腹落ちしたいなという感じもあるのでそのうち興味わいたらやってみようかな〜〜〜〜