Rabbit (algorithm)

Rabbit is a stream cipher that uses a 128-bit key and a 64-bit initialization vector .

history

Rabbit was developed in 2003 by Martin Boesgaard, Mette Vesterager, Thomas Pedersen, Jesper Christiansen, and Ove Scavenius and at the company Cryptico and was first presented in February 2003 at the 10th FSE workshop. Rabbit's design was inspired by the complex behavior of real-world chaotic cards . Chaotic maps are primarily characterized by an exponential sensitivity to small disturbances, so that iterations of such maps appear random and unpredictable in the long term.

The algorithm is described in RFC 4503 , a patent was filed by Cryptico for the algorithm and for many years it demanded a license fee for the commercial use of the encryption. The software has been licensed as public domain software since October 2008 and can therefore also be used free of charge for commercial purposes.

Functionality

Encryption with the Rabbit algorithm

Decryption with the Rabbit algorithm

The Rabbit algorithm takes a secret 128 bit key and a 64 bit initialization vector as input and generates an output block of 128 pseudo-random bits from a combination of the internal status bits for each iteration . The encryption and decryption is done by a contravalence of the pseudo-random data with the plain text or encrypted text. The size of the internal status is 513 bits, divided into eight 32-bit status variables, eight 32-bit counters and one carry bit .

The key preparation scheme

The algorithm is initialized by the expansion of the 128-bit key, both in the 8 state variables, as well as the 8 counter so that a one-to-one correspondence between the key and the initial state variables and the start points exist. The key is divided into eight sub-key: , , , , , , and ${\displaystyle x_{j,0}}$ ${\displaystyle c_{j,0}}$ ${\displaystyle K^{[127..0]}}$
${\displaystyle K^{[15..0]}}$ ${\displaystyle K^{[31..16]}}$ ${\displaystyle K^{[47..32]}}$ ${\displaystyle K^{[63..48]}}$ ${\displaystyle K^{[79..64]}}$ ${\displaystyle K^{[95..80]}}$ ${\displaystyle K^{[111..96]}}$ ${\displaystyle K^{[127..112]}}$

The status and counter variables are initialized as follows: and
${\displaystyle x_{j,0}={\begin{cases}k_{j+1mod8}\diamond k_{j}&{\text{bei geraden }}j\\k_{j+1mod8}\diamond k_{j}&{\text{bei geraden }}j\end{cases}}}$

${\displaystyle c_{j,0}={\begin{cases}k_{j+4mod8}\diamond k_{j+5mod8}&{\text{bei geraden }}j\\k_{j}\diamond k_{j+1mod8}&{\text{bei geraden }}j\end{cases}}}$

This is iterated four times in accordance with the next-state function below in order to reduce the correlations between the bits in the key and the bits in the internal state variables. Finally, the counter values ​​are re-initialized according to the following formula to restore the key by reversing the To prevent counter system:
${\displaystyle c_{j,4}=c_{j,4}\oplus x_{(j+4mod8),4}}$

IV scheme

The IV setup scheme comes about by XORing the 64 bit IV stream to all 256 bits of the counterstate. The 64 bits of the IV are noted below as . ${\displaystyle IV^{[63::0]}}$

• ${\displaystyle c_{0,4}=c_{0,4}\oplus IV^{[31..0]}}$
• ${\displaystyle c_{2,4}=c_{2,4}\oplus IV^{[63..32]}}$
• ${\displaystyle c_{4,4}=c_{4,4}\oplus IV^{[31..0]}}$
• ${\displaystyle c_{6,4}=c_{6,4}\oplus IV^{[63..32]}}$

• ${\displaystyle c_{1,4}=c_{1,4}\oplus (IV^{[63..48]}\diamond IV^{[31..16]})}$
• ${\displaystyle c_{3,4}=c_{3,4}\oplus (IV^{[47..32]}\diamond IV^{[15..0]})}$
• ${\displaystyle c_{5,4}=c_{5,4}\oplus (IV^{[63..48]}\diamond IV^{[31..16]})}$
• ${\displaystyle c_{7,4}=c_{7,4}\oplus (IV^{[47..32]}\diamond IV^{[15..0]})}$

The system is then iterated four times in order to make all status bits non-linearly dependent on all IV bits. The modification of the counter by the IV guarantees that all possible combinations of the IV result in a unique keystream. ${\displaystyle 2^{64}}$

Next-state function

The core of the Rabbit algorithm is the iteration of the system, defined by the following equations:

• ${\displaystyle x_{0,i+1}=g_{0,i}+(g_{7,i}\ll 16)+(g_{6,i}\ll 16)}$
• ${\displaystyle x_{1,i+1}=g_{1,i}+(g_{0,i}\ll 8)+g_{7,i}}$
• ${\displaystyle x_{2,i+1}=g_{2,i}+(g_{1,i}\ll 16)+(g_{0,i}\ll 16)}$
• ${\displaystyle x_{3,i+1}=g_{3,i}+(g_{2,i}\ll 8)+g_{1,i}}$
• ${\displaystyle x_{4,i+1}=g_{4,i}+(g_{3,i}\ll 16)+(g_{2,i}\ll 16)}$
• ${\displaystyle x_{5,i+1}=g_{5,i}+(g_{4,i}\ll 8)+g_{3,i}}$
• ${\displaystyle x_{6,i+1}=g_{6,i}+(g_{5,i}\ll 16)+(g_{4,i}\ll 16)}$
• ${\displaystyle x_{7,i+1}=g_{7,i}+(g_{6,i}\ll 8)+g_{5,i}}$

