Results 1-20 of 89.
((uid:50000799))

Bookmark and Share    
Full Text
See detailAnalysis and Probing of Parallel Channels in the Lightning Network
Biryukov, Alexei UL; Naumenko, Gleb; Tikhomirov, Sergei UL

E-print/Working paper (2021)

Bitcoin can process only a few transactions per second, which is insufficient for a global payment network. The Lightning Network (LN) aims to address this challenge. The LN allows for low-latency bitcoin ... [more ▼]

Bitcoin can process only a few transactions per second, which is insufficient for a global payment network. The Lightning Network (LN) aims to address this challenge. The LN allows for low-latency bitcoin transfers through a network of payment channels. In contrast to regular Bitcoin transactions, payments in the LN are not globally broadcast. Thus it may improve not only Bitcoin's scalability but also privacy. However, the probing attack allows an adversary to discover channel balances, threatening users' privacy. Prior work on probing did not account for the possibility of multiple (parallel) channels between two nodes. Naive probing algorithms yield false results for parallel channels. In this work, we develop a new probing model that accurately accounts for parallel channels. We describe jamming-enhanced probing that allows for full balance information extraction in multi-channel hops, which was impossible with earlier probing methods. We quantify the attacker's information gain and propose an optimized algorithm for choosing probe amounts for N-channel hops. We demonstrate its efficiency based on real-world data using our own probing-focused LN simulator. Finally, we discuss countermeasures such as new forwarding strategies, intra-hop payment split, rebalancing, and unannounced channels. [less ▲]

Detailed reference viewed: 74 (6 UL)
Full Text
Peer Reviewed
See detailDummy Shuffling Against Algebraic Attacks in White-Box Implementations
Biryukov, Alexei UL; Udovenko, Aleksei UL

in Canteaut, Anne; Standaert, Francois-Xavier (Eds.) Advances in Cryptology -- EUROCRYPT 2021 (2021)

Detailed reference viewed: 59 (1 UL)
Full Text
See detailDynamic Universal Accumulator with Batch Update over Bilinear Groups
Vitto, Giuseppe UL; Biryukov, Alexei UL

E-print/Working paper (2021)

Detailed reference viewed: 34 (1 UL)
Full Text
Peer Reviewed
See detailCryptanalysis of a Dynamic Universal Accumulator over Bilinear Groups
Biryukov, Alexei UL; Udovenko, Aleksei UL; Vitto, Giuseppe UL

in Topics in Cryptology – CT-RSA 2021 (2021)

In this paper we cryptanalyse the two accumulator variants proposed by Au et al., which we call the alpha-based construction and the common reference string-based (CRS-based) construction. We show that if ... [more ▼]

In this paper we cryptanalyse the two accumulator variants proposed by Au et al., which we call the alpha-based construction and the common reference string-based (CRS-based) construction. We show that if non-membership witnesses are issued according to the alpha-based construction, an attacker that has access to multiple witnesses is able to efficiently recover the secret accumulator parameter alpha and completely break its security. More precisely, if p is the order of the underlying bilinear group, the knowledge of O(log p log log p) non-membership witnesses permits to successfully recover alpha. Further optimizations and different attack scenarios allow to reduce the number of required witnesses to O(log p), together with practical attack complexity. Moreover, we show that accumulator's collision resistance can be broken if just one of these non-membership witnesses is known to the attacker. We then show how all these attacks for the alpha-based construction can be easily prevented by using instead a corrected expression for witnesses. Although outside the original security model assumed by Au \etal but motivated by some possible concrete application of the scheme where the Manager must have exclusive rights for issuing witnesses (e.g. white/black list based authentication mechanisms), we show that if non-membership witnesses are issued using the CRS-based construction and the CRS is kept secret by the Manager, an attacker accessing multiple witnesses can reconstruct the CRS and compute witnesses for arbitrary new elements. In particular, if the accumulator is initialized by adding m secret elements, the knowledge of m non-membership witnesses allows to succeed in such attack. [less ▲]

