References of "Khovratovich, Dmitry 50002087"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailTriathlon of Lightweight Block Ciphers for the Internet of Things
Dinu, Dumitru-Daniel UL; Le Corre, Yann UL; Khovratovich, Dmitry UL 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: 87 (1 UL)
Full Text
See detailGuru: Universal Reputation Module for Distributed Consensus Protocols
Biryukov, Alex UL; Feher, Daniel UL; Khovratovich, Dmitry UL

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: 403 (29 UL)
Full Text
Peer Reviewed
See detailFindel: Secure Derivative Contracts for Ethereum
Biryukov, Alex UL; Khovratovich, Dmitry UL; Tikhomirov, Sergei UL

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: 1539 (85 UL)
Full Text
Peer Reviewed
See detailEquihash: asymmetric proof-of-work based on the Generalized Birthday problem
Biryukov, Alex UL; Khovratovich, Dmitry UL

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: 5655 (40 UL)
Full Text
Peer Reviewed
See detailMultiset-Algebraic Cryptanalysis of Reduced Kuznyechik, Khazad, and secret SPNs
Biryukov, Alex UL; Khovratovich, Dmitry UL; Perrin, Léo Paul UL

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: 126 (9 UL)
Full Text
Peer Reviewed
See detailEgalitarian computing
Biryukov, Alex UL; Khovratovich, Dmitry UL

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: 690 (24 UL)
Full Text
Peer Reviewed
See detailArgon2: New Generation of Memory-Hard Functions for Password Hashing and Other Applications
Biryukov, Alex UL; Dinu, Dumitru-Daniel UL; Khovratovich, Dmitry UL

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: 119 (1 UL)
Full Text
Peer Reviewed
See detailTradeoff Cryptanalysis of Memory-Hard Functions
Biryukov, Alex UL; Khovratovich, Dmitry UL

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: 325 (12 UL)
Full Text
See detailThe memory-hard Argon2 password hash function
Biryukov, Alex UL; Khovratovich, Dmitry UL; Dinu, Dumitru-Daniel UL 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: 130 (6 UL)
Peer Reviewed
See detailTriathlon of Lightweight Block Ciphers for the Internet of Things
Dinu, Dumitru-Daniel UL; Le Corre, Yann UL; Khovratovich, Dmitry UL 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: 349 (30 UL)
Peer Reviewed
See detailFELICS - Fair Evaluation of Lightweight Cryptographic Systems
Dinu, Dumitru-Daniel UL; Biryukov, Alex UL; Groszschädl, Johann UL 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: 372 (14 UL)
Full Text
See detailArgon and Argon2
Biryukov, Alex UL; Dinu, Dumitru-Daniel UL; Khovratovich, Dmitry UL

Report (2015)

This is a design specification for the functions Argon and Argon2 for the international password hashing competition (PHC), 2013-2015. Argon is our original submission to PHC. It is a multipurpose hash ... [more ▼]

This is a design specification for the functions Argon and Argon2 for the international password hashing competition (PHC), 2013-2015. Argon is our original submission to PHC. It is a multipurpose hash function, that is optimized for highest resilience against tradeoff attacks, so that any, even small memory reduction would lead to significant time and computational penalties. Argon can be used for password hashing, key derivation, or any other memory-hard computation (e.g., for cryptocurrencies). Argon2 summarizes the state of the art in the design of memory-hard functions. It is a streamlined and simple design. It aims at the highest memoryfilling rate and effective use of multiple computing units, while still providing defense against tradeoff attacks. Argon2 is optimized for the x86 architecture and exploits the cache and memory organization of the recent Intel and AMD processors. Argon2 has two variants: Argon2d and Argon2i. Argon2d is faster and uses data-depending memory access, which makes it suitable for cryptocurrencies and applications with no threats from side-channel timing attacks. Argon2i uses data-independent memory access, which is preferred for password hashing and password based key derivation. Argon2i is slower as it makes more passes over the memory to protect from tradeoff attacks. We recommend Argon for the applications that aim for the highest tradeoff resilience and want to guarantee prohibitive time and computational penalties on any memory-reducing implementation. According to our cryptanalytic algorithms, an attempt to use half of the requested memory (for instance, 64 MB instead of 128 MB) results in the speed penalty factor of 140 and in the penalty 218. The penalty grows exponentially as the available memory decreases, which effectively prohibits the adversary to use any smaller amount of memory. Such high computational penalties are a unique feature of Argon. We recommend Argon2 for the applications that aim for high performance. Both versions of Argon2 allow to fill 1 GB of RAM in a fraction of second, and smaller amounts even faster. It scales easily to the arbitrary number of parallel computing units. Its design is also optimized for clarity to ease analysis and implementation. [less ▲]

