É crescente a necessidade de prover segurança às informações trocadas nos mais diversos tipos de redes. No entanto, redes amplamente dependentes de dispositivos com recursos limitados (como sensores, tokens e smart cards) apresentam um desafio importante: a reduzida disponibilidade de memória, capacidade de processamento e (principalmente) energia dos mesmos dificulta a utilização de alguns dos principais algoritmos criptográficos considerados seguros atualmente. É neste contexto que se insere o presente documento, que não apenas apresenta uma pesquisa envolvendo projeto e análise de algoritmos criptográficos, mas também descreve um novo algoritmo simétrico denominado CURUPIRA. Esta cifra de bloco baseia-se na metodologia conhecida como Estratégia de Trilha Larga e foi projetada especialmente para ambientes onde existe escassez de recursos. O CURUPIRA possui estrutura involutiva, o que significa que os processos de encriptação e decriptação diferem apenas na seqüência da geração de chaves, dispensando a necessidade de algoritmos distintos para cada uma destas operações. Além disto, são propostas duas formas diferentes para seu algoritmo de geração de chaves, cada qual mais focada em segurança ou em desempenho. Entretanto, ambas as formas caracterizam-se pela possibilidade de computação das sub-chaves de round no momento de sua utilização, em qualquer ordem, garantindo uma operação com reduzido uso de memória RAM. / The need for security is a great concern in any modern network. However, networks that are highly dependent of constrained devices (such as sensors, tokens and smart cards) impose a difficult challenge: their reduced availability of memory, processing power and (more importantly) energy hinders the deployment of many important cryptographic algorithms known to be secure. In this context, this document not only presents the research involving the design and analysis of cryptographic algorithms, but also proposes a new symmetric block cipher named CURUPIRA. The CURUPIRA follows the methodology known as theWide Trail Strategy and was specially developed having constrained platforms in mind. It displays an involutional structure, which means that the encryption and decryption processes differ only in the key schedule and, thus, there is no need to implement them separately. Also, two distinct scheduling algorithms are proposed, whose main focus are either on tight security or improved performance. In spite of this difference, both of them allow the keys to be computed on-the-fly, in any desired order, assuring a reduced consumption of RAM memory during their operation.

Design and analysis of lightweight block ciphers have become more popular due to the fact that the future use of block ciphers in ubiquitous devices is generally assumed to be extensive. In this respect, several lightweight block ciphers are designed, of which HIGHT is proposed by Hong et al. at CHES 2006 as a constrained hardware oriented block cipher. HIGHT is shown to be highly convenient for extremely constrained devices such as RFID tags and sensor networks and it became a standard encryption algorithm in South Korea. Impossible differential cryptanalysis is a technique discovered by Biham et al. and is applied to many block ciphers including Skipjack, IDEA, Khufu, Khafre, HIGHT, AES, Serpent, CRYPTON, Twofish, TEA, XTEA and ARIA. The security of HIGHT against impossible differential attacks is investigated both by Hong et al. and Lu: An 18-round impossible differential attack is given in the proposal of HIGHT and Lu improved this result by giving a 25-round impossible differential attack. Moreover, Lu found a 28-round related-key impossible differential attack which is the best known attack on HIGHT. In related-key attacks, the attacker is assumed to know the relation between the keys but not the keys themselves. In this study, we further analyzed the resistance of HIGHT against impossible differential attacks by mounting a new 26-round impossible differential attack and a new 31-round related-key impossible differential attack. Although our results are theoretical in nature, they show new results in HIGHT and reduce its security margin further.

Cryptanalytic methods are very important tools in terms of evaluating the security of block ciphers in a more accurate and reliable way. Differential and linear attacks have been the most effective cryptanalysis methods since the early 1990s. However, as the technology developed and more secure ciphers are designed, these fundamental methods started to be not so efficient. In order to analyze the ciphers, new methods should be introduced. One approach is inventing new techniques that are different from the existing ones. Another approach is extending or combining known cryptanalytic methods to analyze the cipher in a different way. This thesis is a survey of the attacks that are generated by combination of existing techniques and their applications on specific block ciphers. Mentioned attacks are namely differential-linear, differential-bilinear, higher order differential-linear, differential-nonlinear, square-nonlinear, impossible differential and boomerang type attacks.

In this thesis, two finalists of the AES (Advanced Encryption Standard) contest, RC6 developed by Rivest et al, Twofish proposed by Schneier et al, and preceding algorithm of RC6 cipher, RC5, are studied. The strength of ciphers to cryptanalytic attacks is measured according to different criteria. The studied evaluation criteria are the avalanche criterion and its derivations. After theimplementation of the algorithms and the test procedures, they are compared with each other. Different test criteria, including avalanche criterion, avalanche weight distribution (AWD) for randomness of RC5, RC6 and Twofish algorithms are applied / and the S-boxes of the Twofish algorithm are analyzed according to nonlinearity criterion. The avalanche criteria results of RC6 and Twofish are compared with NIST (National Institute of Standards and Technology) Statistical Test Suite results.

