Cryptology ePrint Archive: Report 2009/127

Side Channel Cube Attacks on Block Ciphers

Itai Dinur and Adi Shamir

Abstract: In this paper we formalize the notion of {\it leakage attacks} on iterated block ciphers, in which the attacker can find (via physical probing, power measurement, or any other type of side channel) one bit of information about the intermediate state of the encryption after each round. Since bits computed during the early rounds can be typically represented by low degree multivariate polynomials, cube attacks seem to be an ideal generic key recovery technique in these situations. However, the original cube attack requires extremely clean data, whereas the information provided by side channel attacks can be quite noisy. To address this problem, we develop a new variant of cube attack which can tolerate considerable levels of noise (affecting more than 11\% of the leaked bits in practical scenarios). Finally, we demonstrate our approach by describing efficient leakage attacks on two of the best known block ciphers, AES (requiring about $2^{35}$ time for full key recovery) and SERPENT (requiring about $2^{18}$ time for full key recovery).

Category / Keywords: secret-key cryptography /

Publication Info: Submitted to CHES 2009

Date: received 18 Mar 2009

Contact author: itaid at weizmann ac il

Available format(s): PDF | BibTeX Citation

Version: 20090320:140218 (All versions of this report)

Short URL: ia.cr/2009/127

Discussion forum: Show discussion | Start new discussion