Analysis of linear relationships in block ciphers

This thesis is devoted to the study of linear relationships in symmetric block ciphers. A block cipher is designed so that the ciphertext is produced as a nonlinear function of the plaintext and secret master key. However, linear relationships within the cipher can still exist if the texts and components of the cipher are manipulated in a number of ways, as shown in this thesis. There are four main contributions of this thesis. The first contribution is the extension of the applicability of integral attacks from word-based to bitbased block ciphers. Integral attacks exploit the linear relationship between texts at intermediate stages of encryption. This relationship can be used to recover subkey bits in a key recovery attack. In principle, integral attacks can be applied to bit-based block ciphers. However, specific tools to define the attack on these ciphers are not available. This problem is addressed in this thesis by introducing a refined set of notations to describe the attack. The bit patternbased integral attack is successfully demonstrated on reduced-round variants of the block ciphers Noekeon, Present and Serpent. The second contribution is the discovery of a very small system of equations that describe the LEX-AES stream cipher. LEX-AES is based heavily on the 128-bit-key (16-byte) Advanced Encryption Standard (AES) block cipher. In one instance, the system contains 21 equations and 17 unknown bytes. This is very close to the upper limit for an exhaustive key search, which is 16 bytes. One only needs to acquire 36 bytes of keystream to generate the equations. Therefore, the security of this cipher depends on the difficulty of solving this small system of equations. The third contribution is the proposal of an alternative method to measure diffusion in the linear transformation of Substitution-Permutation-Network (SPN) block ciphers. Currently, the branch number is widely used for this purpose. It is useful for estimating the possible success of differential and linear attacks on a particular SPN cipher. However, the measure does not give information on the number of input bits that are left unchanged by the transformation when producing the output bits. The new measure introduced in this thesis is intended to complement the current branch number technique. The measure is based on fixed points and simple linear relationships between the input and output words of the linear transformation. The measure represents the average fraction of input words to a linear diffusion transformation that are not effectively changed by the transformation. This measure is applied to the block ciphers AES, ARIA, Serpent and Present. It is shown that except for Serpent, the linear transformations used in the block ciphers examined do not behave as expected for a random linear transformation. The fourth contribution is the identification of linear paths in the nonlinear round function of the SMS4 block cipher. The SMS4 block cipher is used as a standard in the Chinese Wireless LAN Wired Authentication and Privacy Infrastructure (WAPI) and hence, the round function should exhibit a high level of nonlinearity. However, the findings in this thesis on the existence of linear relationships show that this is not the case. It is shown that in some exceptional cases, the first four rounds of SMS4 are effectively linear. In these cases, the effective number of rounds for SMS4 is reduced by four, from 32 to 28. The findings raise questions about the security provided by SMS4, and might provide clues on the existence of a flaw in the design of the cipher.

Bit-pattern based integral attack

Integral attacks are well-known to be effective against byte-based block ciphers. In this document, we outline how to launch integral attacks against bit-based block ciphers. This new type of integral attack traces the propagation of the plaintext structure at bit-level by incorporating bit-pattern based notations. The new notation gives the attacker more details about the properties of a structure of cipher blocks. The main difference from ordinary integral attacks is that we look at the pattern the bits in a specific position in the cipher block has through the structure. The bit-pattern based integral attack is applied to Noekeon, Serpent and present reduced up to 5, 6 and 7 rounds, respectively. This includes the first attacks on Noekeon and present using integral cryptanalysis. All attacks manage to recover the full subkey of the final round.

Linearity within the SMS4 Block Cipher

