ハッシュ関数Lesamnta-256における差分攻撃耐性の評価について

摘要

次世代ハッシュ関数SHA-3の候補であるLesamnta-256を取り上げ、その構成要素である撹拝関数と鍵スケジュール関数の差分特性を解析し、差分攻撃耐性を検討する。撹拝関数は4系統一般化Feistel構造32段で構成される。各段における非線形関数Fは64ビット入出力である4層のAES型SPN構造をなす。S層は最大差分確率2~(-6)である8ビットS-boxの8並列構成であるが、鍵加算は1層目に存在するだけである。提案者は、4層全てに独立鍵加算が存在するとしてアクティブS-box数を数え、差分攻撃耐性を評価しているが、本稿では実際のF関数構造に即した評価を目指す。F関数の2層分を等価変形し16ビット入出力の拡大S-box（XS）を使えば、F関数は2層のSPN構造で表すことができる。XSの最大差分確率は、2~(-11.415)であり、この値は全ての層に独立鍵加算があるとしてアクティブS-box数で評価した最大差分特性確率2~(-18)より遥かに大きい。さらにHongらの手法で求めた鍵平均最大差分確率の上界2~(-12)よりも大きい。また、摸拝関数全体に対しトランケーション評価を行い、少なくとも15個のアクティブF関数が有ることが解った。これによりダ関数の最大差分確率が2~(-256/15)＝2~(-17.067)以下であれば、256ビット程度の安全性を満たすと言える。最後に鍵スケジュール関数については差分解読に対して安全であることを示す。%We focus on the cryptographic hash algorithm Lesamnta-256, which is one of the candidates for the new hash algorithm SHA-3. Lesamnta-256 consists of the Merkle-Damgard iteration of a compression function. The compression function consists of a mixing function and a key scheduling function. The mixing function consists of the 32 rounds of the four-way generalized Feistel structure. There is a nonlinear function F with 64-bit input/output on each round, which consists of the 4 steps of AES type of SPN structure. A subkey is XORed only at the first step of SPN. We analyze the security of these components of Lesamnta as is, although the designers analyzed its security by assuming that the subkey is XORed at every step of SPN. We show that the 2 steps of SPN referred to as XS have the maximum differential probability 2~(11.415). This probability is greater than both of the differential characteristic probability 2~(-18) and the differential probability 2~(-12) derived under the independent subkey assumption. On the strength of whole compression function, we show that there are at least 15 active F functions in the mixing function. As the input bit width of the mixing function is 256, we can say that it is secure against differential attack if the maximum differential probability of F function is less than 2~(-256/15) = 2~(-17.067). Finally we show that the key scheduling function is secure against differential cryptanalysis.