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.

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.

Multi-objective optimisation of bijective s-boxes

In this paper we investigate the heuristic construction of bijective s-boxes that satisfy a wide range of cryptographic criteria including algebraic complexity, high nonlinearity, low autocorrelation and have none of the known weaknesses including linear structures, fixed points or linear redundancy. We demonstrate that the power mappings can be evolved (by iterated mutation operators alone) to generate bijective s-boxes with the best known tradeoffs among the considered criteria. The s-boxes found are suitable for use directly in modern encryption algorithms.

Guidance of aircraft in periodic inspection tasks

This paper presents a guidance approach for aircraft in periodic inspection tasks. The periodic inspection task involves flying to a series of desired fixed points of inspection with specified attitude requirements so that requirements for downward looking sensors, such as cameras, are achieved. We present a solution using a precision guidance law and a bank turn dynamics model. High fidelity simulation studies illustrate the effectiveness of this approach under both ideal (nil-wind) and non-ideal (wind) conditions.

Mapping resilience : A framework for changing cities

Urban centres base their resilience on the ability to evolve and adapt as needed throughout their life. Although constantly developing, changing and subsuming nature for its needs, the current age of environmental awareness requires that cities progress in a more conscious and considered way. While they have become the dominant form of human habitation, there now exists a need to integrate 'green' solutions into urban centres to address social, physical and environmental wellbeing. The means of implementing the vast array of possible solutions without negative impacts is not clear; cities are complex systems, layering meaning, history and cultural memory ‐ they are a manifestation of shared cultural values, and as such, they do not allow a tabula rasa approach of 'blanket' solutions. All around us, cities are continuing to develop and change, and although their form is varied ‐ sprawling cities with density and sustainability problems; or collapsing cities with 'dead' centres and dilapidated districts – a common issue is the resilience of the local identity. The strength or resilience of cities lies in the elements which have become fixed points in the urban structure, giving character and identity to a shared urban experience. These elements need to be identified and either maintained or revitalised. Similarly, the identification of urban elements which can most viably be modified without compromising character and identity of place, will assist in making concrete contributions to increasing both the sustainability and experience of cities, making them more resilient. Through an examination of case studies, this paper suggests a framework to inform urban renewal assessing the widespread elements which generate an urban identity, beyond the traditional approach of heritage conservation for cultural or tourist purposes. The rapid contemporary alteration of urban structures requires an innovative methodology which satisfies on one side the need of new sustainable performances and, on the other, the resilience of the local character.

Security Analysis of Randomize-Hash-then-Sign Digital Signatures

At CRYPTO 2006, Halevi and Krawczyk proposed two randomized hash function modes and analyzed the security of digital signature algorithms based on these constructions. They showed that the security of signature schemes based on the two randomized hash function modes relies on properties similar to the second preimage resistance rather than on the collision resistance property of the hash functions. One of the randomized hash function modes was named the RMX hash function mode and was recommended for practical purposes. The National Institute of Standards and Technology (NIST), USA standardized a variant of the RMX hash function mode and published this standard in the Special Publication (SP) 800-106. In this article, we first discuss a generic online birthday existential forgery attack of Dang and Perlner on the RMX-hash-then-sign schemes. We show that a variant of this attack can be applied to forge the other randomize-hash-then-sign schemes. We point out practical limitations of the generic forgery attack on the RMX-hash-then-sign schemes. We then show that these limitations can be overcome for the RMX-hash-then-sign schemes if it is easy to find fixed points for the underlying compression functions, such as for the Davies-Meyer construction used in the popular hash functions such as MD5 designed by Rivest and the SHA family of hash functions designed by the National Security Agency (NSA), USA and published by NIST in the Federal Information Processing Standards (FIPS). We show an online birthday forgery attack on this class of signatures by using a variant of Dean’s method of finding fixed point expandable messages for hash functions based on the Davies-Meyer construction. This forgery attack is also applicable to signature schemes based on the variant of RMX standardized by NIST in SP 800-106. We discuss some important applications of our attacks and discuss their applicability on signature schemes based on hash functions with ‘built-in’ randomization. Finally, we compare our attacks on randomize-hash-then-sign schemes with the generic forgery attacks on the standard hash-based message authentication code (HMAC).

