Guru: Universal Reputation Module for Distributed Consensus Protocols

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 ▲]

Equihash: asymmetric proof-of-work based on the Generalized Birthday problem

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 ▲]

Egalitarian computing

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 ▲]

Tradeoff Cryptanalysis of Memory-Hard Functions

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 ▲]

FELICS - Fair Evaluation of Lightweight Cryptographic Systems

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 ▲]

Argon and Argon2

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 ▲]

Cryptographic Schemes Based on the ASASA Structure: Black-box, White-box, and Public-key

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 ▲]

Deanonymisation of clients in Bitcoin P2P network

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 ▲]

Key Wrapping with a Fixed Permutation

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 ▲]

Rotational Cryptanalysis of ARX

in Fast Software Encryption 17th International Workshop, FSE 2010, Seoul, Korea (2010)

In this paper we analyze the security of systems based on modular additions, rotations, and XORs (ARX systems). We provide both theoretical support for their security and practical cryptanalysis of real ... [more ▼]

In this paper we analyze the security of systems based on modular additions, rotations, and XORs (ARX systems). We provide both theoretical support for their security and practical cryptanalysis of real ARX primitives. We use a technique called rotational cryptanalysis , that is universal for the ARX systems and is quite efficient. We illustrate the method with the best known attack on reduced versions of the block cipher Threefish (the core of Skein). Additionally, we prove that ARX with constants are functionally complete, i.e. any function can be real- ized with these operations. [less ▲]