ガロア/カウンターモード

暗号学において、ガロア/カウンタモード（GCM）^{[1]は、その性能から広く採用されている}対称鍵暗号ブロック暗号の動作モードです。最先端の高速通信チャネルのGCMスループット率は、安価なハードウェアリソースで達成できます。^[2]

GCM アルゴリズムは、データの信頼性 (整合性) と機密性の両方を提供し、関連データによる認証暗号化 (AEAD)方式のクラスに属します。つまり、入力としてキー K、プレーンテキスト P、および関連データ AD を受け取り、キーを使用してプレーンテキストを暗号化して暗号文 C を生成し、暗号文と関連データ (暗号化されていないまま) から認証タグ T を計算します。K を知っている受信者は、AD、C、および T を受信すると、暗号文を復号化してプレーンテキスト P を復元し、タグ T をチェックして暗号文も関連データも改ざんされていないことを確認できます。

GCM は、暗号化にカウンターモードで動作するブロックサイズ 128 ビットのブロック暗号 (通常はAES-128 )を使用し、認証タグを計算するためにガロア体GF(2 ¹²⁸ ) の演算を使用します。これが名前の由来です。

ガロア メッセージ認証コード( GMAC ) は、増分メッセージ認証コードを形成できる GCM の認証専用バリアントです。GCM と GMAC はどちらも、任意の長さの初期化ベクトルを受け入れることができます。

同じブロック暗号を使用する場合でも、異なるブロック暗号の動作モードではパフォーマンスと効率の特性が大きく異なる場合があります。GCM は並列処理を最大限に活用でき、GCM を実装すると命令パイプラインまたはハードウェア パイプラインを効率的に使用できます。対照的に、暗号ブロック チェーン(CBC) の動作モードではパイプラインの停止が発生し、効率とパフォーマンスが低下します。

通常のカウンター モードと同様に、ブロックには順番に番号が付けられ、このブロック番号は初期化ベクトル(IV) と組み合わされ、ブロック暗号E (通常はAES)で暗号化されます。この暗号化の結果はプレーン テキストとXOR され、暗号文が生成されます。すべてのカウンター モードと同様に、これは基本的にストリーム暗号であるため、暗号化されるストリームごとに異なる IV を使用することが不可欠です。

暗号文ブロックは多項式の係数とみなされ、有限体演算を使用してキー依存の点Hで評価されます。結果は暗号化され、データの整合性を検証するために使用できる認証タグが生成されます。暗号化されたテキストには、IV、暗号文、認証タグが含まれます。

GCMは、よく知られているカウンターモードの暗号化と新しいガロアモードの認証を組み合わせたものです。主な特徴は、認証に使用されるガロア体の乗算の並列計算が容易なことです。この機能により、連鎖モードを使用するCBCなどの暗号化アルゴリズムよりも高いスループットが可能になります。使用されるGF(2 ¹²⁸ )体は、多項式によって定義されます。

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

認証タグは、GHASH関数にデータブロックを投入し、その結果を暗号化することで構築されます。このGHASH関数は次のように定義されます。

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

ここで、H = E _k (0 ¹²⁸ ) はハッシュキー、ブロック暗号を使用して暗号化された 128 個のゼロビットの文字列、Aは認証のみが行われるデータ（暗号化されていない）、Cは暗号文、mはA内の 128 ビットブロックの数（切り上げ）、nはC内の 128 ビットブロックの数（切り上げ）、変数X _i（i = 0、...、m + n + 1）は以下のように定義される。^[3]

まず、認証されたテキストと暗号テキストは別々に128ビットの倍数にゼロパディングされ、単一のメッセージSiに結合さ_れます。

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

ここで、 len( A ) と len( C ) はそれぞれAとCのビット長の 64 ビット表現、v  = len( A ) mod 128 はAの最終ブロックのビット長、u  = len( C ) mod 128 はCの最終ブロックのビット長であり、ビット文字列の連結を表します。 ${\displaystyle \parallel}$

X _{i は}次のように定義されます。

${\displaystyle 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}}}$

2 番目の形式は、最初の形式にホーナー法を適用して生成される効率的な反復アルゴリズム (各X _{i は}X _{i −1}に依存) です。最終的なX _{m + n +1}のみが出力として残ります。

ハッシュ計算を並列化する必要がある場合は、 k回インターリーブすることで実行できます。

${\displaystyle {\begin{aligned}X_{i}^{'}&={\begin{cases}0&{\text{for }}i\leq 0\\\left(X_{ik}^{'}\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+jk}\right)\cdot H^{k-j+1}\end{aligned}}}$

IVの長さが96でない場合は、GHASH関数を使用してカウンター0を計算します。

