Goのcipher packageに実装されている暗号利用モードのベンチマーク

(2020-04-12)

暗号利用モードはブロック長より長いメッセージに対してどのようにブロック暗号を適用するかのアルゴリズム。

ブロック暗号

ブロック暗号は固定長のブロックを暗号化/復号する共通鍵暗号で、入力と同じ長さの出力を返す暗号化/復号関数からなる。 アメリカ国立標準技術研究所(NIST) が標準暗号として採用したAES (Rijndael) が有名。 最も単純な暗号利用モードとして、メッセージをブロックに分割してそれぞれ独立に適用する Electronic Codebook (ECB) というのがあるが、 鍵とブロックが同じなら毎回同じ出力になってしまうため、メッセージのパターンが残ってしまうのとリプレイ攻撃に弱い問題があり使われない。 また、メッセージがブロック長の整数倍になるようにパディングが必要。

ECBによる暗号化/復号

Goのcrypto/cipher packageに実装されている暗号化利用モード

Goのcrypto/cipher packageには次の暗号化利用モードが実装されている。

$ go version
go version go1.14 darwin/amd64

Cipher Block Chaining (CBC)

メッセージをブロックに分割し、前段の暗号文(最初はランダムなIV)と入力ブロックのXORを取ったものが暗号文で、 これを復号関数にかけて前段の暗号文とのXORを取って復号する。IVは平文のまま暗号文の前に付けるなどする。 IVがないと最初のブロックが復号できず、暗号文の一部が破損すると次のブロックまで復号できない。 ECBと同様パディングが必要。最も広く使われているらしい。

最後のブロックの暗号文をMAC(Message Authentication Code)とするCBC-MACでは最初のブロックの改変を防ぐためIVが0固定で、 任意のメッセージの最初のブロックを他のメッセージのMACとXORを取って後ろに結合することで、それまでの影響を打ち消し任意のメッセージ単体のMACと同じ値にする Length extension attackが成立する。そのためメッセージを固定長にするかメッセージ長を先頭に入れるなどの対策が必要。

CBCによる暗号化/復号

Goではパディングは自分でやる必要がある。

func (x *cbcEncrypter) CryptBlocks(dst, src []byte) {
    if len(src)%x.blockSize != 0 {
        panic("crypto/cipher: input not full blocks")
    }
    if len(dst) < len(src) {
        panic("crypto/cipher: output smaller than input")
    }
    if subtle.InexactOverlap(dst[:len(src)], src) {
        panic("crypto/cipher: invalid buffer overlap")
    }

    iv := x.iv

    for len(src) > 0 {
        // Write the xor to dst, then encrypt in place.
        xorBytes(dst[:x.blockSize], src[:x.blockSize], iv)
        x.b.Encrypt(dst[:x.blockSize], dst[:x.blockSize])

        // Move to the next block with this block as the next iv.
        iv = dst[:x.blockSize]
        src = src[x.blockSize:]
        dst = dst[x.blockSize:]
    }

    // Save the iv for the next CryptBlocks call.
    copy(x.iv, iv)
}

足りないバイト数の値でパディングするPKCS#7の方式はこんな感じ。

func pad(data []byte, blockSize int) []byte {
    padSize := blockSize - len(data) % blockSize
    ret := make([]byte, len(data) + padSize)
    copy(ret, data)
    copy(ret[len(data):], bytes.Repeat([]byte{byte(padSize)}, padSize))
    return ret
}

func unpad(data []byte) []byte {
    padSize := int(data[len(data)-1])
    if padSize > len(data) {
        return nil
    }
    return data[:len(data)-padSize]
}

Cipher Feedback (CFB)

ブロック暗号を使ってはいるがブロックに分割不要なストリーム暗号になった。したがってパディングする必要もない。 前段の暗号文(最初はランダムなIV)を暗号関数にかけたものをストリーム暗号のKeystreamとし、これとメッセージのXORを取ったものが暗号文で、XORを再度取って復号する。 暗号化/復号共に暗号関数を用いる。IVや暗号文が破損した場合それ以降の復号はできない。

CFBによる暗号化/復号

xorBytes() はサイズが小さい方に合わせてXORを取る。

