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.

Candidate metastasis suppressor genes uncovered by array comparative genomic hybridization in a mouse allograft model of prostate cancer.

Background The purpose of this study was to identify candidate metastasis suppressor genes from a mouse allograft model of prostate cancer (NE-10). This allograft model originally developed metastases by twelve weeks after implantation in male athymic nude mice, but lost the ability to metastasize after a number of in vivo passages. We performed high resolution array comparative genomic hybridization on the metastasizing and non-metastasizing allografts to identify chromosome imbalances that differed between the two groups of tumors. Results This analysis uncovered a deletion on chromosome 2 that differed between the metastasizing and non-metastasizing tumors. Bioinformatics filters were employed to mine this region of the genome for candidate metastasis suppressor genes. Of the 146 known genes that reside within the region of interest on mouse chromosome 2, four candidate metastasis suppressor genes (Slc27a2, Mall, Snrpb, and Rassf2) were identified. Quantitative expression analysis confirmed decreased expression of these genes in the metastasizing compared to non-metastasizing tumors. Conclusion This study presents combined genomics and bioinformatics approaches for identifying potential metastasis suppressor genes. The genes identified here are candidates for further studies to determine their functional role in inhibiting metastases in the NE-10 allograft model and human prostate cancer.

Performance evaluation of an adaptive travel time prediction model

This paper presents a travel time prediction model and evaluates its performance and transferability. Advanced Travelers Information Systems (ATIS) are gaining more and more importance, increasing the need for accurate, timely and useful information to the travelers. Travel time information quantifies the traffic condition in an easy to understand way for the users. The proposed travel time prediction model is based on an efficient use of nearest neighbor search. The model is calibrated for optimal performance using Genetic Algorithms. Results indicate better performance by using the proposed model than the presently used naïve model.

Cluster-based network model for time-course gene expression data

We propose a model-based approach to unify clustering and network modeling using time-course gene expression data. Specifically, our approach uses a mixture model to cluster genes. Genes within the same cluster share a similar expression profile. The network is built over cluster-specific expression profiles using state-space models. We discuss the application of our model to simulated data as well as to time-course gene expression data arising from animal models on prostate cancer progression. The latter application shows that with a combined statistical/bioinformatics analyses, we are able to extract gene-to-gene relationships supported by the literature as well as new plausible relationships.

Integration of a road traffic noise model (ASJ) and traffic simulation (AVENUE) for a built-up area

A road traffic noise prediction model (ASJ MODEL-1998) has been integrated with a road traffic simulator (AVENUE) to produce the Dynamic areawide Road traffic NoisE simulator-DRONE. This traffic-noise-GIS based integrated tool is upgraded to predict noise levels in built-up areas. The integration of traffic simulation with a noise model provides dynamic access to traffic flow characteristics and hence automated and detailed predictions of traffic noise. The prediction is not only on the spatial scale but also on temporal scale. The linkage with GIS gives a visual representation to noise pollution in the form of dynamic areawide traffic noise contour maps. The application of DRONE on a real world built-up area is also presented.

Tactical driver lane change model using forward search

This paper describes the development and evaluation of a tactical lane change model using the forward search algorithm, for use in a traffic simulator. The tactical lane change model constructs a set of possible choices of near-term maneuver sequences available to the driver and selects the lane change action at the present time to realize the best maneuver plan. Including near term maneuver planning in the driver behavior model can allow a better representation of the complex interactions in situations such as a weaving section and high-occupancy vehicle (HOV) lane systems where drivers must weave across several lanes in order to access the HOV lanes. To support the investigation, a longitudinal control model and a basic lane change model were also analyzed. The basic lane change model is similar to those used by today's commonly-used traffic simulators. Parameters in all models were best-fit estimated for selected vehicles from a real-world freeway vehicle trajectory data set. The best-fit estimation procedure minimizes the discrepancy between the model vehicle and real vehicle's trajectories. With the best fit parameters, the proposed tactical lane change model gave a better overall performance for a greater number of cases than the basic lane change model.