GCM (Galois/Counter Mode of Operation) とはMcGrewとViegaによって提案され た共通鍵認証暗号化モードである。共通鍵認証暗号化モードとは送信者と受信者 のみが知っている値(共通鍵) を用いて認証、すなわち第三者によるデータの改 ざんやなりすましを検出できる機能と、暗号化、すなわちデータを第三者から秘 匿する機能を合わせ持 つ暗号技術である。また、GCMはNISTの推奨方式に選ばれ て幅広く使われており、その安全性はMcGrewとViegaによって論じられてい る。
本発表では、McGrewとViegaが行った安全性の証明で用いている補題の誤りを指 摘し、正しい補題を示す。この補題はGCMがカウンタ衝突 を起こす確率を述べた 補題である。カウンタ衝突が起きた場合、暗号化したいデータの情報が漏れるた め、GCMの安全性を証明するためにはカウンタ 衝突が起きる確率が十分小さいこ とを示す必要がある。本発表ではカウンタ衝突が起きる確率が従来まで考えられ ていた値より大きいことを示し、正し い確率を導出する。
これによりGCMの寿命、つまり共通鍵を交換するまでの期間が従来信じられてい た期間より短いことが分かり、GCMを使用する上で注意が必要であ ることが明ら かになった。