${\displaystyle \mathrm {Counter0} ={\begin{cases}IV\parallel 0^{31}\parallel 1&{\text{for }}\operatorname {len} (IV)=96\\\operatorname {GHASH} \left(IV\parallel 0^{s}\parallel 0^{64}\parallel \operatorname {len} _{64}(IV)\right){\text{ with }}s=128-\operatorname {len} (IV)\mod 128&{\text{otherwise}}\end{cases}}}$

GCMは、カーター・ウェグマンカウンターモード（CWCモード）の改良として、ジョン・ヴィエガとデビッド・A・マクグルーによって設計されました。 ^[4]

2007年11月、NISTはブロック暗号の動作モードに関するNIST特別出版物800-38D勧告：ガロア/カウンターモード（GCM）とGMACのリリースを発表し、 GCMとGMACを公式標準とした。^[5]

GCM モードは、IEEE 802.1AE (MACsec) イーサネット セキュリティ、WPA3-Enterprise Wifi セキュリティ プロトコル、IEEE 802.11ad ( WiGigとも呼ばれる)、ANSI ( INCITS )ファイバー チャネルセキュリティ プロトコル (FC-SP)、IEEE P1619.1テープ ストレージ、IETF IPsec標準、^{[6] [7]} SSH、^[8] TLS 1.2 ^{[9] [10]}および TLS 1.3 ^[11]で使用されます。AES -GCM は、NSA Suite B 暗号化と、2018 年の最新のCommercial National Security Algorithm (CNSA)スイートでの置き換えに含まれています。 ^{[12] GCM モードは、} SoftEther VPNサーバーおよびクライアント^[13]と、バージョン 2.4 以降のOpenVPNで使用されています。

GCM では、暗号化および認証されたデータのブロック (128 ビット) ごとに、1 つのブロック暗号演算とガロア体での 128 ビット乗算が必要です。ブロック暗号演算は簡単にパイプライン化または並列化できます。乗算演算は簡単にパイプライン化でき、多少の労力で並列化できます (実際の演算を並列化するか、元の NIST 提出に従って Horner の方法を適用するか、またはその両方)。

IntelはPCLMULQDQ命令を追加し、GCMでの使用を強調しました。^{[14] 2011年にSPARCは、64×64ビットの}キャリーレス乗算も実行するXMULXおよびXMULXHI命令を追加しました。 2015年にSPARCは、最大2048×2048ビットの入力値までのはるかに大きな値のXOR乗算を実行し、4096ビットの結果を生成するXMPMUL命令を追加しました。 これらの命令は、GF(2n)上の高速乗算を可能にし^、任意の体表現で使用できます。

GCM の優れたパフォーマンス結果が、多くのプラットフォームで公開されています。Käsper と Schwabe は、64 ビット Intel プロセッサで 1 バイトあたり 10.68 サイクルの AES-GCM 認証暗号化を実現する「高速でタイミング攻撃に強い AES-GCM」^[15]について説明しました。Dai らは、Intel の AES-NI および PCLMULQDQ 命令を使用した場合、同じアルゴリズムで 1 バイトあたり 3.5 サイクルを達成したと報告しています。Shay Gueron と Vlad Krasnov は、第 3 世代 Intel プロセッサで 1 バイトあたり 2.47 サイクルを達成しました。OpenSSLおよびNSSライブラリ用の適切なパッチが用意されました。 [ 16 ^]

メッセージに対して認証と暗号化の両方を実行する必要がある場合、ソフトウェア実装では、これらの操作の実行をオーバーラップさせることで速度の向上を実現できます。操作をインターリーブすることで命令レベルの並列性を利用することで、パフォーマンスが向上します。このプロセスは関数ステッチングと呼ばれ、^[17]原理的には暗号化アルゴリズムの任意の組み合わせに適用できますが、GCM が特に適しています。Manley と Gregg ^[18]は、GCM で関数ステッチングを使用すると最適化が容易であることを示しています。彼らは、暗号化アルゴリズムの注釈付き C バージョンを受け取り、ターゲット プロセッサで適切に実行されるコードを生成するプログラム ジェネレーターを提示しています。

GCMは、並列処理が暗号化ハードウェアエンジンの効率的な使用に適していないため、組み込み業界では批判されてきました（たとえば、Silicon Labs）。その結果、GCMは、パフォーマンスに最も敏感なデバイスの一部で暗号化のパフォーマンスを低下させます。^[19] ChaCha20-Poly1305専用のハードウェアアクセラレータは、AESアクセラレータに比べて複雑ではありません。^[20]

著者らの声明によれば、GCMは特許に縛られていない。^[21]

