SOSEMANUK

SOSEMANUK is a software-efficient (profile 1), synchronous stream cipher proposed by Berbain et al. The cipher has a variable key length, ranging from 128 to 256 bits, and takes an initial value (IV) of 128 bits in length. However, for any key length the cipher is only claimed to offer 128-bit security. SOSEMANUK uses similar design principles to the stream cipher SNOW 2.0 and block cipher SERPENT. The design of SOSEMANUK aims to fix some potential structural weaknesses of SNOW 2.0, while providing better performance by decreasing the size of the internal state.

As with the stream cipher SNOW 2.0, SOSEMANUK has two main components: a linear feedback register (LFSR) and a finite state machine (FSM). The LFSR operates on 32-bit words and has length 10; at every clock a new 32-bit word is computed. The FSM has two 32-bit memory registers: at each step the FSM takes as input words from the LFSR, updates the memory registers and produces a 32-bit output. On every four consecutive output words from the FSM an output transformation, based on the block cipher SERPENT, is applied. The resulting four 32-bit output words are XOR-ed with four outputs from the LFSR to produce four 32-bit words of keystream.

Regarding its performance in software, SOSEMANUK can encrypt long data streams at 5.60 cycles/byte on Pentium M and at 4.07 cycles/byte on AMD Athlon 64 X2. For more information about eSTREAM ciphers performance in software, refer to the eSTREAM testing framework page. For a more extensive comparison with many other stream ciphers on several different architectures, refer to the eBACS stream cipher software timings page maintained by D. Bernstein.

Analysis

SOSEMANUK has been the focus of a great deal of cryptographic analysis. As a result several attacks have been published in the literature. However none of the proposed attacks breaks the claimed 128-bit security of the cipher. At SASC 2006, Tsunoo et al. presented a guess-and-determine attack on SOSEMANUK (article). The attack recovers all 384 bits of the internal state after the initialization. It has time complexity 2224 and requires 24 words of key stream. At ASIACRYPT 2008, Jung-Keun Lee et al. presented an attack against SOSEMANUK using the linear masking method (article). The authors are able to recover the 384-bit internal state with time, memory and data complexity of less than 2148. At ICISC 2009, Joo Yeon Cho et al. (article) show that the data complexity of this attack can be reduced by a factor of 210.

The most recent attack on SOSEMANUK has been presented at ASIACRYPT 2010 by Xiutao Feng et al. (article). The paper presents a byte-oriented guess-and-determine attack against the cipher: by guessing bytes rather than 32-bit words and using just a few words of the keystream, the authors are able to recover the internal state with time complexity of around 2176 (which is less than previous guess-and-determine attacks against SOSEMANUK).

Miscellaneous

The designers state that SOSEMANUK is free for any use (see statement).

Links

  • SOSEMANUK, a fast software-oriented stream cipher: article
  • C source: zip
  • API-compliant C code: link
  • SOSEMANUK original eSTREAM process page
  • Software Performance: link
  • Software Implementation: link
XHTML 1.0  |  CSS
Last updated in March 2012. The webmaster can be contacted by email at estream@ecrypt.eu.org