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

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: 569 (8 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: 99 (4 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: 125 (12 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: 903 (28 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 (2016) 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 {\it 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 \emph{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 \textit{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 \textsc{Sparx} - a family of ARX-based block ciphers designed according to the LTS. \textsc{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 \textsc{Simon}, \textsc{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 Wall{\'{e}}n 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 Wall{\'{e}}n challenge. [less ▲] Detailed reference viewed: 95 (8 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: 109 (8 UL) |
||