Detailed reference viewed: 36 (8 UL)
Full Text
See detailAutomated Truncation of Differential Trails and Trail Clustering in ARX
Biryukov, Alexei UL; Cardoso Dos Santos, Luan UL; Feher, Daniel UL et al

E-print/Working paper (2021)

We propose a tool for automated truncation of differential trails in ciphers using modular addition, bitwise rotation, and XOR (ARX). The tool takes as input a differential trail and produces as output a ... [more ▼]

We propose a tool for automated truncation of differential trails in ciphers using modular addition, bitwise rotation, and XOR (ARX). The tool takes as input a differential trail and produces as output a set of truncated differential trails. The set represents all possible truncations of the input trail according to certain predefined rules. A linear-time algorithm for the exact computation of the differential probability of a truncated trail that follows the truncation rules is proposed. We further describe a method to merge the set of truncated trails into a compact set of non-overlapping truncated trails with associated probability and we demonstrate the application of the tool on block cipher Speck64. We have also investigated the effect of clustering of differential trails around a fixed input trail. The best cluster that we have found for 15 rounds has probability 2^−55.03 (consisting of 389 unique output differences) which allows us to build a distinguisher using 128 times less data than the one based on just the single best trail, which has probability 2^−62. Moreover, we show examples for Speck64 where a cluster of trails around a suboptimal (in terms of probability) input trail results in higher overall probability compared to a cluster obtained around the best differential trail. [less ▲]

Detailed reference viewed: 47 (6 UL)
Full Text
Peer Reviewed
See detailAlzette: A 64-Bit ARX-box (Feat. CRAX and TRAX)
Beierle, Christof; Biryukov, Alex UL; Cardoso Dos Santos, Luan UL et al

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

Detailed reference viewed: 183 (19 UL)
Full Text
Peer Reviewed
See detailLightweight AEAD and Hashing using the Sparkle Permutation Family
Beierle, Christof UL; Biryukov, Alex UL; Cardoso Dos Santos, Luan UL et al

in IACR Transactions on Symmetric Cryptology (2020), 2020(S1), 208-261

We introduce the Sparkle family of permutations operating on 256, 384 and 512 bits. These are combined with the Beetle mode to construct a family of authenticated ciphers, Schwaemm, with security levels ... [more ▼]

We introduce the Sparkle family of permutations operating on 256, 384 and 512 bits. These are combined with the Beetle mode to construct a family of authenticated ciphers, Schwaemm, with security levels ranging from 120 to 250 bits. We also use them to build new sponge-based hash functions, Esch256 and Esch384. Our permutations are among those with the lowest footprint in software, without sacrificing throughput. These properties are allowed by our use of an ARX component (the Alzette S-box) as well as a carefully chosen number of rounds. The corresponding analysis is enabled by the long trail strategy which gives us the tools we need to efficiently bound the probability of all the differential and linear trails for an arbitrary number of rounds. We also present a new application of this approach where the only trails considered are those mapping the rate to the outer part of the internal state, such trails being the only relevant trails for instance in a differential collision attack. To further decrease the number of rounds without compromising security, we modify the message injection in the classical sponge construction to break the alignment between the rate and our S-box layer. [less ▲]

Detailed reference viewed: 131 (15 UL)
Full Text
Peer Reviewed
See detailReCon: Sybil-Resistant Consensus from Reputation
Biryukov, Alex UL; Feher, Daniel UL

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

Detailed reference viewed: 169 (10 UL)
Full Text
Peer Reviewed
See detailOn degree-d zero-sum sets of full rank
Beierle, Christof UL; Biryukov, Alex UL; Udovenko, Aleksei UL

in Cryptography and Communications (2019)

A set 𝑆⊆𝔽𝑛2 is called degree-d zero-sum if the sum ∑𝑠∈𝑆𝑓(𝑠) vanishes for all n-bit Boolean functions of algebraic degree at most d. Those sets correspond to the supports of the n-bit Boolean ... [more ▼]

