Galois/Counter Mode

Galois/Counter Mode (GCM) について

Galois/Counter Mode（GCM）は、ブロック[[暗号]]の暗号利用モードの一つであり、認証付き暗号（Authenticated Encryption, AE）として知られています。GCMは、データの機密性保護（暗号化）とメッセージ認証（完全性の確認）の両方を同時に提供する点が特徴です。

GCMの動作原理

GCMは、鍵 K、暗号化対象の平文 P、関連データ A（暗号化は行わず認証のみを行うデータ）を入力として受け取ります。GCMは以下のステップで動作します。

1. 暗号化: 平文 P を暗号化して暗号文 C を生成します。
2. 認証タグ生成: 暗号文 C と関連データ A をもとに認証タグ T を生成します。

鍵 K を持つ受信者は、A、C、Tを受け取ることで、次の処理を行います。

1. 復号: 暗号文 C を復号して平文 P を取得します。
2. 認証: 認証タグ T を検証することで、暗号文や関連データが改ざんされていないかを確認します。

GCMは128ビットのブロック長を持つブロック[[暗号]]（例えばAES）に適用できます。また、GCMの派生であるGalois Message Authentication Code (GMAC) は、認証のみを行うメッセージ認証符号として使用可能です。GCMとGMACは共に、任意長の初期化ベクトル（IV）を使用できます。

同じブロック[[暗号]]を使用する場合でも、暗号利用モードが異なると、パフォーマンスや効率に大きな差が生じることがあります。GCMは並列処理が可能であり、実装においては命令パイプラインやハードウェアによるパイプライン化を活用できます。一方、CBCモードなどの連鎖モードでは、パイプラインストールが発生しやすいという課題があります。

GCMの構成要素

GCMは、暗号化にCTRモードを、認証に新しいGaloisモードを組み合わせています。

1. CTRモードによる暗号化: 初期化ベクトル IV からブロック[[暗号]]を用いて鍵ストリームを生成し、平文と鍵ストリームの排他的論理和をとることで暗号文を生成します。CTRモードはストリーム[[暗号]]であるため、異なるIVを使用することが重要です。
2. Galoisモードによる認証: CTRモードで暗号化された暗号文と関連データは、Galoisモードで処理されます。Galoisモードでは、入力データをガロア体上の多項式とみなし、鍵に依存した値 H における多項式評価を行い、その評価値を鍵と IV に依存した値でマスクして認証タグを得ます。Galoisモードにおける多項式評価は並列計算が可能であるため、高速な処理が可能です。

暗号化と認証タグ生成の詳細

1. 初期カウンタ値の生成: 最初に、初期化ベクトル IV から初期カウンタ値 counter0 を生成します。通常、IVは96ビット長が使われます。その場合、counter0は以下のようになります。

`counter0 = IV || 0^31 || 1`

ここで、`||` はビット列の連結を表し、`0^31` は31ビットの0を表します。

2. 鍵ストリームの生成: CTRモードの鍵ストリームは、以下の式で生成されます。

`E_K(counter0+1) || E_K(counter0+2) || E_K(counter0+3) || ...`

ここで、`E_K` は鍵 K によるブロック[[暗号]]（通常はAES）による暗号化を表します。

3. 暗号文の生成: 平文 P と鍵ストリームの排他的論理和を計算し、暗号文 C を生成します。

4. ガロア体 GF(2^128)
Galoisモードで利用される有限体 GF(2^128) は以下の多項式で定義されます。

`x^128 + x^7 + x^2 + x + 1`

5. 認証タグの生成: 認証タグは、GHASH関数にデータブロックを与え、その結果をマスクすることで生成されます。GHASH関数は以下の式で定義されます。

`GHASH(H, A, C) = X_{m+n+1}`

ここで、H は128個のゼロから成る文字列をブロック[[暗号]]によって暗号化したもの、A は関連データ、C は暗号文、m は A に含まれる128ビットのブロック数、n は C に含まれる128ビットのブロック数です。X_i は以下の式で定義されます。

まず、A と C を128ビットの倍数になるように0でパディングして連結し、S_i を生成します。

`S_i = { A_i for i = 1, …, m-1; A_m || 0^(128-v) for i = m; C_{i-m} for i = m+1, …, m+n-1; C_n || 0^(128-u) for i = m+n; len(A) || len(C) for i= m+n+1 }`

ここで len(A), len(C) はそれぞれ A, C のビット長を64ビットで表したものであり、vはAの最終ブロックのビット長、uはCの最終ブロックのビット長を示します。

次に、X_i は以下の式で定義されます。