We present several new observations on the SMS4 block cipher, and discuss their cryptographic significance. The crucial observation is the existence of fixed points and also of simple linear relationships between the bits of the input and output words for each component of the round functions for some input words. This implies that the non-linear function T of SMS4 does not appear random and that the linear transformation provides poor diffusion. Furthermore, the branch number of the linear transformation in the key scheduling algorithm is shown to be less than optimal. The main security implication of these observations is that the round function is not always non-linear. Due to this linearity, it is possible to reduce the number of effective rounds of SMS4 by four. We also investigate the susceptibility of SMS4 to further cryptanalysis. Finally, we demonstrate a successful differential attack on a slightly modified variant of SMS4. These findings raise serious questions on the security provided by SMS4.

The GATA factor Serpent is required for the onset of the humoral immune response in Drosophila embryos

Innate immunity in Drosophila is characterized by the inducible expression of antimicrobial peptides. We have investigated the development and regulation of immune responsiveness in Drosophila embryos after infection. Immune competence, as monitored by the induction of Cecropin A1-lacZ constructs, was observed first in the embryonic yolk. This observation suggests that the yolk plays an important role in the humoral immune response of the developing embryo by synthesizing antimicrobial peptides. Around midembryogenesis, the response in the yolk was diminished. Simultaneously, Cecropin expression became inducible in a large number of cells in the epidermis, demonstrating that late-stage embryos can synthesize their own antibiotics in the epidermis. This production likely serves to provide the hatching larva with an active antimicrobial barrier and protection against systemic infections. Cecropin expression in the yolk required the presence of a GATA site in the promoter as well as the involvement of the GATA-binding transcription factor Serpent (dGATAb). In contrast, neither the GATA site nor Serpent were necessary for Cecropin expression in the epidermis. Thus, the inducible immune responses in the yolk and in the epidermis can be uncoupled and call for distinct sets of transcription factors. Our data suggest that Serpent is involved in the distinction between a systemic response in the yolk/fat body and a local immune response in epithelial cells. In addition, the present study shows that signal transduction pathways controlling innate and epithelial defense reactions can be dissected genetically in Drosophila embryos.

Non-motorized public transport development : present scenario and future approach in developing cities

Over the last few decades, most large cities in the developing world have been experiencing rapid and imbalanced transport sector development resulting in severe congestion and poor levels of service. The most common response at a policy level under this circumstance has been to focus on private and public motorized transport modes, and especially on traffic control measures and mass transit systems. Despite their major role in the overall transport system in many developing cities in Asia & Latin America, relatively little attention is given to non-motorized transport (NMT) modes (walk, bicycle and cycle-rickshaw). In particular, this ideology is applicable to the paid category of non-motorized public transport (NMPT), notably three-wheeler cycle rickshaws that still have an important socio-economic, environmental and trip-making role in many developing cities. Despite, they are often seen as inefficient and backward; an impediment to progress; and inconsistent with modern urban image. Policy measures therefore, to restrict or eliminate non-motorized transport from urban arterials and other feeder networks have been implemented in cities as diverse as Dhaka, Delhi, Karachi, Bangkok, Jakarta, Manila, Surabaya and Beijing . This paper will primarily investigate the key contribution of NMPT in the sustainable transport system and urban fabric of developing cities, with Dhaka as case study. The paper will also highlight in detail the impediments towards NMPT development and provide introductory concept on possible role this mode is expected to play into the future of these cities

Daddies, assistants and foolsbdifferentiation of male representations in present-day advertising.

This paper explores the way men are represented in present-day advertising. Most gender related studies have concentrated in studying women in advertising and claim that men are still represented as the dominant gender and in more active, independent and functional roles than women. This paper asks whether this still holds for advertising in the beginning of 21st century. Many cultural changes may have broken the earlier stereotypes, for example changes in the family life, attitudes toward various sexual identities, concepts of masculinity and femininity, and changes in cultural style.

The present via the past : an archaelogical approach to analysing the design and use of a contemporary urban village

