Go 言語で学ぶ『暗号技術入門』Part 3 -CBC Mode-

結城浩さんの『暗号技術入門』を Go 言語を使って学ぶ記事の第3回です。前回は AES について解説しました。

今回は第4章「ブロック暗号のモード」です。そもそも、ブロック暗号の「モード」とは何なのでしょうか。

ブロック暗号の「モード」とは

前回の終わりにも書いたように、僕らが暗号化したい平文の長さは、たいていの場合ブロック暗号のブロック長 (AES なら 128 ビット) より長いことが多いです。そのため、ブロック暗号を繰り返し使って、長い文章全体を暗号化する必要があります。このブロック暗号を繰り返す方法のことをブロック暗号の「モード」と呼びます。

ブロック暗号のモードにはいくつもの種類がありますが、今回と次回でその中でも比較的使用が推奨されている CBC モードとCTR モードについて説明します。今回は CBC モードについてです。

なお、この記事中の Go のソースコードのバージョンはすべて 1.6 です。

Go におけるブロック暗号モード

Go ではブロック暗号のモードはすべて crypto/cipher パッケージに定義されている BlockMode という統一のインターフェースを介して利用するようになっています。 CryptoBlocks() で src のデータを dst に暗号化または復号します。

1
2
3
4
5
6
7
8
9
type BlockMode interface {
        // BlockSize returns the mode's block size.
        BlockSize() int

        // CryptBlocks encrypts or decrypts a number of blocks. The length of
        // src must be a multiple of the block size. Dst and src may point to
        // the same memory.
        CryptBlocks(dst, src []byte)
}

Block インターフェースと違い、 BlockMode インターフェースには CryptBlocks() メソッド1つしかありません。これは、そもそも暗号化と復号で別のオブジェクトを用いる必要があるからです。たとえば、あとで見るように、 CBC モードでの暗号化には NewCBCEncrypter() によるオブジェクトを使って、復号には NewCBCDecrypter() によるオブジェクトを使って CryptBlocks() を呼ぶ必要があります。

CBC (Cipher Block Chaining) モード

CBC モードとは

CBC (Cipher Block Chaining) モードは、1つ前の暗号文ブロックと平文ブロックの内容を混ぜ合わせてから暗号化をおこなう方法です。暗号文ブロックをチェーンのように連鎖させることが名前の由来になっています。

では CBC モードの具体的なアルゴリズムを見てみましょう。

CBC モードのアルゴリズム

以下の図のように、 CBC モードでは1つ前の暗号文ブロックと平文ブロックの XOR をとってから暗号化をおこないます。 “block cipher encryption” の中身には、たとえば AES を用いるのであればその処理が入ります。

https://upload.wikimedia.org/wikipedia/commons/thumb/8/80/CBC_encryption.svg/601px-CBC_encryption.svg.png

ただし、最初の平文ブロックを暗号化するときには「1つ前の暗号文ブロック」が存在しません。そこで、その代わりに「初期化ベクトル (initialization vector; IV)」というランダムなビット列を用意し、それを用います。

最終的に、生成される暗号文ブロックをつなげたものが暗号化されたデータになります。

逆に、復号化は以下の図のようになります。 XOR の対称的な性質により、復号化したブロックと1つ前の暗号文ブロックの XOR を再びとれば、元の平文が得られます。

https://upload.wikimedia.org/wikipedia/commons/thumb/2/2a/CBC_decryption.svg/601px-CBC_decryption.svg.png

CBC モードを使ってみる

Go 言語を使い、実際に CBC モードで長い平文を暗号化してみます。ブロック暗号としては AES を使います。

http://play.golang.org/p/_q54T5eDwe

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package main

import (
	"crypto/aes"
	"crypto/cipher"
	"crypto/rand"
	"fmt"
	"io"
	"log"
)

func main() {
	// 平文。長さが 16 バイトの整数倍でない場合はパディングする必要がある
	plainText := []byte("secret text 9999")
	// 暗号化データ。先頭に初期化ベクトル (IV) を入れるため、1ブロック分余計に確保する
	encrypted := make([]byte, aes.BlockSize+len(plainText))

	// IV は暗号文の先頭に入れておくことが多い
	iv := encrypted[:aes.BlockSize]
	// IV としてランダムなビット列を生成する
	if _, err := io.ReadFull(rand.Reader, iv); err != nil {
		log.Fatal(err)
	}

	// ブロック暗号として AES を使う場合
	key := []byte("secret-key-12345")
	block, err := aes.NewCipher(key)
	if err != nil {
		log.Fatal(err)
	}

	// CBC モードで暗号化する
	mode := cipher.NewCBCEncrypter(block, iv)
	mode.CryptBlocks(encrypted[aes.BlockSize:], plainText)
	fmt.Printf("encrypted: %x\n", encrypted)

	// 復号するには復号化用オブジェクトが別に必要
	mode = cipher.NewCBCDecrypter(block, iv)
	decrypted := make([]byte, len(plainText))
	// 先頭の IV を除いた部分を復号する
	mode.CryptBlocks(decrypted, encrypted[aes.BlockSize:])
	fmt.Printf("decrypted: %s\n", decrypted)
	// Output:
	// decrypted: secret text 9999
}

