Improved cryptanalysis of the Common Scrambling Algorithm Stream Cipher

This paper provides a fresh analysis of the widely-used Common Scrambling Algorithm Stream Cipher (CSA-SC). Firstly, a new representation of CSA-SC with a state size of only 89 bits is given, a significant reduction from the 103 bit state of a previous CSA-SC representation. Analysis of this 89-bit representation demonstrates that the basis of a previous guess-and-determine attack is flawed. Correcting this flaw increases the complexity of that attack so that it is worse than exhaustive key search. Although that attack is not feasible, the reduced state size of our representation makes it obvious that CSA-SC is vulnerable to several generic attacks, for which feasible parameters are given.

Weaknesses in the initialisation process of the Common Scrambling Algorithm Stream Cipher

The Common Scrambling Algorithm Stream Cipher (CSASC) is a shift register based stream cipher designed to encrypt digital video broadcast. CSA-SC produces a pseudo-random binary sequence that is used to mask the contents of the transmission. In this paper, we analyse the initialisation process of the CSA-SC keystream generator and demonstrate weaknesses which lead to state convergence, slid pairs and shifted keystreams. As a result, the cipher may be vulnerable to distinguishing attacks, time-memory-data trade-off attacks or slide attacks.

Secure stream cipher initialisation processes

Stream ciphers are symmetric key cryptosystems that are used commonly to provide confidentiality for a wide range of applications; such as mobile phone, pay TV and Internet data transmissions. This research examines the features and properties of the initialisation processes of existing stream ciphers to identify flaws and weaknesses, then presents recommendations to improve the security of future cipher designs. This research investigates well-known stream ciphers: A5/1, Sfinks and the Common Scrambling Algorithm Stream Cipher (CSA-SC). This research focused on the security of the initialisation process. The recommendations given are based on both the results in the literature and the work in this thesis.

Cryptanalysis of RC4(n, m) stream cipher

RC4(n, m) is a stream cipher based on RC4 and is designed by G. Gong et al. It can be seen as a generalization of the famous RC4 stream cipher designed by Ron Rivest. The authors of RC4(n, m) claim that the cipher resists all the attacks that are successful against the original RC4. The paper reveals cryptographic weaknesses of the RC4(n, m) stream cipher. We develop two attacks. The first one is based on non-randomness of internal state and allows to distinguish it from a truly random cipher by an algorithm that has access to 24·n bits of the keystream. The second attack exploits low diffusion of bits in the KSA and PRGA algorithms and recovers all bytes of the secret key. This attack works only if the initial value of the cipher can be manipulated. Apart from the secret key, the cipher uses two other inputs, namely, initial value and initial vector. Although these inputs are fixed in the cipher specification, some applications may allow the inputs to be under the attacker control. Assuming that the attacker can control the initial value, we show a distinguisher for the cipher and a secret key recovery attack that for the L-bit secret key, is able to recover it with about (L/n) · 2n steps. The attack has been implemented on a standard PC and can reconstruct the secret key of RC(8, 32) in less than a second.

Security evaluation of Rakaposhi Stream Cipher

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 29 pairs of (K,IV). Based on the proposed related-key attack, the number of related (K,IV) pairs is 2(128 + 192)/4 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 263.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 217 observations of keystream bits. There is also the key recovery algorithm that allows to find the secret key with complexity 2 54.

Message Integrity in the World Wide Web: Use of Nested Hash Function and a Fast Stream Cipher

The focus of this work is to provide authentication and confidentiality of messages in a swift and cost effective manner to suit the fast growing Internet applications. A nested hash function with lower computational and storage demands is designed with a view to providing authentication as also to encrypt the message as well as the hash code using a fast stream cipher MAJE4 with a variable key size of 128-bit or 256-bit for achieving confidentiality. Both nested Hash function and MAJE4 stream cipher algorithm use primitive computational operators commonly found in microprocessors; this makes the method simple and fast to implement both in hardware and software. Since the memory requirement is less, it can be used for handheld devices for security purposes.

The Dragon stream cipher: Design, analysis and implementation issues