Detailed reference viewed: 335 (14 UL)
Full Text
Peer Reviewed
See detailRotational Cryptanalysis of ARX Revisited
Khovratovich, Dmitry UL; Nikolic, Ivica; Pieprzyk, Josef et al

in Fast Software Encryption - 22nd International Workshop, FSE 2015 Istanbul, Turkey, March 8-11, 2015, Revised Selected Papers (2015)

Detailed reference viewed: 90 (0 UL)
Full Text
Peer Reviewed
See detailCryptographic Schemes Based on the ASASA Structure: Black-box, White-box, and Public-key
Biryukov, Alex UL; Bouillaguet, Charles; Khovratovich, Dmitry UL

in 20th International Conference on the Theory and Application of Cryptology and Information Security (2014, December)

In this paper we pick up an old challenge to design public key or white-box constructions from symmetric cipher components. We design several encryption schemes based on the ASASA structure ranging from ... [more ▼]

In this paper we pick up an old challenge to design public key or white-box constructions from symmetric cipher components. We design several encryption schemes based on the ASASA structure ranging from fast and generic symmetric ciphers to compact public key and white-box constructions based on generic affine transformations combined with specially designed low degree non-linear layers. While explaining our design process we show several instructive attacks on the weaker variants of our schemes. [less ▲]

Detailed reference viewed: 312 (11 UL)
Full Text
Peer Reviewed
See detailDeanonymisation of clients in Bitcoin P2P network
Biryukov, Alex UL; Khovratovich, Dmitry UL; Pustogarov, Ivan UL

in ACM Conference on Computer and Communications Security (CCS) (2014, November)

Bitcoin is a digital currency which relies on a distributed set of miners to mint coins and on a peer-to-peer network to broadcast transactions. The identities of Bitcoin users are hidden behind ... [more ▼]

Bitcoin is a digital currency which relies on a distributed set of miners to mint coins and on a peer-to-peer network to broadcast transactions. The identities of Bitcoin users are hidden behind pseudonyms (public keys) which are recommended to be changed frequently in order to increase transaction unlinkability. We present an efficient method to deanonymize Bitcoin users, which allows to link user pseudonyms to the IP addresses where the transactions are generated. Our techniques work for the most common and the most challenging scenario when users are behind NATs or firewalls of their ISPs. They allow to link transactions of a user behind a NAT and to distinguish connections and transactions of different users behind the same NAT. We also show that a natural countermeasure of using Tor or other anonymity services can be cut-off by abusing anti-DoS countermeasures of the bitcoin network. Our attacks require only a few machines and have been experimentally verified. We propose several countermeasures to mitigate these new attacks. [less ▲]

Detailed reference viewed: 14128 (135 UL)
Full Text
Peer Reviewed
See detailPAEQ: Parallelizable Permutation-Based Authenticated Encryption
Biryukov, Alex UL; Khovratovich, Dmitry UL

in 17th Information Security Conference (2014, November)

We propose a new authenticated encryption scheme PAEQ, which employs a fixed public permutation. In contrast to the recent sponge-based proposals, our scheme is fully parallelizable. It also allows ... [more ▼]

