Galois/Counter Mode

Galois/Counter Mode（ガロア カウンター モード、GCM）は、ブロック暗号の暗号利用モードの一つであり、認証付き暗号の一つである。

GCMは認証付き暗号の一つであり、データ保護と認証（完全性確認）の両方の機能を提供する。GCMはブロック長128ビットのブロック暗号に適用可能である。Galois Message Authentication Code (GMAC) は、認証のみに特化したGCMの派生であり、メッセージ認証符号として利用できる。GCM、GMACのいずれも、任意長の初期化ベクトルを用いることが可能である。

同じブロック暗号であっても、暗号利用モードが異なればそのパフォーマンスや効率には大きな違いが生じる。GCMは並列処理が可能であり、また、その実装は命令パイプラインやハードウェアでのパイプラインを活用することが可能である。一方、CBCモードはしばしばパイプラインストール（命令やユニット間の相互関係によってパイプラインが停止すること）に陥る。

暗号化と認証

GCM encryption operation

名称が示すように、GCMは暗号化としてCTRモードを、認証として新しいGalois modeを組み合わせたものである。鍵となるのは認証に用いられるガロア体 (Galois field)における乗法であり、並列計算が可能であることからCBCモードのように連鎖モードを用いる認証アルゴリズムよりも高速化が可能である。利用される GF(2¹²⁸) 有限体は以下の多項式で定義される。

$x^{128}+x^{7}+x^{2}+x+1$

認証タグはGHASH関数にデータブロックを与えることで構成され、その結果は暗号化される。GHASH関数は以下のように定義される。

${\text{GHASH}}(H,A,C)=X_{m+n+1}$

ここで H は128個のゼロから成る文字列をブロック暗号によって暗号化したもの、A は認証のみ行う（暗号化はしない）データ、C は暗号文、m は A に含まれる128ビットのブロックの数、nは C に含まれる128ビットのブロックの数である（A および C の最終ブロックは128ビットちょうどである必要はない）。i = 0, ..., m + n + 1 に対する X_i は以下のように定義される。

$X_{i}={\begin{cases}0&{\text{for }}i=0\\(X_{i-1}\oplus A_{i})\cdot H&{\text{for }}i=1,\ldots ,m-1\\(X_{m-1}\oplus (A_{m}^{*}\lVert 0^{128-v}))\cdot H&{\text{for }}i=m\\(X_{i-1}\oplus C_{i-m})\cdot H&{\text{for }}i=m+1,\ldots ,m+n-1\\(X_{m+n-1}\oplus (C_{n}^{*}\lVert 0^{128-u}))\cdot H&{\text{for }}i=m+n\\(X_{m+n}\oplus (\operatorname {len} (A)\lVert \operatorname {len} (C)))\cdot H&{\text{for }}i=m+n+1\\\end{cases}}$

ここで v は A の最終ブロックのビット長、 u は C の最終ブロックのビット長であり、$\lVert$ はビット列の連結を示している。ここで注意することは、これが反復アルゴリズムであり、各々の X_i が X_i-1 に依存し、最終的な X_i のみが出力として現れることである。

GCMは、Carter–Wegman Counter mode（CWCモード）の改良としてJohn ViegaおよびDavid A. McGrewによって設計された。

2007年11月2日、NISTはNIST Special Publication 800-38D Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMACを発表し、GCMおよびGMACを公式な標準として認定した。

利用

その効率の良さとパフォーマンスから、広く用いられており、その最先端かつ高速でのコミュニケーションは、適切なハードウェア資源によって達成されているとされる。GCMは、IEEEの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年のWestmere以降のプロセッサに、GCMの計算の高速化のためのCLMUL instruction set (PCLMULQDQ)を実装している。これは、GF(2ⁿ) 有限体上での乗法を高速化するものであり、任意の体の表現に適用可能である。

さまざまなプラットフォームにおいて、GCMのパフォーマンスについての報告がなされている。KäsperとSchwabeは、"Faster and Timing-Attack Resistant AES-GCM"と題する報告で、インテルの64ビットプロセッサを用いたAES-GCMでの暗号化で10.68 cycles per byteを達成している。Daiらは、同じアルゴリズムでAES-NI（AES暗号化のハードウェアアクセラレーション）とPCLMULQDQ（GCMの高速化）を併用することで3.5 cycles per byteを報告している。Shay Gueron とVlad Krasnovは、Ivy Bridgeにおいて2.47 cycles per byteを達成している。OpenSSLおよびNSSに対しても、GCMの高速化のためのパッチが提出されている。