Dragon is a word-based stream cipher. It was submitted to the eSTREAM project in 2005 and has advanced to Phase 3 of the software profile. This paper discusses the Dragon cipher from three perspectives: design, security analysis and implementation. The design of the cipher incorporates a single word-based non-linear feedback shift register and a non-linear filter function with memory. This state is initialized with 128- or 256-bit key-IV pairs. Each clock of the stream cipher produces 64 bits of keystream, using simple operations on 32-bit words. This provides the cipher with a high degree of efficiency in a wide variety of environments, making it highly competitive relative to other symmetric ciphers. The components of Dragon were designed to resist all known attacks. Although the design has been open to public scrutiny for several years, the only published attacks to date are distinguishing attacks which require keystream lengths greatly exceeding the stated 264 bit maximum permitted keystream length for a single key-IV pair.

State convergence in the initialisation of the Sfinks stream cipher

Sfinks is a shift register based stream cipher designed for hardware implementation. The initialisation state update function is different from the state update function used for keystream generation. We demonstrate state convergence during the initialisation process, even though the individual components used in the initialisation are one-to-one. However, the combination of these components is not one-to-one.

A different algebraic analysis of the ZUC stream cipher

Existing algebraic analyses of the ZUC cipher indicate that the cipher should be secure against algebraic attacks. In this paper, we present an alternative algebraic analysis method for the ZUC stream cipher, where a combiner is used to represent the nonlinear function and to derive equations representing the cipher. Using this approach, the initial states of ZUC can be recovered from 2^97 observed words of keystream, with a complexity of 2^282 operations. This method is more successful when applied to a modified version of ZUC, where the number of output words per clock is increased. If the cipher outputs 120 bits of keystream per clock, the attack can succeed with 219 observed keystream bits and 2^47 operations. Therefore, the security of ZUC against algebraic attack could be significantly reduced if its throughput was to be increased for efficiency.

Algebraic analysis of the SSS stream cipher

Both the SSS and SOBER-t32 stream cipher designs use a single word-based shift register and a nonlinear filter function to produce keystream. In this paper we show that the algebraic attack method previously applied to SOBER-t32 is prevented from succeeding on SSS by the use of the key dependent substitution box (SBox) in the nonlinear filter of SSS. Additional assumptions and modifications to the SSS cipher in an attempt to enable algebraic analysis result in other difficulties that also render the algebraic attack infeasible. Based on these results, we conclude that a well chosen key-dependent substitution box used in the nonlinear filter of the stream cipher provides resistance against such algebraic attacks.

State convergence and keyspace reduction of the mixer stream cipher

This paper presents an analysis of the stream cipher Mixer, a bit-based cipher with structural components similar to the well-known Grain cipher and the LILI family of keystream generators. Mixer uses a 128-bit key and 64-bit IV to initialise a 217-bit internal state. The analysis is focused on the initialisation function of Mixer and shows that there exist multiple key-IV pairs which, after initialisation, produce the same initial state, and consequently will generate the same keystream. Furthermore, if the number of iterations of the state update function performed during initialisation is increased, then the number of distinct initial states that can be obtained decreases. It is also shown that there exist some distinct initial states which produce the same keystream, resulting in a further reduction of the effective key space

State cycles, initialization and the Trivium stream cipher

Trivium is a keystream generator for a binary additive synchronous stream cipher. It was selected in the final portfolio for the Profile 2 category of the eSTREAM project. The keystream generator is constructed using bit- based shift registers. In this paper we present an alternate representation of Trivium using word-based shift registers, with a word size of three bits. This representation is useful for determining cycles of internal state values. Under this representation it is clear that the state space can be partitioned into subspaces and that over some of these subspaces the state update function is effectively linear. The role of the initialization process is critical in ensuring the states used for generating keystream are updated nonlinearly at some point, as the state update function alone does not provide this.

Slide attacks on the Sfinks stream cipher

Sfinks is a shift register based stream cipher designed for hardware implementation and submitted to the eSTREAM project. In this paper, we analyse the initialisation process of Sfinks. We demonstrate a slid property of the loaded state of the Sfinks cipher, where multiple key-IV pairs may produce phase shifted keystream sequences. The state update functions of both the initialisation process and keystream generation and also the pattern of the padding affect generation of the slid pairs.

Slid pairs in the initialisation of the A5/1 stream cipher

A5/1 is a shift register based stream cipher which uses a majority clocking rule to update its registers. It is designed to provide privacy for the GSM system. In this paper, we analyse the initialisation process of A5/1. We demonstrate a sliding property of the A5/1 cipher, where every valid internal state is also a legitimate loaded state and multiple key-IV pairs produce phase shifted keystream sequences. We describe a possible ciphertext only attack based on this property.