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.

State convergence and keyspace reduction of the mixer stream cipher

This paper presents an analysis of the stream cipher Mixer, a bit-based cipher with structural components similar to the well-known Grain cipher and the LILI family of keystream generators. Mixer uses a 128-bit key and 64-bit IV to initialise a 217-bit internal state. The analysis is focused on the initialisation function of Mixer and shows that there exist multiple key-IV pairs which, after initialisation, produce the same initial state, and consequently will generate the same keystream. Furthermore, if the number of iterations of the state update function performed during initialisation is increased, then the number of distinct initial states that can be obtained decreases. It is also shown that there exist some distinct initial states which produce the same keystream, resulting in a further reduction of the effective key space

Distinguishing attack on SOBER-128 with linear masking

We present a distinguishing attack against SOBER-128 with linear masking. We found a linear approximation which has a bias of 2^− − 8.8 for the non-linear filter. The attack applies the observation made by Ekdahl and Johansson that there is a sequence of clocks for which the linear combination of some states vanishes. This linear dependency allows that the linear masking method can be applied. We also show that the bias of the distinguisher can be improved (or estimated more precisely) by considering quadratic terms of the approximation. The probability bias of the quadratic approximation used in the distinguisher is estimated to be equal to O(2^− − 51.8), so that we claim that SOBER-128 is distinguishable from truly random cipher by observing O(2^103.6) keystream words.

Cryptanalysis of Tav-128 Hash Function

Many RFID protocols use cryptographic hash functions for their security. The resource constrained nature of RFID systems forces the use of light weight cryptographic algorithms. Tav-128 is one such 128-bit light weight hash function proposed by Peris-Lopez et al. for a low-cost RFID tag authentication protocol. Apart from some statistical tests for randomness by the designers themselves, Tav-128 has not undergone any other thorough security analysis. Based on these tests, the designers claimed that Tav-128 does not posses any trivial weaknesses. In this article, we carry out the first third party security analysis of Tav-128 and show that this hash function is neither collision resistant nor second preimage resistant. Firstly, we show a practical collision attack on Tav-128 having a complexity of 237 calls to the compression function and produce message pairs of arbitrary length which produce the same hash value under this hash function. We then show a second preimage attack on Tav-128 which succeeds with a complexity of 262 calls to the compression function. Finally, we study the constituent functions of Tav-128 and show that the concatenation of nonlinear functions A and B produces a 64-bit permutation from 32-bit messages. This could be a useful light weight primitive for future RFID protocols.

Low probability differentials and the cryptanalysis of full-round CLEFIA-128

So far, low probability differentials for the key schedule of block ciphers have been used as a straightforward proof of security against related-key differential analysis. To achieve resistance, it is believed that for cipher with k-bit key it suffices the upper bound on the probability to be 2− k . Surprisingly, we show that this reasonable assumption is incorrect, and the probability should be (much) lower than 2− k . Our counter example is a related-key differential analysis of the well established block cipher CLEFIA-128. We show that although the key schedule of CLEFIA-128 prevents differentials with a probability higher than 2− 128, the linear part of the key schedule that produces the round keys, and the Feistel structure of the cipher, allow to exploit particularly chosen differentials with a probability as low as 2− 128. CLEFIA-128 has 214 such differentials, which translate to 214 pairs of weak keys. The probability of each differential is too low, but the weak keys have a special structure which allows with a divide-and-conquer approach to gain an advantage of 27 over generic analysis. We exploit the advantage and give a membership test for the weak-key class and provide analysis of the hashing modes. The proposed analysis has been tested with computer experiments on small-scale variants of CLEFIA-128. Our results do not threaten the practical use of CLEFIA.

Portrait of Lili Meyerhof nee Dienemann on her 90th Birthday; Johannesburg, South Africa.

Digital Image

Autographed portrait of Albert Einstein with Alice (Lili) Kahler-Loewy Portraits Groups

Handwritten dedication signed by Einstein

Fungal Planet description sheets: 128-153

