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.

Analysis of authenticated encryption stream ciphers

Authenticated Encryption (AE) is the cryptographic process of providing simultaneous confidentiality and integrity protection to messages. AE is potentially more efficient than applying a two-step process of providing confidentiality for a message by encrypting the message and in a separate pass, providing integrity protection by generating a Message Authentication Code (MAC) tag. This paper presents results on the analysis of three AE stream ciphers submitted to the recently completed eSTREAM competition. We classify the ciphers based on the methods the ciphers use to provide authenticated encryption and discuss possible methods for mounting attacks on these ciphers.

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.

An analysis of the RC4 family of stream ciphers against algebraic attacks

To date, most applications of algebraic analysis and attacks on stream ciphers are on those based on lin- ear feedback shift registers (LFSRs). In this paper, we extend algebraic analysis to non-LFSR based stream ciphers. Specifically, we perform an algebraic analysis on the RC4 family of stream ciphers, an example of stream ciphers based on dynamic tables, and inves- tigate its implications to potential algebraic attacks on the cipher. This is, to our knowledge, the first pa- per that evaluates the security of RC4 against alge- braic attacks through providing a full set of equations that describe the complex word manipulations in the system. For an arbitrary word size, we derive alge- braic representations for the three main operations used in RC4, namely state extraction, word addition and state permutation. Equations relating the inter- nal states and keystream of RC4 are then obtained from each component of the cipher based on these al- gebraic representations, and analysed in terms of their contributions to the security of RC4 against algebraic attacks. Interestingly, it is shown that each of the three main operations contained in the components has its own unique algebraic properties, and when their respective equations are combined, the resulting system becomes infeasible to solve. This results in a high level of security being achieved by RC4 against algebraic attacks. On the other hand, the removal of an operation from the cipher could compromise this security. Experiments on reduced versions of RC4 have been performed, which confirms the validity of our algebraic analysis and the conclusion that the full RC4 stream cipher seems to be immune to algebraic attacks at present.

Algebraic attacks on clock-controlled stream ciphers

