Galois/Counter Mode

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

GCMは認証付き暗号の一つであり、データ保護とメッセージ認証（完全性確認）の両方の機能を提供する。したがって、GCMには鍵 K、平文 P （暗号化されるデータ）、関連データ(associated data. 暗号化せず認証だけされるデータ） A が与えられ、平文から暗号文 C が計算され、Ｃと A から認証タグ T が計算される。鍵 K を知っている受信者が A, C, T を受け取ったならば、受信者は暗号文を復号して平文 P を得ることができ、また認証タグ T をチェックすることで、暗号文や関連データが改ざんされていないことを確認できる。 GCMはブロック長128ビットのブロック暗号に適用可能である。Galois Message Authentication Code (GMAC) は、認証のみに特化したGCMの派生であり、メッセージ認証符号として利用できる。GCM、GMACのいずれも、任意長の初期化ベクトルを用いることが可能である。

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

処理の概要

名称が示すように、GCMは暗号化としてCTRモードを、認証として新しいGalois modeを組み合わせたものである。

暗号化においては、CTRモードと同様に、初期化ベクトル IV からブロック暗号（通常，AES）を用いて鍵ストリームを生成し、平文と鍵ストリームとの排他的論理和を取ることで、暗号文を生成する。暗号化はストリーム暗号であるため、鍵ストリームの生成ごとに異なる IV を用いることが重要である．

CTRモードの暗号文は、関連データ（associated data）に連結され、認証のためのGalois modeで処理される。Galois modeでは、入力されたデータをガロア体 (Galois field)上の多項式とみなし、鍵に依存した値 H における多項式評価をし、最後にその評価値を、鍵と IV に依存した値でマスクすることで認証タグを得る。Galois modeにおいて、認証タグの計算のメインである多項式評価は、ガロア体上の加算と乗算からなり、並列計算が可能である。そのため、CBCモードのように連鎖モードを用いる認証アルゴリズムよりも高速化が可能である。

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

GCM encryption operation

まず、初期化ベクトル IV から初期カウンタ値 counter0 を定める。IV は任意長のビット列を用いることができるが、典型的には96ビットが用いられる。その場合、counter0 は以下で定義される。

counter0=IV\parallel 0^{31}\parallel 1

次いで、CTRモードのための鍵ストリームを

E_{K}(counter0+1)||E_{K}(counter0+2)||E_{K}(counter0+3)||....

と生成し、鍵ストリームと平文 P の排他的論理和を暗号文 C とする。ここで、 $E_{K}$ はブロック暗号（通常，AES）による暗号化である。

Galoisモードで利用される有限体 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ビットのブロックの数であり、i = 0, ..., m + n + 1 に対する X_i は以下のように定義される。

まず、関連データ（認証のみされるデータ） A と暗号文 C を、それぞれ長さが128ビットの倍数になるように0でパディングしてから、つなげて１つのメッセージ $S_{i}$ を生成する：

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

ここで len(A) と len(C) は A と C のビット長を64ビットで表現したものであり、v は A の最終ブロックのビット長、 u は C の最終ブロックのビット長であり、 $\lVert$ はビット列の連結を示している。

これを用いて、X_i は以下で定義される：

X_{i}=\sum _{j=1}^{i}S_{j}\cdot H^{i-j+1}={\begin{cases}0&{\text{for }}i=0\\\left(X_{i-1}\oplus S_{i}\right)\cdot H&{\text{for }}i=1,\ldots ,m+n+1\end{cases}}

二つ目の表現方法は、ホーナー法を利用した効率的な反復アルゴリズムであり、各々の X_i が X_i-1 に依存する。最後のX_m+n+1のみが出力となる。

$X_{i}$ の反復計算は並列化可能である。k 個のリソースを用いる場合、次式のように各リソースが k ブロックおきに処理すればよい。

{\begin{aligned}X_{i}^{'}&={\begin{cases}0&{\text{for }}i\leq 0\\\left(X_{i-k}^{'}\oplus S_{i}\right)\cdot H^{k}&{\text{for }}i=1,\ldots ,m+n+1-k\\\end{cases}}\\[6pt]X_{i}&=\sum _{j=1}^{k}\left(X_{i+j-2k}^{'}\oplus S_{i+j-k}\right)\cdot H^{k-j+1}\end{aligned}}

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を公式な標準として認定した。

利用

その効率の良さとパフォーマンスから、広く用いられており、その最先端かつ高速でのコミュニケーションは、適切なハードウェア資源によって達成されているとされる^[1]。GCMは、IEEEのIEEE 802.1AE (MACsec) イーサネットセキュリティ、IEEE 802.11ad (WiGig)、IEEE P1619.1、ANSI (INCITS)のファイバーチャネルセキュリティプロトコル (FC-SP)、IETFのIPsec^[2]^[3]、SSH^[4]、TLS 1.2^[5]^[6]など、様々な標準規格に採用されている。また、AES-GCMはNSA Suite B Cryptography（英語版）およびその後継である商用国家安全保障アルゴリズムに含まれている。

パフォーマンス

GCMは遅延、オーバーヘッドが少ないことから、パケット化されたデータの保護に適している。

GCMでは、1ブロック（128ビット）の暗号化および認証につき1回のブロック暗号の実行と1回のガロア体での128ビット乗算を必要とする。ブロック暗号の操作は容易にパイプライン化あるいは並列化することが可能であり、乗算操作はパイプライン化が容易に可能であり、少し工夫することで並列化も可能である（実際の操作の並列化あるいはホーナー法の適用、あるいはその両方）。

インテルは、2010年のWestmere以降のプロセッサに、GCMの計算の高速化のためのCLMUL instruction set (PCLMULQDQ)を実装している^[7]。これは、GF(2ⁿ) 有限体上での乗法を高速化するものであり、任意の体の表現に適用可能である。

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

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

特許

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

セキュリティ

GCMの安全性はconcrete security modelによって証明されている^[13]。利用するブロック暗号がランダム置換と見分けがつかない場合には安全であるが、実際の安全性は同一の鍵を用いた個々の暗号化に用いる初期化ベクトルの選択に依存する。任意の鍵と初期化ベクトルの組み合わせにおいて、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 そのものが危うくなり、認証の信頼性は失われる^[14]。

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

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

脚注

^ Lemsitzer, Wolkerstorfer, Felber, Braendli, Multi-gigabit GCM-AES Architecture Optimized for FPGAs. CHES '07: Proceedings of the 9th international workshop on Cryptographic Hardware and Embedded Systems, 2007.
^ 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 5647 AES Galois Counter Mode for the Secure Shell Transport Layer Protocol
^ RFC 5288 AES Galois Counter Mode (GCM) Cipher Suites for TLS
^ RFC 6367 Addition of the Camellia Cipher Suites to Transport Layer Security (TLS)
^ [1]
^ Cryptographic Hardware and Embedded Systems — CHES 2009, Lecture Notes in Computer Science 5745, Springer-Verlag (2009), pp 1—17.
^ https://groups.google.com/g/cryptopp-users/c/5x-vu0KwFRk/m/CO8UIzwgiKYJ
^ Gueron, Shay. “AES-GCM for Efficient Authenticated Encryption – Ending the Reign of HMAC-SHA-1?”. Workshop on Real-World Cryptography. 8 February 2013閲覧。
^ Gopal, V., Feghali, W., Guilford, J., Ozturk, E., Wolrich, G., Dixon, M., Locktyukhin, M., Perminov, M.: Fast Cryptographic Computation on Intel Architecture Via Function Stitching. Intel Corp. (2010) http://download.intel.com/design/intarch/PAPERS/323686.pdf.
^ authors' statement
^ [2] The Security and Performance of the Galois/counter mode (GCM) of Operation, Proceedings of INDOCRYPT 2004, LNCS 3348 (2004)
^ Niels Ferguson, Authentication Weaknesses in GCM, 2005-05-20
^ Markku-Juhani O. Saarinen (2011-04-20). Cycling Attacks on GCM, GHASH and Other Polynomial MACs and Hashes. FSE 2012. http://eprint.iacr.org/2011/202.

参考文献

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

外部リンク

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

[1] Lemsitzer, Wolkerstorfer, Felber, Braendli, Multi-gigabit GCM-AES Architecture Optimized for FPGAs. CHES '07: Proceedings of the 9th international workshop on Cryptographic Hardware and Embedded Systems, 2007.

[2] RFC 4106 The Use of Galois/Counter Mode (GCM) in IPsec Encapsulating Security Payload (ESP)

[3] RFC 4543 The Use of Galois Message Authentication Code (GMAC) in IPsec ESP and AH

[4] RFC 5647 AES Galois Counter Mode for the Secure Shell Transport Layer Protocol

[5] RFC 5288 AES Galois Counter Mode (GCM) Cipher Suites for TLS

[6] RFC 6367 Addition of the Camellia Cipher Suites to Transport Layer Security (TLS)

[7] [1]

[8] Cryptographic Hardware and Embedded Systems — CHES 2009, Lecture Notes in Computer Science 5745, Springer-Verlag (2009), pp 1—17.

[9] ttps://groups.google.com/g/cryptopp-users/c/5x-vu0KwFRk/m/CO8UIzwgiKYJ

[10] Gueron, Shay. “AES-GCM for Efficient Authenticated Encryption – Ending the Reign of HMAC-SHA-1?”. Workshop on Real-World Cryptography. 8 February 2013閲覧。

[11] Gopal, V., Feghali, W., Guilford, J., Ozturk, E., Wolrich, G., Dixon, M., Locktyukhin, M., Perminov, M.: Fast Cryptographic Computation on Intel Architecture Via Function Stitching. Intel Corp. (2010) http://download.intel.com/design/intarch/PAPERS/323686.pdf.

[12] uthors' statement

[13] [2] The Security and Performance of the Galois/counter mode (GCM) of Operation, Proceedings of INDOCRYPT 2004, LNCS 3348 (2004)

[14] Niels Ferguson, Authentication Weaknesses in GCM, 2005-05-20

[gcm-ghash-weak-keys-15] Markku-Juhani O. Saarinen (2011-04-20). Cycling Attacks on GCM, GHASH and Other Polynomial MACs and Hashes. FSE 2012. http://eprint.iacr.org/2011/202.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]