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|CBCモード]]はしばしば{{仮リンク|パイプラインストール|en|pipeline stall}}（命令やユニット間の相互関係によってパイプラインが停止すること）に陥る。

== 処理の概要 ==
名称が示すように、GCMは暗号化として[[暗号利用モード#CTR|CTRモード]]を、認証として新しいGalois modeを組み合わせたものである。

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

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

== 暗号化と認証タグ生成の詳細 ==
[[File:GCM-Galois Counter Mode.svg|right|thumb|''GCM encryption operation'']]
まず、初期化ベクトル ''IV'' から初期カウンタ値 ''counter0'' を定める。''IV'' は任意長のビット列を用いることができるが、典型的には96ビットが用いられる。その場合、''counter0'' は以下で定義される。
:<math>
counter0 = IV \parallel 0^{31} \parallel 1 
</math>

次いで、CTRモードのための鍵ストリームを
:<math>
E_K(counter0 + 1) ||  E_K(counter0 + 2) ||E_K(counter0 + 3) || .... 
</math>
と生成し、鍵ストリームと平文 ''P'' の排他的論理和を暗号文 ''C'' とする。ここで、 <math>E_K</math> はブロック暗号（通常，AES）による暗号化である。

Galoisモードで利用される有限体 GF(2<sup>128</sup>) は以下の多項式で定義される。

: <math>x^{128} + x^7 + x^2 + x + 1</math>

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

: <math>\text{GHASH}(H,A,C) = X_{m+n+1}</math>

ここで ''H'' は128個のゼロから成る文字列を[[ブロック暗号]]によって暗号化したもの、''A'' は認証のみ行う（暗号化はしない）データ、''C'' は[[暗号文]]、''m'' は ''A'' に含まれる128ビットのブロックの数、''n''は ''C'' に含まれる128ビットのブロックの数であり、''i''&nbsp;=&nbsp;0,&nbsp;...,&nbsp;''m''&nbsp;+&nbsp;''n''&nbsp;+&nbsp;1 に対する ''X''<sub>''i''</sub> は以下のように定義される。

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

: <math>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}</math>

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

これを用いて、''X<sub>i</sub>'' は以下で定義される：

: <math>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}</math>

二つ目の表現方法は、[[ホーナー法]]を利用した効率的な[[反復法 (数学)|反復アルゴリズム]]であり、各々の ''X''<sub>''i''</sub> が ''X''<sub>''i-1''</sub> に依存する。最後の''X''<sub>''m''+''n''+1</sub>のみが出力となる。

<math>X_i</math> の反復計算は並列化可能である。''k'' 個のリソースを用いる場合、次式のように各リソースが ''k'' ブロックおきに処理すればよい。
: <math>\begin{align}
  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{align}</math>

GCMは、Carter–Wegman Counter mode（{{仮リンク|CWCモード|en|CWC mode}}）の改良として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を公式な標準として認定した。

== 利用 ==
その効率の良さとパフォーマンスから、広く用いられており、その最先端かつ高速でのコミュニケーションは、適切なハードウェア資源によって達成されているとされる<ref>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.</ref>。GCMは、[[IEEE]]の[[IEEE 802.1AE]] (MACsec) [[イーサネット]]セキュリティ、[[802.11ad|IEEE 802.11ad]] ([[WiGig]])、[[IEEE P1619]].1、[[米国国家規格協会|ANSI]] ([[情報技術規格国際委員会|INCITS]])の[[ファイバーチャネル]]セキュリティプロトコル (FC-SP)、[[Internet Engineering Task Force|IETF]]の[[IPsec]]<ref>{{IETF RFC|4106}} The Use of Galois/Counter Mode (GCM) in IPsec Encapsulating Security Payload (ESP)</ref><ref>{{IETF RFC|4543}} The Use of Galois Message Authentication Code (GMAC) in IPsec ESP and AH</ref>、[[Secure Shell|SSH]]<ref>{{IETF RFC|5647}} AES Galois Counter Mode for the Secure Shell Transport Layer Protocol</ref>、[[Transport Layer Security|TLS]] 1.2<ref>{{IETF RFC|5288}} AES Galois Counter Mode (GCM) Cipher Suites for TLS</ref><ref>{{IETF RFC|6367}} Addition of the Camellia Cipher Suites to Transport Layer Security (TLS)</ref>など、様々な標準規格に採用されている。また、[[Advanced Encryption Standard|AES]]-GCMは{{仮リンク|NSA Suite B Cryptography|en|NSA Suite B Cryptography}}およびその後継である[[商用国家安全保障アルゴリズム]]に含まれている。

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

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