The main objective of this thesis is to examine the trade-offs between security and efficiency within symmetric ciphers. This includes the influence that block ciphers have on the new generation of word-based stream ciphers. By incorporating block-cipher like components into their designs, word-based stream ciphers have experienced hundreds-fold improvement in speed over bit-based stream ciphers, without any observable security degradation. The thesis also emphasizes the importance of keying issues in block and stream ciphers, showing that by reusing components of the principal cipher algorithm in the keying algorithm, security can be enhanced without loss of key-agility or expanding footprint in software memory. Firstly, modern block ciphers from four recent cipher competitions are surveyed and categorized according to criteria that includes the high-level structure of the block cipher, the method in which non-linearity is instilled into each round, and the strength of the key schedule. In assessing the last criterion, a classification by Carter [45] is adopted and modified to improve its consistency. The classification is used to demonstrate that the key schedule of the Advanced Encryption Standard (AES) [62] is surprisingly flimsy for a national standard. The claim is supported with statistical evidence that shows the key schedule suffers from bit leakage and lacks sufficient diffusion. The thesis contains a replacement key schedule that reuses components from the cipher algorithm, leveraging existing analysis to improve security, and reducing the cipher's implementation footprint while maintaining key agility. The key schedule is analyzed from the perspective of an efficiency-security tradeoff, showing that the new schedule rectifies an imbalance towards e±ciency present in the original. The thesis contains a discussion of the evolution of stream ciphers, focusing on the migration from bit-based to word-based stream ciphers, from which follows a commensurate improvement in design flexibility and software performance. It examines the influence that block ciphers, and in particular the AES, have had upon the development of word-based stream ciphers. The thesis includes a concise literature review of recent styles of cryptanalytic attack upon stream ciphers. Also, claims are refuted that one prominent word-based stream cipher, RC4, suffers from a bias in the first byte of each keystream. The thesis presents a divide and conquer attack against Alpha1, an irregularly clocked bit-based stream cipher with a 128-bit state. The dominating aspect of the divide and conquer attack is a correlation attack on the longest register. The internal state of the remaining registers is determined by utilizing biases in the clocking taps and launching a guess and determine attack. The overall complexity of the attack is 261 operations with text requirements of 35,000 bits and memory requirements of 2 29.8 bits. MUGI is a 64-bit word-based cipher with a large Non-linear Feedback Shift Register (NLFSR) and an additional non-linear state. In standard benchmarks, MUGI appears to su®er from poor key agility because it is implemented on an architecture for which it is not designed, and because its NLFSR is too large relative to the size of its master key. An unusual feature of its key initialization algorithm is described. A variant of MUGI, entitled MUGI-M, is proposed to enhance key agility, ostensibly without any loss of security. The thesis presents a new word-based stream cipher called Dragon. This cipher uses a large internal NLFSR in conjunction with a non-linear filter to produce 64 bits of keystream in one round. The non-linear filter looks very much like the round function of a typical modern block cipher. Dragon has a native word size of 32 bits, and uses very simple operations, including addition, exclusive-or and s-boxes. Together these ensure high performance on modern day processors such as the Intel Pentium family. Finally, a set of guidelines is provided for designing and implementing symmetric ciphers on modern processors, using the Intel Pentium 4 as a case study. Particular attention is given to understanding the architecture of the processor, including features such as its register set and size, the throughput and latencies of its instruction set, and the memory layouts and speeds. General optimization rules are given, including how to choose fast primitives for use within the cipher. The thesis describes design decisions that were made for the Dragon cipher with respect to implementation on the Intel Pentium 4. Block Ciphers, Word-based Stream Ciphers, Cipher Design, Cipher Implementa- tion, -

Les algorithmes de chiffrement par blocs paramétrables constituent une généralisation des algorithmes de chiffrement par blocs classiques qui, en plus d'une clé et d'un message à chiffrer ou déchiffrer, admettent un paramètre additionnel, nommé tweak en anglais. Le rôle de ce paramètre additionnel est d'apporter une variabilité à l'algorithme de chiffrement, sans qu'il soit nécessaire de changer la clé ou de garder le tweak secret. Ce dernier doit également pouvoir être contrôlé par l'adversaire sans dégradation de la sécurité. Dans cette thèse nous nous intéressons à une classe particulière d'algorithmes de chiffrement par blocs, les algorithmes de chiffrement par blocs à clé alternée. Plusprécisément, nous étudions la sécurité du schéma d'Even-Mansour, qui constitue une abstraction de la structure de ces algorithmes dans le modèle de la permutation aléatoire, et cherchons à rendre ce schéma paramétrable tout en conservant de fortes garanties de sécurité. À cette fin, nous introduisons une nouvelle construction générique, baptiséeTEM, qui remplace les clés de tours de la construction d'Even-Mansour par une valeur qui dépend de la clé et du tweak, et en étudions la sécurité dans deux cas : lorsque le mixage de la clé et du tweak est linéaire ou lorsqu'il est très non-linéaire. Nos preuves de sécurité utilisent la technique des coefficients H, introduite par Jacques Patarin danssa thèse de doctorat, qui permet de transformer des problèmes cryptographiques en problèmes combinatoires sur des groupes finis. / Tweakable block ciphers are a generalization of classical block ciphers which, in addition to a key and a plaintext or a ciphertext, take an additionnal parameter called a tweak. The goal of this new parameter is to bring variability to the block cipher without needing to change the key or to keep the tweak secret. The tweak should also be adversariallycontrollable without sacrificing security. In this thesis we study a particular class of block ciphers, namely key-alternating ciphers. More precisely, we study the security of the Even-Mansour scheme, which is an abstraction of these ciphers in the random permutation model, and seek to bring tweakability to this scheme while keeping strong security guarantees. To this end, we introduce a new generic construction, dubbed TEM, which replaces the round keys from the Even-Mansour construction by a value depending on both the key and the tweak, and study its security in two cases: when the tweak and key mixing is linear or highly non-linear. Our security proofs rely on the H-coefficients technique, a technique introduced by Jacques Patarin in his PhD thesis which transforms cryptographic problems into combinatorial problems in finite groups.