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.

Model-order selection in Zernike polynomial expansion of corneal surfaces using the efficient detection criterion

Corneal-height data are typically measured with videokeratoscopes and modeled using a set of orthogonal Zernike polynomials. We address the estimation of the number of Zernike polynomials, which is formalized as a model-order selection problem in linear regression. Classical information-theoretic criteria tend to overestimate the corneal surface due to the weakness of their penalty functions, while bootstrap-based techniques tend to underestimate the surface or require extensive processing. In this paper, we propose to use the efficient detection criterion (EDC), which has the same general form of information-theoretic-based criteria, as an alternative to estimating the optimal number of Zernike polynomials. We first show, via simulations, that the EDC outperforms a large number of information-theoretic criteria and resampling-based techniques. We then illustrate that using the EDC for real corneas results in models that are in closer agreement with clinical expectations and provides means for distinguishing normal corneal surfaces from astigmatic and keratoconic surfaces.

Fast hole surface conduction observed for indoline sensitizer dyes immobilized at fluorine-doped tin oxide - TiO2 surfaces

The indoline dyes D102, D131, D149, and D205 have been characterized when adsorved on fluorine-doped tin oxide (FTO) and TiO2 electrode surfaces. Adsorption from 50:50 acetonitrile - tert-butanol onto flourine-doped tin oxide (FTO) allows approximate Langmuirian binding constants of 6.5 x 10(4), 2.01 x 10(3), 2.0 x 10(4), and 1.5 x 10(4) mol-1 dm3, respectively, to be determined. Voltammetric data obtained in acetonitrile/0.1 M NBu4PF6 indicate reversible on-electron oxidation at Emid = 0.94, 0.91, 0.88, and 0.88 V vs Ag/AgCI(3 M KCI), respectively, with dye aggregation (at high coverage) causing additional peak features at more positive potentials. Slow chemical degradation processes and electron transfer catalysis for iodine oxidation were observed for all four oxidezed indolinium cations. When adsorbed onto TiO2 nanoparticle films (ca. 9nm particle diameter and ca.3/um thickness of FTO0, reversible voltammetric responses with Emid = 1.08, 1.156, 0.92 and 0.95 V vs Ag/AgCI(3 M KCI), respectively, suggest exceptionally fast hole hopping diffusion (with Dapp > 5 x 10(-9) m2 s-1) for adsorbed layers of four indoline dyes, presumably due to pie-pie stacking in surface aggregates. Slow dye degradation is shown to affect charge transport via electron hopping. Spectrelectrochemical data for the adsorbed indoline dyes on FTO-TiO2 revealed a red-shift of absorption peaks after oxidation and the presence of a strong charge transfer band in the near-IR region. The implications of the indoline dye reactivity and fast hole mobility for solar cell devices are discussed.

Early osteogenic response of osteoprogenitor cells on modified titanium implant surfaces leads to improved osteogenesis

Background: Implant surface micro-roughness and hydrophilicity are known to improve the osteogenic differentiation potential of osteoprogenitor cells. This study was aimed to determine whether topographically and chemically modified titanium implant surfaces stimulate an initial osteogenic response in osteoprogenitor cells, which leads to their improved osteogenesis. ----- ----- Methods: Statistical analysis of microarray gene expression profiling data available from studies (at 72 hours) on sand-blasted, large grit acid etched (SLA) titanium surfaces was performed. Subsequently, human osteoprogenitor cells were cultured on SLActive (hydrophilic SLA), SLA and polished titanium surfaces for 24 hours, 3 days and 7 days. The expression of BMP2, BMP6, BMP2K, SP1, ACVR1, FZD6, WNT5A, PDLIM7, ITGB1, ITGA2, OCN, OPN, ALP and RUNX2 were studied using qPCR. ----- ----- Results: Several functional clusters related to osteogenesis were highlighted when genes showing statistically significant differences (from microarray data at 72 hours) in expression on SLA surface (compared with control surface) were analysed using DAVID (online tool). This indicates that differentiation begins very early in response to modified titanium surfaces. At 24 hours, ACVR1 (BMP pathway), FZD6 (Wnt pathway) and SP1 (TGF-β pathway) were significantly up-regulated in cultures on the SLActive surface compared to the other surfaces. WNT5A and ITGB1 also showed higher expression on the modified surfaces. Gene expression patterns on Day 3 and Day 7 did not reveal any significant differences.----- ----- Conclusion: These results suggest that the initial molecular response of osteoprogenitor cells to modified titanium surfaces may be responsible for an improved osteogenic response via the BMP and Wnt signalling pathways.