認証と暗号化の両方を必要とする場合には、ソフトウェアでの実装においてそれらの操作を重ね合わせることで高速化が可能である。認証と暗号化の操作を交互に重ねることで並列化を促進することで、パフォーマンスの向上が見込める。この過程はfunction stitchingと呼ばれ、原理上は任意のアルゴリズムの組み合わせにも適用可能であるが、特にGCMに適している。ManleyとGreggは、function stitchingを用いた最適化法を示した。

特許

設計者の声明によれば、GCMは特許によって利用を妨げられることはない。

セキュリティ

GCMの安全性はconcrete security modelによって証明されている。利用するブロック暗号がランダム置換と見分けがつかない場合には安全であるが、実際の安全性は同一の鍵を用いた個々の暗号化に用いる初期化ベクトルの選択に依存する。任意の鍵と初期化ベクトルの組み合わせにおいて、GCMは2³⁹−256ビットまでの平文の暗号化に限定される。NIST Special Publication 800-38Dには、初期化ベクトルの選択に関するガイドラインも含まれている。

他のメッセージ認証符号と同様、GCMの認証の強度は認証タグの長さに依存するので、短い認証タグの使用は推奨されない。タグのビット長 t はセキュリティのパラメータとなる。通常 t は 128、120、112、104、96のいずれである。ソフトウェアによっては t が64あるいは32となることがあるが、これら2つのビット長は、入力データ長や鍵の寿命に制約を加えることがある。NIST SP 800-38DのAppendix Cでは、これらの制約について解説を加えている（一例として、t = 32かつ最大パケット長が2¹⁰の場合、認証復号関数は2¹¹回より多く呼び出されるべきではない。また、t = 64かつ最大パケット長が2¹⁵の場合、認証復号関数は2³²回より多く呼び出されるべきではない）。

他のメッセージ認証符号と同様に、攻撃者が任意の tビットのタグを選んだ場合、それが正しい確率は 2^-t である。しかしながら、GCMの場合には、攻撃者はその確率をより高くするタグを選択することが可能であり、その確率は暗号文の長さとadditional authenticated data (AAD)の長さの和に比例する。したがって、GCMは極めて短いタグあるいは非常に長いメッセージでの利用には適していない。

FergusonとSaarinenはそれぞれ、GCMの認証に対する最適な攻撃法を報告している。

Fergusonは、n をエンコード中（GHASH関数のインプット）のブロックの総数とした場合、およそ n2^−t の確率で対象の暗号文を改竄できる見込みのある手法を示した。タグ長 t が128より短い場合には、一つの改竄の成功が連続した改竄の成功の確率を増加させ、副鍵 H のハッシュ情報の漏えいにつながる。最終的には、H そのものが危うくなり、認証の信頼性は失われる。

これとは独立して、攻撃者は目的とする復号への入力に対して機械的に多数の異なる認証タグを試行することで、そのうちの一つ（あるいは複数）が正当なものとして受け入れられる可能性を増加させることが可能かもしれない。このため、GCMを実装したシステムあるいはプロトコルは、それぞれの鍵ごとに検証に失敗した試行の回数を監視し、必要であれば更なる試行を制限する必要がある。

SaarinenはGCMにおける弱鍵を示した。この研究は、多項式によるハッシュに基づく認証がどのように機能するかについてよい考察を与えている。より正確には、この研究ではn*128ビットのメッセージに対しておおよそ (n/2)¹²⁸ の確率でGCMメッセージを改竄する特定の手法を報告している。しかしながら、この研究では既知の手法より効率の良い攻撃法は提示されていない。Aaarinenは、GCMの派生として、GF(2¹²⁸) ではなく GF(2¹²⁸+12451) （2¹²⁸+12451 はソフィー・ジェルマン素数 (Sophie Germain prime)の一つ）を有限体として用いたSophie Germain Counter Mode (SGCM)を提唱している。

参考文献

• NIST Special Publication 800-38D (November, 2007) Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) for Confidentiality and Authentication

関連項目

• 暗号利用モード
• 認証付き暗号
• Advanced Encryption Standard

外部リンク

• NIST Special Publication SP800-38D defining GCM and GMAC
• 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.
• AES-GCM XPN-MACsec IEEE 802.1AE Free Software (C++) Model