This research applies an archaeological lens to an inner-city master planned development in order to investigate the tension between the design of space and the use of space. The chosen case study for this thesis is Kelvin Grove Urban Village (KGUV), located in inner city Brisbane, Australia. The site of this urban village has strong links to the past. KGUV draws on both the history of the place in particular along with more general mythologies of village life in its design and subsequent marketing approaches. The design and marketing approach depends upon notions of an imagined past where life in a place shaped like a traditional village was better and more socially sustainable than modern urban spaces. The appropriation of this urban village concept has been criticised as a shallow marketing ploy. The translation and applicability of the urban village model across time and space is therefore contentious. KGUV was considered both in terms of its design and marketing and in terms of a reading of the actual use of this master planned place. Central to this analysis is the figure of the boundary and related themes of social heterogeneity, inclusion and exclusion. The refraction of history in the site is also an important theme. An interpretive archaeological approach was used overall as a novel method to derive this analysis.

Speaking to each other at last? the ghost of tv past, present and to come...

John Hartley discusses TV past, present and future and concludes that 'This brave new world does have a couple of dystopian elements. One is that no-one knows how to fund non-universal TV production. Another is that any future 'imagined community' will have to get used to the fact that most people aren't inside it.

Narrative on the "Compliance and Regulatory Journal" : past, present and future

A conversation over a cup of coffee in late 2005 between Australasian Compliance Institute members Bill Dee and Dr Len Gainsford quickly turned to previously unsuccessful attempts to start a professional journal about compliance. There were two main issue - the difficultly in getting a professional journal off the ground and then sustaining a continuous flow of quality contributions. As practitioners, Bill and Len knew there was a considerable amount of 'thought and practice leadership' compliance material out there but they also knew that such material had not been presented in a relevant and interesting way. A foolish thought arose - could we start a professional journal that practitioners might actually read and use?

Non-motorised public transport : the past, the present, the future

Non-motorized public transport (NMPT) involves cycle-powered vehicles that carry several passengers and a small amount of goods; and provide flexible hail-and-ride services. Effectively they are non-motorized taxis. NMPT is widespread in developing countries, where it caters for a wide range of mobility needs. Common forms include cycle-rickshaw (Bangladesh, India), becak (Indonesia), cyclos (Vietnam, Cambodia), bicitaxi (Columbia, Cuba). Over the last 10-15 years there has also been a re-emergence of NMPT in the form of pedicabs in many developed countries because of the operating flexibility of NMPT, its eco-sustainability, and its ability to operate where use of motorized vehicles is restricted. In particular, in cities such as Berlin, London, New York and Vancouver, pedicabs are making the transition from ‘novelty’ to ‘serious’ transport mode. This is creating new transport policy/planning questions about pedicab operation and integration. This paper examines the phenomenon of NMPT and where it is heading. It uses case studies from Asia/Latin America and Europe/North America to examine emerging NMPT issues and possible responses, and how this may affect NMPT in Australia and New Zealand where it is still somewhat a ‘novelty’ but has potential as both an opportunity and a challenge.

Algebraic analysis of small scale LEX-BES

This paper examines the algebraic cryptanalysis of small scale variants of the LEX-BES. LEX-BES is a stream cipher based on the Advanced Encryption Standard (AES) block cipher. LEX is a generic method proposed for constructing a stream cipher from a block cipher, initially introduced by Biryukov at eSTREAM, the ECRYPT Stream Cipher project in 2005. The Big Encryption System (BES) is a block cipher introduced at CRYPTO 2002 which facilitates the algebraic analysis of the AES block cipher. In this paper, experiments were conducted to find solution of the equation system describing small scale LEX-BES using Gröbner Basis computations. This follows a similar approach to the work by Cid, Murphy and Robshaw at FSE 2005 that investigated algebraic cryptanalysis on small scale variants of the BES. The difference between LEX-BES and BES is that due to the way the keystream is extracted, the number of unknowns in LEX-BES equations is fewer than the number in BES. As far as the author knows, this attempt is the first at creating solvable equation systems for stream ciphers based on the LEX method using Gröbner Basis computations.