GCMは具体的なセキュリティモデルで安全であることが証明されています。^[22]ランダムな順列と区別がつかないブロック暗号で使用すると安全ですが、セキュリティは同じ鍵で実行される暗号化ごとに一意の初期化ベクトルを選択することに依存します（ストリーム暗号攻撃を参照 ）。任意の鍵に対して、GCMは2 ³⁹ − 256ビットの平文（64 GiB）の暗号化に制限されています。NIST特別出版800-38D ^[5]には初期化ベクトルの選択に関するガイドラインが含まれています。

認証の強度は、すべての対称メッセージ認証コードと同様に、認証タグの長さに依存します。GCM で短い認証タグを使用することは推奨されません。タグのビット長 ( tで示される) は、セキュリティ パラメータです。一般に、t は、128、120、112、104、または 96 の 5 つの値のいずれかになります。特定のアプリケーションでは、t は64 または 32 になる場合がありますが、これら 2 つのタグ長を使用すると、入力データの長さとキーの有効期間が制限されます。 NIST SP 800-38D の付録 C には、これらの制約に関するガイダンスが記載されています (たとえば、t = 32で最大パケット サイズが 2 ¹⁰バイトの場合、認証復号化関数は 2 ^{11回を超えて呼び出すことはできません}。t = 64で最大パケット サイズが 2 ¹⁵バイトの場合、認証復号化関数は 2 ³²回を超えて呼び出すことはできません)。

他のメッセージ認証コードと同様に、攻撃者がtビットのタグをランダムに選択すると、与えられたデータに対して確率測度 2 ^{− t}で正しいことが期待されます。ただし、GCM を使用すると、攻撃者はnワード (暗号文の合計長と追加の認証データ (AAD) を加えた長さ)のタグをn倍の確率測度 2 ^{− t}で選択することで、成功の可能性を高めることができます。ただし、これらの最適なタグは、任意の大きさのtに対してアルゴリズムの生存測度1 − n ⋅2 ^{− t}によって依然として支配されることに留意する必要があります。さらに、GCM は非常に短いタグ長や非常に長いメッセージでの使用には適していません。

ファーガソンとサーリネンはそれぞれ独立して、攻撃者がGCM認証に対してセキュリティの下限を満たす最適な攻撃を実行する方法について説明しました。ファーガソンは、nがエンコード内のブロックの総数（GHASH関数への入力）を表す場合、およそn ⋅2 ^{− t}の確率で成功すると予想される標的型暗号文偽造を構築する方法があることを示しました。タグの長さtが128より短い場合、この攻撃で偽造が成功するたびに、後続の標的型偽造が成功する確率が高まり、ハッシュサブキー Hに関する情報が漏洩します。最終的には、Hが完全に侵害され、認証の保証が完全に失われる可能性があります。^[23]

この攻撃とは別に、攻撃者は認証された復号化への特定の入力に対して多くの異なるタグを体系的に推測し、その結果、そのうちの 1 つ (または複数) が有効であると判断される可能性を高める可能性があります。このため、GCM を実装するシステムまたはプロトコルは、各キーの検証試行の失敗回数を監視し、必要に応じて制限する必要があります。

Saarinen は GCM の弱い鍵について説明した^[24]。この研究は、多項式ハッシュベースの認証がどのように機能するかについて貴重な洞察を与えている。より正確には、この研究は、有効な GCM メッセージが与えられた場合に、n × 128ビット長のメッセージに対して約n ⋅2 ⁻¹²⁸の確率で機能する GCM メッセージを偽造する特定の方法について述べている。しかし、この研究は、以前に知られていたよりも効果的な攻撃を示しているわけではない。この論文の観察 1 の成功確率は、INDOCRYPT 2004 分析の補題 2 の成功確率と一致している ( w = 128、l = n × 128に設定)。Saarinen はまた、ソフィー・ジェルマン素数に基づく GCM の変形であるソフィー・ジェルマン・カウンター・モード(SGCM)についても説明した。

• 認証された暗号化
• ブロック暗号の動作モード
• AES-GCM-SIV

• GCM と GMAC を定義する NIST 特別出版物 SP800-38D
• RFC 4106: IPsec カプセル化セキュリティ ペイロード (ESP) におけるガロア/カウンター モード (GCM) の使用
• RFC 4543: IPsec ESP および AH におけるガロア メッセージ認証コード (GMAC) の使用
• RFC 5288: TLS 用 AES ガロア カウンター モード (GCM) 暗号スイート
• RFC 6367: トランスポート層セキュリティ (TLS) への Camellia 暗号スイートの追加
• IEEE 802.1AE – メディア アクセス制御 (MAC) セキュリティ
• IEEEストレージセキュリティワーキンググループはP1619.1標準を開発しました。
• INCITS T11 技術委員会は、ファイバー チャネル - セキュリティ プロトコル プロジェクトに取り組んでいます。
• セキュア RTP (SRTP) における AES-GCM および AES-CCM 認証暗号化

• ガロア/カウンタ動作モード (GCM)