${\displaystyle g_{j,i}=((x_{j,i}+c_{j,i})^{2}\oplus ((x_{j,i}+c_{j,i})^{2}\gg 32))mod2^{32}}$

Counting system

The following constants are required for the counter, which are defined as follows:

• ${\displaystyle a_{0}=0x4D34D34D}$
• ${\displaystyle a_{1}=0xD34D34D3}$
• ${\displaystyle a_{2}=0x34D34D34}$
• ${\displaystyle a_{3}=0x4D34D34D}$
• ${\displaystyle a_{4}=0xD34D34D3}$
• ${\displaystyle a_{5}=0x34D34D34}$
• ${\displaystyle a_{6}=0x4D34D34D}$
• ${\displaystyle a_{7}=0xD34D34D3}$

The dynamics of the counters are defined as follows:

• ${\displaystyle c_{0,i+1}=c_{0,i}+a_{0}+\phi _{7,i}mod2^{32}}$
• ${\displaystyle c_{1,i+1}=c_{1,i}+a_{1}+\phi _{0,i+1}mod2^{32}}$
• ${\displaystyle c_{2,i+1}=c_{2,i}+a_{2}+\phi _{1,i+1}mod2^{32}}$
• ${\displaystyle c_{3,i+1}=c_{3,i}+a_{3}+\phi _{2,i+1}mod2^{32}}$
• ${\displaystyle c_{4,i+1}=c_{4,i}+a_{4}+\phi _{3,i+1}mod2^{32}}$
• ${\displaystyle c_{5,i+1}=c_{5,i}+a_{5}+\phi _{4,i+1}mod2^{32}}$
• ${\displaystyle c_{6,i+1}=c_{6,i}+a_{6}+\phi _{5,i+1}mod2^{32}}$

The carry bit is defined according to the following formula: ${\displaystyle \phi _{j,i+1}}$
${\displaystyle \phi _{j,i+1}={\begin{cases}1&{\text{falls }}c_{0,i}+a_{0}+\phi _{7,i}\geq 2^{32}\wedge j=0\\1&{\text{falls }}c_{j,i}+a_{j}+\phi _{j-1,i+1}\geq 2^{32}\wedge j>0\\0&{\text{andernfalls}}\end{cases}}}$

extraction

After each iteration, 128 bits of output are generated as follows:

• ${\displaystyle s_{i}^{[15..0]}=x_{0,i}^{[15..0]}\oplus x_{5,i}^{[31..16]}}$
• ${\displaystyle s_{i}^{[47..32]}=x_{2,i}^{[15..0]}\oplus x_{7,i}^{[31..16]}}$
• ${\displaystyle s_{i}^{[79..64]}=x_{4,i}^{[15..0]}\oplus x_{1,i}^{[31..16]}}$
• ${\displaystyle s_{i}^{[111..96]}=x_{6,i}^{[15..0]}\oplus x_{3,i}^{[31..16]}}$

• ${\displaystyle s_{i}^{[31..16]}=x_{0,i}^{[31..16]}\oplus x_{3,i}^{[15..0]}}$
• ${\displaystyle s_{i}^{[63..48]}=x_{2,i}^{[31..16]}\oplus x_{5,i}^{[15..0]}}$
• ${\displaystyle s_{i}^{[95..80]}=x_{4,i}^{[31..16]}\oplus x_{7,i}^{[15..0]}}$
• ${\displaystyle s_{i}^{[127..112]}=x_{6,i}^{[31..16]}\oplus x_{1,i}^{[15..0]}}$

where the 128 bit output block is after the iteration . ${\displaystyle s_{i}}$ ${\displaystyle i}$

Encryption and decryption

A text / encrypted text is then encrypted or decrypted by means of a contravalency with the output block that is obtained after entering the 128-bit key and the 64-bit initial vector.

example

To encrypt a text using the Rabbit algorithm, all you need is a key and an initialization vector. With the key Wikipedia (0x57696b697065646961) and the initial vector 0x123123 you get the output block 0x9c677286866aad38f8e9b660f5411814

If you counter-enable this with the text to be encrypted Secure Message (0x53696368657265204e6163687269636874), you get the following encrypted text a2115ff62ad536899a8b16d22f47746336

speed

The cipher was developed for high software performance. With a fully optimized implementation, the Rabbit algorithm achieves an encryption speed of 3.7 clock cycles per byte on an Intel Pentium III and an encryption speed of 10.5 clock cycles per byte on a processor based on the ARM7 .

safety

A 128-bit key makes it robust against brute force attacks . It's also pretty easy to implement and requires minimal storage of states. Compared to the Advanced Encryption Standard for devices with low power, there are advantages for the Rabbit algorithm in terms of speed and robustness. So far, no weaknesses have been found in the Rabbit encryption.

application

The Rabbit algorithm finds among others in the open source SSL / TLS - program library WolfSSL (formerly CyaSSL) application, which is popular with embedded systems is used.

Web links

• http://www.ecrypt.eu.org/stream/e2-rabbit.html
• ecrypt.eu.org

Individual evidence

1. ↑ ^{a b c d e f g h} The Stream Cipher Rabbit. (PDF) Retrieved May 20, 2019 (English). 
2. ↑ ^{a b c} Rabbit: A New High-Performance Stream Cipher ( Memento from December 11, 2013 in the Internet Archive )
3. ↑ Rabbit becomes public domain ( Memento from June 30, 2009 in the Internet Archive )
4. ↑ Light-weight crypto: Rabbit. Retrieved May 20, 2019 . 
5. ↑ Ecrypt: Rabbit. Retrieved May 20, 2019 .