Multiset Collision Attacks on Reduced-Round SNOW 3G and SNOW 3G (+)

The stream cipher SNOW 3G designed in 2006 by ETSI/SA-GE is a base algorithm for the second set of 3GPP confidentiality and integrity algorithms. In this paper we study the resynchronization mechanism of SNOW 3G and of a similar cipher SNOW 3G ⊕  using multiset collision attacks. For SNOW 3G we show a simple 13-round multiset distinguisher with complexity of 28 steps. We show full key recovery chosen IV resynchronization attacks for up to 18 out of 33 initialization rounds of SNOW3G ⊕  with a complexity of 257 to generate the data and 253 steps of analysis.