**Security Evaluation of Rakaposhi Stream Cipher**

*Mohammad Ali Orumiehchiha and Josef Pieprzyk and Elham Shakour and Ron Steinfeld*

**Abstract: **Rakaposhi is a synchronous stream cipher, which uses three main components a non-linear
feedback shift register (NLFSR), a dynamic linear feedback shift register (DLFSR) and a
non-linear filtering function ($NLF$). NLFSR consists of 128 bits and is initialised
by the secret key $K$. DLFSR holds 192 bits and is initialised by an initial vector ($IV$).
$NLF$ takes 8-bit inputs and returns a single output bit.
The work identifies weaknesses and properties of the cipher. The main observation
is that the initialisation procedure has the so-called sliding property.
The property can be used to launch distinguishing and key recovery attacks.
The distinguisher needs four observations of the related $(K,IV)$ pairs. The key recovery algorithm allows to discover the secret key $K$ after observing
$2^{9}$ pairs of $(K,IV)$. In the proposed related-key attack, the number of related $(K,IV)$ pairs is $2^{(128+192)/4}$ pairs.
The key recovery algorithm allows to discover the secret key $K$ after observing
$2^9$ related $(K,IV)$ pairs.
Further the cipher is studied when the registers enter short cycles.
When NLFSR is set to all ones, then the cipher degenerates to a linear feedback
shift register with a non-linear filter.
Consequently, the initial state (and Secret Key and $IV$) can be recovered with complexity
$2^{63.87}$.

If DLFSR is set to all zeros, then $NLF$ reduces to a low non-linearity filter function. As the result, the cipher is insecure allowing the adversary to distinguish it from a random cipher after $2^{17}$ observations of keystream bits. There is also the key recovery algorithm that allows to find the secret key with complexity $2^{54}$.

**Category / Keywords: **secret-key cryptography / Rakaposhi Stream Cipher, Related Key Attack, Weak State, Cryptanalysis, Distinguishing Attack, Key Recovery Attack

**Date: **received 16 Nov 2012

**Contact author: **mohammad orumiehchiha at mq edu au

**Available format(s): **PDF | BibTeX Citation

**Version: **20121121:185341 (All versions of this report)

**Short URL: **ia.cr/2012/656

[ Cryptology ePrint archive ]