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.

Scaffolding children’s robot building and programming activities

Since 2001 the School of Information Technology and Electrical Engineering (ITEE) at the University of Queensland has been involved in RoboCupJunior activities aimed at providing children with the Robot building and programming knowledge they need to succeed in RoboCupJunior competitions. These activities include robotics workshops, the organization of the State-wide RoboCupJunior competition, and consultation on all matters robotic with schools and government organizations. The activities initiated by ITEE have succeeded in providing children with the scaffolding necessary to become competent, independent robot builders and programmers. Results from state, national and international competitions suggest that many of the children who participate in the activities supported by ITEE are subsequently able to purpose- build robots to effectively compete in RoboCupJunior competitions. As a result of the scaffolding received within workshops children are able to think deeply and creatively about their designs, and to critique their designs in order to make the best possible creation in an effort to win.

A programming language for software components

Component software has many benefits, most notably increased software re-use; however, the component software process places heavy burdens on programming language technology, which modern object-oriented programming languages do not address. In particular, software components require specifications that are both sufficiently expressive and sufficiently abstract, and, where possible, these specifications should be checked formally by the programming language. This dissertation presents a programming language called Mentok that provides two novel programming language features enabling improved specification of stateful component roles. Negotiable interfaces are interface types extended with protocols, and allow specification of changing method availability, including some patterns of out-calls and re-entrance. Type layers are extensions to module signatures that allow specification of abstract control flow constraints through the interfaces of a component-based application. Development of Mentok's unique language features included creation of MentokC, the Mentok compiler, and formalization of key properties of Mentok in mini-languages called MentokP and MentokL.

Multi-linear strategies for (re)presenting the complexity of young people in research

Within the current climate of unpredictability and constant change, young people at school are faced with a multitude of choices and contradictory influences. In this article, I argue that (re)presentations of young people in youth research need to reflect the complexity and multiplicity of their lives and changing priorities, and I attempt to (re)present a small group of young people in this particular milieu. I illustrate some of the competing influences in their lives, and I outline some specific strategies that are useful for (re)presenting these contextual worlds. The strategies I advocate disrupt the homogenous representations of ‘youth’ as a developmental phase and instead reflect the diverse spheres of influence which shape their subjectivities and practices.

Vision based control for fixed wing UAVs inspecting locally linear infrastructure using skid-to-turn maneuvers

The following paper proposes a novel application of Skid-to-Turn maneuvers for fixed wing Unmanned Aerial Vehicles (UAVs) inspecting locally linear infrastructure. Fixed wing UAVs, following the design of manned aircraft, commonly employ Bank-to-Turn ma- neuvers to change heading and thus direction of travel. Whilst effective, banking an aircraft during the inspection of ground based features hinders data collection, with body fixed sen- sors angled away from the direction of turn and a panning motion induced through roll rate that can reduce data quality. By adopting Skid-to-Turn maneuvers, the aircraft can change heading whilst maintaining wings level flight, thus allowing body fixed sensors to main- tain a downward facing orientation. An Image-Based Visual Servo controller is developed to directly control the position of features as captured by onboard inspection sensors. This improves on the indirect approach taken by other tracking controllers where a course over ground directly above the feature is assumed to capture it centered in the field of view. Performance of the proposed controller is compared against that of a Bank-to-Turn tracking controller driven by GPS derived cross track error in a simulation environment developed to replicate the field of view of a body fixed camera.

Coordinated road-junction traffic control by dynamic programming

This paper presents a novel approach to road-traffic control for interconnected junctions. With a local fuzzy-logic controller (FLC) installed at each junction, a dynamic-programming (DP) technique is proposed to derive the green time for each phase in a traffic-light cycle. Coordination parameters from the adjacent junctions are also taken into consideration so that organized control is extended beyond a single junction. Instead of pursuing the absolute optimization of traffic delay, this study examines a practical approach to enable the simple implementation of coordination among junctions, while attempting to reduce delays, if possible. The simulation results show that the delay per vehicle can be substantially reduced, particularly when the traffic demand reaches the junction capacity. The implementation of this controller does not require complicated or demanding hardware, and such simplicity makes it a useful tool for offline studies or realtime control purposes.

Non-linear oscillations assessment of the distribution static compensator operating in voltage control mode

This article deals with the non-linear oscillations assessment of a distribution static comensator ooperating in voltage control mode using the bifurcation theory. A mathematical model of the distribution static compensator in the voltage control mode to carry out the bifurcation analysis is derived. The stabiity regions in the Thevein equivalent plane are computed. In addition, the stability regions in the control gains space, as well as the contour lines for different Floquet multipliers are computed. The AC and DC capacitor impacts on the stability are analyzed through the bifurcation theory. The observations are verified through simulaation studies. The computation of the stability region allows the assessment of the stable operating zones for a power system that includes a distribution static compensator operating in the voltage mode.

Parallel linear system solution and its application to railway power network simulation

The Streaming SIMD extension (SSE) is a special feature embedded in the Intel Pentium III and IV classes of microprocessors. It enables the execution of SIMD type operations to exploit data parallelism. This article presents improving computation performance of a railway network simulator by means of SSE. Voltage and current at various points of the supply system to an electrified railway line are crucial for design, daily operation and planning. With computer simulation, their time-variations can be attained by solving a matrix equation, whose size mainly depends upon the number of trains present in the system. A large coefficient matrix, as a result of congested railway line, inevitably leads to heavier computational demand and hence jeopardizes the simulation speed. With the special architectural features of the latest processors on PC platforms, significant speed-up in computations can be achieved.

A parallel solution to linear systems

Streaming SIMD Extensions (SSE) is a unique feature embedded in the Pentium III and IV classes of microprocessors. By fully exploiting SSE, parallel algorithms can be implemented on a standard personal computer and a theoretical speedup of four can be achieved. In this paper, we demonstrate the implementation of a parallel LU matrix decomposition algorithm for solving linear systems with SSE and discuss advantages and disadvantages of this approach based on our experimental study.

Parallel solution for railway power network simulation

The Streaming SIMD extension (SSE) is a special feature that is available in the Intel Pentium III and P4 classes of microprocessors. As its name implies, SSE enables the execution of SIMD (Single Instruction Multiple Data) operations upon 32-bit floating-point data therefore, performance of floating-point algorithms can be improved. In electrified railway system simulation, the computation involves the solving of a huge set of simultaneous linear equations, which represent the electrical characteristic of the railway network at a particular time-step and a fast solution for the equations is desirable in order to simulate the system in real-time. In this paper, we present how SSE is being applied to the railway network simulation.

The Spartan-3E Tutorial 1 : Introduction to FPGA Programming, Version 1.0

This tutorial is designed to help new users become familiar with using the Spartan-3E board. The tutorial steps through the following: writing a small program in VHDL which carries out simple combinational logic; connecting the program inputs and outputs to the switches, buttons and LEDs on the Spartan-3E board; and downloading the program to the Spartan-3E board using the Project Navigator software.