A set 𝑆⊆𝔽𝑛2 is called degree-d zero-sum if the sum ∑𝑠∈𝑆𝑓(𝑠) vanishes for all n-bit Boolean functions of algebraic degree at most d. Those sets correspond to the supports of the n-bit Boolean functions of degree at most n − d − 1. We prove some results on the existence of degree-d zero-sum sets of full rank, i.e., those that contain n linearly independent elements, and show relations to degree-1 annihilator spaces of Boolean functions and semi-orthogonal matrices. We are particularly interested in the smallest of such sets and prove bounds on the minimum number of elements in a degree-d zero-sum set of rank n. The motivation for studying those objects comes from the fact that degree-d zero-sum sets of full rank can be used to build linear mappings that preserve special kinds of nonlinear invariants, similar to those obtained from orthogonal matrices and exploited by Todo, Leander and Sasaki for breaking the block ciphers Midori, Scream and iScream. [less ▲]

Detailed reference viewed: 133 (5 UL)
Full Text
Peer Reviewed
See detailPrivacy Aspects and Subliminal Channels in Zcash
Biryukov, Alex UL; Feher, Daniel UL; Vitto, Giuseppe UL

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

Detailed reference viewed: 300 (19 UL)
Full Text
Peer Reviewed
See detailFELICS-AEAD: Benchmarking of Lightweight Authenticated Encryption Algorithms
Cardoso Dos Santos, Luan UL; Groszschädl, Johann UL; Biryukov, Alex UL

in Belaïd, Sonia; Güneysu, Tim (Eds.) Smart Card Research and Advanced Applications, 18th International Conference, CARDIS 2019, Prague, Czech Republic, November 11–13, 2019, Revised Selected Papers (2019, November)

Cryptographic algorithms that can simultaneously provide both encryption and authentication play an increasingly important role in modern security architectures and protocols (e.g. TLS v1.3). Dozens of ... [more ▼]

Cryptographic algorithms that can simultaneously provide both encryption and authentication play an increasingly important role in modern security architectures and protocols (e.g. TLS v1.3). Dozens of authenticated encryption systems have been designed in the past five years, which has initiated a large body of research in cryptanalysis. The interest in authenticated encryption has further risen after the National Institute of Standards and Technology (NIST) announced an initiative to standardize "lightweight" authenticated ciphers and hash functions that are suitable for resource-constrained devices. However, while there already exist some cryptanalytic results on these recent designs, little is known about their performance, especially when they are executed on small 8, 16, and 32-bit microcontrollers. In this paper, we introduce an open-source benchmarking tool suite for a fair and consistent evaluation of Authenticated Encryption with Associated Data (AEAD) algorithms written in C or assembly language for 8-bit AVR, 16-bit MSP430, and 32-bit ARM Cortex-M3 platforms. The tool suite is an extension of the FELICS benchmarking framework and provides a new AEAD-specific low-level API that allows users to collect very fine-grained and detailed results for execution time, RAM consumption, and binary code size in a highly automated fashion. FELICS-AEAD comes with two pre-defined evaluation scenarios, which were developed to resemble security-critical operations commonly carried out by real IoT applications to ensure the benchmarks are meaningful in practice. We tested the AEAD tool suite using five authenticated encryption algorithms, namely AES-GCM and the CAESAR candidates ACORN, ASCON, Ketje-Jr, and NORX, and present some preliminary results. [less ▲]

Detailed reference viewed: 186 (22 UL)
Full Text
Peer Reviewed
See detailCryptocurrencies and Blockchain Technology
Biryukov, Alex UL; García-Alfaro

in Data Privacy Management, Cryptocurrencies and Blockchain Technology - ESORICS 2019 International Workshops (2019, September)

Detailed reference viewed: 76 (0 UL)
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 (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 ▲]

Detailed reference viewed: 226 (4 UL)
Full Text
See detailWhite-Box and Asymmetrically Hard Crypto Design
Biryukov, Alex UL

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

Detailed reference viewed: 196 (8 UL)
Full Text
Peer Reviewed
See detailPortrait of a Miner in a Landscape
Biryukov, Alex UL; Feher, Daniel UL

in IEEE INFOCOM 2019 Workshop Proceedings (2019)

