- Secure Channels

# Cryptanalysis of XOTIC by Dr. Leo Perrin & Dr. Alex Biryukov

*February 12, 2020*

## Report on the Cryptanalysis of XOTIC

**Executive Summary**

The XOTIC encryption algorithm consists of a CSPRNG with an internal state of variable size which is used to derive:

1. a **key stream**, which is XORed with the plaintext,

2. an **additive table**, which is added with the plaintext (modulo 256), and

3. an **S-box **which permutes the set {0*, ..., *255}.

These three components are then used by XOTIC to encrypt the plaintext byte-by-byte. The key size is equal to the state size, and is thus variable. It depends on an additional parameter called the *dial*.

**Notations**

**Bit**. F2 = {0*, *1} denotes one bit, so that F is the set of all bit-strings of length *n*.

**CSPRNG**. Cryptographically Secure Pseudo-Random Number Generator.

**Dial. The value of the dial denoted v.**

**Modular Addition**. *a *+ *b *denotes the addition modulo 2*k *of the k-bit bit- strings *a *and *b *interpreted as integers. Here, we have *k *∈ {8*, *64}.

**Modular Multiplication. ***a * b *denotes the Java long obtained via the product of the two 64-bit long bit strings *a *and *b *interpreted as Java long themselves.

**Modular Ring. **Z / 2 *n *Z is the set of all integers modulo 2*n*.

**Shifts. ***x *« *n *is a shift by *n *to the left, *x *» *n *is a shift by *n *to the right.

**Truncation. **Trunc n is the function returning the n bits of lowest weight of its input.

**XOR. a ⊕ b denotes the XOR of the bit strings a and b.**

**The Design of XOTIC**

XOTIC is an encryption algorithm which turns a readable plaintext into a ciphertext using a secret key. It should not be possible to invert this process without knowledge of the key, meaning that an attacker obtaining a ciphertext should not be able to recover any information about the content of the plaintext. There are two layers in Xotic. The first one consists of a PRNG which has the following components:

an internal state called DSG which is initialized using secret values, and which is updated using a function which depends on the (also secret) values in the DSA; and

a filter function which reads information from the DSG and returns pseudo-random bits.

At a high level, these two components are classical building blocks for a *stream cipher *(see Section 1.2.1). Stream ciphers are encryption algorithms that take inspiration from the one-time pad. They generate a pseudo-random key stream starting from a secret key and an initialization vector (IV). The key stream is then XORed with the plaintext to obtain the ciphertext—and vice-versa. The triple cascade, i.e. the sequential use of three different encryption algorithms, was shown in [BR06] to be far more secure than the simple or double cascade.

**CONCLUSION **- XOTIC is an encryption algorithm built on top of a CSPRNG. The PRNG is used in a “classical” way to generate a keystream during encryption, but it is also used to construct additional security layers (the **additive table **and the **S-box**) that are likely intended to compensate for well-known shortcomings of stream ciphers. The PRNG itself uses a classical structure that combines the output of several simple PRNGs using a non-linear filter function to create the actual output. A notable feature of XOTIC is its support of various key sizes including very large ones (several KB and more). This may provide an additional security margin.

The encryption algorithm itself is built using three components: the key stream, the additive table and the S-box. The way these are used does not depend on the specifics of the CSPRNG. Thus, their combination can be thought of as a mode of operation that turns a CSPRNG into an encryption algorithm. This CSPRNG could be replaced by a different secure random number generator such as a Quantum Random Number Generator (QRNG).

XOTIC encryption can be described with a single equation:

**1. On the S-BOX Generation**

When constructing a symmetric primitive, the S-box used must have some specific mathematical properties in order to allow the primitive itself to withstand attacks like differential [BS91] and linear [Mat94] cryptanalysis. Although the use of the S-box in Xotic is different, in particular because it is completely key dependent, these properties are still a good measure for what we may call the “cryptographic quality” (for lack of a better term) of the S-box.

**CONCLUSION - **The main conclusion that we draw from the results in this section is that the S-boxes generated by XOTIC have properties on par with those expected from random S-boxes.

We were able to show that this process has the following two properties, even though neither of them is concerning. First, while completely weak DSAs have an observable effect, it is unlikely to happen, and this effect is not likely to be an issue. Second, the parts of the DSA and DSG that are only used in this context have a significant influence over it, meaning that said words cannot be discarded until the S-box is generated.

The XOTIC encryption algorithm consists of a CSPRNG with an internal state of variable size which is used to derive:

XOTIC is an encryption algorithm built on top of a CSPRNG. The PRNG is used in a “classical” way to generate a keystream during encryption, but it is also used to construct additional security layers (the additive table and the S-box ) that are likely intended to compensate for well-known shortcomings of stream ciphers. The PRNG itself uses a classical structure that combines the output of several simple PRNGs using a non-linear filter function to create the actual output. A notable feature of XOTIC is its support of various key sizes including very large ones (several KB and more). This may provide an additional security margin.

The encryption algorithm itself is built using three components: the key stream, the additive table and the S-box. The way these are used does not depend on the specifics of the CSPRNG. Thus, their combination can be thought of as a mode of operation that turns a CSPRNG into an encryption algorithm. This CSPRNG could be replaced by a different secure random number generator such as a Quantum Random Number Generator (QRNG).

**2. Structural Observations**

**CONCLUSION **- The main conclusion we derive from our attack recovering the additive table and the S-Box is that in theoretical sense these component do not really add to the security of the cipher. Indeed, reusing the same DSA/DSG pair twice is sufficient to be able to efficiently recover both and then expose the keystream. Though the attacker does not know the DSA/DSG pair, they are able to encrypt or decrypt data as if they did know it.

In summary: for a simple stream cipher, we need 1 known plaintext/ciphertext pair to be able to encrypt/decrypt data as if we knew the key. The additive table and the S-box used in XOTIC increase this number to 2.

**3. Estimating the Key Size**

**CONCLUSION **- The effective key size of XOTIC is slightly smaller than might be expected. Indeed, there are equivalent keys because of the fact that all DSA/DSG blocks play the same role. When the filter we were given is used and if the dial is greater than 4, then it is more efficient to guess

the S-box than to guess the DSA/DSG values that appear exclusively during its generation. Still, the effective keysize does increase exponentially when the dial increases, and this issue is fixed by the new filter design.

The key sizes considered are extremely high (against attackers that use practical amounts of key-stream, see Remark 1): we do not foresee the brute-force search to become a threat of any practical importance, even when the dial is minimum.

**REPORT CONCLUSION**

XOTIC is the combination of CSPRNG with a mode of operation using this CSPRNG to provide encryption.

Instead of simply XORing the keystream generated by the CSPRNG with the plaintext, XOTIC uses a more sophisticated plaintext combiner, which involves a periodic addition followed by an 8-bit lookup from a randomly generated S-box. While a typical stream cipher is vulnerable to simple bit-flipping, for XOTIC an attacker would have less than 1/256 chance to succeed. Note that such modifications would anyway be identified by the message authentication code used (HMAC).

If the same DSA and DSG values are used twice then the additive table and the S-box can be recovered efficiently given two known-plaintexts, a property the mode of operation of XOTIC shares with usual stream ciphers. Thus, they do not offer strong security by themselves.