Statistical Analysis of chi-square Attacks

概要

論文の詳細を見る
The χ^2-attack was originally proposed by Knudsen and Meier. This attack is one of the most effective attacks for RC6. The χ^2-attack can be used for both distinguishing attacks and for key recovery attacks. Although, up to the present, theoretical analysis of χ^2-attacks, especially the relation between a distinguishing attack and a key recovery attack, has not been discussed, the security against key recovery attacks has been often discussed by the results of distinguishing attacks. In this paper, we investigate the theoretical relation between the distinguishing attack and the key recovery attack, and prove one theorem to evaluate the exact security against the key recovery attacks by using the results of the distinguishing attack. Furthermore we propose two key recovery attacks against RC5-64 and implement them. Our best key recovery attack can analyze RC5-64 with 16 rounds by using 2^<125.23> plaintexts with a success probability of 30%. This result works faster than exhaustive key search. As far as the authors know, this is the best result of known plaintext attacks to RC5-64. We also apply our theory on our key recovery attacks and demonstrate the validity.
2003-05-01