Mining is one of the core elements of the proof-of-work based cryptocurrency economy. In this paper we investigate the generic landscape and hierarchy of miners on the example of Ethereum and Zcash, two ... [more ▼]

Mining is one of the core elements of the proof-of-work based cryptocurrency economy. In this paper we investigate the generic landscape and hierarchy of miners on the example of Ethereum and Zcash, two blockchains that are among the top 5 in terms of USD value of created coins. Both chains used ASIC resistant proofs-of-work which favors GPU mining in order to keep mining decentralized. This however has changed with recent introduction of ASIC miners for these chains. This transition allows us to develop methods that might detect hidden ASIC mining in a chain (if it exists), and to study how the introduction of ASICs effects the decentralization of mining power. Finally, we describe how an attacker might use public blockchain information to invalidate the privacy of miners, deducing the mining hardware of individual miners and their mining rewards. [less ▲]

Detailed reference viewed: 222 (13 UL)
Full Text
Peer Reviewed
See detailTransaction Clustering Using Network Traffic Analysis for Bitcoin and Derived Blockchains
Biryukov, Alex UL; Tikhomirov, Sergei UL

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

Detailed reference viewed: 415 (7 UL)
Full Text
Peer Reviewed
See detailSecurity and Privacy of Mobile Wallet Users in Bitcoin, Dash, Monero, and Zcash
Biryukov, Alex UL; Tikhomirov, Sergei UL

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

Detailed reference viewed: 312 (13 UL)
Full Text
Peer Reviewed
See detailDeanonymization and linkability of cryptocurrency transactions based on network analysis
Biryukov, Alex UL; Tikhomirov, Sergei UL

in Proceedings of 2019 IEEE European Symposium on Security and Privacy (EuroS&P) (2019)

Bitcoin, introduced in 2008 and launched in 2009, is the first digital currency to solve the double spending problem without relying on a trusted third party. Bitcoin provides a way to transact without ... [more ▼]

Bitcoin, introduced in 2008 and launched in 2009, is the first digital currency to solve the double spending problem without relying on a trusted third party. Bitcoin provides a way to transact without any trusted intermediary, but its privacy guarantees are questionable. Despite the fact that Bitcoin addresses are not linked to any identity, multiple deanonymization attacks have been proposed. Alternative cryptocurrencies such as Dash, Monero, and Zcash aim to provide stronger privacy by using sophisticated cryptographic techniques to obfuscate transaction data. Previous work in cryptocurrency privacy mostly focused on applying data mining algorithms to the transaction graph extracted from the blockchain. We focus on a less well researched vector for privacy attacks: network analysis. We argue that timings of transaction messages leak information about their origin, which can be exploited by a well connected adversarial node. For the first time, network level attacks on Bitcoin and the three major privacy-focused cryptocurrencies have been examined. We describe the message propagation mechanics and privacy guarantees in Bitcoin, Dash, Monero, and Zcash. We propose a novel technique for linking transactions based on transaction propagation analysis. We also unpack address advertisement messages (ADDR), which under certain assumptions may help in linking transaction clusters to IP addresses of nodes. We implement and evaluate our method, deanonymizing our own transactions in Bitcoin and Zcash with a high level of accuracy. We also show that our technique is applicable to Dash and Monero. We estimate the cost of a full-scale attack on the Bitcoin mainnet at hundreds of US dollars, feasible even for a low budget adversary. [less ▲]

Detailed reference viewed: 1015 (28 UL)
Full Text
Peer Reviewed
See detailPrivacy and Linkability of Mining in Zcash
Biryukov, Alex UL; Feher, Daniel UL

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

Detailed reference viewed: 297 (21 UL)
Full Text
See detailAlzette: A 64-bit ARX-box
Beierle, Christof UL; Biryukov, Alex UL; Cardoso Dos Santos, Luan UL et al

E-print/Working paper (2019)

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. In this paper, 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, while two iterations are at least as secure as the AES super S-box. Since 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. [less ▲]

Detailed reference viewed: 135 (6 UL)