Combining Algebraic and Side-Channel Cryptanalysis against Block Ciphers
Mathieu Renauld, François‐Xavier Standaert · 2009
This paper introduces a new type of cryptanalysis against block ciphers, denoted as algebraic side-channel attacks. In these attacks, we first write the target block cipher as a system of low degree equations. But since directly solving this system is generally hard, we additionally provide it with physical information. As a consequence, the algebraic cryptanalysis that was previously conjectured can be experimented and turns out to be very efficient to break block ciphers in practice. The proposed attacks differ from most previously known side-channel attacks in a number of interesting aspects. Namely they have a significantly reduced data complexity, the possibility to exploit the information of all the cipher rounds in an unknown plaintext/ciphertext scenario and different requirements for countermeasures. As an illustration, we apply them to the implementations of two block ciphers using a single leakage trace and discuss their specificities. 1