[インデックス 18279] ファイルの概要

このコミットは、Go言語のcrypto/cipherパッケージにおけるCBC (Cipher Block Chaining) モードの暗号化および復号処理のパフォーマンス改善を目的としています。具体的には、データコピーの回数を削減することで、処理効率を高めています。

コミット

commit 701982f173d65cca3f8a88df825c008b203775c8
Author: Luke Curley <qpingu@gmail.com>
Date:   Fri Jan 17 11:07:04 2014 -0500

    crypto/cipher: improved cbc performance
    
    decrypt: reduced the number of copy calls from 2n to 1.
    encrypt: reduced the number of copy calls from n to 1.
    
    Encryption is straight-forward: use dst instead of tmp when
    xoring the block with the iv.
    
    Decryption now loops backwards through the blocks abusing the
    fact that the previous block's ciphertext (src) is the iv. This
    means we don't need to copy the iv every time, in addition to
    using dst instead of tmp like encryption.
    
    R=golang-codereviews, agl, mikioh.mikioh
    CC=golang-codereviews
    https://golang.org/cl/50900043

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/701982f173d65cca3f8a88df825c008b203775c8

元コミット内容

crypto/cipher: improved cbc performance

• decrypt: コピー呼び出しの数を 2n から 1 に削減。
• encrypt: コピー呼び出しの数を n から 1 に削減。

暗号化は単純で、ブロックとIV (Initialization Vector) をXORする際に、一時的なバッファ (tmp) の代わりに宛先 (dst) を使用します。

復号は、ブロックを逆順にループすることで、前のブロックの暗号文 (src) がIVとして機能するという事実を利用します。これにより、暗号化と同様に、IVを毎回コピーする必要がなくなり、一時的なバッファの代わりに宛先を使用できます。

変更の背景

このコミットの主な背景は、Go言語の標準ライブラリであるcrypto/cipherパッケージにおけるCBCモードの暗号化および復号処理のパフォーマンス最適化です。暗号化処理において、特にブロックごとに中間結果をコピーする操作は、大量のデータを扱う際にオーバーヘッドとなり、全体のパフォーマンスを低下させる要因となります。

以前の実装では、暗号化・復号の各ブロック処理において、中間データを一時的なバッファにコピーし、その後最終的な出力バッファに再度コピーするといった、冗長なコピー操作が発生していました。このコミットは、これらの不要なコピー操作を削減し、インプレース（in-place）での処理を促進することで、CPUサイクルとメモリ帯域幅の消費を抑え、スループットを向上させることを目指しています。

特に、暗号化ではn回、復号では2n回（nはブロック数）発生していたコピー操作を、それぞれ1回にまで削減するという具体的な目標が掲げられています。これは、暗号処理がCPUバウンドなタスクであるため、このような低レベルでの最適化が全体的なアプリケーションのパフォーマンスに大きく寄与するという認識に基づいています。

前提知識の解説

1. ブロック暗号とCBCモード

• ブロック暗号: データを固定長のブロック（例: 16バイト）に分割し、そのブロック単位で暗号化・復号を行う暗号方式です。AES (Advanced Encryption Standard) は代表的なブロック暗号の一つです。
• CBC (Cipher Block Chaining) モード: ブロック暗号の運用モードの一つで、各ブロックの暗号化が前のブロックの暗号文に依存する方式です。
  • 暗号化: 各平文ブロックは、まず前の暗号文ブロック（または最初のブロックの場合は初期化ベクトルIV）とXORされ、その結果がブロック暗号アルゴリズムによって暗号化されます。これにより、同じ平文ブロックが異なる暗号文ブロックにマッピングされ、パターン認識攻撃を防ぎます。
  • 復号: 各暗号文ブロックは、まずブロック暗号アルゴリズムによって復号され、その結果が前の暗号文ブロック（または最初のブロックの場合はIV）とXORされて平文ブロックが生成されます。
• 初期化ベクトル (IV): CBCモードの最初のブロックを暗号化する際に使用されるランダムな値です。各暗号化セッションで異なるIVを使用することで、同じ平文が常に同じ暗号文になることを防ぎ、セキュリティを向上させます。IVは通常、暗号文とともに送信されます。

2. インプレース操作

インプレース操作とは、データを新しいメモリ領域にコピーすることなく、既存のメモリ領域内で直接データを変更する操作のことです。これにより、メモリ割り当てやデータコピーのオーバーヘッドを削減し、パフォーマンスを向上させることができます。暗号処理のような計算集約的なタスクでは、インプレース操作の採用が特に重要になります。

