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

Mathematical Aspects of Division Property

in Cryptography and Communications (2023)

This work surveys mathematical aspects of division property, which is a state of the art technique in cryptanalysis of symmetric-key algorithms, such as authenticated encryption, block ciphers and stream ... [more ▼]

This work surveys mathematical aspects of division property, which is a state of the art technique in cryptanalysis of symmetric-key algorithms, such as authenticated encryption, block ciphers and stream ciphers. It aims to find integral distinguishers and cube attacks, which exploit weakness in the algebraic normal forms of the output coordinates of the involved vectorial Boolean functions. Division property can also be used to provide arguments for security of primitives against these attacks. The focus of this work is a formal presentation of the theory behind the division property, including rigorous proofs, which were often omitted in the existing literature. This survey covers the two major variants of division property, namely conventional and perfect division property. In addition, we explore relationships of the technique with classic degree bounds [less ▲]

Revisiting Meet-in-the-Middle Cryptanalysis of SIDH/SIKE with Application to the $IKEp182 Challenge

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

We report a break of the \$IKEp182 challenge using a meet-in-the-middle attack strategy improved with multiple SIKE-specific optimizations. The attack was executed on the HPC cluster of the University of ... [more ▼]

We report a break of the \$IKEp182 challenge using a meet-in-the-middle attack strategy improved with multiple SIKE-specific optimizations. The attack was executed on the HPC cluster of the University of Luxembourg and required less than 10 core-years and 256TiB of high-performance network storage (GPFS). Different trade-offs allow execution of the attack with similar time complexity and reduced storage requirements of only about 70TiB. [less ▲]

An overview of the Eight International Olympiad in Cryptography "Non-Stop University CRYPTO"

E-print/Working paper (2022)

Non-Stop University CRYPTO is the International Olympiad in Cryptography that was held for the eight time in 2021. Hundreds of university and school students, professionals from 33 countries worked on ... [more ▼]

Non-Stop University CRYPTO is the International Olympiad in Cryptography that was held for the eight time in 2021. Hundreds of university and school students, professionals from 33 countries worked on mathematical problems in cryptography during a week. The aim of the Olympiad is to attract attention to curious and even open scientific problems of modern cryptography. In this paper, problems and their solutions of the Olympiad’2021 are presented. We consider 19 problems of varying difficulty and topics: ciphers, online machines, passwords, binary strings, permutations, quantum circuits, historical ciphers, elliptic curves, masking, implementation on a chip, etc. We discuss several open problems on quantum error correction, finding special permutations and s-Boolean sharing of a function, obtaining new bounds on the distance to affine vectorial functions. [less ▲]

Cryptanalysis of a Dynamic Universal Accumulator over Bilinear Groups

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

The Seventh International Olympiad in Cryptography NSUCRYPTO: problems and solutions

E-print/Working paper (2021)

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 the Sixth International Olympiad in Cryptography NSUCRYPTO

E-print/Working paper (2020)

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

Cryptanalysis of SKINNY in the Framework of the SKINNY 2018--2019 Cryptanalysis Competition

in Patterson, Kenneth G.; Stebila, Douglas (Eds.) Selected Areas in Cryptography -- SAC 2019 (2019)

In April 2018, Beierle et al. launched the 3rd SKINNY cryptanalysis competition, a contest that aimed at motivating the analysis of their recent tweakable block cipher SKINNY . In contrary to the previous ... [more ▼]

In April 2018, Beierle et al. launched the 3rd SKINNY cryptanalysis competition, a contest that aimed at motivating the analysis of their recent tweakable block cipher SKINNY . In contrary to the previous editions, the focus was made on practical attacks: contestants were asked to recover a 128-bit secret key from a given set of 2^20 plaintext blocks. The suggested SKINNY instances are 4- to 20-round reduced variants of SKINNY-64-128 and SKINNY-128-128. In this paper, we explain how to solve the challenges for 10-round SKINNY-128-128 and for 12-round SKINNY-64-128 in time equivalent to roughly 2^52 simple operations. Both techniques benefit from the highly biased sets of messages that are provided and that actually correspond to the encryption of various books in ECB mode. [less ▲]