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.

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

Distinguishing attack on SOBER-128 with linear masking

We present a distinguishing attack against SOBER-128 with linear masking. We found a linear approximation which has a bias of 2^− − 8.8 for the non-linear filter. The attack applies the observation made by Ekdahl and Johansson that there is a sequence of clocks for which the linear combination of some states vanishes. This linear dependency allows that the linear masking method can be applied. We also show that the bias of the distinguisher can be improved (or estimated more precisely) by considering quadratic terms of the approximation. The probability bias of the quadratic approximation used in the distinguisher is estimated to be equal to O(2^− − 51.8), so that we claim that SOBER-128 is distinguishable from truly random cipher by observing O(2^103.6) keystream words.

Cryptanalysis of Tav-128 Hash Function

Many RFID protocols use cryptographic hash functions for their security. The resource constrained nature of RFID systems forces the use of light weight cryptographic algorithms. Tav-128 is one such 128-bit light weight hash function proposed by Peris-Lopez et al. for a low-cost RFID tag authentication protocol. Apart from some statistical tests for randomness by the designers themselves, Tav-128 has not undergone any other thorough security analysis. Based on these tests, the designers claimed that Tav-128 does not posses any trivial weaknesses. In this article, we carry out the first third party security analysis of Tav-128 and show that this hash function is neither collision resistant nor second preimage resistant. Firstly, we show a practical collision attack on Tav-128 having a complexity of 237 calls to the compression function and produce message pairs of arbitrary length which produce the same hash value under this hash function. We then show a second preimage attack on Tav-128 which succeeds with a complexity of 262 calls to the compression function. Finally, we study the constituent functions of Tav-128 and show that the concatenation of nonlinear functions A and B produces a 64-bit permutation from 32-bit messages. This could be a useful light weight primitive for future RFID protocols.

Low probability differentials and the cryptanalysis of full-round CLEFIA-128

So far, low probability differentials for the key schedule of block ciphers have been used as a straightforward proof of security against related-key differential analysis. To achieve resistance, it is believed that for cipher with k-bit key it suffices the upper bound on the probability to be 2− k . Surprisingly, we show that this reasonable assumption is incorrect, and the probability should be (much) lower than 2− k . Our counter example is a related-key differential analysis of the well established block cipher CLEFIA-128. We show that although the key schedule of CLEFIA-128 prevents differentials with a probability higher than 2− 128, the linear part of the key schedule that produces the round keys, and the Feistel structure of the cipher, allow to exploit particularly chosen differentials with a probability as low as 2− 128. CLEFIA-128 has 214 such differentials, which translate to 214 pairs of weak keys. The probability of each differential is too low, but the weak keys have a special structure which allows with a divide-and-conquer approach to gain an advantage of 27 over generic analysis. We exploit the advantage and give a membership test for the weak-key class and provide analysis of the hashing modes. The proposed analysis has been tested with computer experiments on small-scale variants of CLEFIA-128. Our results do not threaten the practical use of CLEFIA.

A pilot study on the effect of indoor particle sources on indoor particle concentration in residential houses

Characterization of indoor particle sources from 14 residential houses in Brisbane, Australia, was performed. The approximation of PM2.5 and the submicrometre particle number concentrations were measured simultaneously for more than 48 h in the kitchen of all the houses by using a photometer (DustTrak) and a condensation particle counter (CPC), respectively. From the real time indoor particle concentration data and a diary of indoor activities, the indoor particle sources were identified. The study found that among the indoor activities recorded in this study, frying, grilling, stove use, toasting, cooking pizza, smoking, candle vaporizing eucalyptus oil and fan heater use, could elevate the indoor particle number concentration levels by more than five times. The indoor approximation of PM2.5 concentrations could be close to 90 times, 30 times and three times higher than the background levels during grilling, frying and smoking, respectively.

Space-time variation of malaria incidence in Yunnan province, China

