利用旁道資訊對RC6進行的代數攻擊分析

Abstract

本篇論文詳述一種新的CCA(Chosen Ciphertext Attack)攻擊法，可利用旁道攻擊(Side Channel Attack)所獲得的資訊，建立減法差分代數式並以SAT Solver工具求解。經學理分析驗證，本論文所提方法可在2^43的資料量與2^78的計算複雜度內成功破譯RC6最末回合之加密密鑰(round key)，並利用末回合密鑰還原對應的漂白密鑰值(whitening key)，其計算複雜度僅約2^32。另外，本論文亦在不同強度之資訊假設（又稱oracle）下，分析攻擊所需資料量與計算複雜度之間的trade-off關係。

This paper details a novel chosen ciphertext attack on RC6 cipher which has been chosen as one of the finalists for AES competition (March 1999) and has been declared to be resistant to all known cryptanalysis since then. In this paper, it’ll be shown that with the aid of side channel information and algebraic analysis the attacker can recover all round keys and whitening keys by using at most 2^43 ciphertext pairs and 2^78 computations. Moreover, this paper also provides theoretic analysis of the trade-off between different oracles and the general assumption (without any side channel information given), and then proves that the distribution of round key candidates may not be uniformly random.