標準ライブラリのみを用いて直接暗号化をおこなおうとすると、結構面倒なことがわかります。実際にはアプリケーションが使いやすいようなラッパー処理を書き、それを用いることになると思います。

Go での実装

では標準ライブラリの crypto/cipher において、 CBC モードがどのように実装されているのか見てみましょう。

CBC モードを表すのは以下の cbc 構造体です。

1
2
3
4
5
6
type cbc struct {
	b         Block
	blockSize int
	iv        []byte
	tmp       []byte
}

cbc 構造体のコンストラクタは newCBC() です。書き換えの影響を受けないように、 cbc.iv には引数の iv を完全にコピーしたものが入れられます。

1
2
3
4
5
6
7
8
func newCBC(b Block, iv []byte) *cbc {
	return &cbc{
		b:         b,
		blockSize: b.BlockSize(),
		iv:        dup(iv),
		tmp:       make([]byte, b.BlockSize()),
	}
}

cbc 構造体は直接 BlockMode インターフェースを実装してわけではありません。実際はそのエイリアスの cbcEncrypter / cbcDecrypter 型が暗号化 / 復号処理を実装しています。同じ構造体に複数の別名型をつけ、それぞれで違うメソッドを実装するというのは、参考になる実装方法ですね。

暗号化用オブジェクトは NewCBCEncrypter() で生成します。この戻り値が BlockMode インターフェースを実装した cbcEncrypter オブジェクトになります。

1
2
3
4
5
6
7
8
9
10
11
type cbcEncrypter cbc

// NewCBCEncrypter returns a BlockMode which encrypts in cipher block chaining
// mode, using the given Block. The length of iv must be the same as the
// Block's block size.
func NewCBCEncrypter(b Block, iv []byte) BlockMode {
	if len(iv) != b.BlockSize() {
		panic("cipher.NewCBCEncrypter: IV length must equal block size")
	}
	return (*cbcEncrypter)(newCBC(b, iv))
}

では、 cbcEncrypter の CryptBlocks() メソッドの実装を見てみましょう。やっているのは先に説明したアルゴリズム通り、平文ブロック (src[:x.BlockSize]) と1つ前の暗号文ブロック (iv) の XOR をとり (xorBytes())、それを暗号化する (x.b.Encrypt()) ことです。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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")
	}

	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)
}

一方、復号用オブジェクトは NewCBCDecrypter() で生成します。この戻り値が BlockMode インターフェースを実装した cbcDecrypter オブジェクトになります。

1
2
3
4
5
6
7
8
9
10
11
type cbcDecrypter cbc

// NewCBCDecrypter returns a BlockMode which decrypts in cipher block chaining
// mode, using the given Block. The length of iv must be the same as the
// Block's block size and must match the iv used to encrypt the data.
func NewCBCDecrypter(b Block, iv []byte) BlockMode {
	if len(iv) != b.BlockSize() {
		panic("cipher.NewCBCDecrypter: IV length must equal block size")
	}
	return (*cbcDecrypter)(newCBC(b, iv))
}

続いて cbcDecrypter の CryptBlocks() メソッドの実装を見てみます。 To avoid making a copy each time, we loop over the blocks BACKWARDS. というコメントがある通り、復号処理は暗号文の末尾から逆順でおこなっているようです。しかしながら、「コピーを防ぐため」ということの意図はよくわかりませんでした。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
func (x *cbcDecrypter) 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 len(src) == 0 {
		return
	}

	// For each block, we need to xor the decrypted data with the previous block's ciphertext (the iv).
	// To avoid making a copy each time, we loop over the blocks BACKWARDS.
	end := len(src)
	start := end - x.blockSize
	prev := start - x.blockSize

	// Copy the last block of ciphertext in preparation as the new iv.
	copy(x.tmp, src[start:end])

	// Loop over all but the first block.
	for start > 0 {
		x.b.Decrypt(dst[start:end], src[start:end])
		xorBytes(dst[start:end], dst[start:end], src[prev:start])

		end = start
		start = prev
		prev -= x.blockSize
	}

	// The first block is special because it uses the saved iv.
	x.b.Decrypt(dst[start:end], src[start:end])
	xorBytes(dst[start:end], dst[start:end], x.iv)

	// Set the new iv to the first block we copied earlier.
	x.iv, x.tmp = x.tmp, x.iv
}

CBC モードについては以上です。次回はブロック暗号でよく使われるもう1つのモード、 CTR モードについて書く予定です。