func (x *cfb) XORKeyStream(dst, src []byte) {
    if len(dst) < len(src) {
        panic("crypto/cipher: output smaller than input")
    }
    if subtle.InexactOverlap(dst[:len(src)], src) {
        panic("crypto/cipher: invalid buffer overlap")
    }
    for len(src) > 0 {
        if x.outUsed == len(x.out) {
            x.b.Encrypt(x.out, x.next)
            x.outUsed = 0
        }

        if x.decrypt {
            // We can precompute a larger segment of the
            // keystream on decryption. This will allow
            // larger batches for xor, and we should be
            // able to match CTR/OFB performance.
            copy(x.next[x.outUsed:], src)
        }
        n := xorBytes(dst, src, x.out[x.outUsed:])
        if !x.decrypt {
            copy(x.next[x.outUsed:], dst)
        }
        dst = dst[n:]
        src = src[n:]
        x.outUsed += n
    }
}

Output Feedback (OFB)

同じくストリーミング暗号。 CFBが暗号文を次にフィードバックしていたのに対し、OFBは暗号関数の出力をXORを取って暗号文にする前にフィードバックする。 したがってKeystreamはIVがn回暗号関数を通ったものとなりメッセージに依存しないため先に計算することもできる。 それらとXORを取ったものが暗号文になるため復号も全く同じ処理になる。

OFBによる暗号化/復号

func (x *ofb) refill() {
    bs := x.b.BlockSize()
    remain := len(x.out) - x.outUsed
    if remain > x.outUsed {
        return
    }
    copy(x.out, x.out[x.outUsed:])
    x.out = x.out[:cap(x.out)]
    for remain < len(x.out)-bs {
        x.b.Encrypt(x.cipher, x.cipher)
        copy(x.out[remain:], x.cipher)
        remain += bs
    }
    x.out = x.out[:remain]
    x.outUsed = 0
}

func (x *ofb) XORKeyStream(dst, src []byte) {
    if len(dst) < len(src) {
        panic("crypto/cipher: output smaller than input")
    }
    if subtle.InexactOverlap(dst[:len(src)], src) {
        panic("crypto/cipher: invalid buffer overlap")
    }
    for len(src) > 0 {
        if x.outUsed >= len(x.out)-x.b.BlockSize() {
            x.refill()
        }
        n := xorBytes(dst, src, x.out[x.outUsed:])
        dst = dst[n:]
        src = src[n:]
        x.outUsed += n
    }
}

Counter (CTR)

同じくストリーミング暗号。IV相当のNonceと重複しないCounterを合わせて暗号関数に通したCounter blockをKeystreamとする。

CTRによる暗号化/復号

前段に依存しないため並列に暗号化できるがGoではしていない。

func NewCTR(block Block, iv []byte) Stream {
    if ctr, ok := block.(ctrAble); ok {
        return ctr.NewCTR(iv)
    }
    if len(iv) != block.BlockSize() {
        panic("cipher.NewCTR: IV length must equal block size")
    }
    bufSize := streamBufferSize
    if bufSize < block.BlockSize() {
        bufSize = block.BlockSize()
    }
    return &ctr{
        b:       block,
        ctr:     dup(iv),
        out:     make([]byte, 0, bufSize),
        outUsed: 0,
    }
}

func (x *ctr) refill() {
    remain := len(x.out) - x.outUsed
    copy(x.out, x.out[x.outUsed:])
    x.out = x.out[:cap(x.out)]
    bs := x.b.BlockSize()
    for remain <= len(x.out)-bs {
        x.b.Encrypt(x.out[remain:], x.ctr)
        remain += bs

        // Increment counter
        for i := len(x.ctr) - 1; i >= 0; i-- {
            x.ctr[i]++
            if x.ctr[i] != 0 {
                break
            }
        }
    }
    x.out = x.out[:remain]
    x.outUsed = 0
}

func (x *ctr) XORKeyStream(dst, src []byte) {
    if len(dst) < len(src) {
        panic("crypto/cipher: output smaller than input")
    }
    if subtle.InexactOverlap(dst[:len(src)], src) {
        panic("crypto/cipher: invalid buffer overlap")
    }
    for len(src) > 0 {
        if x.outUsed >= len(x.out)-x.b.BlockSize() {
            x.refill()
        }
        n := xorBytes(dst, src, x.out[x.outUsed:])
        dst = dst[n:]
        src = src[n:]
        x.outUsed += n
    }
}

ベンチマーク

