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 E-print/Working paper (2018) In the 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 ... [more ▼] In the 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 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 applies to most existent white-box implementations both from academia and industry. The attack comes from side-channel cryptanalysis method. The most common method protecting against such side-channel attacks is masking. Therefore, masking can be used in white-box implementations to protect against the DCA attack. In this paper we investigate this possibility and 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. We suggest partial countermeasures against the attacks. Some of our attacks were successfully applied to the WhibOx 2017 challenges. [less ▲] Detailed reference viewed: 272 (5 UL)Guru: Universal Reputation Module for Distributed Consensus Protocols Biryukov, Alex ; Feher, Daniel ; Khovratovich, Dmitry Report (2017) In this paper we describe how to couple reputation systems with distributed consensus protocols to provide high-throughput highly-scalable consensus for large peer-to-peer networks of untrusted validators ... [more ▼] In this paper we describe how to couple reputation systems with distributed consensus protocols to provide high-throughput highly-scalable consensus for large peer-to-peer networks of untrusted validators. We introduce reputation module Guru, which can be laid on top of various consensus protocols such as PBFT or HoneyBadger. It ranks nodes based on the outcomes of consensus rounds run by a small committee, and adaptively selects the committee based on the current reputation. The protocol can also take external reputation ranking as input. Guru can tolerate larger threshold of malicious nodes (up to slightly above 1/2) compared to the 1/3 limit of BFT consensus algorithms. [less ▲] Detailed reference viewed: 186 (13 UL)Side-Channel Attacks meet Secure Network Protocols Biryukov, Alex ; Dinu, Dumitru-Daniel ; Le Corre, Yann in Gollmann, Dieter; Miyaji, Atsuko; Kikuchi, Hiroaki (Eds.) Applied Cryptography and Network Security - 15th International Conference, ACNS 2017, Kanazawa, Japan, July 10-12, 2017. Proceedings (2017, June) Side-channel attacks are powerful tools for breaking systems that implement cryptographic algorithms. The Advanced Encryption Standard (AES) is widely used to secure data, including the communication ... [more ▼] Side-channel attacks are powerful tools for breaking systems that implement cryptographic algorithms. The Advanced Encryption Standard (AES) is widely used to secure data, including the communication within various network protocols. Major cryptographic libraries such as OpenSSL or ARM mbed TLS include at least one implementation of the AES. In this paper, we show that most implementations of the AES present in popular open-source cryptographic libraries are vulnerable to side-channel attacks, even in a network protocol scenario when the attacker has limited control of the input. We present an algorithm for symbolic processing of the AES state for any input configuration where several input bytes are variable and known, while the rest are fixed and unknown as is the case in most secure network protocols. Then, we classify all possible inputs into 25 independent evaluation cases depending on the number of bytes controlled by attacker and the number of rounds that must be attacked to recover the master key. Finally, we describe an optimal algorithm that can be used to recover the master key using Correlation Power Analysis (CPA) attacks. Our experimental results raise awareness of the insecurity of unprotected implementations of the AES used in network protocol stacks. [less ▲] Detailed reference viewed: 91 (25 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: 299 (7 UL)Findel: Secure Derivative Contracts for Ethereum Biryukov, Alex ; Khovratovich, Dmitry ; Tikhomirov, Sergei Scientific Conference (2017, April 07) Blockchain-based smart contracts are considered a promising technology for handling financial agreements securely. In order to realize this vision, we need a formal language to unambiguously describe ... [more ▼] Blockchain-based smart contracts are considered a promising technology for handling financial agreements securely. In order to realize this vision, we need a formal language to unambiguously describe contract clauses. We introduce Findel -- a purely declarative financial domain-specific language (DSL) well suited for implementation in blockchain networks. We implement an Ethereum smart contract that acts as a marketplace for Findel contracts and measure the cost of its operation. We analyze challenges in modeling financial agreements in decentralized networks and outline directions for future work. [less ▲] Detailed reference viewed: 924 (64 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: 457 (13 UL)Topics and Research Directions for Symmetric Cryptography Biryukov, Alex ; ; et al in Proceedings of Early Symmetric Crypto workshop, 2017 (2017, April) This is a summary of the open discussion on future research topics for symmetric cryptography chaired by Stefan Lucks. During this session participants were suggesting topics of potential future interest. Detailed reference viewed: 183 (6 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: 107 (9 UL)Correlation Power Analysis of Lightweight Block Ciphers: From Theory to Practice Biryukov, Alex ; Dinu, Dumitru-Daniel ; Groszschädl, Johann in Manulis, Mark; Sadeghi, Ahmad-Reza; Schneider, Steve (Eds.) Applied Cryptography and Network Security - 14th International Conference, ACNS 2016, Guildford, UK, June 19-22, 2016. Proceedings (2016, June) Side-Channel Analysis (SCA) represents a serious threat to the security of millions of smart devices that form part of the so-called Internet of Things (IoT). Choosing the "right" cryptographic primitive ... [more ▼] Side-Channel Analysis (SCA) represents a serious threat to the security of millions of smart devices that form part of the so-called Internet of Things (IoT). Choosing the "right" cryptographic primitive for the IoT is a highly challenging task due to the resource constraints of IoT devices and the variety of primitives. An important criterion to assess the suitability of a lightweight cipher with respect to SCA is the amount of leakage available to an adversary. In this paper, we analyze the efficiency of different selection functions that are commonly used in Correlation Power Analysis (CPA) attacks on symmetric primitives. To this end, we attacked implementations of the lightweight block ciphers AES, Fantomas, LBlock, Piccolo, PRINCE, RC5, Simon, and Speck on an 8-bit AVR processor. By exploring the relation between the nonlinearity of the studied selection functions and the measured leakages, we discovered some imperfections when using nonlinearity to quantify the resilience against CPA. Then, we applied these findings in an evaluation of the "intrinsic" CPA-resistance of unprotected implementations of the eight mentioned ciphers. We show that certain implementation aspects can influence the leakage level and try to explain why. Our results shed new light on the resilience of basic operations executed by these ciphers against CPA and help to bridge the gap between theory and practice. [less ▲] Detailed reference viewed: 256 (67 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: 877 (28 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: 141 (3 UL)Equihash: asymmetric proof-of-work based on the Generalized Birthday problem Biryukov, Alex ; Khovratovich, Dmitry in Proceedings of NDSS 2016 (2016, February) The proof-of-work is a central concept in modern cryptocurrencies, but the requirement for fast verification so far made it an easy prey for GPU-, ASIC-, and botnet-equipped users. The attempts to rely on ... [more ▼] The proof-of-work is a central concept in modern cryptocurrencies, but the requirement for fast verification so far made it an easy prey for GPU-, ASIC-, and botnet-equipped users. The attempts to rely on memory-intensive computations in order to remedy the disparity between architectures have resulted in slow or broken schemes. In this paper we solve this open problem and show how to construct an asymmetric proof-of-work (PoW) based on a computationally hard problem, which requires a lot of memory to generate a proof (called "memory-hardness" feature) but is instant to verify. Our primary proposal is a PoW based on the generalized birthday problem and enhanced Wagner's algorithm for it. We introduce the new technique of algorithm binding to prevent cost amortization and demonstrate that possible parallel implementations are constrained by memory bandwidth. Our scheme has tunable and steep time-space tradeoffs, which impose large computational penalties if less memory is used. Our solution is practical and ready to deploy: a reference implementation of a proof-of-work requiring 700 MB of RAM runs in 30 seconds on a 1.8 GHz CPU, increases the computations by the factor of 1000 if memory is halved, and presents a proof of just 148 bytes long. [less ▲] Detailed reference viewed: 3461 (29 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: 60 (6 UL)Automatic Search for the Best Trails in ARX: Application to Block Cipher Speck Biryukov, Alex ; Velichkov, Vesselin ; Le Corre, Yann in Fast Software Encryption - FSE 2016 (2016) We propose the first adaptation of Matsui's algorithm for finding the best differential and linear trails to the class of ARX ciphers. It is based on a branch-and-bound search strategy, does not use any ... [more ▼] We propose the first adaptation of Matsui's algorithm for finding the best differential and linear trails to the class of ARX ciphers. It is based on a branch-and-bound search strategy, does not use any heuristics and returns optimal results. The practical application of the new algorithm is demonstrated on reduced round variants of block ciphers from the Speck family. More specifically, we report the probabilities of the best differential trails for up to 10, 9, 8, 7, and 7 rounds of Speck32, Speck48, Speck64, Speck96 and Speck128 respectively, together with the exact number of differential trails that have the best probability. The new results are used to compute bounds, under the Markov assumption, on the security of Speck against single-trail differential cryptanalysis. Finally, we propose two new ARX primitives with provable bounds against single-trail differential and linear cryptanalysis -- a long standing open problem in the area of ARX design. [less ▲] Detailed reference viewed: 70 (14 UL)Argon2: New Generation of Memory-Hard Functions for Password Hashing and Other Applications Biryukov, Alex ; Dinu, Dumitru-Daniel ; Khovratovich, Dmitry in IEEE European Symposium on Security and Privacy (2016) We present a new hash function Argon2, which is oriented at protection of low-entropy secrets without secret keys. It requires a certain (but tunable) amount of memory, imposes prohibitive time-memory and ... [more ▼] We present a new hash function Argon2, which is oriented at protection of low-entropy secrets without secret keys. It requires a certain (but tunable) amount of memory, imposes prohibitive time-memory and computation-memory tradeoffs on memory-saving users, and is exceptionally fast on regular PC. Overall, it can provide ASIC-and botnet-resistance by filling the memory in 0.6 cycles per byte in the non-compressible way. [less ▲] Detailed reference viewed: 43 (1 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: 81 (9 UL)Egalitarian computing Biryukov, Alex ; Khovratovich, Dmitry in USENIX Security 2016 (2016) In this paper we explore several contexts where an adversary has an upper hand over the defender by using special hardware in an attack. These include password processing, hard-drive protection ... [more ▼] In this paper we explore several contexts where an adversary has an upper hand over the defender by using special hardware in an attack. These include password processing, hard-drive protection, cryptocurrency mining, resource sharing, code obfuscation, etc. We suggest memory-hard computing as a generic paradigm, where every task is amalgamated with a certain procedure requiring intensive access to RAM both in terms of size and (very importantly) bandwidth, so that transferring the computation to GPU, FPGA, and even ASIC brings little or no cost reduction. Cryptographic schemes that run in this framework become \emph{egalitarian} in the sense that both users and attackers are equal in the price-performance ratio conditions. Based on existing schemes like {Argon2} and the recent generalized-birthday proof-of-work, we suggest a generic framework and two new schemes: {MTP}, a memory-hard Proof-of-Work based on the memory-hard function with fast verification and short proofs. It can be also used for memory-hard time-lock puzzles. {MHE}, the concept of memory-hard encryption, which utilizes available RAM to strengthen the encryption for the low-entropy keys (allowing to bring back 6 letter passwords). [less ▲] Detailed reference viewed: 332 (21 UL)Tradeoff Cryptanalysis of Memory-Hard Functions Biryukov, Alex ; Khovratovich, Dmitry in 21st International Conference on the Theory and Application of Cryptology and Information Security (2015, December) We explore time-memory and other tradeoffs for memory-hard functions, which are supposed to impose significant computational and time penalties if less memory is used than intended. We analyze two schemes ... [more ▼] We explore time-memory and other tradeoffs for memory-hard functions, which are supposed to impose significant computational and time penalties if less memory is used than intended. We analyze two schemes: Catena, which has been presented at Asiacrypt 2014, and Lyra2, the fastest finalist of the Password Hashing Competition (PHC). We demonstrate that Catena's proof of tradeoff resilience is flawed, and attack it with a novel \emph{precomputation tradeoff}. We show that using $M^{2/3}$ memory instead of $M$ we may have no time penalties. We further generalize our method for a wide class of schemes with predictable memory access. For Lyra2, which addresses memory unpredictability (depending on the input), we develop a novel \emph{ranking tradeoff} and show how to decrease the time-memory and the time-area product by significant factors. We also generalize the ranking method for a wide class of schemes with unpredictable memory access [less ▲] Detailed reference viewed: 231 (12 UL)The memory-hard Argon2 password hash function Biryukov, Alex ; Khovratovich, Dmitry ; Dinu, Dumitru-Daniel et al Report (2015) This document describes the Argon2 memory-hard function for password hashing and other applications. We provide a implementer oriented description together with sample code and test vectors. The purpose ... [more ▼] This document describes the Argon2 memory-hard function for password hashing and other applications. We provide a implementer oriented description together with sample code and test vectors. The purpose is to simplify adoption of Argon2 for Internet protocols. [less ▲] Detailed reference viewed: 95 (6 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: 157 (13 UL) |
||