Abstract Background Understanding spatio-temporal variation in malaria incidence provides a basis for effective disease control planning and monitoring. Methods Monthly surveillance data between 1991 and 2006 for Plasmodium vivax and Plasmodium falciparum malaria across 128 counties were assembled for Yunnan, a province of China with one of the highest burdens of malaria. County-level Bayesian Poisson regression models of incidence were constructed, with effects for rainfall, maximum temperature and temporal trend. The model also allowed for spatial variation in county-level incidence and temporal trend, and dependence between incidence in June–September and the preceding January–February. Results Models revealed strong associations between malaria incidence and both rainfall and maximum temperature. There was a significant association between incidence in June–September and the preceding January–February. Raw standardised morbidity ratios showed a high incidence in some counties bordering Myanmar, Laos and Vietnam, and counties in the Red River valley. Clusters of counties in south-western and northern Yunnan were identified that had high incidence not explained by climate. The overall trend in incidence decreased, but there was significant variation between counties. Conclusion Dependence between incidence in summer and the preceding January–February suggests a role of intrinsic host-pathogen dynamics. Incidence during the summer peak might be predictable based on incidence in January–February, facilitating malaria control planning, scaled months in advance to the magnitude of the summer malaria burden. Heterogeneities in county-level temporal trends suggest that reductions in the burden of malaria have been unevenly distributed throughout the province.

Staking a claim : the role of stakeholders in government

The stakeholder approach which emerged under the auspices of new public management has been in use in public agencies for the past 25 years. However it remains a difficult and demanding task for agencies to determine who their stakeholders are and how to optimise interactions with them. This paper will examine how government agencies identify, classify and engage with stakeholders who have competing demands, differing access to resources and the ability to exert political pressure. To do this, the stakeholder approaches of nine agencies at three levels of government in Queensland were studied. The contribution of this paper is the development of a Stakeholder Classification Model for Public Agencies which could be used to create more focused and relevant stakeholder interventions.

Managing infrastructure transitions : a complex adaptive systems perspective

Engineering assets such as roads, rail, bridges and other forms of public works are vital to the effective functioning of societies {Herder, 2006 #128}. Proficient provision of this physical infrastructure is therefore one of the key activities of government {Lædre, 2006 #123}. In order to ensure engineering assets are procured and maintained on behalf of citizens, government needs to devise the appropriate policy and institutional architecture for this purpose. The changing institutional arrangements around the procurement of engineering assets are the focus of this paper. The paper describes and analyses the transition to new, more collaborative forms of procurement arrangements which are becoming increasingly prevalent in Australia and other OECD countries. Such fundamental shifts from competitive to more collaborative approaches to project governance can be viewed as a major transition in procurement system arrangements. In many ways such changes mirror the shift from New Public Management, with its emphasis on the use of market mechanisms to achieve efficiencies {Hood, 1991 #166}, towards more collaborative approaches to service delivery, such as those under network governance arrangements {Keast, 2007 #925}. However, just as traditional forms of procurement in a market context resulted in unexpected outcomes for industry, such as a fragmented industry afflicted by chronic litigation {Dubois, 2002 #9}, the change to more collaborative forms of procurement is unlikely to be a panacea to the problems of procurement, and may well also have unintended consequences. This paper argues that perspectives from complex adaptive systems (CAS) theory can contribute to the theory and practice of managing system transitions. In particular the concept of emergence provides a key theoretical construct to understand the aggregate effect that individual project governance arrangements can have upon the structure of specific industries, which in turn impact individual projects. Emergence is understood here as the macro structure that emerges out of the interaction of agents in the system {Holland, 1998 #100; Tang, 2006 #51}.

Multiple-choice versus short-response items: Differences in omit behavior

The overall rate of omission of items for 28,331 17 year old Australian students on a high stakes test of achievement in the common elements or cognitive skills of the senior school curriculum is reported for a subtest in multiple choice format and a subtest in short response format. For the former, the omit rates were minuscule and there was no significant difference by gender or by type of school attended. For the latter, where an item can be 'worth' up to five times that of a single multiple choice item, the omit rates were between 10 and 20 times that for multiple choice and the difference between male and female omit rate was significant as was the difference between students from government and non-government schools. For both formats, females from single sex schools omitted significantly fewer items than did females from co-educational schools. Some possible explanations of omit behaviour are alluded to.