Browse ORBi

- What it is and what it isn't
- Green Road / Gold Road?
- Ready to Publish. Now What?
- How can I support the OA movement?
- Where can I learn more?

ORBi

Schwaemm and Esch: Lightweight Authenticated Encryption and Hashing using the Sparkle Permutation Family Beierle, Christof ; Biryukov, Alex ; Cardoso Dos Santos, Luan et al E-print/Working paper (2019) Detailed reference viewed: 17 (4 UL)Alzette: A 64-bit ARX-box Beierle, Christof ; Biryukov, Alex ; Cardoso Dos Santos, Luan et al E-print/Working paper (2019) S-boxes are the only source of non-linearity in many symmetric primitives. While they are often defined as being functions operating on a small space, some recent designs propose the use of much larger ... [more ▼] S-boxes are the only source of non-linearity in many symmetric primitives. While they are often defined as being functions operating on a small space, some recent designs propose the use of much larger ones (e.g., 32 bits). In this context, an S-box is then defined as a subfunction whose cryptographic properties can be estimated precisely. In this paper, we present a 64-bit ARX-based S-box called Alzette, which can be evaluated in constant time using only 12 instructions on modern CPUs. Its parallel application can also leverage vector (SIMD) instructions. One iteration of Alzette has differential and linear properties comparable to those of the AES S-box, while two iterations are at least as secure as the AES super S-box. Since the state size is much larger than the typical 4 or 8 bits, the study of the relevant cryptographic properties of Alzette is not trivial. [less ▲] Detailed reference viewed: 41 (5 UL)Triathlon of Lightweight Block Ciphers for the Internet of Things Dinu, Dumitru-Daniel ; Le Corre, Yann ; Khovratovich, Dmitry et al in Journal of Cryptographic Engineering (2018) In this paper, we introduce a framework for the benchmarking of lightweight block ciphers on a multitude of embedded platforms. Our framework is able to evaluate the execution time, RAM footprint, as well ... [more ▼] In this paper, we introduce a framework for the benchmarking of lightweight block ciphers on a multitude of embedded platforms. Our framework is able to evaluate the execution time, RAM footprint, as well as binary code size, and allows one to define a custom "figure of merit" according to which all evaluated candidates can be ranked. We used the framework to benchmark implementations of 19 lightweight ciphers, namely AES, Chaskey, Fantomas, HIGHT, LBlock, LEA, LED, Piccolo, PRESENT, PRIDE, PRINCE, RC5, RECTANGLE, RoadRunneR, Robin, Simon, SPARX, Speck, and TWINE, on three microcontroller platforms: 8-bit AVR, 16-bit MSP430, and 32-bit ARM. Our results bring some new insights into the question of how well these lightweight ciphers are suited to secure the Internet of things. The benchmarking framework provides cipher designers with an easy-to-use tool to compare new algorithms with the state of the art and allows standardization organizations to conduct a fair and consistent evaluation of a large number of candidates. [less ▲] Detailed reference viewed: 121 (1 UL)State of the Art in Lightweight Symmetric Cryptography Biryukov, Alex ; Perrin, Léo Paul E-print/Working paper (2017) Lightweight cryptography has been one of the ``hot topics'' in symmetric cryptography in the recent years. A huge number of lightweight algorithms have been published, standardized and/or used in ... [more ▼] Lightweight cryptography has been one of the ``hot topics'' in symmetric cryptography in the recent years. A huge number of lightweight algorithms have been published, standardized and/or used in commercial products. In this paper, we discuss the different implementation constraints that a ``lightweight'' algorithm is usually designed to satisfy. We also present an extensive survey of all lightweight symmetric primitives we are aware of. It covers designs from the academic community, from government agencies and proprietary algorithms which were reverse-engineered or leaked. Relevant national (\nist{}...) and international (\textsc{iso/iec}...) standards are listed. We then discuss some trends we identified in the design of lightweight algorithms, namely the designers' preference for \arx{}-based and bitsliced-S-Box-based designs and simple key schedules. Finally, we argue that lightweight cryptography is too large a field and that it should be split into two related but distinct areas: \emph{ultra-lightweight} and \emph{IoT} cryptography. The former deals only with the smallest of devices for which a lower security level may be justified by the very harsh design constraints. The latter corresponds to low-power embedded processors for which the \aes{} and modern hash function are costly but which have to provide a high level security due to their greater connectivity. [less ▲] Detailed reference viewed: 1153 (12 UL)Cryptanalysis, Reverse-Engineering and Design of Symmetric Cryptographic Algorithms Perrin, Léo Paul Doctoral thesis (2017) In this thesis, I present the research I did with my co-authors on several aspects of symmetric cryptography from May 2013 to December 2016, that is, when I was a PhD student at the university of ... [more ▼] In this thesis, I present the research I did with my co-authors on several aspects of symmetric cryptography from May 2013 to December 2016, that is, when I was a PhD student at the university of Luxembourg under the supervision of Alex Biryukov. My research has spanned three different areas of symmetric cryptography. In Part I of this thesis, I present my work on lightweight cryptography. This field of study investigates the cryptographic algorithms that are suitable for very constrained devices with little computing power such as RFID tags and small embedded processors such as those used in sensor networks. Many such algorithms have been proposed recently, as evidenced by the survey I co-authored on this topic. I present this survey along with attacks against three of those algorithms, namely GLUON, PRINCE and TWINE. I also introduce a new lightweight block cipher called SPARX which was designed using a new method to justify its security: the Long Trail Strategy. Part II is devoted to S-Box reverse-engineering, a field of study investigating the methods recovering the hidden structure or the design criteria used to build an S-Box. I co-invented several such methods: a statistical analysis of the differential and linear properties which was applied successfully to the S-Box of the NSA block cipher Skipjack, a structural attack against Feistel networks called the yoyo game and the TU-decomposition. This last technique allowed us to decompose the S-Box of the last Russian standard block cipher and hash function as well as the only known solution to the APN problem, a long-standing open question in mathematics. Finally, Part III presents a unifying view of several fields of symmetric cryptography by interpreting them as purposefully hard. Indeed, several cryptographic algorithms are designed so as to maximize the code size, RAM consumption or time taken by their implementations. By providing a unique framework describing all such design goals, we could design modes of operations for building any symmetric primitive with any form of hardness by combining secure cryptographic building blocks with simple functions with the desired form of hardness called plugs. Alex Biryukov and I also showed that it is possible to build plugs with an asymmetric hardness whereby the knowledge of a secret key allows the privileged user to bypass the hardness of the primitive. [less ▲] Detailed reference viewed: 1305 (53 UL)Summary of an Open Discussion on IoT and Lightweight Cryptography ; Biryukov, Alex ; Perrin, Léo Paul in Proceedings of Early Symmetric Crypto workshop, 2017 (2017, April) This is a summary of the open discussion on IoT security and regulation which took place at the Early Symmetric Crypto (ESC) seminar. Participants have identified that IoT poses critical threat to ... [more ▼] This is a summary of the open discussion on IoT security and regulation which took place at the Early Symmetric Crypto (ESC) seminar. Participants have identified that IoT poses critical threat to security and privacy. It was agreed that government regulation and dialogue of security researchers with engineers and manufacturers is necessary in order to find proper control mechanisms. [less ▲] Detailed reference viewed: 985 (14 UL)Exponential S-Boxes: a Link Between the S-Boxes of BelT and Kuznyechik/Streebog Perrin, Léo Paul ; Udovenko, Aleksei in IACR Transactions on Symmetric Cryptology (2017), 2016(2), 99-124 The block cipher Kuznyechik and the hash function Streebog were recently standardized by the Russian Federation. These primitives use a common 8-bit S-Box, denoted 𝜋, which is given only as a look-up ... [more ▼] The block cipher Kuznyechik and the hash function Streebog were recently standardized by the Russian Federation. These primitives use a common 8-bit S-Box, denoted 𝜋, which is given only as a look-up table. The rationale behind its design is, for all practical purposes, kept secret by its authors. In a paper presented at Eurocrypt 2016, Biryukov et al. reverse-engineered this S-Box and recovered an unusual Feistel-like structure relying on finite field multiplications. In this paper, we provide a new decomposition of this S-Box and describe how we obtained it. The first step was the analysis of the 8-bit S-Box of the current standard block cipher of Belarus, BelT. This S-Box is a variant of a so-called exponential substitution, a concept we generalize into pseudo-exponential substitution. We derive distinguishers for such permutations based on properties of their linear approximation tables and notice that 𝜋 shares some of them. We then show that 𝜋 indeed has a decomposition based on a pseudo-exponential substitution. More precisely, we obtain a simpler structure based on an 8-bit finite field exponentiation, one 4-bit S-Box, a linear layer and a few modular arithmetic operations. We also make several observations which may help cryptanalysts attempting to reverse-engineer other S-Boxes. For example, the visual pattern used in the previous work as a starting point to decompose 𝜋 is mathematically formalized and the use of differential patterns involving operations other than exclusive-or is explored. [less ▲] Detailed reference viewed: 172 (9 UL)Design Strategies for ARX with Provable Bounds: SPARX and LAX Dinu, Dumitru-Daniel ; Perrin, Léo Paul ; Udovenko, Aleksei et al in Cheon, Jung Hee; Takagi, Tsuyoshi (Eds.) Advances in Cryptology --- ASIACRYPT 2016, 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I (2016, December) We present, for the first time, a general strategy for designing ARX symmetric-key primitives with provable resistance against single-trail differential and linear cryptanalysis. The latter has been a ... [more ▼] We present, for the first time, a general strategy for designing ARX symmetric-key primitives with provable resistance against single-trail differential and linear cryptanalysis. The latter has been a long standing open problem in the area of ARX design. The Wide-Trail design Strategy (WTS), that is at the basis of many S-box based ciphers, including the AES, is not suitable for ARX designs due to the lack of S-boxes in the latter. In this paper we address the mentioned limitation by proposing the Long-Trail design Strategy (LTS) -- a dual of the WTS that is applicable (but not limited) to ARX constructions. In contrast to the WTS, that prescribes the use of small and efficient S-boxes at the expense of heavy linear layers with strong mixing properties, the LTS advocates the use of large (ARX-based) S-Boxes together with sparse linear layers. With the help of the so-called long-trail argument, a designer can bound the maximum differential and linear probabilities for any number of rounds of a cipher built according to the LTS. To illustrate the effectiveness of the new strategy, we propose Sparx -- a family of ARX-based block ciphers designed according to the LTS. Sparx has 32-bit ARX-based S-boxes and has provable bounds against differential and linear cryptanalysis. In addition, Sparx is very efficient on a number of embedded platforms. Its optimized software implementation ranks in the top-6 of the most software-efficient ciphers along with Simon, Speck, Chaskey, LEA and RECTANGLE. As a second contribution we propose another strategy for designing ARX ciphers with provable properties, that is completely independent of the LTS. It is motivated by a challenge proposed earlier by Wallen and uses the differential properties of modular addition to minimize the maximum differential probability across multiple rounds of a cipher. A new primitive, called LAX is designed following those principles. LAX partly solves the Wallen challenge. [less ▲] Detailed reference viewed: 195 (13 UL)Cryptanalysis of a Theorem: Decomposing the Only Known Solution to the Big APN Problem Perrin, Léo Paul ; Udovenko, Aleksei ; Biryukov, Alex in Robshaw, Matthew; Katz, Jonathan (Eds.) Advances in Cryptology – CRYPTO 2016 (2016, July 21) The existence of Almost Perfect Non-linear (APN) permutations operating on an even number of bits has been a long standing open question until Dillon et al., who work for the NSA, provided an example on 6 ... [more ▼] The existence of Almost Perfect Non-linear (APN) permutations operating on an even number of bits has been a long standing open question until Dillon et al., who work for the NSA, provided an example on 6 bits in 2009. In this paper, we apply methods intended to reverse-engineer S-Boxes with unknown structure to this permutation and find a simple decomposition relying on the cube function over GF(2^3) . More precisely, we show that it is a particular case of a permutation structure we introduce, the butterfly. Such butterflies are 2n-bit mappings with two CCZ-equivalent representations: one is a quadratic non-bijective function and one is a degree n+1 permutation. We show that these structures always have differential uniformity at most 4 when n is odd. A particular case of this structure is actually a 3-round Feistel Network with similar differential and linear properties. These functions also share an excellent non-linearity for n=3,5,7. Furthermore, we deduce a bitsliced implementation and significantly reduce the hardware cost of a 6-bit APN permutation using this decomposition, thus simplifying the use of such a permutation as building block for a cryptographic primitive. [less ▲] Detailed reference viewed: 206 (16 UL)Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1 Biryukov, Alex ; Perrin, Léo Paul ; Udovenko, Aleksei in Fischlin, Marc, Coron, Jean-Sébastien (Ed.) Advances in Cryptology – EUROCRYPT 2016 (2016, April 28) The Russian Federation's standardization agency has recently published a hash function called Streebog and a 128-bit block cipher called Kuznyechik. Both of these algorithms use the same 8-bit S-Box but ... [more ▼] The Russian Federation's standardization agency has recently published a hash function called Streebog and a 128-bit block cipher called Kuznyechik. Both of these algorithms use the same 8-bit S-Box but its design rationale was never made public. In this paper, we reverse-engineer this S-Box and reveal its hidden structure. It is based on a sort of 2-round Feistel Network where exclusive-or is replaced by a finite field multiplication. This structure is hidden by two different linear layers applied before and after. In total, five different 4-bit S-Boxes, a multiplexer,two 8-bit linear permutations and two finite field multiplications in a field of size $2^{4}$ are needed to compute the S-Box. The knowledge of this decomposition allows a much more efficient hardware implementation by dividing the area and the delay by 2.5 and 8 respectively. However, the small 4-bit S-Boxes do not have very good cryptographic properties. In fact, one of them has a probability 1 differential. We then generalize the method we used to partially recover the linear layers used to whiten the core of this S-Box and illustrate it with a generic decomposition attack against 4-round Feistel Networks whitened with unknown linear layers. Our attack exploits a particular pattern arising in the Linear Approximations Table of such functions. [less ▲] Detailed reference viewed: 1007 (31 UL)Cryptanalysis of Feistel Networks with Secret Round Functions Biryukov, Alex ; ; Perrin, Léo Paul in Dunkelman, Orr; Keliher, Liam (Eds.) Selected Areas in Cryptography -- SAC 2015, 21st International Conference, Sackville, NB, Canada, August 12-14, 2015, Revised Selected Papers (2016, March) Generic distinguishers against Feistel Network with up to 5 rounds exist in the regular setting and up to 6 rounds in a multi-key setting. We present new cryptanalyses against Feistel Networks with 5, 6 ... [more ▼] Generic distinguishers against Feistel Network with up to 5 rounds exist in the regular setting and up to 6 rounds in a multi-key setting. We present new cryptanalyses against Feistel Networks with 5, 6 and 7 rounds which are not simply distinguishers but actually recover completely the unknown Feistel functions. When an exclusive-or is used to combine the output of the round function with the other branch, we use the so-called \textit{yoyo game} which we improved using a heuristic based on particular cycle structures. The complexity of a complete recovery is equivalent to $\bigO(2^{2n})$ encryptions where $n$ is the branch size. This attack can be used against 6- and 7-round Feistel Networks in time respectively $\bigO(2^{n2^{n-1}+2n})$ and $\bigO(2^{n2^{n}+2n})$. However when modular addition is used, this attack does not work. In this case, we use an optimized guess-and-determine strategy to attack 5 rounds with complexity $\bigO(2^{n2^{3n/4}})$. Our results are, to the best of our knowledge, the first recovery attacks against generic 5-, 6- and 7-round Feistel Networks. [less ▲] Detailed reference viewed: 239 (4 UL)Algebraic Insights into the Secret Feistel Network Perrin, Léo Paul ; Udovenko, Aleksei in Peyrin, Thomas (Ed.) Fast Software Encryption - 23rd International Workshop, FSE 2016, Bochum, March 20-23, 2016 (2016) We introduce the high-degree indicator matrix (HDIM), an object closely related with both the linear approximation table and the algebraic normal form (ANF) of a permutation. We show that the HDIM of a ... [more ▼] We introduce the high-degree indicator matrix (HDIM), an object closely related with both the linear approximation table and the algebraic normal form (ANF) of a permutation. We show that the HDIM of a Feistel Network contains very specific patterns depending on the degree of the Feistel functions, the number of rounds and whether the Feistel functions are 1-to-1 or not. We exploit these patterns to distinguish Feistel Networks, even if the Feistel Network is whitened using unknown affine layers. We also present a new type of structural attack exploiting monomials that cannot be present at round r-1 to recover the ANF of the last Feistel function of a r-round Feistel Network. Finally, we discuss the relations between our findings, integral attacks, cube attacks, Todo's division property and the congruence modulo 4 of the Linear Approximation Table. [less ▲] Detailed reference viewed: 159 (9 UL)Multiset-Algebraic Cryptanalysis of Reduced Kuznyechik, Khazad, and secret SPNs Biryukov, Alex ; Khovratovich, Dmitry ; Perrin, Léo Paul in IACR Transactions on Symmetric Cryptology (2016), 2016(2), 226-247 We devise the first closed formula for the number of rounds of a blockcipher with secret components so that these components can be revealed using multiset, algebraic-degree, or division-integral ... [more ▼] We devise the first closed formula for the number of rounds of a blockcipher with secret components so that these components can be revealed using multiset, algebraic-degree, or division-integral properties, which in this case are equivalent. Using the new result, we attack 7 (out of 9) rounds of Kuznyechik, the recent Russian blockcipher standard, thus halving its security margin. With the same technique we attack 6 (out of 8) rounds of Khazad, the legacy 64-bit blockcipher. Finally, we show how to cryptanalyze and find a decomposition of generic SPN construction for which the inner-components are secret. All the attacks are the best to date. [less ▲] Detailed reference viewed: 149 (9 UL)On Reverse-Engineering S-Boxes with Hidden Design Criteria or Structure Biryukov, Alex ; Perrin, Léo Paul in Gennaro, Rosario; Robshaw, Matthew (Eds.) Advances in Cryptology -- CRYPTO 2015, (2015, August) S-Boxes are the key components of many cryptographic primitives and designing them to improve resilience to attacks such as linear or differential cryptanalysis is well understood. In this paper, we ... [more ▼] S-Boxes are the key components of many cryptographic primitives and designing them to improve resilience to attacks such as linear or differential cryptanalysis is well understood. In this paper, we investigate techniques that can be used to reverse-engineer S-box design and illustrate those by studying the S-Box $F$ of the Skipjack block cipher whose design process so far remained secret. We first show that the linear properties of $F$ are far from random and propose a design criteria, along with an algorithm which generates S-Boxes very similar to that of Skipjack. Then we consider more general S-box decomposition problems and propose new methods for decomposing S-Boxes built from arithmetic operations or as a Feistel Network of up to 5 rounds. Finally, we develop an S-box generating algorithm which can fix a large number of DDT entries to the values chosen by the designer. We demonstrate this algorithm by embedding images into the visual representation of S-box's DDT. [less ▲] Detailed reference viewed: 244 (14 UL)Triathlon of Lightweight Block Ciphers for the Internet of Things Dinu, Dumitru-Daniel ; Le Corre, Yann ; Khovratovich, Dmitry et al Scientific Conference (2015, July) In this paper we introduce an open framework for the benchmarking of lightweight block ciphers on a multitude of embedded platforms. Our framework is able to evaluate execution time, RAM footprint, as ... [more ▼] In this paper we introduce an open framework for the benchmarking of lightweight block ciphers on a multitude of embedded platforms. Our framework is able to evaluate execution time, RAM footprint, as well as (binary) code size, and allows a user to define a custom "figure of merit" according to which all evaluated candidates can be ranked. We used the framework to benchmark various implementations of 13 lightweight ciphers, namely AES, Fantomas, HIGHT, LBlock, LED, Piccolo, PRESENT, PRINCE, RC5, Robin, Simon, Speck, and TWINE, on three different platforms: 8-bit ATmega, 16-bit MSP430, and 32-bit ARM. Our results give new insights to the question of how well these ciphers are suited to secure the Internet of Things (IoT). The benchmarking framework provides cipher designers with a tool to compare new algorithms with the state-of-the-art and allows standardization bodies to conduct a fair and comprehensive evaluation of a large number of candidates. [less ▲] Detailed reference viewed: 405 (30 UL)FELICS - Fair Evaluation of Lightweight Cryptographic Systems Dinu, Dumitru-Daniel ; Biryukov, Alex ; Groszschädl, Johann et al Scientific Conference (2015, July) In this paper we introduce FELICS, a free and open-source benchmarking framework designed for fair and consistent evaluation of software implementations of lightweight cryptographic primitives for ... [more ▼] In this paper we introduce FELICS, a free and open-source benchmarking framework designed for fair and consistent evaluation of software implementations of lightweight cryptographic primitives for embedded devices. The framework is very flexible thanks to its modular structure, which allows for an easy integration of new metrics, target devices and evaluation scenarios. It consists of two modules that can currently asses the performance of lightweight block and stream ciphers on three widely used microcontrollers: 8-bit AVR, 16-bit MSP and 32-bit ARM. The metrics extracted are execution time, RAM consumption and binary code size. FELICS has a simple user interface and is intended to be used by cipher designers to compare new primitives with the state of the art. The extracted metrics are very detailed and assist embedded software engineers in selecting the best cipher to match the requirements of a particular application. The tool aims to increase the transparency and trust in benchmarking results of lightweight primitives and facilitates a fair comparison between different primitives using the same evaluation conditions. [less ▲] Detailed reference viewed: 445 (14 UL)Meet-in-the-Middle Attacks and Structural Analysis of Round-Reduced PRINCE Derbez, Patrick ; Perrin, Léo Paul in Leander, Gregor (Ed.) Fast Software Encryption - 22nd International Workshop, FSE 2015, Istanbul, March 8-11, 2015 (2015, March) NXP Semiconductors and its academic partners challenged the cryptographic community with finding practical attacks on the block cipher they designed, PRINCE. Instead of trying to attack as many rounds as ... [more ▼] NXP Semiconductors and its academic partners challenged the cryptographic community with finding practical attacks on the block cipher they designed, PRINCE. Instead of trying to attack as many rounds as possible using attacks which are usually impractical despite being faster than brute-force, the challenge invites cryptographers to find practical attacks and encourages them to actually implement them. In this paper, we present new attacks on round-reduced PRINCE including the ones which won the challenge in the 6 and 8-round categories --- the highest for which winners were identified. Our first attacks rely on a meet-in-the-middle approach and break up to 10 rounds of the cipher. We also describe heuristic methods we used to find practical SAT-based and differential attacks. Finally, we also present an analysis of the cycle structure of the internal rounds of PRINCE leading both to a low complexity distinguisher for 4-round PRINCE-core and an alternative representation of the cipher valid in particular contexts and which highlights, in this cases, a poor diffusion. [less ▲] Detailed reference viewed: 132 (13 UL)Differential Analysis and Meet-in-the-Middle Attack against Round-Reduced TWINE Biryukov, Alex ; Derbez, Patrick ; Perrin, Léo Paul in Leander, Gregor (Ed.) Fast Software Encryption - 22nd International Workshop, FSE 2015, Istanbul, March 8-11, 2015 (2015, March) TWINE is a recent lightweight block cipher based on a Feistel structure. We first present two new attacks on TWINE-128 reduced to 25 rounds that have a slightly higher overall complexity than the 25-round ... [more ▼] TWINE is a recent lightweight block cipher based on a Feistel structure. We first present two new attacks on TWINE-128 reduced to 25 rounds that have a slightly higher overall complexity than the 25-round attack presented by Wang and Wu at ACISP 2014, but a lower data complexity. Then, we introduce alternative representations of both the round function of this block cipher and of a sequence of 4 rounds. LBlock, another lightweight block cipher, turns out to exhibit the same behaviour. Then, we illustrate how this alternative representation can shed new light on the security of TWINE by deriving high probability iterated truncated differential trails covering 4 rounds with probability $2^{-16}$. The importance of these is shown by combining different truncated differential trails to attack 23-rounds TWINE-128 and by giving a tighter lower bound on the high probability of some differentials by clustering differential characteristics following one of these truncated trails. A comparison between these high probability differentials and those recently found in a variant of LBlock by Leurent highlights the importance of considering the whole distribution of the coefficients in the difference distribution table of a S-Box and not only their maximum value. [less ▲] Detailed reference viewed: 234 (12 UL)More differentially 6-uniform power functions ; Perrin, Léo Paul in Designs, Codes and Cryptography (2014), 73(2), 487-505 Detailed reference viewed: 121 (6 UL)Collision Spectrum, Entropy Loss, T-Sponges, and Cryptanalysis of GLUON-64 Perrin, Léo Paul ; Khovratovich, Dmitry in Fast Software Encryption - 21th International Workshop, FSE 2014, London, March 3-5, 2014 (2014, March) In this paper, we investigate the security provided by iterative non-injective functions. We introduce the Collision Probabilities Spectrum (CPS) to quantify how far from a permutation a function is. In ... [more ▼] In this paper, we investigate the security provided by iterative non-injective functions. We introduce the Collision Probabilities Spectrum (CPS) to quantify how far from a permutation a function is. In particular, we show that the size of the iterated image of such a function decreases linearly with the number of iterations and that collision trees of quadratic size appear. We discuss the influence of the CPS over collision search efficiency by connecting it with the function's balance. We then show that the security of a so-called T-Sponge is only marginally impacted by the number of collisions occurring because of the update function. However, the loss of entropy in the update function can lead to a greatly simplified preimage search for a particular family of messages if the rate is small. Consequences of the entropy loss when duplexing the sponge to provide one-pass authenticated encryption and for Davies-Meyer construction are also studied. Finally, we use a heuristic method to estimate the CPS of the update function of GLUON-64. Applying our results, we prove for instance that if a message is only known to end with a sequence of 1 Mb (respectively 1 Gb) of zero bytes, then it is possible to find a preimage for its digest in time $2^{115.3}$ (respectively $2^{105.3}$) instead of $2^{128}$. [less ▲] Detailed reference viewed: 232 (31 UL) |
||