The security of RC6 against asymmetric Chi-square test attack

概要

論文の詳細を見る
Knudsen and Meier applied the χ^2-attack to RC6. The χ^2-attack recovers a key by using high correlations measured by χ^2-value. The best χ^2-attacks to RC6 whose security is guaranteed theoretically works on 16-round RC6 with 192- and 256-bit key but just 8-round RC6 with 128-bit key, because it recovers keys of RC6 symmetrically, which requires a time complexity of #plaintexts ×2^<54> and a memory complexity of 2^<80> for recovering one key. In this paper, we improve the χ^2-attack to reduce the time complexity. We give the theorem that evaluates the success probability of the χ^2-attack on RC6 without using any experimental result. Our key recovery attack recovers keys asymmetrically, which requires a time complexity of #plaintexts ×2^<31> and a memory complexity of 2^<52> for recovering one key. As a result, our key recovery attack works on 16-round RC6 with 192- and 256-bit key and 12-round RC6 with 128-bit key. In the case both of 196- and 256-bit keys, our attack surprisingly reduces the time and memory complexity compared with that of the previous attack. We also demonstrate our theorem on RC6-8/4/8 and make sure of the accuracy by comparing our approximation with the experimental results.
一般社団法人情報処理学会の論文
2007-09-15