Slid Pairs in Salsa20 and Trivium

The stream ciphers Salsa20 and Trivium are two of the finalists of the eSTREAM project which are in the final portfolio of new
promising stream ciphers. In this paper we show that initialization and
key-stream generation of these ciphers is slidable, i.e. one can find distinct
(Key, IV) pairs that produce identical (or closely related) key-streams.
There are 2256 and more then 239 such pairs in Salsa20 and Trivium
respectively. We write out and solve the non-linear equations which describe such related (Key, IV) pairs. This allows us to sample the space of
such related pairs efficiently as well as detect such pairs in large portions
of key-stream very efficiently. We show that Salsa20 does not have 256-bit
security if one considers general birthday and related key distinguishing
and key-recovery attacks.