Stream ciphers are encryption algorithms used for ensuring the privacy of digital telecommunications. They have been widely used for encrypting military communications, satellite communications, pay TV encryption and for voice encryption of both fixed lined and wireless networks. The current multi year European project eSTREAM, which aims to select stream ciphers suitable for widespread adoptation, reflects the importance of this area of research. Stream ciphers consist of a keystream generator and an output function. Keystream generators produce a sequence that appears to be random, which is combined with the plaintext message using the output function. Most commonly, the output function is binary addition modulo two. Cryptanalysis of these ciphers focuses largely on analysis of the keystream generators and of relationships between the generator and the keystream it produces. Linear feedback shift registers are widely used components in building keystream generators, as the sequences they produce are well understood. Many types of attack have been proposed for breaking various LFSR based stream ciphers. A recent attack type is known as an algebraic attack. Algebraic attacks transform the problem of recovering the key into a problem of solving multivariate system of equations, which eventually recover the internal state bits or the key bits. This type of attack has been shown to be effective on a number of regularly clocked LFSR based stream ciphers. In this thesis, algebraic attacks are extended to a number of well known stream ciphers where at least one LFSR in the system is irregularly clocked. Applying algebriac attacks to these ciphers has only been discussed previously in the open literature for LILI-128. In this thesis, algebraic attacks are first applied to keystream generators using stop-and go clocking. Four ciphers belonging to this group are investigated: the Beth-Piper stop-and-go generator, the alternating step generator, the Gollmann cascade generator and the eSTREAM candidate: the Pomaranch cipher. It is shown that algebraic attacks are very effective on the first three of these ciphers. Although no effective algebraic attack was found for Pomaranch, the algebraic analysis lead to some interesting findings including weaknesses that may be exploited in future attacks. Algebraic attacks are then applied to keystream generators using (p; q) clocking. Two well known examples of such ciphers, the step1/step2 generator and the self decimated generator are investigated. Algebraic attacks are shown to be very powerful attack in recovering the internal state of these generators. A more complex clocking mechanism than either stop-and-go or the (p; q) clocking keystream generators is known as mutual clock control. In mutual clock control generators, the LFSRs control the clocking of each other. Four well known stream ciphers belonging to this group are investigated with respect to algebraic attacks: the Bilateral-stop-and-go generator, A5/1 stream cipher, Alpha 1 stream cipher, and the more recent eSTREAM proposal, the MICKEY stream ciphers. Some theoretical results with regards to the complexity of algebraic attacks on these ciphers are presented. The algebraic analysis of these ciphers showed that generally, it is hard to generate the system of equations required for an algebraic attack on these ciphers. As the algebraic attack could not be applied directly on these ciphers, a different approach was used, namely guessing some bits of the internal state, in order to reduce the degree of the equations. Finally, an algebraic attack on Alpha 1 that requires only 128 bits of keystream to recover the 128 internal state bits is presented. An essential process associated with stream cipher proposals is key initialization. Many recently proposed stream ciphers use an algorithm to initialize the large internal state with a smaller key and possibly publicly known initialization vectors. The effect of key initialization on the performance of algebraic attacks is also investigated in this thesis. The relationships between the two have not been investigated before in the open literature. The investigation is conducted on Trivium and Grain-128, two eSTREAM ciphers. It is shown that the key initialization process has an effect on the success of algebraic attacks, unlike other conventional attacks. In particular, the key initialization process allows an attacker to firstly generate a small number of equations of low degree and then perform an algebraic attack using multiple keystreams. The effect of the number of iterations performed during key initialization is investigated. It is shown that both the number of iterations and the maximum number of initialization vectors to be used with one key should be carefully chosen. Some experimental results on Trivium and Grain-128 are then presented. Finally, the security with respect to algebraic attacks of the well known LILI family of stream ciphers, including the unbroken LILI-II, is investigated. These are irregularly clock- controlled nonlinear filtered generators. While the structure is defined for the LILI family, a particular paramater choice defines a specific instance. Two well known such instances are LILI-128 and LILI-II. The security of these and other instances is investigated to identify which instances are vulnerable to algebraic attacks. The feasibility of recovering the key bits using algebraic attacks is then investigated for both LILI- 128 and LILI-II. Algebraic attacks which recover the internal state with less effort than exhaustive key search are possible for LILI-128 but not for LILI-II. Given the internal state at some point in time, the feasibility of recovering the key bits is also investigated, showing that the parameters used in the key initialization process, if poorly chosen, can lead to a key recovery using algebraic attacks.

Evolutionary biology of Gondwanan non-biting midges (Diptera: Chironomidae)