We propose a new authenticated encryption scheme PAEQ, which employs a fixed public permutation. In contrast to the recent sponge-based proposals, our scheme is fully parallelizable. It also allows flexible key and nonce length, and is one of the few which achieves 128-bit security for both confidentiality and data authenticity with the same key length. The permutation within PAEQ is a new design called AESQ, which is based on AES and is 512 bits wide. In contrast to similar constructions used in the SHA-3 competition, our permutation fully benefits from the newest Intel AES instructions and runs at 2.5 cycles per byte if used as the counter-mode PRF. [less ▲]

Detailed reference viewed: 288 (3 UL)
Full Text
Peer Reviewed
See detailCollision Spectrum, Entropy Loss, T-Sponges, and Cryptanalysis of GLUON-64
Perrin, Léo Paul UL; Khovratovich, Dmitry UL

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: 204 (31 UL)
Full Text
Peer Reviewed
See detailKey Wrapping with a Fixed Permutation
Khovratovich, Dmitry UL

in Topics in Cryptology - {CT-RSA} 2014 - The Cryptographer's Track at the {RSA} Conference 2014, San Francisco, CA, USA, February 25-28, 2014. Proceedings (2014)

We present an efficient key wrapping scheme that uses a single public permutation as the basic element. As the scheme does not rely on block ciphers, it can be used on a resource-constrained device where ... [more ▼]

We present an efficient key wrapping scheme that uses a single public permutation as the basic element. As the scheme does not rely on block ciphers, it can be used on a resource-constrained device where such a permutation comes from an implemented hash function, regular (SHA-3/Keccak) or lightweight one (Quark, Photon). The scheme is capable of wrapping keys up to 1400 bits long and processing arbitrarily long headers. Our scheme easily delivers the security level of 128 bits or higher with the master key of the same length. We use the security notion from the concept of Deterministic Authenticated Encryption (DAE) introduced by Rogaway and Shrimpton. Though the permutation is inevitably modeled as a random permutation, the resulting proof of security is short and easy to verify and hence provide a reasonable alternative to authentication modes based on block ciphers [less ▲]

Detailed reference viewed: 74 (1 UL)
See detailNew approaches to the cryptanalysis of symmetric primitives
Khovratovich, Dmitry UL

Doctoral thesis (2010)

Detailed reference viewed: 58 (5 UL)
Full Text
Peer Reviewed
See detailKey Recovery Attacks of Practical Complexity on AES-256 Variants with up to 10 Rounds
Biryukov, Alex UL; Dunkelman, Orr; Keller, Nathan et al

in EUROCRYPT 2010 (2010)

AES is the best known and most widely used block cipher. Its three versions (AES-128, AES-192, and AES-256) differ in their key sizes (128 bits, 192 bits and 256 bits) and in their number of rounds (10 ... [more ▼]

AES is the best known and most widely used block cipher. Its three versions (AES-128, AES-192, and AES-256) differ in their key sizes (128 bits, 192 bits and 256 bits) and in their number of rounds (10, 12, and 14, respectively). While for AES-128, there are no known attacks faster than exhaustive search, AES-192 and AES-256 were recently shown to be breakable by attacks which require 2^176 and 2^99.5 time, respectively. While these complexities are much faster than exhaustive search, they are completely non-practical, and do not seem to pose any real threat to the security of AES-based systems. In this paper we aim to increase our understanding of AES security, and we concentrate on attacks with practical complexity, i.e., attacks that can be experimentally verified. We show attacks on reduced-round variants of AES-256 with up to 10 rounds with complexity which is feasible. One of our attacks uses only two related keys and 239 time to recover the complete 256-bit key of a 9-round version of AES-256 (the best previous attack on this variant required 4 related keys and 2^120 time). Another attack can break a 10-round version of AES-256 in 2^45 time, but it uses a stronger type of related subkey attack (the best previous attack on this variant required 64 related keys and 2^172 time). While the full AES-256 cannot be directly broken by these attacks, the fact that 10 rounds can be broken with such a low complexity raises serious concerns about the remaining safety margin offered by AES-256. [less ▲]

Detailed reference viewed: 167 (2 UL)