認証暗号化モードGCMの理論的なところの解説

ブロック暗号（代表的なのはAES）を使い、暗号化と認証を同時に行うものです。
以下の参考文書をベースに。

参考文書

[1] https://www.ieice-hbkb.org/files/01/01gun_03hen_03.pdf
3-1 暗号化モード
3-3 認証暗号化モード

暗号化モード

ブロック暗号は固定長のブロックを暗号化するもので、AESであれば128ビットです。つまり、AESでは128ビット（16バイト）の暗号化しかできません。
それ以上のサイズのメッセージをどうやって暗号化するかは、いくつか方法があり、暗号化モードと呼ばれます。

一番簡単なのはECBモードで、メッセージ $M$ を16バイトのブロックに分割し、$M[i] (i = 1,\cdots,n)$ それぞれを個別に暗号化します。

C[i] = E_K(M[i])

$E_K$ は秘密鍵Kの暗号化関数です。数学的な関数ですが、例えばオープンソースの tiny-AES-c (https://github.com/kokke/tiny-AES-c) であれば、以下のようになります。
（$E_K$ はAESである必要はありませんが、ここではAESを想定します）

// aes.h
void AES_init_ctx(struct AES_ctx* ctx, const uint8_t* key);
void AES_ECB_encrypt(const struct AES_ctx* ctx, uint8_t* buf);

struct AES_ctx ctx;
void E_K(unsigned char *K, unsigned char *M)
{
    AES_init_ctx(&ctx, K);
    AES_ECB_encrypt(&ctx, M);
}

GCMでは、CTRモードを使います。
（CTRモードの詳細は補足を参照）

$I[0] = N0^{31}1$ を初期値として、カウンタ系列 $I[i] = \text{inc}_{32}(I[i-1])$ を生成します。ここで、$N$ は96ビットの初期化ベクトル $IV$ (Initialization Vector)で、それに31ビットの0と1ビットの1をつなげて128ビットにします。96ビットでなくてもよいですが、ブロック長と一致する方がよいようです。

$\text{inc}_{32}$ は、128ビットのうち下位32ビットだけインクリメントさせるもので、イメージとしては

void inc32(unsigned char I[16])
{
    unsigned long *ctr = &I[12];
    *ctr += 1;
}

このカウンタ系列を暗号化して、メッセージブロックとのXORを取ることで、暗号文を生成します

S[i] = E_K(I[i])\ (i = 1,2,\cdots,m)

C[i] = \left\{
\begin{array}{}
S[i] \oplus M[i] \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (i = 1,2,\cdots,m-1)\\
\text{msb}_l(S[m]) \oplus M[m] \ \ (i = m)
\end{array}
\right.

tiny-AES-cはCTRモードに対応しています。

void AES_CTR_xcrypt_buffer(struct AES_ctx* ctx, uint8_t* buf, size_t length);

暗号化、復号とも同じ関数を使います。lengthにメッセージのバイト数を渡すと、16バイトごとにカウンタをインクリメントしながら暗号化します。ただし、$\text{inc}_{32}$ ではないようなので、ひとつの $IV$ から $2^{32} = 4294967296$ 回以上暗号化する可能性がある場合は注意が必要です。

メッセージ認証コード

暗号化が機密性を保持するためのものに対し、メッセージ認証はなりすましや改ざんを防ぐためのものです。認証のみの方式もありますが、その場合は平文をそのまま送信することになります。機密性はありませんが、本当にその人からのメッセージかの確認ができます。
出力される認証コードは16バイトのブロックで、MACやタグとも言います。

ハッシュ鍵 $L$ とのガロア体 $GF(2^{128})$ 上のかけ算で、ハッシュ関数 $\text{GHASH}_L$ を定義します。入力 $X[i]\ (i=1,2,\cdots,n)$ はそれぞれが16バイトのブロックで、

\begin{align}
Y[0] &= 0^{128} = \sum_{i=0}^{127} 0x^i \\
Y[i] &= (Y[i-1] \oplus X[i]) \cdot L \ (i=1,2,\cdots,n)
\end{align}

として、$Y[n]$ が出力（ハッシュ値）になります。

void GHASH(unsigned char *L, unsigned char *X, unsigned char *Y, int blockNum)
{
    memset(Y, 0, 16);                // Y[0] = 0^{128}
    for (int i = 0; i < blockNum; i++)
    {
        GF2_128_add(Y, &X[16*i], Y); // Y[i-1] + X
        GF2_128_multiply(Y, L, Y);   // (Y[i-1] + X)・L
    }
}

$L$ は $GF(2^{128})$ の $0$ の暗号化により生成します。

L = E_K(0)

（ガロア体については補足を参照）

認証コード $T$ は、

S = \text{GHASH}_L(A\ ||\ 0^{\nu}\ ||\ C\ ||\ 0^u\ ||\ [|A|]_{64}\ ||\ [|C|]_{64}) \\
T = E_K(I[0]) \oplus S

$0^{\nu}, 0^u$ は、$A,C$ が128ビットの倍数でないときのパディングです。$||$ はビット列の連結、$[n]_{64}$ は数値 $n$ を64桁の2進数で表したものです。

$A$ はadditional authenticated data(AAD)で、なくても構いません。その場合は、

S = \text{GHASH}_L(\ C\ ||\ 0^u\ ||\ [0]_{64}\ ||\ [|C|]_{64}) \\

$A$ がなくて $|C|$ が128の倍数のときは、

S = \text{GHASH}_L(\ C\ ||\ [|C|]_{128})

ただし、$|C| < 2^{64}$ である必要があります。
最後の128ビットは、AADと暗号文のビット数を格納するもので、暗号文とそのサイズをハッシュ化するということです。例えば $|C| = $ 8ブロック = 512ビットの場合は

[|C|]_{64} = 00 \cdots 0200

となります。ビッグエンディアンであることに注意してください。

$C[i]$ と $T$ を求めれば、認証暗号化のプロセスは完了です。
受信者は、受信した認証コードと暗号文から計算した認証コードが一致するかで、なりすましかどうかを判別できます。

サンプルプログラム

struct AES_ctx ecb_ctx, ctr_ctx;

void GCM_init(unsigned char *K, unsigned char *IV)
{
    AES_init_ctx(&ecb_ctx, K);

    memcpy(I, IV, 16);
    I[15] = 1;                        // I[0] = N 0^{32}1

    memcpy(EK_I0, I, 16);
    AES_ECB_encrypt(&ecb_ctx, EK_I0); // E_K(I[0])

    I[15] = 2;
    AES_init_ctx_iv(&ctr_ctx, K, I);  // I[1] = inc_32(I[0])

    memset(L, 0, 16);
    AES_ECB_encrypt(&ecb_ctx, L);     // L = E_K(0)
}

void GCM_authenticated_encrypt(unsigned char *M, unsigned char *C, unsigned char *T, int Mlen)
{
    memcpy(C, M, Mlen);
    AES_CTR_xcrypt_buffer(&ctr_ctx, C, Mlen);

    unsigned long lenC = Mlen*8;
    C[Mlen + 15] = (unsigned char)(lenC & 0xff); lenC >>= 8;
    C[Mlen + 14] = (unsigned char)(lenC & 0xff); lenC >>= 8;
    C[Mlen + 13] = (unsigned char)(lenC & 0xff); lenC >>= 8;
    C[Mlen + 12] = (unsigned char)(lenC & 0xff);

    GHASH(L, C, S, Mlen/16 + 1);
    GF2_128_add(S, EK_I0, T);
}

void GCM_authenticated_decrypt(unsigned char* C, unsigned char* M, unsigned char* T, int Mlen)
{
    memcpy(M, C, Mlen);
    AES_CTR_xcrypt_buffer(&ctr_ctx, M, Mlen);

    unsigned long lenC = Mlen*8;
    C[Mlen + 15] = (unsigned char)(lenC & 0xff); lenC >>= 8;
    C[Mlen + 14] = (unsigned char)(lenC & 0xff); lenC >>= 8;
    C[Mlen + 13] = (unsigned char)(lenC & 0xff); lenC >>= 8;
    C[Mlen + 12] = (unsigned char)(lenC & 0xff);

    GHASH(L, C, S, Mlen/16 + 1);
    GF2_128_add(S, EK_I0, T);
}

encryptとdecryptはほぼ同じですが、GHASHに渡すCが第二引数(encrypt)か第一引数(decrypt)かという違いがあります。そのため、共通の関数にするのは難しいと思われます。

テスト

AESの鍵を128ビットとして、以下のテストデータでテストします。
https://csrc.nist.gov/Projects/cryptographic-standards-and-guidelines/example-values
Block Cipher Modes
GCM-AES

GCM-AES128
Example #2
Taglen = 128
AADlen = 0
PTlen = 512

// 秘密鍵
unsigned char K[16] =
{
    0xFE, 0xFF, 0xE9, 0x92, 0x86, 0x65, 0x73, 0x1C, 0x6D, 0x6A, 0x8F, 0x94, 0x67, 0x30, 0x83, 0x08,
};

// 初期化ベクトル
unsigned char IV[16] =
{
    0xCA, 0xFE, 0xBA, 0xBE, 0xFA, 0xCE, 0xDB, 0xAD, 0xDE, 0xCA, 0xF8, 0x88,
    0x00, 0x00, 0x00, 0x00,
};

$IV$ の前半12バイトはN(nonce)、後半4バイトはCTRモードのカウンタです。

// メッセージ
unsigned char M[64] =
{
    0xD9, 0x31, 0x32, 0x25, 0xF8, 0x84, 0x06, 0xE5, 0xA5, 0x59, 0x09, 0xC5, 0xAF, 0xF5, 0x26, 0x9A,
    0x86, 0xA7, 0xA9, 0x53, 0x15, 0x34, 0xF7, 0xDA, 0x2E, 0x4C, 0x30, 0x3D, 0x8A, 0x31, 0x8A, 0x72,
    0x1C, 0x3C, 0x0C, 0x95, 0x95, 0x68, 0x09, 0x53, 0x2F, 0xCF, 0x0E, 0x24, 0x49, 0xA6, 0xB5, 0x25,
    0xB1, 0x6A, 0xED, 0xF5, 0xAA, 0x0D, 0xE6, 0x57, 0xBA, 0x63, 0x7B, 0x39, 0x1A, 0xAF, 0xD2, 0x55,
};

// 暗号文
unsigned char C[64 + 16];
unsigned char C_exp[64] =
{
    0x42, 0x83, 0x1E, 0xC2, 0x21, 0x77, 0x74, 0x24, 0x4B, 0x72, 0x21, 0xB7, 0x84, 0xD0, 0xD4, 0x9C, 
    0xE3, 0xAA, 0x21, 0x2F, 0x2C, 0x02, 0xA4, 0xE0, 0x35, 0xC1, 0x7E, 0x23, 0x29, 0xAC, 0xA1, 0x2E, 
    0x21, 0xD5, 0x14, 0xB2, 0x54, 0x66, 0x93, 0x1C, 0x7D, 0x8F, 0x6A, 0x5A, 0xAC, 0x84, 0xAA, 0x05, 
    0x1B, 0xA3, 0x0B, 0x39, 0x6A, 0x0A, 0xAC, 0x97, 0x3D, 0x58, 0xE0, 0x91, 0x47, 0x3F, 0x59, 0x85, 
};

// メッセージ認証コード
unsigned char T[16];
unsigned char T_exp[16] =
{
    0x4D, 0x5C, 0x2A, 0xF3, 0x27, 0xCD, 0x64, 0xA6, 0x2C, 0xF3, 0x5A, 0xBD, 0x2B, 0xA6, 0xFA, 0xB4, 
};

// ハッシュ鍵
extern unsigned char L[16];
unsigned char L_exp[16] =
{
    0xB8, 0x3B, 0x53, 0x37, 0x08, 0xBF, 0x53, 0x5D, 0x0A, 0xA6, 0xE5, 0x29, 0x80, 0xD5, 0x3B, 0x78, 
};

TEST(GCM_AES128, Example2_encrypt)
{
    GCM_init(K, IV);
    EXPECT_EQ(memcmp(L, L_exp, 16), 0);

    memcpy(C, M, sizeof(M));
    GCM_authenticated_encrypt(M, C, T, sizeof(M));
    EXPECT_EQ(memcmp(C, C_exp, sizeof(M)), 0);
    EXPECT_EQ(memcmp(T, T_exp, 16), 0);
}

TEST(GCM_AES128, Example2_decrypt)
{
    unsigned char M_dec[64], T_dec[16];

    GCM_init(K, IV);

    memcpy(C, M, sizeof(M));
    memset(&C[64], 0, 16);

    GCM_authenticated_decrypt(C, M_dec, T_dec, sizeof(M));
    EXPECT_EQ(memcmp(M_dec, M, sizeof(M)), 0);
    EXPECT_EQ(memcmp(T_dec, T, 16), 0);
}

実行結果

[==========] Running 2 tests from 1 test case.
[----------] Global test environment set-up.
[----------] 2 tests from GCM_AES128
[ RUN ] GCM_AES128.Example2_encrypt
[ OK ] GCM_AES128.Example2_encrypt (1 ms)
[ RUN ] GCM_AES128.Example2_decrypt
[ OK ] GCM_AES128.Example2_decrypt (1 ms)
[----------] 2 tests from GCM_AES128 (4 ms total)

[----------] Global test environment tear-down
[==========] 2 tests from 1 test case ran. (6 ms total)
[ PASSED ] 2 tests.

GCMの安全性

GCM自体の安全性というよりは、運用の問題になりますが、初期化ベクトル $IV$ を繰り返し使用してはならないとされています。もし繰り返し使うと、、、

$\text{GHASH}_L$ を以下のように書き直し、

\begin{align}
Y[m] &= C[m] \cdot L + C[m-1] \cdot L^2 + \cdots + C[1] \cdot L^m \\
&= \sum_{i=1}^m C_{m-i+1} \cdot L^i
\end{align}

これを（$GF(2)$ ではなく）$GF(2^{128})$ 上の多項式 $f(x) = \sum C_{m-i+1} x^i$ の値 $f(L)$ とみなします。
同じ $IV$ で異なるメッセージ $M^{(1)}, M^{(2)}$ を暗号化し、その暗号文 $C^{(1)}, C^{(2)}$ と認証コード $T^{(1)}, T^{(2)}$ が攻撃者に取得されたとします。すると、

\begin{align}
T^{(1)} \oplus T^{(2)} &= (E_K(I[0]) \oplus S^{(1)}) \oplus (E_K(I[0]) \oplus S^{(2)}) \\
&= S^{(1)} \oplus S^{(2)} \\
&= \sum C_i^{(1)} L^i + \sum C_i^{(2)} L^i 
\end{align}

左辺は既知の値、右辺は既知の多項式の $L$ における値です。つまり、$L$ は $GF(2^{128})$ 上の多項式の根ということになります。$GF(2^{128})$ 上の多項式は、ブロック数を $m$ として $GF((2^{128})^m) = GF(2^{128m})$ と同型なので、$GF(2)$ 上の $128m$ 次の多項式の根を求めることに帰着します。$L$ がバレるということは、セキュリティが失われたことを意味します。

【参考】
Authentication Failures in NIST version of GCM, Natl. Inst. Stand. Technol.
3. A forbidden attack with repeated IV

補足

暗号化モード

ECBモード

メッセージ $M$ を16バイトのブロックに分割し、$M[i] (i = 1,\cdots,n)$ それぞれを個別に暗号化します。

C[i] = E_K(M[i])

復号は、復号関数 $D_K$ を用いて

M[i] = D_K(C[i])

ECBモードでは、メッセージのバイト数は16の倍数である必要があります。
また、
$$M[i] = M[j] \iff C[i] = C[j]$$
となるので、暗号ブロックが同じなら元のメッセージブロックも同じだということになります。メッセージの部分情報が漏洩するということであり、安全性が低いと言われます。

CBCモード

ECBモードと同様にメッセージ $M$ を16バイトのブロックに分割し、直前の暗号ブロックを組み合わせて暗号化します。

C[i] = \left\{
\begin{array}{}
E_K(M[1]\oplus IV) \\
E_K(M[i]\oplus C[i-1])
\end{array}
\right.

$IV$ は（AESなら）16バイトの初期化ベクトルです。
復号は、

M[i] = \left\{
\begin{array}{}
D_K(C[1])\oplus IV) \\
D_K(C[i])\oplus C[i-1]
\end{array}
\right.

実際、$D_K(E_K(X)) = X$ であることに注意すると、

\begin{align}
D_K(C[1]) \oplus IV &= D_K(E_K(M[1]) \oplus IV) \oplus IV \\
&= M[1] \oplus IV \oplus IV \\
&= M[1]
\end{align}

\begin{align}
D_K(C[i]) \oplus C[i-1] &= D_K(E_K(M[i] \oplus C[i-1])) \oplus C[i-1] \\
&= M[i] \oplus C[i-1] \oplus C[i-1] \\
&= M[i]
\end{align}

$IV$ は送信者と共有する必要があります。
CBCモードでは、$M[i] = M[j]$ であっても、$C[i] = C[j]$ にはならないので、ECBモードのような漏洩は起きません。

CTRモード

メッセージブロックと同じ数のカウンタ系列を生成し、その組み合わせで暗号化するモードです。適当な初期値から16バイトのブロック $\text{ctr}_1, \text{ctr}_2, \cdots$ を生成し、
$$
S[i] = E_K(\text{ctr}_i)\ (i = 1,2,\cdots,m)
$$

C[i] = \left\{
\begin{array}{}
S[i] \oplus M[i] \\
\text{msb}_l(S[m]) \oplus M[m]
\end{array}
\right.

最後のブロックが128ビット未満$(|M[m]| = l < 128)$の場合は、$S[m]$ の上位 $l$ ビットとのXORを取ります。

面白いのは、メッセージ自体の暗号化はしないということです。そのため、受信者も復号関数 $D_K$ を使う必要はなく、送信者と同じ手順で復号できます。
$$S[i] = E_K(\text{ctr}_i)\ (i = 1,2,\cdots,m)$$

M[i] = \left\{
\begin{array}{}
S[i] \oplus C[i] \\
\text{msb}_l(S[m]) \oplus C[m]
\end{array}
\right.

実際、

\begin{align}
S[i] \oplus C[i] &= S[i] \oplus (S[i] \oplus M[i]) \\
&= (S[i] \oplus S[i]) \oplus M[i] \\
&= M[i]
\end{align}

$C$ と $M$ を入れ替えると、暗号化の式になることがわかると思います。カウンタ系列 $\text{ctr}_i$ は送信者と共有する必要があります。

ガロア体について

ガロア体（有限体）とは、実数のように足し算とかけ算ができて、要素数が有限のものです。最小のガロア体は $GF(2) = \lbrace 0,1 \rbrace$ で、$1 + 1 = 0$ になります。その次に小さなガロア体は $GF(3)$ で、$1 + 1 + 1 = 0$ になります。その次は $GF(4)$ ですが、これは $GF(2^2)$ なので、$1 + 1 = 0$ です。

$GF(2^{128})$ は $GF(4)$ をさらに拡大したもので、足し算だけに注目すれば、$GF(2)$ 上の128次元のベクトル空間です。かけ算に注目すると巡回群になります。つまり、$1$ の $(2^{128}-1)$ 乗根を $\alpha$ とおくと、$GF(2^{128}) = \lbrace 0, 1, \alpha, \cdots, \alpha^{2^{128}-2} \rbrace$ と表すこともできます。
また、$GF(2)$ を係数に持つ多項式（正確には、128次の既約多項式を法とする剰余類）で表すことができます。

a = \sum_{i=0}^{127} a_i x^i\ (a_i = 0,1)

足し算とかけ算を扱えるので、多項式で考えることが多いと思います。

ちなみに、多項式で表せるというのは、任意の $a \in GF(2^{128})$ に対して $a \cdot b \equiv 1$ となる多項式 $b = \sum b_i x^i \in GF(2^{128})$ が存在するということで、

• 既約多項式から生成されるイデアルは極大イデアルであること
• 極大イデアルを法とする剰余類(環)は体であること

から導かれます。

※もう少し正確に言うと、上記は「多項式 $\implies$ ガロア体」を言っているだけなので、その逆も言う必要があります。つまり、多項式で表せないガロア体は存在しないことを言う必要があります。これは、要素数が同じガロア体はすべて同型であることから示されます。

足し算は、

\begin{align}
a + b &= \sum_{i=0}^{127} a_i x^i + \sum_{i=0}^{127} b_i x^i \\
&= \sum_{i=0}^{127} (a_i + b_i)x^i \\
&= a \oplus b
\end{align}

ここで、$\oplus$ はビット単位のXORです。$1 + 1 = 0$ なので、このようになります。

void GF2_128_add(unsigned char *a, unsigned char *b, unsigned char *c)
{
    int i;
    for (i = 0; i < 16; i++)
    {
        c[i] = a[i] ^ b[i];
    }    
}

$x^{128} + x^7 + x^2 + x + 1$ を既約多項式に取ると、$x$ とのかけ算は

\begin{align}
a \cdot x &= \left(\sum_{i=0}^{127} a_i x^i\right) \cdot x \\
&= \sum_{i=0}^{126} a_i x^{i+1} + a_{127}x^{128} \\
&= \sum_{i=1}^{127} a_{i-1} x^i + a_{127}(1 + x + x^2 + x^7) \\
&= (a >> 1) \oplus a_{127}(1 + x + x^2 + x^7)
\end{align}

ここで、$$x^{128} = x^{128} + (x^7 + x^2 + x + 1) + (x^7 + x^2 + x + 1) \equiv x^7 + x^2 + x + 1$$ を利用しています。
ビット列を多項式として解釈するときの規約は、GCMではリトルエンディアンです。つまり、多項式 $a$ のビット列は ($a_0, a_1,\cdots,a_{127})$ となります。そうすると、$a_{127} = 0$ のときは、単なる1ビットのシフト$(a>>1)$になります。$a_{127} = 1$ のときは、それに加えて $x^7 + x^2 + x + 1$ との足し算$(\oplus (1 + x + x^2 + x^7))$ になります。

void GF2_128_multiply_x(unsigned char* a)
{
    int i;
    unsigned char a_127 = (a[15] & 0x01);

    // a >> 1
    for (i = 15; i > 0; i--)
    {
        a[i] = (a[i] >> 1) | (a[i - 1] << 7);
    }
    a[0] = a[0] >> 1;

    if (a_127 == 1)
    {
        a[0] ^= 0xe1; // 1 + x + x^2 + x^7
    }
}

任意の値のかけ算については、$b = \sum b_i x^i$ の係数が1の項を $\lbrace b_{i_1}, b_{i_2} \cdots \rbrace$ とおくと

a \cdot b = ax^{i_1} + ax^{i_2} + \cdots

$a \cdot x^{j+1} = (a \cdot x^j) \cdot x$ であることから、$a \cdot x, a \cdot x^2, \cdots$ を順番に計算し、$b$ の係数が1のときだけ $a \cdot x^j$ を結果に加算すればよいことになります。

void GF2_128_multiply(unsigned char* a, unsigned char* b, unsigned char* c)
{
    int i, j;
    static unsigned char a_xj[16];

    memcpy(a_xj, a, 16); // ax^0 = a
    memset(c, 0, 16);    // c = 0

    for (i = 0; i < 16; i++)
    {
        for (j = 7; j >= 0; j--)
        {
            if (((b[i] >> j) & 0x01) == 1) // b^j == 1
            {
                GF2_128_add(c, a_xj, c);   // c += ax^j
            }
            GF2_128_multiply_x(a_xj);      // ax^{j+1} = (ax^j)・x
        }
    }
}