3. xorBytes 関数

xorBytes(dst, a, b) は、バイトスライス a と b の対応する要素をXOR演算し、その結果を dst に書き込む関数です。暗号化処理において、平文とIV（または前の暗号文）を組み合わせる際によく使用されます。

4. Go言語のスライスとメモリ管理

Go言語のスライスは、配列の一部を参照する軽量なデータ構造です。スライスは基盤となる配列のビューを提供するため、スライスを操作しても通常はデータのコピーは発生しません。しかし、スライスから新しいスライスを作成したり、異なるスライス間でデータを移動したりする際には、copy関数などを用いて明示的にデータをコピーする必要があります。このコミットは、このような明示的なコピー操作の回数を減らすことに焦点を当てています。

技術的詳細

このコミットの技術的な核心は、CBCモードにおける暗号化と復号のループ処理において、中間データのコピーを極力排除し、インプレースでの処理を最大化することにあります。

暗号化 (cbcEncrypter.CryptBlocks) の改善

変更前は、各ブロックの処理でIVと平文ブロックのXOR結果を一時的なバッファ（x.iv）に書き込み、その後そのバッファを暗号化し、最後にその結果をdstにコピーしていました。

変更後は、xorBytesの出力先を直接dstの現在のブロックに指定し、そのdstのブロックをそのまま暗号化するようになりました。 xorBytes(dst[:x.blockSize], src[:x.blockSize], iv) x.b.Encrypt(dst[:x.blockSize], dst[:x.blockSize]) これにより、x.ivへの一時的な書き込みと、その後のdstへのコピーが不要になり、各ブロックあたりのコピー回数が1回削減されます。最終的なIVの保存はループの最後に1回だけ行われます。

復号 (cbcDecrypter.CryptBlocks) の改善

復号処理の最適化はより複雑で、ブロックを逆順に処理するというアプローチが採用されています。

変更前は、各ブロックを順方向に処理し、復号結果を一時的なバッファ（x.tmp）に書き込み、IVを更新し、最後にx.tmpからdstにコピーしていました。このプロセスでは、各ブロックでIVのコピーと復号結果のコピーが発生していました。

変更後、復号は最後のブロックから最初のブロックへと逆方向にループします。 CBC復号の特性として、現在のブロックの平文を得るためには、現在の暗号文ブロックを復号した結果と、前の暗号文ブロック（これが次のブロックのIVとなる）をXORする必要があります。 逆順に処理することで、src[prev:start]（前の暗号文ブロック）が常に利用可能であり、これを直接IVとして使用できます。これにより、IVを毎回コピーする必要がなくなります。

1. 最後のブロックの処理: 最後のブロックの暗号文をx.tmpにコピーし、これを新しいIVとして準備します。
2. 逆順ループ: 最後のブロックから2番目のブロックまでを逆順に処理します。
   • x.b.Decrypt(dst[start:end], src[start:end]): 現在の暗号文ブロックをインプレースで復号します。
   • xorBytes(dst[start:end], dst[start:end], src[prev:start]): 復号結果と前の暗号文ブロックをXORし、結果をdstにインプレースで書き込みます。
3. 最初のブロックの処理: 最初のブロックは、ループの外で特別に処理されます。これは、最初のブロックのIVがx.ivに保存されているためです。
   • x.b.Decrypt(dst[start:end], src[start:end]): 最初の暗号文ブロックをインプレースで復号します。
   • xorBytes(dst[start:end], dst[start:end], x.iv): 復号結果と保存されていたIVをXORし、結果をdstにインプレースで書き込みます。
4. IVの更新: 最後に、x.ivとx.tmpをスワップすることで、次のCryptBlocks呼び出しのためのIVを効率的に設定します。

この逆順処理とインプレース操作の組み合わせにより、復号におけるコピー呼び出しの回数が大幅に削減され、パフォーマンスが向上します。

テストコードの変更

テストコードも、暗号化と復号のテストをそれぞれ独立した関数TestCBCEncrypterAESとTestCBCDecrypterAESに分割し、より明確に検証できるように変更されています。また、テストデータもインプレース操作を考慮して、copy(data, test.in)やcopy(data, test.out)のように、テスト対象の関数に渡す前に明示的にコピーを作成するようになっています。これは、CryptBlocksが入力バッファを直接変更する可能性があるため、元のテストデータを保護し、テストの独立性を保つためです。

