Galois/Counter Mode

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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(2128) 有限体は以下の多項式で定義される。

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

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

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

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

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\lVert0^{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\lVert0^{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}

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

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

利用[編集]

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

パフォーマンス[編集]

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

GCMでは、1ブロック(128バイト)の暗号化および認証につき1ブロックの暗号化操作と1回のガロア域での128ビット乗算を必要とする。ブロック暗号の操作は容易にパイプライン化あるいは並列化することが可能であり、乗算操作はパイプライン化が容易に可能であり、並列化についても近年の研究によって可能となった(実際の操作の並列化あるいはホーナー法の適用、あるいはその両方)。

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

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

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

特許[編集]

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

セキュリティ[編集]

GCMの安全性はconcrete security modelによって証明されている[14]。ランダムな順列と見分けのつかない暗号利用モードと一緒に利用する場合には安全であるが、実際の安全性は同一の鍵を用いた個々の暗号化に用いる初期化ベクトルの選択に依存する。任意の鍵と初期化ベクトルの組み合わせにおいて、GCMは239−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かつ最大パケット長が210の場合、認証復号化関数は211回より多く呼び出されるべきではない。また、t = 64かつ最大パケット長が215の場合、認証復号化関数は232回より多く呼び出されるべきではない)。

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

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

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

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

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

関連項目[編集]

脚注[編集]

  1. ^ The Galois/Counter Mode of Operation (GCM)”. p. 5 (2005年). 2013年12月21日閲覧。 Note that there is a typo in the formulas in the article.
  2. ^ 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.
  3. ^ RFC 4106 The Use of Galois/Counter Mode (GCM) in IPsec Encapsulating Security Payload (ESP)
  4. ^ RFC 4543 The Use of Galois Message Authentication Code (GMAC) in IPsec ESP and AH
  5. ^ RFC 5647 AES Galois Counter Mode for the Secure Shell Transport Layer Protocol
  6. ^ RFC 5288 AES Galois Counter Mode (GCM) Cipher Suites for TLS
  7. ^ RFC 6367 Addition of the Camellia Cipher Suites to Transport Layer Security (TLS)
  8. ^ [1]
  9. ^ Cryptographic Hardware and Embedded Systems — CHES 2009, Lecture Notes in Computer Science 5745, Springer-Verlag (2009), pp 1—17.
  10. ^ http://groups.google.com/group/cryptopp-users/msg/a688203c2314ef08
  11. ^ Gueron, Shay. “AES-GCM for Efficient Authenticated Encryption – Ending the Reign of HMAC-SHA-1?”. Workshop on Real-World Cryptography. 2013年2月8日閲覧。
  12. ^ 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.
  13. ^ authors' statement
  14. ^ [2] The Security and Performance of the Galois/counter mode (GCM) of Operation, Proceedings of INDOCRYPT 2004, LNCS 3348 (2004)
  15. ^ Niels Ferguson, Authentication Weaknesses in GCM, 2005-05-20
  16. ^ 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. 

参考文献[編集]

外部リンク[編集]