Security Analysis of salt||password Hashes

Protection of passwords used to authenticate computer systems and networks is one of the most important application of cryptographic hash functions. Due to the application of precomputed memory look up attacks such as birthday and dictionary attacks on the hash values of passwords to find passwords, it is usually recommended to apply hash function to the combination of both the salt and password, denoted salt||password, to prevent these attacks. In this paper, we present the first security analysis of salt||password hashing application. We show that when hash functions based on the compression functions with easily found fixed points are used to compute the salt||password hashes, these hashes are susceptible to precomputed offline birthday attacks. For example, this attack is applicable to the salt||password hashes computed using the standard hash functions such as MD5, SHA-1, SHA-256 and SHA-512 that are based on the popular Davies-Meyer compression function. This attack exposes a subtle property of this application that although the provision of salt prevents an attacker from finding passwords, salts prefixed to the passwords do not prevent an attacker from doing a precomputed birthday attack to forge an unknown password. In this forgery attack, we demonstrate the possibility of building multiple passwords for an unknown password for the same hash value and salt. Interestingly, password||salt (i.e. salts suffixed to the passwords) hashes computed using Davies-Meyer hash functions are not susceptible to this attack, showing the first security gap between the prefix-salt and suffix-salt methods of hashing passwords.

Permanent shift: the topology of Didier Vermeiren's Cariatide à la Pierre

Photographic documentation of sculpture produces significant consequences for the way in which sculptural space is conceived. When viewed as discrete mediums the interaction of the photograph and its sculptural subject is always framed by notions of loss. However, when taken as a composite system, the sculpture-photograph proposes a new ontology of space. In place of the fixity of medium, we can observe a topology at play: a theory drawn from mathematics in which space is understood not as a static field but in terms of properties of connectedness, movement and differentiation. Refracted through the photographic medium, sculpture becomes not a field of fixed points in space, but rather as a fluid set of relations - a continuous sequence of multiple ‘surfaces’, a network of shifting views. This paper will develop a topological account of studio practice through an examination of the work of the contemporary Belgian sculptor Didier Vermeiren (b. 1951). Since the 1980s, Vermeiren has made extensive use of photography in his sculptural practice. By analysing a series of iterations of his work Cariatide à la Pierre (1997-1998), this paper proposes that Vermeiren’s use of photography reveals patterns of connection that expand and complicate the language of sculpture, while also emphasising the broader topology of the artist’s practice as a network of ‘backward glances’ to previous works from the artist’s oeuvre and the art-historical canon. In this context, photography is not simply a method of documentation, but rather a means of revealing the intrinsic condition of sculpture as medium shaped by dynamic patterns of connection and change. In Vermeiren’s work the sculpture-photograph, has a composite identity that exceeds straightforward categories of medium. In their place, we can observe a practice based upon the complex interactions of objects whose ontology is always underpinned by a certain contingency. It is in this fundamental mobility, that the topology of Vermeiren’s practice can be said to rest.

Robust video stabilisation algorithm using feature point selection and delta optical flow

In this study, the authors propose a novel video stabilisation algorithm for mobile platforms with moving objects in the scene. The quality of videos obtained from mobile platforms, such as unmanned airborne vehicles, suffers from jitter caused by several factors. In order to remove this undesired jitter, the accurate estimation of global motion is essential. However it is difficult to estimate global motions accurately from mobile platforms due to increased estimation errors and noises. Additionally, large moving objects in the video scenes contribute to the estimation errors. Currently, only very few motion estimation algorithms have been developed for video scenes collected from mobile platforms, and this paper shows that these algorithms fail when there are large moving objects in the scene. In this study, a theoretical proof is provided which demonstrates that the use of delta optical flow can improve the robustness of video stabilisation in the presence of large moving objects in the scene. The authors also propose to use sorted arrays of local motions and the selection of feature points to separate outliers from inliers. The proposed algorithm is tested over six video sequences, collected from one fixed platform, four mobile platforms and one synthetic video, of which three contain large moving objects. Experiments show our proposed algorithm performs well to all these video sequences.