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.

Algebraic analysis of small Scale LEX-BES

This work 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 article, experiments were conducted to find solutions of equation systems 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 authors know, this attempt is the first at creating solvable equation systems for stream ciphers based on the LEX method using Gröbner Basis computations.

Optimization problems for controlled mechanical systems : bridging the gap between theory and application

Mechanical control systems have become a part of our everyday life. Systems such as automobiles, robot manipulators, mobile robots, satellites, buildings with active vibration controllers and air conditioning systems, make life easier and safer, as well as help us explore the world we live in and exploit it’s available resources. In this chapter, we examine a specific example of a mechanical control system; the Autonomous Underwater Vehicle (AUV). Our contribution to the advancement of AUV research is in the area of guidance and control. We present innovative techniques to design and implement control strategies that consider the optimization of time and/or energy consumption. Recent advances in robotics, control theory, portable energy sources and automation increase our ability to create more intelligent robots, and allows us to conduct more explorations by use of autonomous vehicles. This facilitates access to higher risk areas, longer time underwater, and more efficient exploration as compared to human occupied vehicles. The use of underwater vehicles is expanding in every area of ocean science. Such vehicles are used by oceanographers, archaeologists, geologists, ocean engineers, and many others. These vehicles are designed to be agile, versatile and robust, and thus, their usage has gone from novelty to necessity for any ocean expedition.

A geometric approach to trajectory design for an autonomous underwater vehicle : surveying the bulbous bow of a ship

In this paper, we present a control strategy design technique for an autonomous underwater vehicle based on solutions to the motion planning problem derived from differential geometric methods. The motion planning problem is motivated by the practical application of surveying the hull of a ship for implications of harbor and port security. In recent years, engineers and researchers have been collaborating on automating ship hull inspections by employing autonomous vehicles. Despite the progresses made, human intervention is still necessary at this stage. To increase the functionality of these autonomous systems, we focus on developing model-based control strategies for the survey missions around challenging regions, such as the bulbous bow region of a ship. Recent advances in differential geometry have given rise to the field of geometric control theory. This has proven to be an effective framework for control strategy design for mechanical systems, and has recently been extended to applications for underwater vehicles. Advantages of geometric control theory include the exploitation of symmetries and nonlinearities inherent to the system. Here, we examine the posed inspection problem from a path planning viewpoint, applying recently developed techniques from the field of differential geometric control theory to design the control strategies that steer the vehicle along the prescribed path. Three potential scenarios for surveying a ship?s bulbous bow region are motivated for path planning applications. For each scenario, we compute the control strategy and implement it onto a test-bed vehicle. Experimental results are analyzed and compared with theoretical predictions.

A geometrical analysis of trajectory design for underwater vehicles

Designing trajectories for a submerged rigid body motivates this paper. Two approaches are addressed: the time optimal approach and the motion planning ap- proach using concatenation of kinematic motions. We focus on the structure of singular extremals and their relation to the existence of rank-one kinematic reduc- tions; thereby linking the optimization problem to the inherent geometric frame- work. Using these kinematic reductions, we provide a solution to the motion plan- ning problem in the under-actuated scenario, or equivalently, in the case of actuator failures. We finish the paper comparing a time optimal trajectory to one formed by concatenation of pure motions.

A geometrical approach to the motion planning problem for a submerged rigid body

The main focus of this paper is the motion planning problem for a deeply submerged rigid body. The equations of motion are formulated and presented by use of the framework of differential geometry and these equations incorporate external dissipative and restoring forces. We consider a kinematic reduction of the affine connection control system for the rigid body submerged in an ideal fluid, and present an extension of this reduction to the forced affine connection control system for the rigid body submerged in a viscous fluid. The motion planning strategy is based on kinematic motions; the integral curves of rank one kinematic reductions. This method is of particular interest to autonomous underwater vehicles which can not directly control all six degrees of freedom (such as torpedo shaped AUVs) or in case of actuator failure (i.e., under-actuated scenario). A practical example is included to illustrate our technique.

A first extension of geometric control theory to underwater vehicles

This paper serves as a first study on the implementation of control strategies developed using a kinematic reduction onto test bed autonomous underwater vehicles (AUVs). The equations of motion are presented in the framework of differential geometry, including external dissipative forces, as a forced affine connection control system. We show that the hydrodynamic drag forces can be included in the affine connection, resulting in an affine connection control system. The definitions of kinematic reduction and decoupling vector field are thus extended from the ideal fluid scenario. Control strategies are computed using this new extension and are reformulated for implementation onto a test-bed AUV. We compare these geometrically computed controls to time and energy optimal controls for the same trajectory which are computed using a previously developed algorithm. Through this comparison we are able to validate our theoretical results based on the experiments conducted using the time and energy efficient strategies.

Decoupled trajectory planning for a submerged rigid body subject to dissipative and potential forces

This paper studies the practical but challenging problem of motion planning for a deeply submerged rigid body. Here, we formulate the dynamic equations of motion of a submerged rigid body under the architecture of differential geometric mechanics and include external dissipative and potential forces. The mechanical system is represented as a forced affine-connection control system on the configuration space SE(3). Solutions to the motion planning problem are computed by concatenating and reparameterizing the integral curves of decoupling vector fields. We provide an extension to this inverse kinematic method to compensate for external potential forces caused by buoyancy and gravity. We present a mission scenario and implement the theoretically computed control strategy onto a test-bed autonomous underwater vehicle. This scenario emphasizes the use of this motion planning technique in the under-actuated situation; the vehicle loses direct control on one or more degrees of freedom. We include experimental results to illustrate our technique and validate our method.

