暗号利用モードはブロック長より長いメッセージに対してどのようにブロック暗号を適用するかのアルゴリズム。
ブロック暗号
ブロック暗号は固定長のブロックを暗号化/復号する共通鍵暗号で、入力と同じ長さの出力を返す暗号化/復号関数からなる。 アメリカ国立標準技術研究所（NIST) が標準暗号として採用したAES (Rijndael) が有名。 最も単純な暗号利用モードとして、メッセージをブロックに分割してそれぞれ独立に適用する Electronic Codebook (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が成立する。そのためメッセージを固定長にするかメッセージ長を先頭に入れるなどの対策が必要。
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や暗号文が破損した場合それ以降の復号はできない。
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を取ったものが暗号文になるため復号も全く同じ処理になる。
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モードによる暗号文と、任意で付加できる平文のadditional authenticated data (AAD)に 完全性確認のためのTagを付けたものがGCM(Galois/Counter Mode)で、 Go実装では暗号文の後にTagがくっついて返ってくる。
前段に依存しないため並列に暗号化できるが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
参考
golang で AES/CBC/PKCS#7Padding の暗号化・復号化 - 理系学生日記