Algebraic side channel attack (ASCA) on stream ciphers

Abstract

Stream ciphers are known to have less complex hardware design and are generally faster than the block ciphers. Their employment is necessitated in systems where buffering is limited and bits must be processed immediately upon arrival or when data comes in unknown lengths like in wireless communication. Till the advent of algebraic attacks on stream ciphers, a decade and a half ago, linear feedback shift register (LFSR) based stream ciphers were quite common due to their efficient implementation. However, later years saw a host of new stream ciphers based on nonlinear feedback shift registers (NLFSR), which were highly resistant against traditional algebraic cryptanalysis. At present the success of algebraic attacks against stream ciphers is only limited to lightweight stream ciphers or reduced variants of popular stream ciphers. Side Channel Analysis (SCA) being an implementation attack, requires access to the hardware implementation of the target stream cipher to capture side channel leakages associated with internal processing. However to find exact secret key or internal state, a handsome quantity of leakage information is needed. In contrast to algebraic attacks, research work on SCA against stream ciphers has been less frequent but more successful. Combining two cryptanalysis techniques can pay dividends not only in the form of achieving better attack complexities and facilitating exploitation of new vulnerabilities, but also lowering the effect of individual weaknesses of attack techniques. Algebraic attacks and SCA can both be strong candidates for such combination. Rather they are already being applied against block ciphers in unison for quite some time now. However no published work as of this writing can be found on combining algebraic cryptanalysis and SCA against stream ciphers. In this work we propose to combine algebraic attacks with SCA, on stream ciphers, in a manner that reduces overall attack complexity/ difficulty as compared to isolated application of the two constituent attacks. This combination attack, termed as Algebraic Side Channel Attack (ASCA), utilize whatever side channel leakage is available from the target stream cipher’s implementation in limited time exposure and converts it into algebraic equations. These SCA equations are added into the system of multivariate polynomial equations obtained from algebraic attack technique. Union of these equation sets, can then be resolved through any mathematical method/ tool, to find the unknown variables, i.e., either secret key or internal state of the stream cipher. Stream ciphers of today, which mostly rely on nonlinearity by design to make them extremely immune to algebraic cryptanalysis, can also fall prey to ASCA. To demonstrate this, we successfully attack Crypto-1, Bivium-B, Trivium and Grain stream ciphers using our proposed technique in 0.158, 11.531, 21.54 and 28.25 seconds respectively.