Advancing the Meet-in-the-Filter Technique: Applications to CHAM and KATAN

in Smith, Benjamin; Wu, Huapeng (Eds.) Selected Areas in Cryptography (in press)

Recently, Biryukov et al. presented a new technique for key recovery in differential cryptanalysis, called meet-in-the-filter (MiF). In this work, we develop theoretical and practical aspects of the ... [more ▼]

Recently, Biryukov et al. presented a new technique for key recovery in differential cryptanalysis, called meet-in-the-filter (MiF). In this work, we develop theoretical and practical aspects of the technique, which helps understanding and simplifies application. In particular, we show bounds on MiF complexity and conditions when the MiF-enhanced attack may reach them. We present a method based on trail counting which allows to estimate filtering strength of involved rounds and perform consequent complexity analysis with pen and paper, compared to the computer-aided approach of the original work. Furthermore, we show how MiF can be combined with plaintext structures for linear key schedules, allowing to increase the number of attacked rounds or to reduce the data complexity. We illustrate our methods on block cipher families CHAM and KATAN and show best-to-date single-key differential attacks for these ciphers. [less ▲]

Analysis and Probing of Parallel Channels in the Lightning Network

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

Dynamic Universal Accumulator with Batch Update over Bilinear Groups

E-print/Working paper (2021)

Automated Truncation of Differential Trails and Trail Clustering in ARX

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

Lightweight AEAD and Hashing using the Sparkle Permutation Family

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

On degree-d zero-sum sets of full rank

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

FELICS-AEAD: Benchmarking of Lightweight Authenticated Encryption Algorithms

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

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

Portrait of a Miner in a Landscape

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

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