[インデックス 17967] ファイルの概要
このコミットは、Go言語の crypto/cipher パッケージ内の gcm.go ファイルに対する変更です。具体的には、GCM (Galois/Counter Mode) 暗号モードで使用されるカウンタのインクリメント処理 gcmInc32 関数のパフォーマンス改善を目的としています。
コミット
commit b2a198ce39569687e277f794f189299c530a0021
Author: Han-Wen Nienhuys <hanwen@google.com>
Date: Thu Dec 12 11:25:17 2013 -0500
crypto/cipher: speed up gcmInc32.
The counter is not secret, so the code does not need to be
constant time.
benchmark old MB/s new MB/s speedup
BenchmarkAESGCMSeal1K 89.90 92.84 1.03x
BenchmarkAESGCMOpen1K 89.16 92.30 1.04x
R=agl
CC=golang-dev
https://golang.org/cl/40690046
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/b2a198ce39569687e277f794f189299c530a0021
元コミット内容
crypto/cipher: speed up gcmInc32.
The counter is not secret, so the code does not need to be constant time.
benchmark old MB/s new MB/s speedup
BenchmarkAESGCMSeal1K 89.90 92.84 1.03x
BenchmarkAESGCMOpen1K 89.16 92.30 1.04x
変更の背景
このコミットの背景には、暗号処理のパフォーマンス最適化という明確な目的があります。GCM (Galois/Counter Mode) は、認証付き暗号化 (Authenticated Encryption with Associated Data, AEAD) を提供するブロック暗号の動作モードであり、高速性とセキュリティの両方が求められます。GCMでは、カウンタモードが使用され、各ブロックの暗号化にユニークなカウンタ値が生成されます。このカウンタのインクリメント処理は、暗号化・復号化のたびに頻繁に実行されるため、その効率が全体のパフォーマンスに大きく影響します。
元の実装では、カウンタのインクリメント処理 gcmInc32 が、サイドチャネル攻撃を防ぐための「定数時間 (constant time)」処理を意識した実装になっていた可能性があります。定数時間処理とは、入力データの内容によらず、処理時間が一定になるように設計されたアルゴリズムのことです。これは、秘密鍵やその他の機密情報が処理時間から推測されるのを防ぐために、暗号アルゴリズムにおいて非常に重要です。
しかし、このコミットの作者は、「カウンタは秘密ではない (The counter is not secret)」と明記しています。GCMにおけるカウンタは、各ブロックの暗号化に使用されるユニークな値であり、通常は公開されても問題ない情報です。したがって、カウンタのインクリメント処理が定数時間である必要はないと判断されました。定数時間処理は、通常、追加の計算や複雑なロジックを伴うため、パフォーマンスのオーバーヘッドが発生します。このオーバーヘッドを排除することで、カウンタのインクリメント処理、ひいてはGCM全体のパフォーマンスを向上させることが可能になります。
ベンチマーク結果が示すように、この変更によってAES-GCMのSeal (暗号化) および Open (復号化) 処理において、わずかながらもパフォーマンスの向上が見られました（約3〜4%の速度向上）。これは、暗号処理のような計算負荷の高い操作においては、小さな改善でも全体として大きな効果をもたらす可能性があることを示しています。
前提知識の解説
1. GCM (Galois/Counter Mode)
GCMは、ブロック暗号の動作モードの一つで、認証付き暗号化 (Authenticated Encryption with Associated Data, AEAD) を提供します。これは、データの機密性（暗号化）と完全性・認証性（改ざん検知と送信元認証）を同時に保証するものです。GCMは、カウンタモード (CTR) とGHASHと呼ばれるユニバーサルハッシュ関数を組み合わせたものです。
- カウンタモード (CTR): ブロック暗号をストリーム暗号のように動作させるモードです。各ブロックは、ユニークなカウンタ値と鍵をブロック暗号で暗号化した結果と、平文ブロックをXORすることで暗号化されます。カウンタ値は通常、初期ベクトル (IV) と連番を組み合わせたものです。
- GHASH: 認証タグを生成するために使用されるハッシュ関数です。関連データ (Associated Data, AD) と暗号文を組み合わせてハッシュ値を計算し、認証タグを生成します。
GCMは、TLS/SSL、IPsec、SSHなど、多くのセキュリティプロトコルで広く使用されています。
2. カウンタ (Counter)
GCMにおけるカウンタは、各ブロックの暗号化に使用されるユニークな入力値です。通常、これは初期ベクトル (IV) と、暗号化されるブロックのインデックス（連番）を組み合わせたものです。カウンタは、同じ平文ブロックが異なるカウンタ値で暗号化されることを保証し、これによりストリーム暗号の再利用攻撃を防ぎます。カウンタ値は、暗号化の過程で予測可能な方法でインクリメントされます。
3. 定数時間 (Constant Time) 処理
定数時間処理とは、アルゴリズムの実行時間が入力データの内容に依存せず、常に一定であるように設計された処理のことです。これは、サイドチャネル攻撃（Side-channel attack）を防ぐために、暗号アルゴリズムにおいて非常に重要な概念です。
- サイドチャネル攻撃: 暗号システムの実装から漏洩する情報（実行時間、消費電力、電磁波放射など）を分析することで、秘密鍵などの機密情報を推測しようとする攻撃です。
- 時間ベースのサイドチャネル攻撃: 特に、処理時間のわずかな違いを利用して、秘密鍵のビット値などを推測する攻撃です。例えば、ある条件分岐が秘密鍵のビットに依存し、その分岐の有無で処理時間が変わる場合、攻撃者はその時間の差を測定することで秘密鍵を推測できる可能性があります。
定数時間処理を実装するためには、条件分岐を避けたり、ループ回数を固定したり、メモリアクセスパターンを一定に保つなどの工夫が必要です。しかし、これらの工夫はしばしばコードの複雑性を増し、パフォーマンスを低下させる可能性があります。
このコミットでは、GCMのカウンタ値が秘密情報ではないため、カウンタのインクリメント処理が定数時間である必要がないと判断されました。これにより、より高速な非定数時間の実装に切り替えることが可能になりました。
技術的詳細
このコミットは、crypto/cipher パッケージ内の gcm.go ファイルにある gcmInc32 関数を最適化しています。この関数は、GCMモードで使用される16バイトのカウンタブロックの最後の4バイトをビッグエンディアンの32ビット値として扱い、それをインクリメントする役割を担っています。
元の実装では、カウンタのインクリメントに際して、c という一時変数を使用し、キャリー（繰り上がり）を明示的に処理していました。これは、定数時間処理を意識した実装、あるいはより汎用的な多倍長整数インクリメントのロジックに似ています。具体的には、最下位バイトから順に1を加え、繰り上がりがあれば次のバイトに伝播させるという処理を行っていました。
// 元のコード
func gcmInc32(counterBlock *[16]byte) {
c := 1
for i := gcmBlockSize - 1; i >= gcmBlockSize-4; i-- {
c += int(counterBlock[i])
counterBlock[i] = byte(c)
c >>= 8
}
}
このコードでは、c += int(counterBlock[i]) と c >>= 8 の操作が各バイトに対して行われ、c の値が変化することで、ループ内の処理がわずかに異なる時間で実行される可能性がありました。これは、厳密な定数時間処理を求める文脈では問題となることがあります。
新しい実装では、このロジックが大幅に簡素化されています。カウンタが秘密ではないという前提に基づき、定数時間処理の制約が取り払われたため、より直接的なインクリメント方法が採用されました。
// 変更後のコード
func gcmInc32(counterBlock *[16]byte) {
for i := gcmBlockSize - 1; i >= gcmBlockSize-4; i-- {
counterBlock[i]++
if counterBlock[i] != 0 {
break
}
}
}
この新しいコードでは、最下位バイトから順に1を加え (counterBlock[i]++)、その結果が0でなければ（つまり、繰り上がりがなければ）ループを終了します。これは、32ビットカウンタのインクリメントにおいて、繰り上がりが生じない限り、それより上位のバイトは変化しないという性質を利用したものです。例えば、...FF が ...00 になれば繰り上がりが発生し、次のバイトがインクリメントされます。...01 が ...02 になる場合は繰り上がりがないため、それ以上処理する必要はありません。
この変更により、各バイトの処理がよりシンプルになり、特に繰り上がりが頻繁に発生しない場合には、ループの実行回数が減る可能性があります。これにより、CPUのサイクル数が削減され、全体的なパフォーマンスが向上します。ベンチマーク結果が示すように、この最適化はAES-GCMのSealおよびOpen操作において、わずかながらも測定可能な速度向上をもたらしました。
コアとなるコードの変更箇所
src/pkg/crypto/cipher/gcm.go ファイルの gcmInc32 関数が変更されています。
--- a/src/pkg/crypto/cipher/gcm.go
+++ b/src/pkg/crypto/cipher/gcm.go
@@ -258,11 +258,11 @@ func (g *gcm) update(y *gcmFieldElement, data []byte) {
// gcmInc32 treats the final four bytes of counterBlock as a big-endian value
// and increments it.
func gcmInc32(counterBlock *[16]byte) {
- c := 1
for i := gcmBlockSize - 1; i >= gcmBlockSize-4; i-- {
- c += int(counterBlock[i])
- counterBlock[i] = byte(c)
- c >>= 8
+ counterBlock[i]++
+ if counterBlock[i] != 0 {
+ break
+ }
}
}
コアとなるコードの解説
変更された gcmInc32 関数は、GCMモードにおけるカウンタブロックのインクリメントを担当します。GCMでは、カウンタブロックは通常16バイト（128ビット）ですが、この関数は特にその最後の4バイト（32ビット）をビッグエンディアンの整数として扱い、1だけインクリメントします。
変更前:
func gcmInc32(counterBlock *[16]byte) {
c := 1 // インクリメントする値とキャリーを保持する変数
for i := gcmBlockSize - 1; i >= gcmBlockSize-4; i-- { // 最後の4バイトを逆順に処理
c += int(counterBlock[i]) // 現在のバイトにcを加える
counterBlock[i] = byte(c) // 結果をバイトに格納
c >>= 8 // キャリーを次のバイトのために右シフト
}
}
この実装は、各バイトに対して加算とキャリーの伝播を明示的に行っています。c の値が0または1になるため、c >>= 8 は実質的に c が1の場合は0になり、0の場合は0のままです。これは、多倍長整数演算の一般的なアプローチであり、定数時間処理を維持しようとする場合に採用されることがあります。
変更後:
func gcmInc32(counterBlock *[16]byte) {
for i := gcmBlockSize - 1; i >= gcmBlockSize-4; i-- { // 最後の4バイトを逆順に処理
counterBlock[i]++ // 現在のバイトをインクリメント
if counterBlock[i] != 0 { // インクリメント結果が0でなければ（繰り上がりがなければ）
break // ループを終了
}
}
}
この新しい実装は、より効率的です。
counterBlock[i]++: 現在のバイトを1だけインクリメントします。if counterBlock[i] != 0: インクリメントした結果が0でなければ、それは繰り上がりが生じなかったことを意味します（例:0x01が0x02になった場合）。この場合、それより上位のバイトは変化しないため、ループを終了して処理を完了します。- もし
counterBlock[i]が0になった場合（例:0xFFが0x00になった場合）、それは繰り上がりが生じたことを意味します。この場合、ループは続行され、次の上位バイトがインクリメントされます。
この変更により、カウンタのインクリメント処理は、繰り上がりが生じない限り、最大で1回のバイト操作と1回の比較で完了するようになります。これにより、特にカウンタ値が頻繁に繰り上がりを起こさない場合に、CPUサイクルが削減され、パフォーマンスが向上します。
関連リンク
- Galois/Counter Mode (GCM):
- NIST Special Publication 800-38D: Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38d.pdf
- Wikipedia: Galois/Counter Mode https://en.wikipedia.org/wiki/Galois/Counter_Mode
- Constant-time programming:
- Wikipedia: Side-channel attack https://en.wikipedia.org/wiki/Side-channel_attack
- "Constant-Time Programming" by Daniel J. Bernstein https://cr.yp.to/talks/2005.04.14/slides.pdf (スライド資料)
参考にした情報源リンク
- コミットメッセージ内のベンチマーク結果
- Go言語の
crypto/cipherパッケージのソースコード - GCMおよび定数時間処理に関する一般的な暗号学の知識
- NIST Special Publication 800-38D (GCMの公式仕様)
- Wikipediaの関連ページ (GCM, Side-channel attack)
- Daniel J. Bernstein氏による定数時間プログラミングに関する資料