Alzette: A 64-Bit ARX-box (Feat. CRAX and TRAX)

in Micciancio, Daniele; Ristenpart, Thomas (Eds.) Advances in Cryptology -- CRYPTO 2020, 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17-21, 2020, Proceedings, Part III (2020, August)

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. 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, and two are at least as secure as the AES super S-box. As 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. We further discuss how such wide S-boxes could be used to construct round functions of 64-, 128- and 256-bit (tweakable) block ciphers with good cryptographic properties that are guaranteed even in the related-tweak setting. We use these structures to design a very lightweight 64-bit block cipher (Crax) which outperforms SPECK-64/128 for short messages on micro-controllers, and a 256-bit tweakable block cipher (Trax) which can be used to obtain strong security guarantees against powerful adversaries (nonce misuse, quantum attacks). [less ▲]

ReCon: Sybil-Resistant Consensus from Reputation

in Pervasive and Mobile Computing (2020)

In this paper we describe how to couple reputation systems with distributed consensus protocols to provide a scalable permissionless consensus protocol with a low barrier of entry, while still providing ... [more ▼]

In this paper we describe how to couple reputation systems with distributed consensus protocols to provide a scalable permissionless consensus protocol with a low barrier of entry, while still providing strong resistance against Sybil attacks for large peer-to-peer networks of untrusted validators. We introduce reputation module ReCon, which can be laid on top of various consensus protocols such as PBFT or HoneyBadger. The protocol takes external reputation ranking as input and then ranks nodes based on the outcomes of consensus rounds run by a small committee, and adaptively selects the committee based on the current reputation. ReCon can tolerate larger threshold of malicious nodes (up to slightly above 1/2) compared to the 1/3 limit of BFT consensus algorithms. [less ▲]

Privacy Aspects and Subliminal Channels in Zcash

in Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Securit (2019, November)

In this paper we analyze two privacy and security issues for the privacy-oriented cryptocurrency Zcash. First we study shielded transactions and show ways to fingerprint user transactions, including ... [more ▼]

In this paper we analyze two privacy and security issues for the privacy-oriented cryptocurrency Zcash. First we study shielded transactions and show ways to fingerprint user transactions, including active attacks.We introduce two new attacks which we call Danaan-gift attack and Dust attack. Following the recent Sapling update of Zcash protocol we study the interaction between the new and the old zk-SNARK protocols and the effects of their interaction on transaction privacy. In the second part of the paper we check for the presence of subliminal channels in the zk-SNARK protocol and in Pedersen Commitments. We show presence of efficient 70-bit channels which could be used for tagging of shielded transactions which would allow the attacker (malicious transaction verifier) to link transactions issued by a maliciously modified zk-SNARK prover, while would be indistinguishable from regular transactions for the honest verifier/user. We discuss countermeasures against both of these privacy issues. [less ▲]

Triathlon of Lightweight Block Ciphers for the Internet of Things

in Journal of Cryptographic Engineering (2019), 9(3), 283-302

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

White-Box and Asymmetrically Hard Crypto Design

Presentation (2019, May 18)

In this talk we surveyed some our recent works related to the area of white-box cryptogaphy. Specifically the resource hardness framework from Asiacrypt'2017 and its relation to the incompressibility and ... [more ▼]

In this talk we surveyed some our recent works related to the area of white-box cryptogaphy. Specifically the resource hardness framework from Asiacrypt'2017 and its relation to the incompressibility and weak-WBC. [less ▲]

Privacy and Linkability of Mining in Zcash

in 2019 IEEE Conference on Communications and Network Security (CNS) (2019)

With the growth in popularity for cryptocurrencies the need for privacy preserving blockchains is growing as well. Zcash is such a blockchain, providing transaction privacy through zero-knowledge proofs ... [more ▼]

With the growth in popularity for cryptocurrencies the need for privacy preserving blockchains is growing as well. Zcash is such a blockchain, providing transaction privacy through zero-knowledge proofs. In this paper we analyze transaction linkability in Zcash based on the currency minting transactions (mining). Using predictable usage patterns and clustering heuristics on mining transactions an attacker can link to publicly visible addresses over 84% of the volume of the transactions that use a ZK-proof. Since majority of Zcash transactions are not yet using ZK-proofs, we show that overall 95.5% of the total number of Zcash transactions are potentially linkable to public addresses by just observing the mining activity. [less ▲]

Security and Privacy of Mobile Wallet Users in Bitcoin, Dash, Monero, and Zcash

in Pervasive and Mobile Computing (2019)

Mobile devices play an increasingly important role in the cryptocurrency ecosystem, yet their privacy guarantees remain unstudied. To verify transactions, they either trust a server or use simple payment ... [more ▼]

Mobile devices play an increasingly important role in the cryptocurrency ecosystem, yet their privacy guarantees remain unstudied. To verify transactions, they either trust a server or use simple payment verification. First, we review the security and privacy of popular Android wallets for Bitcoin and the three major privacy-focused cryptocurrencies (Dash, Monero, Zcash). Then, we investigate the network-level properties of cryptocurrencies and propose a method of transaction clustering based on timing analysis. We implement and test our method on selected wallets and show that a moderately resourceful attacker can correlate transactions issued from one device with relatively high accuracy. [less ▲]

Transaction Clustering Using Network Traffic Analysis for Bitcoin and Derived Blockchains

in IEEE INFOCOM 2019 Workshop Proceedings (2019)

Bitcoin is a decentralized digital currency introduced in 2008 and launched in 2009. Bitcoin provides a way to transact without any trusted intermediary, but its privacy guarantees are questionable, and ... [more ▼]

Bitcoin is a decentralized digital currency introduced in 2008 and launched in 2009. Bitcoin provides a way to transact without any trusted intermediary, but its privacy guarantees are questionable, and multiple deanonymization attacks have been proposed. Cryptocurrency privacy research has been mostly focused on blockchain analysis, i.e., extracting information from the transaction graph. We focus on another vector for privacy attacks: network analysis. We describe the message propagation mechanics in Bitcoin and propose a novel technique for transaction clustering based on network traffic analysis. We show that timings of transaction messages leak information about their origin, which can be exploited by a well connected adversarial node. We implement and evaluate our method in the Bitcoin testnet with a high level of accuracy, deanonymizing our own transactions issued from a desktop wallet (Bitcoin Core) and from a mobile (Mycelium) wallet. Compared to existing approaches, we leverage the propagation information from multiple peers, which allows us to overcome an anti-deanonymization technique (“diffusion”) used in Bitcoin. [less ▲]

Attacks and Countermeasures for White-box Designs

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

Optimal First-Order Boolean Masking for Embedded IoT Devices

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