Novel species of microfungi described in the present study include the following from Australia: Catenulostroma corymbiae from Corymbia, Devriesia stirlingiae from Stirlingia, Penidiella carpentariae from Carpentaria, Phaeococcomyces eucalypti from Eucalyptus, Phialophora livistonae from Livistona, Phyllosticta aristolochiicola from Aristolochia, Clitopilus austroprunulus on sclerophyll forest litter of Eucalyptus regnans and Toxicocladosporium posoqueriae from Posoqueria. Several species are also described from South Africa, namely: Ceramothyrium podocarpi from Podocarpus, Cercospora chrysanthemoides from Chrysanthemoides, Devriesia shakazului from Aloe, Penidiella drakensbergensis from Protea, Strelitziana cliviae from Clivia and Zasmidium syzygii from Syzygium. Other species include Bipolaris microstegii from Microstegium and Synchaetomella acerina from Acer (USA), Brunneiapiospora austropalmicola from Rhopalostylis (New Zealand), Calonectria pentaseptata from Eucalyptus and Macadamia (Vietnam), Ceramothyrium melastoma from Melastoma (Indonesia), Collembolispora aristata from stream foam (Czech Republic), Devriesia imbrexigena from glazed decorative tiles (Portugal), Microcyclospora rhoicola from Rhus (Canada), Seiridium phylicae from Phylica (Tristan de Cunha, Inaccessible Island), Passalora lobeliaefistulosis from Lobelia (Brazil) and Zymoseptoria verkleyi from Poa (The Netherlands). Valsalnicola represents a new ascomycete genus from Alnus (Austria) and Parapenidiella a new hyphomycete genus from Eucalyptus (Australia). Morphological and culture characteristics along with ITS DNA barcodes are also provided. © 2012 Nationaal Herbarium Nederland & Centraalbureau voor Schimmelcultures.

Sapientia, 1978, Vol. XXXIII, nº 128 (número completo)

Contenido: Vida del espíritu / Octavio N. Derisi – Tomás de Aquino y las tres esferas del espíritu / Ángel González Álvarez – Función de la razón en la ética / Teófilo Urdánoz – Entre la ontología y la antropología filosófica / Diego F. Pró -- Notas y comentarios -- Bibliografía

Diário da Constituinte [gravação de vídeo] : [programa n. 128]

Os constituintes avaliam o andamento da Assembleia Nacional Constituinte e destacam a necessidade de compactar o texto elaborado pela Comissão de Sistematização. Francisco Pinto (PMDB-BA) afirma que a nova Carta não pode ser conjuntural. Genebaldo Correia (PMDB-BA) defende uma Constituição de consenso, que represente a média da sociedade brasileira. Cristovam Chiaradia (PFL-MG) relata que devemos ter uma Constituição humana que contemple todas as classes sociais. Oswaldo Macedo (PMDB-PR) comenta a participação popular na Constituinte. Gonzaga Patriota (PMDB-PE) afirma que a população participou de muitos artigos da Constituição e acredita numa Carta duradoura. Celso Furtado, Ministro da Cultura, ressalta a importância da participação dos brasileiros neste momento. Carlos Eduardo Novaes, jornalista, conclama o povo a participar da Assembleia Nacional Constituinte (ANC). Na sessão O Povo Pergunta, cidadão quer saber o que a Constituinte está fazendo para melhorar a justiça no país. Leite Chaves (PMDB-PR) responde que a justiça será mais rápida, mais barata e mais próxima do povo, pois as cortes serão especializadas e alcançarão as demandas da sociedade.

The influence of blue-green algae on development of the zooplankton. [Translation of: Byull.mosk.Obshch.Ispyt.Prir.(Biol.) 67, 128-131, 1962]

Many have observed the reduction of the quantity of zooplankton in the presence of water blooms. It is known that in seas zooplankton as it were avoids places of accumulation of blue-green algae. By observations on one of the tributaries of the Rybinsk reservoir - the River Shumorovka - the authors tried by simultaneous collections to trace the changes in numbers, not only of zoo- and phytoplankton but also of bacteria. The plankton was collected by quantitative nets with suitable numbers of gauze and bacteria were taken account of by the method of direct calculation on membrane filters. It can be seen that the development of blue-green algae appears as an important factor, determining not only the intensity but also the direction of the process of production of zooplankton.