On the Key Schedule of Lightweight Block Ciphers

Key schedules in lightweight block ciphers are often highly simplified, which causes weakness that can be exploited in many attacks. Today it remains an open problem on how to use limited operations to guarantee enough diffusion of key bits in lightweight key schedules. Also, there are few tools special for detecting weakness in the key schedule. In 2013 Huang et al. pointed out that insufficient actual key information (AKI) in computation chains is responsible for many attacks especially the meet-in-the-middle (MITM) attacks. Motivated by this fact, in this paper we develop an efficient (with polynomial time complexity) and effective tool to search the computation chains which involve insufficient AKI for iterated key schedules of lightweight ciphers. The effectiveness of this tool is shown by an application on TWINE-80. Then, we formulate the cause of key bits leakage phenomenon, where the knowledge of subkey bits is leaked or overlapped by other subkey bits in the same computation chain. Based on the interaction of diffusion performed by the key schedule and by the round function, a necessary condition is thus given on how to avoid key bits leakage. Therefore, our work sheds light on the design of lightweight key schedules by guiding how to quickly rule out unreasonable key schedules and maximize the security under limited diffusion.

High performance VLSI architectures implementing strong cryptographic primitives

Feth Allah Cherigui

The main topic of this thesis is related to the state of the art in designing cryptographic primitives from a hardware point of view. A special emphasis is dedicated to low-power/low-energy CMOS design. A set of solutions is proposed including an LFSR based stream cipher with self-synchronizing capabilities, a new memory-less Rijndael block cipher architecture and a public key scheme in the class of discrete logarithm. The former is based on arithmetic in large finite field, mainly Galois extension field GF(2‴). These solutions are droved using low-energy techniques, in order to decrease both the switching activity and the total delay. The fundamental motivation supporting this work, is to demonstrate that practical solutions can be obtained for implementing such complex primitives in large scaled circuits, that arc at once, high performance architectures (low-power, high-speed) and cryptographicaly strong, using the well known trade-off between area-speed or area-power. Security constraint has been duly considered, mainly by increasing the key-size. In this work, we explore the general aspects of designing the above mentioned cryptographic functions. We give an extensive survey of some cryptographic primitives from the hardware point of view and expose their security properties. The thesis favours stream cipher and public-key schemes, as currently the most promising advance to capture the notion of key generation and establishment and data bulk encryption. One contribution is the convenient notation for expressing cryptographic self-synchronizing stream ciphers SSSC schemes and our SSMG proposal, a scheme based on packet fingerprint identification, that relies on keyed cryptographic hash function to achieve the security requirements. We maintain an important distinction between hardware implementation and algorithm's security, because the security of cryptographic primitives cannot be based on mathematically strong functions only but requires an extensive cryptanalysis at different levels including the application. This causes a concern for a formalization of the security of an implemented cryptographic primitive. Nevertheless, while some schemes arc well known to be secure such as DL based public key schemes and enough cryptanalyzed such as the new standard Rijndael, some security aspects of the SSMG are discussed. A part of this work studies the specific aspects related to hardware implementation of Rijndael block cipher, the new standard designed to be a substitute for DES. An efficient architecture is developed targeting FPGA implementation, by simply avoiding memory blocks dedicated to the implementation of S-boxes and replacing them by on-chip forward computation using composite Galois field. This technique helps to reduce considerably the amount of hardware required at the cost of little increase of the switching activity. The main conclusion is that, while security constraint of cryptographic primitives increases the hardware complexity and reduces the performances, practical solutions exist for reducing such complexities while keeping or increasing the level of security. Nevertheless, major open questions remain both for a firm theoretical foundation and the proper cryptanalysis of certain solutions.

EPFL2002

Lightweight Block Ciphers Revisited: Cryptanalysis of Reduced Round PRESENT and HIGHT

Onur Özen, Cihangir Tezcan, Kerem Varici

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 PRESENT and HIGHT are two recently proposed ones by Bogdanov et al. and Hong et al. respectively. In this paper, we propose new attacks on PRESENT and HIGHT. Firstly, we present the first related-key cryptanalysis of 128-bit keyed PRESENT by introducing 17-round related-key rectangle attack with time complexity approximately 2^104 memory accesses. Moreover, we further analyze the resistance of HIGHT against impossible differential attacks by mounting new 26-round impossible differential and 31-round related-key impossible differential attacks where the former requires time complexity of 2^119.53 reduced round HIGHT evaluations and the latter is slightly better than exhaustive search.

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2009

Capacity and Data Complexity in Multidimensional Linear Attack

Jialin Huang, Serge Vaudenay

Multidimensional linear attacks are one of the most powerful variants of linear cryptanalytic techniques now. However, there is no knowledge on the key-dependent capacity and data complexity so far. Their values were assumed to be close to the average value for a vast majority of keys. This assumption is not accurate. In this paper, under a reasonable condition, we explicitly formulate the capacity as a Gamma distribution and the data complexity as an Inverse Gamma distribution, in terms of the average linear probability and the dimension. The capacity distribution is experimentally verified on the 5-round PRESENT. Regarding to complexity, we solve the problem of estimating the average data complexity, which was difficult to estimate because of the existence of zero correlations. We solve the problem of using the median complexity in multidimensional linear attacks, which is an open problem since proposed in Eurocrypt 2011. We also evaluate the difference among the median complexity, the average complexity and a lower bound of the average complexity -- the reciprocal of average capacity. In addition, we estimate more accurately the key equivalent hypothesis, and reveal the fact that the average complexity only provides an accurate estimate for less than half of the keys no matter how many linear approximations are involved. Finally, we revisit the so far best attack on PRESENT based on our theoretical result.

Springer2015

High performance VLSI architectures implementing strong cryptographic primitives

Feth Allah Cherigui

EPFL2002