References of "Biryukov, Alexei 50000799"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailAdvancing the Meet-in-the-Filter Technique: Applications to CHAM and KATAN
Biryukov, Alexei UL; Teh, Je Sen UL; Udovenko, Aleksei UL

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

Detailed reference viewed: 11 (0 UL)
See detailMeet-in-the-Filter and Dynamic Counting with Applications to Speck
Biryukov, Alexei UL; Cardoso Dos Santos, Luan UL; Teh, Je Sen UL et al

E-print/Working paper (2022)

We propose a new cryptanalytic tool for differential cryptanalysis, called meet-in-the-filter (MiF). It is suitable for ciphers with a slow or incomplete diffusion layer such as the ones based on Addition ... [more ▼]

We propose a new cryptanalytic tool for differential cryptanalysis, called meet-in-the-filter (MiF). It is suitable for ciphers with a slow or incomplete diffusion layer such as the ones based on Addition-Rotation-XOR (ARX). The main idea of the MiF technique is to stop the difference propagation earlier in the cipher, allowing to use differentials with higher probability. This comes at the expense of a deeper analysis phase in the bottom rounds possible due to the slow diffusion of the target cipher. The MiF technique uses a meet-in-the-middle matching to construct differential trails connecting the differential’s output and the ciphertext difference. The proposed trails are used in the key recovery procedure, reducing time complexity and allowing flexible time-data trade-offs. In addition, we show how to combine MiF with a dynamic counting technique for key recovery. We illustrate MiF in practice by reporting improved attacks on the ARXbased family of block ciphers Speck. We improve the time complexities of the best known attacks up to 15 rounds of Speck32 and 20 rounds of Speck64/128. Notably, our new attack on 11 rounds of Speck32 has practical analysis and data complexities of 224.66 and 226.70 respectively, and was experimentally verified, recovering the master key in a matter of seconds. It significantly improves the previous deep learning-based attack by Gohr from CRYPTO 2019, which has time complexity 238. As an important milestone, our conventional cryptanalysis method sets a new high benchmark to beat for cryptanalysis relying on machine learning. [less ▲]

Detailed reference viewed: 12 (0 UL)
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: 87 (7 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: 64 (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: 41 (11 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: 51 (6 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: 41 (2 UL)