Key Recovery with Probabilistic Neutral Bits.

Abstract
The initialization function of a stream cipher maps the key and the initialization vector IV to the initial state, and the automaton produces thereafter keystream bits using an output and update function. The initialization should have good mixing properties with regard to key and IV bits. If mixing is not complete, a few key bits may have less influence on the value of output bits than others, which allows to separate probabilistic neutral key bits from essential key bits. In a reduced complexity key recovery one considers approximations of initialization that focus on determining essential key bits. As the initialization is often a complex process, probabilistic neutral key bits may not be detected directly, but only show up in a well chosen intermediate computation. This is exploited in chosen IV key recovery attacks in two directions. A key recovery faster than exhaustive search of the eSTREAM candidate Salsa20 reduced to 8 rounds is described that is based on a 4 round truncated differential together with an approximate backwards computation that exploits the existence of probabilistic neutral key bits. In a different direction, a recent framework for chosen IV statistical distinguishing analysis of stream ciphers is exploited to provide new methods for key recovery attacks. This rests on a polynomial description of the output bits as a function of the key and the IV. It is demonstrated that a deviation of the algebraic normal form from random can be exploited to derive information on the key faster than exhaustive key search. This elaborates on suitable approximations of the polynomial description and on probabilistic neutral key bits. As applications, a reduced complexity key recovery for Trivium with IV initialization reduced to 672 of its 1152 iterations, and a reduced complexity key recovery for Grain-128 with IV initialization reduced to 180 of its 256 iterations are given. These methods are not capable to provide key recovery faster than exhaustive key search of the eSTREAM candidates Trivium and Grain-128 with full initialization.
(This is joint work with Simon Fischer and Shahram Khazaei.)

TimeInfo: Arrival on Sunday, leave on Thursday morning
Neutralbits.pdf

"MEIER Willi" is mentioned on: Home | Participants