コアとなるコードの変更箇所

src/pkg/crypto/cipher/cbc.go

cbcEncrypter.CryptBlocks (暗号化)

@@ -48,13 +48,22 @@ func (x *cbcEncrypter) CryptBlocks(dst, src []byte) {
 	if len(dst) < len(src) {
 		panic("crypto/cipher: output smaller than input")
 	}
+
+	iv := x.iv
+
 	for len(src) > 0 {
-		xorBytes(x.iv, x.iv, src[:x.blockSize])
-		x.b.Encrypt(x.iv, x.iv)
-		copy(dst, x.iv)
+		// 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)
 }

cbcDecrypter.CryptBlocks (復号)

@@ -85,14 +94,35 @@ func (x *cbcDecrypter) CryptBlocks(dst, src []byte) {
 	if len(dst) < len(src) {
 		panic("crypto/cipher: output smaller than input")
 	}
-	for len(src) > 0 {
-		x.b.Decrypt(x.tmp, src[:x.blockSize])
-		xorBytes(x.tmp, x.tmp, x.iv)
-		copy(x.iv, src)
-		copy(dst, x.tmp)
-		src = src[x.blockSize:]
-		dst = dst[x.blockSize:]
+	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
 }

src/pkg/crypto/cipher/cbc_aes_test.go

テスト関数の分割と、テストデータコピーの追加。

@@ -63,28 +63,42 @@ var cbcAESTests = []struct {
 	},
 }
 
-func TestCBC_AES(t *testing.T) {
-	for _, tt := range cbcAESTests {
-		test := tt.name
-
-		c, err := aes.NewCipher(tt.key)
+func TestCBCEncrypterAES(t *testing.T) {
+	for _, test := range cbcAESTests {
+		c, err := aes.NewCipher(test.key)
 		if err != nil {
-			t.Errorf("%s: NewCipher(%d bytes) = %s", test, len(tt.key), err)
+			t.Errorf("%s: NewCipher(%d bytes) = %s", test.name, len(test.key), err)
 			continue
 		}
 
-		encrypter := cipher.NewCBCEncrypter(c, tt.iv)
-		d := make([]byte, len(tt.in))
-		encrypter.CryptBlocks(d, tt.in)
-		if !bytes.Equal(tt.out, d) {
-			t.Errorf("%s: CBCEncrypter\nhave %x\nwant %x", test, d, tt.out)
+		encrypter := cipher.NewCBCEncrypter(c, test.iv)
+
+		data := make([]byte, len(test.in))
+		copy(data, test.in)
+
+		encrypter.CryptBlocks(data, data)
+		if !bytes.Equal(test.out, data) {
+			t.Errorf("%s: CBCEncrypter\nhave %x\nwant %x", test.name, data, test.out)
 		}
+	}
+}
+
+func TestCBCDecrypterAES(t *testing.T) {
+	for _, test := range cbcAESTests {
+		c, err := aes.NewCipher(test.key)
+		if err != nil {
+			t.Errorf("%s: NewCipher(%d bytes) = %s", test.name, len(test.key), err)
+			continue
+		}
+
+		decrypter := cipher.NewCBCDecrypter(c, test.iv)
+
+		data := make([]byte, len(test.out))
+		copy(data, test.out)
 
-		decrypter := cipher.NewCBCDecrypter(c, tt.iv)
-		p := make([]byte, len(d))
-		decrypter.CryptBlocks(p, d)
-		if !bytes.Equal(tt.in, p) {
-			t.Errorf("%s: CBCDecrypter\nhave %x\nwant %x", test, d, tt.in)
+		decrypter.CryptBlocks(data, data)
+		if !bytes.Equal(test.in, data) {
+			t.Errorf("%s: CBCDecrypter\nhave %x\nwant %x", test.name, data, test.in)
 		}
 	}
 }

コアとなるコードの解説

cbcEncrypter.CryptBlocks の解説

• iv := x.iv: 各ブロックの処理を開始する前に、現在のIVをローカル変数ivにコピーします。これにより、ループ内でx.ivに直接アクセスする代わりに、ローカル変数を使用することで、潜在的なエイリアシングの問題を避けつつ、コードの可読性を向上させています。
• xorBytes(dst[:x.blockSize], src[:x.blockSize], iv): ここが重要な変更点です。以前はxorBytes(x.iv, x.iv, src[:x.blockSize])のように、x.ivを一時的なバッファとして使用していました。変更後は、XORの結果を直接出力先であるdstの現在のブロックに書き込むようにしました。これにより、中間的なコピーが不要になります。
• x.b.Encrypt(dst[:x.blockSize], dst[:x.blockSize]): XORの結果が書き込まれたdstの現在のブロックを、そのままインプレースで暗号化します。ここでも、一時的なバッファへのコピーと、その後のdstへのコピーが削減されます。
• iv = dst[:x.blockSize]: 暗号化された現在のブロックが、次のブロックのIVとして機能するため、ivを更新します。
• copy(x.iv, iv): ループが終了した後、最終的なIVの状態をx.ivに一度だけコピーして保存します。これにより、次のCryptBlocks呼び出し時に正しいIVが使用されることを保証します。

この変更により、各ブロック処理におけるcopy呼び出しが実質的に1回（最終的なIVの保存）に削減され、n回のコピーが1回に改善されます。

cbcDecrypter.CryptBlocks の解説

• if len(src) == 0 { return }: 空の入力に対する早期リターンを追加し、不要な処理を避けます。
• end := len(src), start := end - x.blockSize, prev := start - x.blockSize: 復号処理を逆順に行うためのインデックスを計算します。endは現在のブロックの終了位置、startは開始位置、prevは前のブロックの開始位置を示します。
• copy(x.tmp, src[start:end]): 復号のループに入る前に、最後の暗号文ブロックをx.tmpにコピーします。これは、このブロックが次のCryptBlocks呼び出しのための新しいIVとなるためです。
• for start > 0 { ... }: 最初のブロックを除くすべてのブロックを逆順にループ処理します。
  • x.b.Decrypt(dst[start:end], src[start:end]): 現在の暗号文ブロックをインプレースで復号します。
  • xorBytes(dst[start:end], dst[start:end], src[prev:start]): 復号結果と前の暗号文ブロック（src[prev:start]）をXORし、結果をdstにインプレースで書き込みます。この「前の暗号文ブロック」が、CBC復号におけるIVの役割を果たします。逆順に処理することで、この値が常にsrcから直接利用可能となり、IVのコピーが不要になります。
  • end = start, start = prev, prev -= x.blockSize: 次のブロック（逆順なので前のブロック）へ移動するためにインデックスを更新します。
• x.b.Decrypt(dst[start:end], src[start:end]): ループを抜けた後、最初のブロックを処理します。このブロックは、保存されていたx.ivとXORされます。
• xorBytes(dst[start:end], dst[start:end], x.iv): 最初のブロックの復号結果と、cbcDecrypter構造体に保存されている初期IVをXORします。
• x.iv, x.tmp = x.tmp, x.iv: 最後に、x.ivとx.tmpをスワップします。これにより、x.tmpにコピーしておいた最後の暗号文ブロックが新しいx.ivとなり、次のCryptBlocks呼び出しに備えます。

この逆順処理とインプレース操作により、復号におけるcopy呼び出しが実質的に1回（最後のブロックのコピー）に削減され、2n回のコピーが1回に改善されます。

関連リンク

• Go言語のcrypto/cipherパッケージドキュメント: https://pkg.go.dev/crypto/cipher
• Go言語のcrypto/aesパッケージドキュメント: https://pkg.go.dev/crypto/aes
• Cipher Block Chaining (CBC) モード - Wikipedia: https://ja.wikipedia.org/wiki/Cipher_Block_Chaining
• Authenticated Encryption with Associated Data (AEAD) - Wikipedia: https://ja.wikipedia.org/wiki/Authenticated_Encryption_with_Associated_Data (CBCのセキュリティ上の注意点に関連)

参考にした情報源リンク

• Go CL 50900043: crypto/cipher: improved cbc performance - https://golang.org/cl/50900043
• Go-nuts メーリングリストでの議論 (2014年): AES-128-CBC および AES-256-CBC のパフォーマンスに関する言及
• Medium記事 (2019年): GoのAES CBC+HMACおよびGCMパフォーマンスとJava JCEの比較
• Cloudflareブログ (2015年): Goの暗号スタックのパフォーマンス改善とTLSサーバーでの利用
• GitHub golang/go リポジトリのIssue (2017年): 標準Go cryptoとBoringSSLのパフォーマンス差に関する議論
• Go.dev: AEADモードの推奨に関する情報