ブロック暗号アルゴリズムCLEFIAの11段96階差分攻撃の高速化

CLEFIA は 2007 年に SONY の白井らが提案したブロック暗号アルゴリズムである。ブロック長は 128 ビットであり、鍵長は 128、192、256 ビットがサポートされている。データ攪拌部の段数は鍵長によって異なり、鍵長が 128、192、256 ビットの場合それぞれ 18 段、22段、 26 段となっている。これまでに、 CLEFIA の 8 段目出力 128 ビット中の 64 ビットについては、その 96 階差分がゼロとなる特性が知られており、我々はこの特性を利用した CLEFIA の 11 段 96 階差分攻撃を報告している。この攻撃には選択平文数 298.3、暗号化計算量 2159 を要する。本稿では Ferguson らが提案した部分和法を用いて、解読時の中間データの mod2 頻度分布表を逐次導出することにより攻撃に要する計算量を削減する。さらに攻撃方程式の計算過程において、繰り返し計算ループの入れ子構造を採用し、入れ子の順序を適切に設定することにより計算量を削減し、 11 段 96 階差分攻撃を高速化できることを報告する。結果としては従来よりも 251.4 倍高速化でき、選択平文数 298.3、平均暗号化計算量 2107.6 で攻撃できることを示す。

CLEFIA is a block cipher proposed by Shirai of SONY et al. in 2007. Its block size is 128 bits and its key size is 128, 192, or 256 bits. The number of round is depend on a key size, viz., it is 18, 22, or 26 rounds for 128, 192, or 256 bits of a key size, respectively. Such a characteristic of CLEFIA have been known that the 96th-order differential of 64 bits out of 128 bits of the 8th-round's output is zero. With this characteristic, we reported the 96th-order differential attack on CLEFIA of 11 rounds. This attack requires 298.3 of plain text and 2159 of computational complexity. In this paper, we reduce this computational complexity by applying a partial sum technique proposed by Ferguson et al.. With the partial sum technique, we sequentially derive frequency distribution tables modulo 2 of intermediate data of cryptanalysis. We also reduce the complexity by introducing a nesting structure of iterative computations. As a result, we reduce the complexity to 2107.6.