それぞれの暗号利用モードで暗号化/復号する際のベンチマークを取る。コードはGitHubにある。 CBCはパディング込み。OFBとCTRは暗号化/復号処理が同じなのでまとめている。

package sandbox

import (
    "bytes"
    "crypto/cipher"
)

func pad(data []byte, blockSize int) []byte {
    padSize := blockSize - len(data) % blockSize
    ret := make([]byte, len(data) + padSize)
    copy(ret, data)
    copy(ret[len(data):], bytes.Repeat([]byte{byte(padSize)}, padSize))
    return ret
}

func unpad(data []byte) []byte {
    padSize := int(data[len(data)-1])
    if padSize > len(data) {
        return nil
    }
    return data[:len(data)-padSize]
}

func EncryptWithCBC(block cipher.Block, iv []byte, data []byte) []byte {
    data = pad(data, block.BlockSize())
    enc := cipher.NewCBCEncrypter(block, iv)
    encrypted := make([]byte, len(data))
    enc.CryptBlocks(encrypted, data)
    return encrypted
}

func DecryptWithCBC(block cipher.Block, iv []byte, data []byte) []byte {
    dec := cipher.NewCBCDecrypter(block, iv)
    decrypted := make([]byte, len(data))
    dec.CryptBlocks(decrypted, data)
    return decrypted
}

func EncryptWithCFB(block cipher.Block, iv []byte, data []byte) []byte {
    enc := cipher.NewCFBEncrypter(block, iv)
    encrypted := make([]byte, len(data))
    enc.XORKeyStream(encrypted, data)
    return encrypted
}

func DecryptWithCFB(block cipher.Block, iv []byte, data []byte) []byte {
    dec := cipher.NewCFBDecrypter(block, iv)
    decrypted := make([]byte, len(data))
    dec.XORKeyStream(decrypted, data)
    return decrypted
}

func EncryptDecryptWithOFB(block cipher.Block, iv []byte, data []byte) []byte {
    enc := cipher.NewOFB(block, iv)
    encrypted := make([]byte, len(data))
    enc.XORKeyStream(encrypted, data)
    return encrypted
}


func EncryptDecryptWithCTR(block cipher.Block, iv []byte, data []byte) []byte {
    enc := cipher.NewCTR(block, iv)
    encrypted := make([]byte, len(data))
    enc.XORKeyStream(encrypted, data)
    return encrypted
}

入力は128 bytesと12800 bytesのランダムなバイト列。 128 bytesではCFBが最速でCBCがそれに次ぎ、OFBとCTRのパフォーマンスが悪く、 12800 bytesではOFBが最速でCBCとCTRが同じくらい、CFBのパフォーマンスが悪いという結果になった。

$ go test -bench ".*" -benchmem main_test.go  main.go
goos: darwin
goarch: amd64
BenchmarkShortEncryptWithCBC-4                    852924              1323 ns/op             416 B/op          6 allocs/op
BenchmarkShortDecryptWithCBC-4                   1000000              1045 ns/op             240 B/op          4 allocs/op
BenchmarkShortEncryptWithCFB-4                   1213734               987 ns/op             240 B/op          4 allocs/op
BenchmarkShortDecryptWithCFB-4                   1228692              1155 ns/op             240 B/op          4 allocs/op
BenchmarkShortEncryptDecryptWithOFB-4             701252              1608 ns/op             736 B/op          4 allocs/op
BenchmarkShortEncryptDecryptWithCTR-4             709312              1747 ns/op             736 B/op          4 allocs/op
BenchmarkLongEncryptWithCBC-4                      60972             23010 ns/op           27264 B/op          6 allocs/op
BenchmarkLongDecryptWithCBC-4                      54586             22122 ns/op           13680 B/op          4 allocs/op
BenchmarkLongEncryptWithCFB-4                      34948             30435 ns/op           13680 B/op          4 allocs/op
BenchmarkLongDecryptWithCFB-4                      38904             28475 ns/op           13680 B/op          4 allocs/op
BenchmarkLongEncryptDecryptWithOFB-4               59216             20488 ns/op           14176 B/op          4 allocs/op
BenchmarkLongEncryptDecryptWithCTR-4               50810             23594 ns/op           14176 B/op          4 allocs/op

参考

暗号利用モード - Wikipedia

golang で AES/CBC/PKCS#7Padding の暗号化・復号化 - 理系学生日記

Padding (cryptography) - Wikipedia