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

The Seventh International Olympiad in Cryptography NSUCRYPTO: problems and solutions ; ; et al E-print/Working paper (2021) Detailed reference viewed: 40 (0 UL)Cryptanalysis of a Dynamic Universal Accumulator over Bilinear Groups Biryukov, Alexei ; Udovenko, Aleksei ; Vitto, Giuseppe in Topics in Cryptology – CT-RSA 2021 (2021) In this paper we cryptanalyse the two accumulator variants proposed by Au et al., which we call the alpha-based construction and the common reference string-based (CRS-based) construction. We show that if ... [more ▼] In this paper we cryptanalyse the two accumulator variants proposed by Au et al., which we call the alpha-based construction and the common reference string-based (CRS-based) construction. We show that if non-membership witnesses are issued according to the alpha-based construction, an attacker that has access to multiple witnesses is able to efficiently recover the secret accumulator parameter alpha and completely break its security. More precisely, if p is the order of the underlying bilinear group, the knowledge of O(log p log log p) non-membership witnesses permits to successfully recover alpha. Further optimizations and different attack scenarios allow to reduce the number of required witnesses to O(log p), together with practical attack complexity. Moreover, we show that accumulator's collision resistance can be broken if just one of these non-membership witnesses is known to the attacker. We then show how all these attacks for the alpha-based construction can be easily prevented by using instead a corrected expression for witnesses. Although outside the original security model assumed by Au \etal but motivated by some possible concrete application of the scheme where the Manager must have exclusive rights for issuing witnesses (e.g. white/black list based authentication mechanisms), we show that if non-membership witnesses are issued using the CRS-based construction and the CRS is kept secret by the Manager, an attacker accessing multiple witnesses can reconstruct the CRS and compute witnesses for arbitrary new elements. In particular, if the accumulator is initialized by adding m secret elements, the knowledge of m non-membership witnesses allows to succeed in such attack. [less ▲] Detailed reference viewed: 39 (11 UL)MILP modeling of Boolean functions by minimum number of inequalities Udovenko, Aleksei E-print/Working paper (2021) Detailed reference viewed: 37 (0 UL)Convexity of Division Property Transitions: Theory, Algorithms and Compact Models Udovenko, Aleksei in Wang, Huaxiong; Tibouchi, Mehdi (Eds.) Advances in Cryptology -- ASIACRYPT 2021 (2021) Detailed reference viewed: 28 (2 UL)Breaking the $IKEp182 Challenge Udovenko, Aleksei ; Vitto, Giuseppe E-print/Working paper (2021) We report a break of the \$IKEp182 challenge using a meet-in-the-middle attack strategy improved with multiple SIKE-specific optimizations. The attack was executed on the HPC cluster of the University of ... [more ▼] We report a break of the \$IKEp182 challenge using a meet-in-the-middle attack strategy improved with multiple SIKE-specific optimizations. The attack was executed on the HPC cluster of the University of Luxembourg and required less than 10 core-years and 256TiB of high-performance network storage (GPFS). Different trade-offs allow execution of the attack with similar time complexity and reduced storage requirements of only about 70TiB. [less ▲] Detailed reference viewed: 43 (4 UL)Dummy Shuffling Against Algebraic Attacks in White-Box Implementations Biryukov, Alexei ; Udovenko, Aleksei in Canteaut, Anne; Standaert, Francois-Xavier (Eds.) Advances in Cryptology -- EUROCRYPT 2021 (2021) Detailed reference viewed: 60 (1 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 (2020), 2020(S1), 208-261 We introduce the Sparkle family of permutations operating on 256, 384 and 512 bits. These are combined with the Beetle mode to construct a family of authenticated ciphers, Schwaemm, with security levels ... [more ▼] We introduce the Sparkle family of permutations operating on 256, 384 and 512 bits. These are combined with the Beetle mode to construct a family of authenticated ciphers, Schwaemm, with security levels ranging from 120 to 250 bits. We also use them to build new sponge-based hash functions, Esch256 and Esch384. Our permutations are among those with the lowest footprint in software, without sacrificing throughput. These properties are allowed by our use of an ARX component (the Alzette S-box) as well as a carefully chosen number of rounds. The corresponding analysis is enabled by the long trail strategy which gives us the tools we need to efficiently bound the probability of all the differential and linear trails for an arbitrary number of rounds. We also present a new application of this approach where the only trails considered are those mapping the rate to the outer part of the internal state, such trails being the only relevant trails for instance in a differential collision attack. To further decrease the number of rounds without compromising security, we modify the message injection in the classical sponge construction to break the alignment between the rate and our S-box layer. [less ▲] Detailed reference viewed: 134 (15 UL)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: 177 (8 UL)On the Sixth International Olympiad in Cryptography NSUCRYPTO ; ; et al E-print/Working paper (2020) Detailed reference viewed: 33 (0 UL)Cryptanalysis of the Legendre PRF and generalizations ; ; Udovenko, Aleksei et al in IACR Transactions on Symmetric Cryptology (2020), 2020(1), 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: 86 (9 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: 135 (5 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: 147 (1 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: 137 (6 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: 104 (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: 912 (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: 227 (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: 62 (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: 249 (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: 263 (15 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: 277 (16 UL) |
||