`X_i = Σ(j=1 to i) S_j H^(i-j+1)`

または以下の反復式でも計算できます

`X_i = 0 for i = 0; (X_{i-1} ⊕ S_i) H for i= 1, …, m+n+1`

X_i の計算は並列化も可能です。例えば、k個のリソースを使う場合、次のように計算できます。
`X'_i = 0 for i <= 0; (X'_{i-k}⊕S_i)H^k for i=1, …, m+n+1-k`
`X_i = Σ(j=1 to k) (X'_{i+j-2k}⊕S_{i+j-k})H^{k-j+1}`

GCMの歴史と標準化

GCMは、Carter-Wegman Counter Mode (CWC) の改良として、John ViegaとDavid A. McGrewによって設計されました。2007年11月2日、NISTは NIST Special Publication 800-38D を公開し、GCMとGMACを公式な標準として認定しました。

GCMの利用

GCMはその効率性とパフォーマンスから広く採用されており、IEEE 802.1AE (MACsec)、IEEE 802.11ad (WiGig)、IEEE P1619.1、ANSI (INCITS) のファイバーチャネルセキュリティプロトコル (FC-SP)、IETFのIPsec、SSH、TLS 1.2など、多くの標準規格で使用されています。また、AES-GCMはNSA Suite B Cryptographyの一部としても採用されています。

パフォーマンス

GCMは、遅延が少なく、オーバーヘッドが少ないため、パケット化されたデータの保護に適しています。GCMは、1ブロック（128ビット）の暗号化と認証に、1回のブロック[[暗号]]実行と1回のガロア体での128ビット乗算を必要とします。これらの処理は並列化やパイプライン化が可能で、高速な処理を実現できます。

インテルは、2010年以降のプロセッサにGCMの計算を高速化するためのCLMUL命令セット (PCLMULQDQ) を実装しています。この命令セットは、GF(2n) 有限体上での乗算を高速化します。

様々なプラットフォームでGCMのパフォーマンスが報告されており、AES-GCMで10.68 cycles per byte、AES-NIとPCLMULQDQを併用した場合で3.5 cycles per byte、Ivy Bridgeで2.47 cycles per byteなどが報告されています。

暗号化と認証の両方が必要な場合、これらの処理を重ね合わせることで高速化が可能です。この手法は「function stitching」と呼ばれ、GCMに特に適しています。

特許

GCMは特許による利用制限がないことが設計者によって表明されています。

セキュリティ

GCMの安全性は、concrete security model によって証明されています。ただし、実際の安全性は、初期化ベクトルの選択に依存します。GCMは、任意の鍵とIVの組み合わせにおいて、2^39〜2^56ビットまでの平文の暗号化に限定されます。初期化ベクトルの選択に関するガイドラインは NIST SP 800-38D に記載されています。

認証の強度は認証タグの長さに依存するため、短いタグの使用は推奨されません。通常、タグ長 t は128、120、112、104、96ビットが用いられます。64ビットや32ビットのタグ長が使われることもありますが、入力データ長や鍵の寿命に制約が加えられる可能性があります。

攻撃者が任意の t ビットのタグを選択した場合、それが正しい確率は 2^-t です。しかし、GCMでは攻撃者が確率を高くするタグを選択できる可能性があり、その確率は暗号文と関連データの長さに比例します。そのため、GCMは短いタグや長いメッセージでの利用には適していません。

Fergusonは、エンコード中のブロック数を n とした場合、n^2 2^-t の確率で暗号文を改竄できる可能性を示しました。Saarinenは、GCMにおける弱鍵を提示し、(n/2) 2^-128 の確率でメッセージを改竄できる手法を報告しました。Saarinenは、GF(2^128) の代わりに GF(2^128+12451) を用いたSophie Germain Counter Mode (SGCM) を提唱しています。

参考資料

NIST Special Publication 800-38D: Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) for Confidentiality and Authentication
RFC 4106: The Use of Galois/Counter Mode (GCM) in IPsec Encapsulating Security Payload (ESP)
RFC 4543: The Use of Galois Message Authentication Code (GMAC) in IPsec ESP and AH
RFC 5288: AES Galois Counter Mode (GCM) Cipher Suites for TLS
RFC 6367: Addition of the Camellia Cipher Suites to Transport Layer Security (TLS)
RFC 7714: AES-GCM Authenticated Encryption in the Secure Real-time Transport Protocol (SRTP)
IEEE 802.1AE - Media Access Control (MAC) Security
IEEE Security in Storage Working Group developed the P1619.1 standard
* INCITS T11 Technical Committee works on Fibre Channel - Security Protocols project.

もう一度検索