The potential restriction to effective dispersal and gene flow caused by habitat fragmentation can apply to multiple levels of evolutionary scale; from the fragmentation of ancient supercontinents driving diversification and speciation on disjunct landmasses, to the isolation of proximate populations as a result of their inability to cross intervening unsuitable habitat. Investigating the role of habitat fragmentation in driving diversity within and among taxa can thus include inferences of phylogenetic relationships among taxa, assessments of intraspecific phylogeographic structure and analyses of gene flow among neighbouring populations. The proposed Gondwanan clade within the chironomid (non-biting midge) subfamily Orthocladiinae (Diptera: Chironomidae) represents a model system for investigating the role that population fragmentation and isolation has played at different evolutionary scales. A pilot study by Krosch et al (2009) indentified several highly divergent lineages restricted to ancient rainforest refugia and limited gene flow among proximate sites within a refuge for one member of this clade, Echinocladius martini Cranston. This study provided a framework for investigating the evolutionary history of this taxon and its relatives more thoroughly. Populations of E. martini were sampled in the Paluma bioregion of northeast Queensland to investigate patterns of fine-scale within- and among-stream dispersal and gene flow within a refuge more rigorously. Data was incorporated from Krosch et al (2009) and additional sites were sampled up- and downstream of the original sites. Analyses of genetic structure revealed strong natal site fidelity and high genetic structure among geographically proximate streams. Little evidence was found for regular headwater exchange among upstream sites, but there was distinct evidence for rare adult flight among sites on separate stream reaches. Overall, however, the distribution of shared haplotypes implied that both larval and adult dispersal was largely limited to the natal stream channel. Patterns of regional phylogeographic structure were examined in two related austral orthoclad taxa – Naonella forsythi Boothroyd from New Zealand and Ferringtonia patagonica Sæther and Andersen from southern South America – to provide a comparison with patterns revealed in their close relative E. martini. Both taxa inhabit tectonically active areas of the southern hemisphere that have also experienced several glaciation events throughout the Plio-Pleistocene that are thought to have affected population structure dramatically in many taxa. Four highly divergent lineages estimated to have diverged since the late Miocene were revealed in each taxon, mirroring patterns in E. martini; however, there was no evidence for local geographical endemism, implying substantial range expansion post-diversification. The differences in pattern evident among the three related taxa were suggested to have been influenced by variation in the responses of closed forest habitat to climatic fluctuations during interglacial periods across the three landmasses. Phylogeographic structure in E. martini was resolved at a continental scale by expanding upon the sampling design of Krosch et al (2009) to encompass populations in southeast Queensland, New South Wales and Victoria. Patterns of phylogeographic structure were consistent with expectations and several previously unrecognised lineages were revealed from central- and southern Australia that were geographically endemic to closed forest refugia. Estimated divergence times were congruent with the timing of Plio-Pleistocene rainforest contractions across the east coast of Australia. This suggested that dispersal and gene flow of E. martini among isolated refugia was highly restricted and that this taxon was susceptible to the impacts of habitat change. Broader phylogenetic relationships among taxa considered to be members of this Gondwanan orthoclad group were resolved in order to test expected patterns of evolutionary affinities across the austral continents. The inferred phylogeny and estimated divergence times did not accord with expected patterns based on the geological sequence of break-up of the Gondwanan supercontinent and implied instead several transoceanic dispersal events post-vicariance. Difficulties in appropriate taxonomic sampling and accurate calibration of molecular phylogenies notwithstanding, the sampling regime implemented in the current study has been the most intensive yet performed for austral members of the Orthocladiinae and unsurprisingly has revealed both novel taxa and phylogenetic relationships within and among described genera. Several novel associations between life stages are made here for both described and previously unknown taxa. Investigating evolutionary relationships within and among members of this clade of proposed Gondwanan orthoclad taxa has demonstrated that a complex interaction between historical population fragmentation and dispersal at several levels of evolutionary scale has been important in driving diversification in this group. While interruptions to migration, colonisation and gene flow driven by population fragmentation have clearly contributed to the development and maintenance of much of the diversity present in this group, long-distance dispersal has also played a role in influencing diversification of continental biotas and facilitating gene flow among disjunct populations.

State convergence in the initialisation of stream ciphers

An initialisation process is a key component in modern stream cipher design. A well-designed initialisation process should ensure that each key-IV pair generates a different key stream. In this paper, we analyse two ciphers, A5/1 and Mixer, for which this does not happen due to state convergence. We show how the state convergence problem occurs and estimate the effective key-space in each case.

The use of temporal speech and lip information for multi-modal speaker identification via multi-stream HMMs

Investigates the use of temporal lip information, in conjunction with speech information, for robust, text-dependent speaker identification. We propose that significant speaker-dependent information can be obtained from moving lips, enabling speaker recognition systems to be highly robust in the presence of noise. The fusion structure for the audio and visual information is based around the use of multi-stream hidden Markov models (MSHMM), with audio and visual features forming two independent data streams. Recent work with multi-modal MSHMMs has been performed successfully for the task of speech recognition. The use of temporal lip information for speaker identification has been performed previously (T.J. Wark et al., 1998), however this has been restricted to output fusion via single-stream HMMs. We present an extension to this previous work, and show that a MSHMM is a valid structure for multi-modal speaker identification

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.