Geometric Control Theory and its Application to Underwater Vehicles

This dissertation is based on theoretical study and experiments which extend geometric control theory to practical applications within the field of ocean engineering. We present a method for path planning and control design for underwater vehicles by use of the architecture of differential geometry. In addition to the theoretical design of the trajectory and control strategy, we demonstrate the effectiveness of the method via the implementation onto a test-bed autonomous underwater vehicle. Bridging the gap between theory and application is the ultimate goal of control theory. Major developments have occurred recently in the field of geometric control which narrow this gap and which promote research linking theory and application. In particular, Riemannian and affine differential geometry have proven to be a very effective approach to the modeling of mechanical systems such as underwater vehicles. In this framework, the application of a kinematic reduction allows us to calculate control strategies for fully and under-actuated vehicles via kinematic decoupled motion planning. However, this method has not yet been extended to account for external forces such as dissipative viscous drag and buoyancy induced potentials acting on a submerged vehicle. To fully bridge the gap between theory and application, this dissertation addresses the extension of this geometric control design method to include such forces. We incorporate the hydrodynamic drag experienced by the vehicle by modifying the Levi-Civita affine connection and demonstrate a method for the compensation of potential forces experienced during a prescribed motion. We present the design method for multiple different missions and include experimental results which validate both the extension of the theory and the ability to implement control strategies designed through the use of geometric techniques. By use of the extension presented in this dissertation, the underwater vehicle application successfully demonstrates the applicability of geometric methods to design implementable motion planning solutions for complex mechanical systems having equal or fewer input forces than available degrees of freedom. Thus, we provide another tool with which to further increase the autonomy of underwater vehicles.

Controlling a submerged rigid body : a geometric analysis

In this paper we analyze the equations of motion of a submerged rigid body. Our motivation is based on recent developments done in trajectory design for this problem. Our goal is to relate some properties of singular extremals to the existence of decoupling vector fields. The ideas displayed in this paper can be viewed as a starting point to a geometric formulation of the trajectory design problem for mechanical systems with potential and external forces.

Geometry‐specified troposphere decorrelation for subcentimeter real‐time kinematic solutions over long baselines

Real‐time kinematic (RTK) GPS techniques have been extensively developed for applications including surveying, structural monitoring, and machine automation. Limitations of the existing RTK techniques that hinder their applications for geodynamics purposes are twofold: (1) the achievable RTK accuracy is on the level of a few centimeters and the uncertainty of vertical component is 1.5–2 times worse than those of horizontal components and (2) the RTK position uncertainty grows in proportional to the base‐torover distances. The key limiting factor behind the problems is the significant effect of residual tropospheric errors on the positioning solutions, especially on the highly correlated height component. This paper develops the geometry‐specified troposphere decorrelation strategy to achieve the subcentimeter kinematic positioning accuracy in all three components. The key is to set up a relative zenith tropospheric delay (RZTD) parameter to absorb the residual tropospheric effects and to solve the established model as an ill‐posed problem using the regularization method. In order to compute a reasonable regularization parameter to obtain an optimal regularized solution, the covariance matrix of positional parameters estimated without the RZTD parameter, which is characterized by observation geometry, is used to replace the quadratic matrix of their “true” values. As a result, the regularization parameter is adaptively computed with variation of observation geometry. The experiment results show that new method can efficiently alleviate the model’s ill condition and stabilize the solution from a single data epoch. Compared to the results from the conventional least squares method, the new method can improve the longrange RTK solution precision from several centimeters to the subcentimeter in all components. More significantly, the precision of the height component is even higher. Several geosciences applications that require subcentimeter real‐time solutions can largely benefit from the proposed approach, such as monitoring of earthquakes and large dams in real‐time, high‐precision GPS leveling and refinement of the vertical datum. In addition, the high‐resolution RZTD solutions can contribute to effective recovery of tropospheric slant path delays in order to establish a 4‐D troposphere tomography.

Geometry vs appearance for discriminating between posed and spontaneous emotions

Spontaneous facial expressions differ from posed ones in appearance, timing and accompanying head movements. Still images cannot provide timing or head movement information directly. However, indirectly the distances between key points on a face extracted from a still image using active shape models can capture some movement and pose changes. This information is superposed on information about non-rigid facial movement that is also part of the expression. Does geometric information improve the discrimination between spontaneous and posed facial expressions arising from discrete emotions? We investigate the performance of a machine vision system for discrimination between posed and spontaneous versions of six basic emotions that uses SIFT appearance based features and FAP geometric features. Experimental results on the NVIE database demonstrate that fusion of geometric information leads only to marginal improvement over appearance features. Using fusion features, surprise is the easiest emotion (83.4% accuracy) to be distinguished, while disgust is the most difficult (76.1%). Our results find different important facial regions between discriminating posed versus spontaneous version of one emotion and classifying the same emotion versus other emotions. The distribution of the selected SIFT features shows that mouth is more important for sadness, while nose is more important for surprise, however, both the nose and mouth are important for disgust, fear, and happiness. Eyebrows, eyes, nose and mouth are important for anger.