[[インテル]]は、2010年の[[Nehalemマイクロアーキテクチャ|Westmere]]以降のプロセッサに、GCMの計算の高速化のための[[CLMUL instruction set]] (PCLMULQDQ)を実装している<ref>[http://software.intel.com/en-us/articles/intel-carry-less-multiplication-instruction-and-its-usage-for-computing-the-gcm-mode]</ref>。これは、GF(2<sup>n</sup>) 有限体上での乗法を高速化するものであり、任意の体の表現に適用可能である。

さまざまなプラットフォームにおいて、GCMのパフォーマンスについての報告がなされている。KäsperとSchwabeは、"Faster and Timing-Attack Resistant AES-GCM"と題する報告で、インテルの64ビットプロセッサを用いた[[AES]]-GCMでの暗号化で10.68 cycles per byteを達成している<ref>Cryptographic Hardware and Embedded Systems — CHES 2009, Lecture Notes in Computer Science 5745, Springer-Verlag (2009), pp 1—17.</ref>。Daiらは、同じアルゴリズムで[[AES-NI]]（AES暗号化のハードウェアアクセラレーション）とPCLMULQDQ（GCMの高速化）を併用することで3.5 cycles per byteを報告している<ref>https://groups.google.com/g/cryptopp-users/c/5x-vu0KwFRk/m/CO8UIzwgiKYJ</ref>。Shay Gueron とVlad Krasnovは、[[Ivy Bridge]]において2.47 cycles per byteを達成している。[[OpenSSL]]および[[Network Security Services|NSS]]に対しても、GCMの高速化のためのパッチが提出されている<ref>{{cite web|last=Gueron|first=Shay|title=AES-GCM for Efficient Authenticated Encryption – Ending the Reign of HMAC-SHA-1?|url=https://crypto.stanford.edu/RealWorldCrypto/slides/gueron.pdf|work=Workshop on Real-World Cryptography|accessdate=8 February 2013}}</ref>。

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

== 特許 ==
設計者の声明によれば、GCMは特許によって利用を妨げられることはない<ref>[http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm-nist-ipr.pdf authors' statement]</ref>。

== セキュリティ ==
GCMの安全性はconcrete security modelによって証明されている<ref>[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.4591] The Security and Performance of the Galois/counter mode (GCM) of Operation, Proceedings of INDOCRYPT 2004, LNCS 3348 (2004)</ref>。利用するブロック暗号がランダム置換と見分けがつかない場合には安全であるが、実際の安全性は同一の鍵を用いた個々の暗号化に用いる[[初期化ベクトル]]の選択に依存する。任意の鍵と初期化ベクトルの組み合わせにおいて、GCMは2<sup>39</sup>−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<sup>10</sup>の場合、認証復号関数は2<sup>11</sup>回より多く呼び出されるべきではない。また、''t'' = 64かつ最大パケット長が2<sup>15</sup>の場合、認証復号関数は2<sup>32</sup>回より多く呼び出されるべきではない）。

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

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

Fergusonは、''n'' をエンコード中（GHASH関数のインプット）のブロックの総数とした場合、およそ ''n''2<sup>−''t''</sup> の確率で対象の暗号文を改竄できる見込みのある手法を示した。タグ長 ''t'' が128より短い場合には、一つの改竄の成功が連続した改竄の成功の確率を増加させ、副鍵 ''H'' のハッシュ情報の漏えいにつながる。最終的には、''H'' そのものが危うくなり、認証の信頼性は失われる<ref>Niels Ferguson, [http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/CWC-GCM/Ferguson2.pdf Authentication Weaknesses in GCM], 2005-05-20</ref>。

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

SaarinenはGCMにおける[[弱鍵]]を示した<ref name="gcm-ghash-weak-keys">{{cite paper |author=Markku-Juhani O. Saarinen |date=2011-04-20 |title=Cycling Attacks on GCM, GHASH and Other Polynomial MACs and Hashes|publisher=FSE 2012 |url=http://eprint.iacr.org/2011/202 }}</ref>。この研究は、多項式によるハッシュに基づく認証がどのように機能するかについてよい考察を与えている。より正確には、この研究ではn*128ビットのメッセージに対しておおよそ (n/2){{sup|128}} の確率でGCMメッセージを改竄する特定の手法を報告している。しかしながら、この研究では既知の手法より効率の良い攻撃法は提示されていない。Aaarinenは、GCMの派生として、GF(2<sup>128</sup>) ではなく GF(2<sup>128</sup>+12451) （2<sup>128</sup>+12451 は[[ソフィー・ジェルマン素数]] (Sophie Germain prime)の一つ）を有限体として用いた{{仮リンク|Sophie Germain Counter Mode|en|Sophie Germain Counter Mode}} (SGCM)を提唱している。

== 脚注 ==
{{reflist}}

== 参考文献 ==
* [http://csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf 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]]

== 外部リンク ==
* [http://csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf NIST Special Publication SP800-38D defining GCM and GMAC]
* {{IETF RFC|4106}}: The Use of Galois/Counter Mode (GCM) in IPsec Encapsulating Security Payload (ESP)
* {{IETF RFC|4543}}: The Use of Galois Message Authentication Code (GMAC) in IPsec ESP and AH
* {{IETF RFC|5288}}: AES Galois Counter Mode (GCM) Cipher Suites for TLS
* {{IETF RFC|6367}}: Addition of the Camellia Cipher Suites to Transport Layer Security (TLS)
* {{IETF RFC|7714}}: AES-GCM Authenticated Encryption in the Secure Real-time Transport Protocol (SRTP)
* [http://www.ieee802.org/1/pages/802.1ae.html IEEE 802.1AE - Media Access Control (MAC) Security]
* [http://siswg.org/ IEEE Security in Storage Working Group] developed the P1619.1 standard
* [http://www.t11.org/index.htm INCITS T11 Technical Committee] works on [http://www.t11.org/t11/stat.nsf/7db1e1431d9d045f852566dc004cc14d/43b527df16f4b28d85256b9a00653843?OpenDocument Fibre Channel - Security Protocols] project.
* [http://eai-design.com/C_ASM_page.html  AES-GCM XPN-MACsec IEEE 802.1AE Free Software (C++) Model]

{{cryptography navbox|hash}}

{{デフォルトソート:かろあかうんたあもおと}}
[[Category:暗号利用モード]]
[[Category:認証付き暗号]]
[[Category:メッセージ認証コード]]
[[Category:有限体]]