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

Optimized Collision Search for STARK-Friendly Hash Challenge Candidates Udovenko, Aleksei E-print/Working paper (2020) In this note, we report several solutions to the STARK-Friendly Hash Challenge: a competition with the goal of finding collisions for several hash functions designed specifically for zero-knowledge proofs ... [more ▼] In this note, we report several solutions to the STARK-Friendly Hash Challenge: a competition with the goal of finding collisions for several hash functions designed specifically for zero-knowledge proofs (ZKP) and multiparty computations (MPC). We managed to find collisions for 3 instances of 91-bit hash functions. The method used is the classic parallel collision search with distinguished points from van Oorshot and Wiener (1994). As this is a general attack on hash functions, it does not exhibit any particular weakness of the chosen hash functions. The crucial part is to optimize the implementations to make the attack cost realistic, and we describe several arithmetic tricks. [less ▲] Detailed reference viewed: 98 (5 UL)On degree-d zero-sum sets of full rank Beierle, Christof ; Biryukov, Alex ; Udovenko, Aleksei in Cryptography and Communications (2019) A set 𝑆⊆𝔽𝑛2 is called degree-d zero-sum if the sum ∑𝑠∈𝑆𝑓(𝑠) vanishes for all n-bit Boolean functions of algebraic degree at most d. Those sets correspond to the supports of the n-bit Boolean ... [more ▼] A set 𝑆⊆𝔽𝑛2 is called degree-d zero-sum if the sum ∑𝑠∈𝑆𝑓(𝑠) vanishes for all n-bit Boolean functions of algebraic degree at most d. Those sets correspond to the supports of the n-bit Boolean functions of degree at most n − d − 1. We prove some results on the existence of degree-d zero-sum sets of full rank, i.e., those that contain n linearly independent elements, and show relations to degree-1 annihilator spaces of Boolean functions and semi-orthogonal matrices. We are particularly interested in the smallest of such sets and prove bounds on the minimum number of elements in a degree-d zero-sum set of rank n. The motivation for studying those objects comes from the fact that degree-d zero-sum sets of full rank can be used to build linear mappings that preserve special kinds of nonlinear invariants, similar to those obtained from orthogonal matrices and exploited by Todo, Leander and Sasaki for breaking the block ciphers Midori, Scream and iScream. [less ▲] Detailed reference viewed: 85 (3 UL)Lightweight AEAD and Hashing using the Sparkle Permutation Family Beierle, Christof ; Biryukov, Alex ; Cardoso Dos Santos, Luan et al in IACR Transactions on Symmetric Cryptology (2019) Detailed reference viewed: 46 (9 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: 77 (5 UL)Cryptanalysis of the Legendre PRF and generalizations ; ; Udovenko, Aleksei et al E-print/Working paper (2019) The Legendre PRF relies on the conjectured pseudorandomness properties of the Legendre symbol with a hidden shift. Originally proposed as a PRG by Damgård at CRYPTO 1988, it was recently suggested as an ... [more ▼] The Legendre PRF relies on the conjectured pseudorandomness properties of the Legendre symbol with a hidden shift. Originally proposed as a PRG by Damgård at CRYPTO 1988, it was recently suggested as an efficient PRF for multiparty computation purposes by Grassi et al. at CCS 2016. Moreover, the Legendre PRF is being considered for usage in the Ethereum 2.0 blockchain. This paper improves previous attacks on the Legendre PRF and its higher-degree variant due to Khovratovich by reducing the time complexity from O(plogp/M) to O(plog^2p/M2) Legendre symbol evaluations when M≤p√4 queries are available. The practical relevance of our improved attack is demonstrated by breaking two concrete instances of the PRF proposed by the Ethereum foundation. Furthermore, we generalize our attack in a nontrivial way to the higher-degree variant of the Legendre PRF and we point out a large class of weak keys for this construction. Lastly, we provide the first security analysis of two additional generalizations of the Legendre PRF originally proposed by Damgård in the PRG setting, namely the Jacobi PRF and the power residue PRF. [less ▲] Detailed reference viewed: 34 (2 UL)Cryptanalysis of SKINNY in the Framework of the SKINNY 2018--2019 Cryptanalysis Competition Derbez, Patrick ; ; Udovenko, Aleksei in Patterson, Kenneth G.; Stebila, Douglas (Eds.) Selected Areas in Cryptography -- SAC 2019 (2019) In April 2018, Beierle et al. launched the 3rd SKINNY cryptanalysis competition, a contest that aimed at motivating the analysis of their recent tweakable block cipher SKINNY . In contrary to the previous ... [more ▼] In April 2018, Beierle et al. launched the 3rd SKINNY cryptanalysis competition, a contest that aimed at motivating the analysis of their recent tweakable block cipher SKINNY . In contrary to the previous editions, the focus was made on practical attacks: contestants were asked to recover a 128-bit secret key from a given set of 2^20 plaintext blocks. The suggested SKINNY instances are 4- to 20-round reduced variants of SKINNY-64-128 and SKINNY-128-128. In this paper, we explain how to solve the challenges for 10-round SKINNY-128-128 and for 12-round SKINNY-64-128 in time equivalent to roughly 2^52 simple operations. Both techniques benefit from the highly biased sets of messages that are provided and that actually correspond to the encryption of various books in ECB mode. [less ▲] Detailed reference viewed: 111 (0 UL)On Degree-d Zero-Sum Sets of Full Rank Beierle, Christof ; Biryukov, Alex ; Udovenko, Aleksei E-print/Working paper (2018) A set S⊆Fn2 is called degree-d zero-sum if the sum ∑s∈Sf(s) vanishes for all n-bit Boolean functions of algebraic degree at most d. Those sets correspond to the supports of the n-bit Boolean functions of ... [more ▼] A set S⊆Fn2 is called degree-d zero-sum if the sum ∑s∈Sf(s) vanishes for all n-bit Boolean functions of algebraic degree at most d. Those sets correspond to the supports of the n-bit Boolean functions of degree at most n−d−1. We prove some results on the existence of degree-d zero-sum sets of full rank, i.e., those that contain n linearly independent elements, and show relations to degree-1 annihilator spaces of Boolean functions and semi-orthogonal matrices. We are particularly interested in the smallest of such sets and prove bounds on the minimum number of elements in a degree-d zero-sum set of rank n. The motivation for studying those objects comes from the fact that degree-d zero-sum sets of full rank can be used to build linear mappings that preserve special kinds of nonlinear invariants, similar to those obtained from orthogonal matrices and exploited by Todo, Leander and Sasaki for breaking the block ciphers Midori, Scream and iScream. [less ▲] Detailed reference viewed: 57 (1 UL)Attacks and Countermeasures for White-box Designs Biryukov, Alex ; Udovenko, Aleksei in Peyrin, Thomas; Galbraith, Steven (Eds.) Advances in Cryptology – ASIACRYPT 2018 (2018, November) In traditional symmetric cryptography, the adversary has access only to the inputs and outputs of a cryptographic primitive. In the white-box model the adversary is given full access to the implementation ... [more ▼] In traditional symmetric cryptography, the adversary has access only to the inputs and outputs of a cryptographic primitive. In the white-box model the adversary is given full access to the implementation. He can use both static and dynamic analysis as well as fault analysis in order to break the cryptosystem, e.g. to extract the embedded secret key. Implementations secure in such model have many applications in industry. However, creating such implementations turns out to be a very challenging if not an impossible task. Recently, Bos et al. proposed a generic attack on white-box primitives called differential computation analysis (DCA). This attack was applied to many white-box implementations both from academia and industry. The attack comes from the area of side-channel analysis and the most common method protecting against such attacks is masking, which in turn is a form of secret sharing. In this paper we present multiple generic attacks against masked white-box implementations. We use the term “masking” in a very broad sense. As a result, we deduce new constraints that any secure white-box implementation must satisfy. Based on the new constraints, we develop a general method for protecting white-box implementations. We split the protection into two independent components: value hiding and structure hiding. Value hiding must pro- vide protection against passive DCA-style attacks that rely on analysis of computation traces. Structure hiding must provide protection against circuit analysis attacks. In this paper we focus on developing the value hiding component. It includes protection against the DCA attack by Bos et al. and protection against a new attack called algebraic attack. We present a provably secure first-order protection against the new al- gebraic attack. The protection is based on small gadgets implementing secure masked XOR and AND operations. Furthermore, we give a proof of compositional security allowing to freely combine secure gadgets. We derive concrete security bounds for circuits built using our construction. [less ▲] Detailed reference viewed: 818 (20 UL)Optimal First-Order Boolean Masking for Embedded IoT Devices Biryukov, Alex ; Dinu, Dumitru-Daniel ; Le Corre, Yann et al in CARDIS 2017: Smart Card Research and Advanced Applications (2018, January 26) Boolean masking is an effective side-channel countermeasure that consists in splitting each sensitive variable into two or more shares which are carefully manipulated to avoid leakage of the sensitive ... [more ▼] Boolean masking is an effective side-channel countermeasure that consists in splitting each sensitive variable into two or more shares which are carefully manipulated to avoid leakage of the sensitive variable. The best known expressions for Boolean masking of bitwise operations are relatively compact, but even a small improvement of these expressions can significantly reduce the performance penalty of more complex masked operations such as modular addition on Boolean shares or of masked ciphers. In this paper, we present and evaluate new secure expressions for performing bitwise operations on Boolean shares. To this end, we describe an algorithm for efficient search of expressions that have an optimal cost in number of elementary operations. We show that bitwise AND and OR on Boolean shares can be performed using less instructions than the best known expressions. More importantly, our expressions do no require additional random values as the best known expressions do. We apply our new expressions to the masked addition/subtraction on Boolean shares based on the Kogge-Stone adder and we report an improvement of the execution time between 14% and 19%. Then, we compare the efficiency of first-order masked implementations of three lightweight block ciphers on an ARM Cortex-M3 to determine which design strategies are most suitable for efficient masking. All our masked implementations passed the t-test evaluation and thus are deemed secure against first-order side-channel attacks. [less ▲] Detailed reference viewed: 162 (7 UL)Analysis of the NORX Core Permutation Biryukov, Alex ; Udovenko, Aleksei ; Velichkov, Vesselin E-print/Working paper (2017) NORX is one of the fifteen authenticated encryption algorithms that have reached the third round of the CAESAR competition. NORX is built using the sponge-based Monkey Duplex construction. In this note we ... [more ▼] NORX is one of the fifteen authenticated encryption algorithms that have reached the third round of the CAESAR competition. NORX is built using the sponge-based Monkey Duplex construction. In this note we analyze the core permutation F. We show that it has rotational symmetries on different structure levels. This yields simple distinguishing properties for the permutation, which propagate with very high probability or even probability one. We also investigate differential symmetries in NORX at the word level. A new type of truncated differentials called symmetric truncated differentials (STD) is proposed. It is shown that, under the Markov assumption, up to 2.125 rounds of the F function of NORX32 and NORX64 can be distinguished using STD. Finally, we note that our analysis covers only the permutation F and does not immediately threaten the security claims of the designers. [less ▲] Detailed reference viewed: 32 (0 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: 193 (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: 216 (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: 221 (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: 1031 (31 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: 169 (9 UL) |
||