bluuebunny/crossref_metadata_2025 huggingface dataset:
Cryptanalysis of Haraka
Authors: Jean Jérémy
Published: November 2020

In this paper, we describe attacks on the recently proposed Haraka hash functions. First, for the two hash functions Haraka-256/256 and Haraka-512/256 in the family, we show how two colliding messages can be constructed in about 216 function evaluations. Second, we invalidate the preimage security claim for Haraka-512/256 with an attack finding one preimage in about 2192 function evaluations. These attacks are possible thanks to symmetries in the internal state that are preserved over several rounds.
Invariant Subspace Attack Against Midori64 and The Resistance Criteria for S-box Designs
Authors: Guo Jian , Jean Jérémy , Nikolic Ivica , Qiao Kexin , Sasaki Yu , Sim Siang Meng
Published: November 2020

We present an invariant subspace attack on the block cipher Midori64, proposed at Asiacrypt 2015. Our analysis shows that Midori64 has a class of 232 weak keys. Under any such key, the cipher can be distinguished with only a single chosen query, and the key can be recovered in 216 time with two chosen queries. As both the distinguisher and the key recovery have very low complexities, we confirm our analysis by implementing the attacks. Some tweaks of round constants make Midori64 more resistant to the attacks, but some lead to even larger weak-key classes. To eliminate the dependency on the round constants, we investigate alternative S-boxes for Midori64 that provide certain level of security against the found invariant subspace attacks, regardless of the choice of the round constants. Our search for S-boxes is enhanced with a dedicated tool which evaluates the depth of any given 4-bit S-box that satisfies certain design criteria. The tool may be of independent interest to future S-box designs.
Linking Online Misuse-Resistant Authenticated Encryption and Blockwise Attack Models
Authors: Endignoux Guillaume , Vizár Damian
Published: November 2020

Real-world applications of authenticated encryption often require the encryption to be computable online, e.g. to compute the ith block of ciphertext after having processed the first i blocks of plaintext. A significant line of research was dedicated to identifying security notions for online authenticated encryption schemes, that capture various security goals related to real-life scenarios. Fouque, Joux, Martinet and Valette proposed definitions of privacy and integrity against adversaries that can query their oracles in a blockwise-adaptive manner, to model memory-constrained applications. A decade later, Fleischmann, Forler and Lucks proposed the notion of online nonce misuse-resistant authenticated encryption (OAE) to capture the security of online authenticated encryption under nonce-reuse. In this work we investigate the relation between these notions. We first recast the blockwise notions of Fouque et al. to make them compatible with online authenticated encryption schemes that support headers. We then show that OAE and the conjunction of the blockwise notions are “almost” equivalent. We identify the missing property on the side of blockwise notions, and formalize it under the name PR-TAG. With PR-TAG being just an auxiliary definition, the equivalence we finally show suggests that OAE and the blockwise model for online authenticated encryption capture essentially the same notion of security.
Improved Parameter Estimates for Correlation and Capacity Deviates in Linear Cryptanalysis
Authors: Blondeau Céline , Nyberg Kaisa
Published: November 2020

Statistical attacks form an important class of attacks against block ciphers. By analyzing the distribution of the statistics involved in the attack, cryptanalysts aim at providing a good estimate of the data complexity of the attack. Recently multiple papers have drawn attention to how to improve the accuracy of the estimated success probability of linear key-recovery attacks. In particular, the effect of the key on the distribution of the sample correlation and capacity has been investigated and new statistical models developed. The major problem that remains open is how to obtain accurate estimates of the mean and variance of the correlation and capacity. In this paper, we start by presenting a solution for a linear approximation which has a linear hull comprising a number of strong linear characteristics. Then we generalize this approach to multiple and multidimensional linear cryptanalysis and derive estimates of the variance of the test statistic. Our simplest estimate can be computed given the number of the strong linear approximations involved in the offline analysis and the resulting estimate of the capacity. The results tested experimentally on SMALLPRESENT-[4] show the accuracy of the estimated variance is significantly improved. As an application we give more realistic estimates of the success probability of the multidimensional linear attack of Cho on 26 rounds of PRESENT.
Practical Key-Recovery Attack on MANTIS5
Authors: Dobraunig Christoph , Eichlseder Maria , Kales Daniel , Mendel Florian
Published: November 2020

MANTIS is a lightweight tweakable block cipher published at CRYPTO 2016. In addition to the full 14-round version, MANTIS7, the designers also propose an aggressive 10-round version, MANTIS5. The security claim for MANTIS5 is resistance against “practical attacks”, defined as related-tweak attacks with data complexity 2d less than 230 chosen plaintexts (or 240 known plaintexts), and computational complexity at most 2126−d. We present a key-recovery attack against MANTIS5 with 228 chosen plaintexts and a computational complexity of about 238 block cipher calls, which violates this claim. Our attack is based on a family of differential characteristics and exploits several properties of the lightweight round function and tweakey schedule. To verify the validity of the attack, we also provide a practical implementation which recovers the full key in about 1 core hour using 230 chosen plaintexts.
Meet-in-the-Middle Attacks on Classes of Contracting and Expanding Feistel Constructions
Authors: Guo Jian , Jean Jérémy , Nikolic Ivica , Sasaki Yu
Published: November 2020

We show generic attacks on unbalanced Feistel ciphers based on the meet-in-the-middle technique. We analyze two general classes of unbalanced Feistel structures, namely contracting Feistels and expanding Feistels. In both of the cases, we consider the practical scenario where the round functions are keyless and known to the adversary. In the case of contracting Feistels with 4 branches, we show attacks on 16 rounds when the key length k (in bits) is as large as the block length n (in bits), and up to 24 rounds when k = 2n. In the case of expanding Feistels, we consider two scenarios: one, where different nonlinear functions without particular structures are used in the round function, and a more practical one, where a single nonlinear is used but different linear functions are introduced in the state update. In the former case, we propose generic attacks on 13 rounds when k = n, and up to 21 rounds when k = 2n. In the latter case, 16 rounds can be attacked for k = n, and 24 rounds for k = 2n.
On Ciphers that Continuously Access the Non-Volatile Key
Authors: Mikhalev Vasily , Armknecht Frederik , Müller Christian
Published: November 2020

Due to the increased use of devices with restricted resources such as limited area size, power or energy, the community has developed various techniques for designing lightweight ciphers. One approach that is increasingly discussed is to use the cipher key that is stored on the device in non-volatile memory not only for the initialization of the registers but during the encryption/decryption process as well. Recent examples are the ciphers Midori (Asiacrypt’15) and Sprout (FSE’15). This may on the one hand help to save resources, but also may allow for a stronger key involvement and hence higher security. However, only little is publicly known so far if and to what extent this approach is indeed practical. Thus, cryptographers without strong engineering background face the problem that they cannot evaluate whether certain designs are reasonable (from a practical point of view) which hinders the development of new designs.In this work, we investigate this design principle from a practical point of view. After a discussion on reasonable approaches for storing a key in non-volatile memory, motivated by several commercial products we focus on the case that the key is stored in EEPROM. Here, we highlight existing constraints and derive that some designs, based on the impact on their throughput, are better suited for the approach of continuously reading the key from all types of non-volatile memory. Based on these findings, we improve the design of Sprout for proposing a new lightweight stream cipher that (i) has a significantly smaller area size than almost all other stream ciphers and (ii) can be efficiently realized using common non-volatile memory techniques. Hence, we see our work as an important step towards putting such designs on a more solid ground and to initiate further discussions on realistic designs.
Cryptanalysis of GOST2
Authors: Ashur Tomer , Bar-On Achiya , Dunkelman Orr
Published: November 2020

GOST 28147 is a 256-bit key 64-bit block cipher developed by the USSR, later adopted by the Russian government as a national standard. In 2010, GOST was suggested to be included in ISO/IEC 18033-3, but was rejected due to weaknesses found in its key schedule. In 2015, a new version of GOST was suggested with the purpose of mitigating such attacks. In this paper, we show that similar weaknesses exist in the new version as well. More specifically, we present a fixed-point attack on the full cipher with time complexity of 2237 encryptions. We also present a reflection attack with time complexity of 2192 for a key that is chosen from a class of 2224 weak keys. Finally, we discuss an impossible reflection attack which improves on exhaustive search by a factor of 2e, and several possible related-key attacks.
A Note on 5-bit Quadratic Permutations’ Classification
Authors: Božilov Dušan , Bilgin Begül , Sahin Hacı Ali
Published: November 2020

Classification of vectorial Boolean functions up to affine equivalence is used widely to analyze various cryptographic and implementation properties of symmetric-key algorithms. We show that there exist 75 affine equivalence classes of 5-bit quadratic permutations. Furthermore, we explore important cryptographic properties of these classes, such as linear and differential properties and degrees of their inverses, together with multiplicative complexity and existence of uniform threshold realizations.
Security Notions for Bidirectional Channels
Authors: Marson Giorgia Azzurra , Poettering Bertram
Published: November 2020

This paper closes a definitional gap in the context of modeling cryptographic two-party channels. We note that, while most security models for channels consider exclusively unidirectional communication, real-world protocols like TLS and SSH are rather used for bidirectional interaction. The motivational question behind this paper is: Can analyses conducted with the unidirectional setting in mind—including the current ones for TLS and SSH—also vouch for security in the case of bidirectional channel usage? And, in the first place, what does security in the bidirectional setting actually mean? After developing confidentiality and integrity notions for bidirectional channels, we analyze a standard way of combining two unidirectional channels to realize one bidirectional channel. Although it turns out that this construction is, in general, not as secure as commonly believed, we confirm that for many practical schemes security is provided also in the bidirectional sense.
Refined Probability of Differential Characteristics Including Dependency Between Multiple Rounds
Authors: Canteaut Anne , Lambooij Eran , Neves Samuel , Rasoolzadeh Shahram , Sasaki Yu , Stevens Marc
Published: November 2020

The current paper studies the probability of differential characteristics for an unkeyed (or with a fixed key) construction. Most notably, it focuses on the gap between two probabilities of differential characteristics: probability with independent S-box assumption, pind, and exact probability, pexact. It turns out that pexact is larger than pind in Feistel network with some S-box based inner function. The mechanism of this gap is then theoretically analyzed. The gap is derived from interaction of S-boxes in three rounds, and the gap depends on the size and choice of the S-box. In particular the gap can never be zero when the S-box is bigger than six bits. To demonstrate the power of this improvement, a related-key differential characteristic is proposed against a lightweight block cipher RoadRunneR. For the 128-bit key version, pind of 2−48 is improved to pexact of 2−43. For the 80-bit key version, pind of 2−68 is improved to pexact of 2−62. The analysis is further extended to SPN with an almost-MDS binary matrix in the core primitive of the authenticated encryption scheme Minalpher: pind of 2−128 is improved to pexact of 2−96, which allows to extend the attack by two rounds.
Analysis and Improvement of Entropy Estimators in NIST SP 800-90B for Non-IID Entropy Sources
Authors: Zhu Shuangyi , Ma Yuan , Chen Tianyu , Lin Jingqiang , Jing Jiwu
Published: November 2020

Random number generators (RNGs) are essential for cryptographic applications. In most practical applications, the randomness of RNGs is provided by entropy sources. If the randomness is less than the expected, the security of cryptographic applications could be undermined. Accurate entropy estimation is a critical method for the evaluation of RNG security, and significant overestimation and underestimation are both inadvisable. The NIST Special Publication 800-90B is one of the most common certifications for entropy estimation. It makes no assumption of the entropy source and provides min-entropy estimation results by a set of entropy estimators. It estimates the entropy sources in two tracks: the IID (independent and identically distributed) track and non-IID track. In practice, non-IID entropy sources are more common, as physical phenomenon, sampling process or external perturbation could cause the dependency of the outputs. In this paper, we prove that the Collision Estimate and the Compression Estimate in non-IID track could provide significant underestimates in theory. In order to accurately estimate the min-entropy of non-IID sources, we provide a formula of minentropybased on conditional probability, and propose a new estimator to approximate the result of this formula. Finally, we perform experiments to compare our estimator with the NIST estimators using simulated non-IID data. Results show that our estimator gives close estimates to the real min-entropy.
Multivariate Profiling of Hulls for Linear Cryptanalysis
Authors: Bogdanov Andrey , Tischhauser Elmar , Vejre Philip S.
Published: November 2020

Extensions of linear cryptanalysis making use of multiple approximations, such as multiple and multidimensional linear cryptanalysis, are an important tool in symmetric-key cryptanalysis, among others being responsible for the best known attacks on ciphers such as Serpent and present. At CRYPTO 2015, Huang et al. provided a refined analysis of the key-dependent capacity leading to a refined key equivalence hypothesis, however at the cost of additional assumptions. Their analysis was extended by Blondeau and Nyberg to also cover an updated wrong key randomization hypothesis, using similar assumptions. However, a recent result by Nyberg shows the equivalence of linear dependence and statistical dependence of linear approximations, which essentially invalidates a crucial assumption on which all these multidimensional models are based. In this paper, we develop a model for linear cryptanalysis using multiple linearly independent approximations which takes key-dependence into account and complies with Nyberg’s result. Our model considers an arbitrary multivariate joint distribution of the correlations, and in particular avoids any assumptions regarding normality. The analysis of this distribution is then tailored to concrete ciphers in a practically feasible way by combining a signal/noise decomposition approach for the linear hulls with a profiling of the actual multivariate distribution of the signal correlations for a large number of keys, thereby entirely avoiding assumptions regarding the shape of this distribution. As an application of our model, we provide an attack on 26 rounds of present which is faster and requires less data than previous attacks, while using more realistic assumptions and far fewer approximations. We successfully extend the attack to present the first 27-round attack which takes key-dependence into account.
Revisiting and Improving Algorithms for the 3XOR Problem
Authors: Bouillaguet Charles , Delaplace Claire , Fouque Pierre-Alain
Published: November 2020

The 3SUM problem is a well-known problem in computer science and many geometric problems have been reduced to it. We study the 3XOR variant which is more cryptologically relevant. In this problem, the attacker is given black-box access to three random functions F,G and H and she has to find three inputs x, y and z such that F(x) ⊕ G(y) ⊕ H(z) = 0. The 3XOR problem is a difficult case of the more-general k-list birthday problem. Wagner’s celebrated k-list birthday algorithm, and the ones inspired by it, work by querying the functions more than strictly necessary from an information-theoretic point of view. This gives some leeway to target a solution of a specific form, at the expense of processing a huge amount of data. However, to handle such a huge amount of data can be very difficult in practice. This is why we first restricted our attention to solving the 3XOR problem for which the total number of queries to F, G and H is minimal. If they are n-bit random functions, it is possible to solve the problem with roughly
State-Recovery Attacks on Modified Ketje Jr
Authors: Fuhr Thomas , Naya-Plasencia María , Rotella Yann
Published: November 2020

In this article we study the security of the authenticated encryption algorithm Ketje against divide-and-conquer attacks. Ketje is a third-round candidate in the ongoing CAESAR competition, which shares most of its design principles with the SHA-3 hash function. Several versions of Ketje have been submitted, with different sizes for its internal state. We describe several state-recovery attacks on the smaller variant, called Ketje Jr. We show that if one increases the amount of keystream output after each round from 16 bits to 40 bits, Ketje Jr becomes vulnerable to divide-and-conquer attacks with time complexities 271.5 for the original version and 282.3 for the current tweaked version, both with a key of 96 bits. We also propose a similar attack when considering rates of 32 bits for the non-tweaked version. Our findings do not threaten the security of Ketje, but should be taken as a warning against potential future modifications that would aim at increasing the performance of the algorithm.
Revisiting Variable Output Length XOR Pseudorandom Function
Authors: Bhattacharya Srimanta , Nandi Mridul
Published: November 2020

Let σ be some positive integer and C ⊆ {(i, j) : 1 ≤ i < j ≤ σ}. The theory behind finding a lower bound on the number of distinct blocks P1, . . . , Pσ ∈ {0, 1}n satisfying a set of linear equations {Pi ⊕Pj = ci,j : (i, j) ∈ C} for some ci,j ∈ {0, 1}n, is called mirror theory. Patarin introduced the mirror theory and provided a proof for this. However, the proof, even for a special class of equations, is complex and contains several non-trivial gaps. As an application of mirror theory, XORP[w] (known as XOR construction) returning (w−1) block output, is a pseudorandom function (PRF) for some parameter w, called width. The XOR construction can be seen as a basic structure of some encryption algorithms, e.g., the CENC encryption and the CHM authenticated encryption, proposed by Iwata in 2006. Due to potential application of XORP[w] and the nontrivial gaps in the proof of mirror theory, an alternative simpler analysis of PRF-security of XORP[w] would be much desired. Recently (in Crypto 2017) Dai et al. introduced a tool, called the χ2 method, for analyzing PRF-security. Using this tool, the authors have provided a proof of PRF-security of XORP[2] without relying on the mirror theory. In this paper, we resolve the general case; we apply the χ2 method to obtain a simpler security proof of XORP[w] for any w ≥ 2. For w = 2, we obtain a tighter bound for a wider range of parameters than that of Dai et al.. Moreover, we consider variable width construction XORP[∗] (in which the widths are chosen by adversaries adaptively), and also provide variable output length pseudorandom function (VOLPRF) security analysis for it. As an application of VOLPRF, we propose an authenticated encryption which is a simple variant of CHM or AES-GCM and provides much higher security than those at the cost of one extra blockcipher call for every message.
Distinguishing Attack on NORX Permutation
Authors: Huang Tao , Wu Hongjun
Published: November 2020

NORX is a permutation-based authentication scheme which is currently a third-round candidate of the ongoing CAESAR competition. The security bound of NORX is derived from the sponge construction applied to an ideal underlying permutation. In this paper, we show that the NORX core permutation is non-ideal with a new distinguishing attack. More specifically, we can distinguish NORX64 permutation with 248.5 queries and distinguish NORX32 permutation with 264.7 queries using carefully crafted differential-linear attacks. We have experimentally verified the distinguishing attack on NORX64 permutation. Although the distinguishing attacks reveal the weakness of the NORX permutation, it does not directly threat the security of the NORX authenticated encryption scheme.
Clustering Related-Tweak Characteristics: Application to MANTIS-6
Authors: Eichlseder Maria , Kales Daniel
Published: November 2020

The TWEAKEY/STK construction is an increasingly popular approach for designing tweakable block ciphers that notably uses a linear tweakey schedule. Several recent attacks have analyzed the implications of this approach for differential cryptanalysis and other attacks that can take advantage of related tweakeys. We generalize the clustering approach of a recent differential attack on the tweakable block cipher MANTIS5 and describe a tool for efficiently finding and evaluating such clusters. More specifically, we consider the set of all differential characteristics compatible with a given truncated characteristic, tweak difference, and optional constraints for the differential. We refer to this set as a semi-truncated characteristic and estimate its probability by analyzing the distribution of compatible differences at each step. We apply this approach to find a semi-truncated differential characteristic for MANTIS6 with probability about 2−67.73 and derive a key-recovery attack with a complexity of about 255.09 chosen-plaintext queries and 255.52 computations. The data-time product is 2110.61 << 2126.
Conditional Linear Cryptanalysis – Cryptanalysis of DES with Less Than 242 Complexity
Authors: Biham Eli , Perle Stav
Published: November 2020

In this paper we introduce a new extension of linear cryptanalysis that may reduce the complexity of attacks by conditioning linear approximations on other linear approximations. We show that the bias of some linear approximations may increase under such conditions, so that after discarding the known plaintexts that do not satisfy the conditions, the bias of the remaining known plaintexts increases. We show that this extension can lead to improvements of attacks, which may require fewer known plaintexts and time of analysis. We present several types of such conditions, including one that is especially useful for the analysis of Feistel ciphers. We exemplify the usage of such conditions for attacks by a careful application of our extension to Matsui’s attack on the full 16-round DES, which succeeds to reduce the complexity of the best attack on DES to less than 242. We programmed a test implementation of our attack and verified our claimed results with a large number of runs. We also introduce a new type of approximations, to which we call scattered approximations, and discuss its applications.
New Yoyo Tricks with AES-based Permutations
Authors: Saha Dhiman , Rahman Mostafizar , Paul Goutam
Published: November 2020

In Asiacrypt 2017, Rønjom et al. reported some interesting generic properties of SPNs, leading to what they call the Yoyo trick, and applied it to find the most efficient distinguishers on AES. In this work, we explore the Yoyo idea in distinguishing public permutations for the first time. We introduce the notion of nested zero difference pattern which extends the Yoyo idea and helps to compose it using improbable and impossible differential strategies to penetrate higher number of rounds. We devise a novel inside-out application of Yoyo which enables us to start the Yoyo game from an internal round. As an application, we investigate the AES-based public permutation AESQ used inside the authenticated cipher PAEQ. We achieve the first deterministic distinguisher of AESQ up to 8 rounds and the first 9-round distinguisher of AESQ that start from the first round with a practical complexity of around 226. We manage to augment Yoyo with improbable and impossible differentials leading to distinguishers on 9, 10, 12 rounds with complexities of about 22, 228, 2126 respectively. Further, with impossible differentials and a bi-directional Yoyo strategy, we obtain a 16-round impossible differential distinguisher with a complexity of 2126. Our results outperform all previous records on AESQ by a substantial margin. As another application, we apply the proposed strategies on AES in the known-key setting leading to one of the best 8-round known-key distinguisher with a complexity of 230. Finally, this work amplifies the scope of the Yoyo technique as a generic cryptanalysis tool.
Key Assignment Scheme with Authenticated Encryption
Authors: Kandele Suyash , Paul Souradyuti
Published: November 2020

The Key Assignment Scheme (KAS) is a well-studied cryptographic primitive used for hierarchical access control (HAC) in a multilevel organisation where the classes of people with higher privileges can access files of those with lower ones. Our first contribution is the formalization of a new cryptographic primitive, namely, KAS-AE that supports the aforementioned HAC solution with an additional authenticated encryption property. Next, we present three efficient KAS-AE schemes that solve the HAC and the associated authenticated encryption problem more efficiently – both with respect to time and memory – than the existing solutions that achieve it by executing KAS and AE separately. Our first KAS-AE construction is built by using the cryptographic primitive MLE (EUROCRYPT 2013) as a black box; the other two constructions (which are the most efficient ones) have been derived by cleverly tweaking the hash function FP (Indocrypt 2012) and the authenticated encryption scheme APE (FSE 2014). This high efficiency of our constructions is critically achieved by using two techniques: design of a mechanism for reverse decryption used for reduction of time complexity, and a novel key management scheme for optimizing storage requirements when organizational hierarchy forms an arbitrary access graph (instead of a linear graph). We observe that constructing a highly efficient KAS-AE scheme using primitives other than MLE, FP and APE is a non-trivial task. We leave it as an open problem. Finally, we provide a detailed comparison of all the KAS-AE schemes.
On Beyond-Birthday-Bound Security: Revisiting the Development of ISO/IEC 9797-1 MACs
Authors: Shen Yaobin , Wang Lei
Published: November 2020

ISO/IEC 9797-1 is an international standard for block-cipher-based Message Authentication Code (MAC). The current version ISO/IEC 9797-1:2011 specifies six single-pass CBC-like MAC structures that are capped at the birthday bound security. For a higher security that is beyond-birthday bound, it recommends to use the concatenation combiner of two single-pass MACs. In this paper, we reveal the invalidity of the suggestion, by presenting a birthday bound forgery attack on the concatenation combiner, which is essentially based on Joux’s multi-collision. Notably, our new forgery attack for the concatenation of two MAC Algorithm 1 with padding scheme 2 only requires 3 queries. Moreover, we look for patches by revisiting the development of ISO/IEC 9797-1 with respect to the beyond-birthday bound security. More specifically, we evaluate the XOR combiner of single-pass CBC-like MACs, which was used in previous version of ISO/IEC 9797-1.
Classification of Balanced Quadratic Functions
Authors: De Meyer Lauren , Bilgin Begül
Published: November 2020

S-boxes, typically the only nonlinear part of a block cipher, are the heart of symmetric cryptographic primitives. They significantly impact the cryptographic strength and the implementation characteristics of an algorithm. Due to their simplicity, quadratic vectorial Boolean functions are preferred when efficient implementations for a variety of applications are of concern. Many characteristics of a function stay invariant under affine equivalence. So far, all 6-bit Boolean functions, 3- and 4-bit permutations have been classified up to affine equivalence. At FSE 2017, Bozoliv et al. presented the first classification of 5-bit quadratic permutations. In this work, we propose an adaptation of their work resulting in a highly efficient algorithm to classify n x m functions for n ≥ m. Our algorithm enables for the first time a complete classification of 6-bit quadratic permutations as well as all balanced quadratic functions for n ≤ 6. These functions can be valuable for new cryptographic algorithm designs with efficient multi-party computation or side-channel analysis resistance as goal. In addition, we provide a second tool for finding decompositions of length two. We demonstrate its use by decomposing existing higher degree S-boxes and constructing new S-boxes with good cryptographic and implementation properties.
Reconstructing an S-box from its Difference Distribution Table
Authors: Dunkelman Orr , Huang Senyang
Published: November 2020

In this paper we study the problem of recovering a secret S-box from its difference distribution table (DDT). While being an interesting theoretical problem on its own, the ability to recover the S-box from the DDT of a secret S-box can be used in cryptanalytic attacks where the attacker can obtain the DDT (e.g., in Bar-On et al.’s attack on GOST), in supporting theoretical analysis of the properties of difference distribution tables (e.g., in Boura et al.’s work), or in some analysis of S-boxes with unknown design criteria (e.g., in Biryukov and Perrin’s analysis).We show that using the well established relation between the DDT and the linear approximation table (LAT), one can devise an algorithm different from the straightforward guess-and-determine (GD) algorithm proposed by Boura et al. Moreover, we show how to exploit this relation, and embed the knowledge obtained from it in the GD algorithm. We tested our new algorithm on random S-boxes of different sizes, and for random 14-bit bijective S-boxes, our results outperform the GD attack by several orders of magnitude.
Revisit Division Property Based Cube Attacks: Key-Recovery or Distinguishing Attacks?
Authors: Ye Chen-Dong , Tian Tian
Published: November 2020

Cube attacks are an important type of key recovery attacks against stream ciphers. In particular, they are shown to be powerful against Trivium-like ciphers. Traditional cube attacks are experimental attacks which could only exploit cubes of size less than 40. At CRYPTO 2017, division property based cube attacks were proposed by Todo et al., and an advantage of introducing the division property to cube attacks is that large cube sizes which are beyond the experimental range could be explored, and so powerful theoretical attacks were mounted on many lightweight stream ciphers.In this paper, we revisit the division property based cube attacks. There is an important assumption, called Weak Assumption, proposed in division property based cube attacks to support the effectiveness of key recovery. Todo et al. in CRYPTO 2017 said that the Weak Assumption was expected to hold for theoretically recovered superpolies of Trivium according to some experimental results on small cubes. In this paper, it is shown that the Weak Assumption often fails in cube attacks against Trivium, and moreover a new method to recover the exact superpoly of a given cube is developed based on the bit-based division property. With our method, for the cube I proposed by Todo et al. at CRYPTO 2017 to attack the 832-round Trivium, we recover its superpoly pI(x, v) = v68v78 · (x58⊕v70) · (x59x60⊕x34⊕x61). Furthermore, we prove that some best key recovery results given at CRYPTO 2018 on Trivium are actually distinguishing attacks. Hopefully this paper gives some new insights on accurately recovering the superpolies with the bit-based division property and also attract some attention on the validity of division property based cube attacks against stream ciphers.
Lightweight Iterative MDS Matrices: How Small Can We Go?
Authors: Li Shun , Sun Siwei , Shi Danping , Li Chaoyun , Hu Lei
Published: November 2020

As perfect building blocks for the diffusion layers of many symmetric-key primitives, the construction of MDS matrices with lightweight circuits has received much attention from the symmetric-key community. One promising way of realizing low-cost MDS matrices is based on the iterative construction: a low-cost matrix becomes MDS after rising it to a certain power. To be more specific, if At is MDS, then one can implement A instead of At to achieve the MDS property at the expense of an increased latency with t clock cycles. In this work, we identify the exact lower bound of the number of nonzero blocks for a 4 × 4 block matrix to be potentially iterative-MDS. Subsequently, we show that the theoretically lightest 4 × 4 iterative MDS block matrix (whose entries or blocks are 4 × 4 binary matrices) with minimal nonzero blocks costs at least 3 XOR gates, and a concrete example achieving the 3-XOR bound is provided. Moreover, we prove that there is no hope for previous constructions (GFS, LFS, DSI, and spares DSI) to beat this bound. Since the circuit latency is another important factor, we also consider the lower bound of the number of iterations for certain iterative MDS matrices. Guided by these bounds and based on the ideas employed to identify them, we explore the design space of lightweight iterative MDS matrices with other dimensions and report on improved results. Whenever we are unable to find better results, we try to determine the bound of the optimal solution. As a result, the optimality of some previous results is proved.
Efficient Side-Channel Secure Message Authentication with Better Bounds
Authors: Guo Chun , Standaert François-Xavier , Wang Weijia , Yu Yu
Published: November 2020

We investigate constructing message authentication schemes from symmetric cryptographic primitives, with the goal of achieving security when most intermediate values during tag computation and verification are leaked (i.e., mode-level leakage-resilience). Existing efficient proposals typically follow the plain Hash-then-MAC paradigm T = TGenK(H(M)). When the domain of the MAC function TGenK is {0, 1}128, e.g., when instantiated with the AES, forgery is possible within time 264 and data complexity 1. To dismiss such cheap attacks, we propose two modes: LRW1-based Hash-then-MAC (LRWHM) that is built upon the LRW1 tweakable blockcipher of Liskov, Rivest, and Wagner, and Rekeying Hash-then-MAC (RHM) that employs internal rekeying. Built upon secure AES implementations, LRWHM is provably secure up to (beyond-birthday) 278.3 time complexity, while RHM is provably secure up to 2121 time. Thus in practice, their main security threat is expected to be side-channel key recovery attacks against the AES implementations. Finally, we benchmark the performance of instances of our modes based on the AES and SHA3 and confirm their efficiency.
New Techniques for Searching Differential Trails in Keccak
Authors: Liu Guozhen , Qiu Weidong , Tu Yi
Published: November 2020

Keccak-f is the permutation used in the NIST SHA-3 hash function standard. Inspired by the previous exhaustive differential trail search methods by Mella et al. at ToSC 2017, we introduce in this paper new algorithms to cover 3-round trail cores with propagation weight at least 53, up from the previous best weight 45. To achieve the goal, the concept of ideal improvement assumption is proposed to construct theoretical representative of subspaces so as to efficiently cover the search space of 3-round trail cores with at least one out-Kernel α state. Of particular note is that the exhaustiveness in 3-round trail core search of at least one out-Kernel α is only experimentally verified. With the knowledge of all 3-round trail cores of weight up to 53, lower bounds on 4/5/6-round trails are tightened to 56/58/108, from the previous 48/50/92, respectively.
Towards Low-Energy Leakage-Resistant Authenticated Encryption from the Duplex Sponge Construction
Authors: Guo Chun , Pereira Olivier , Peters Thomas , Standaert François-Xavier
Published: November 2020

The ongoing NIST lightweight cryptography standardization process highlights the importance of resistance to side-channel attacks, which has renewed the interest for Authenticated Encryption schemes (AEs) with light(er)-weight sidechannel secure implementations. To address this challenge, our first contribution is to investigate the leakage-resistance of a generic duplex-based stream cipher. When the capacity of the duplex is of c bits, we prove the classical bound, i.e., ≈ 2c/2, under an assumption of non-invertible leakage. Based on this, we propose a new 1-pass AE mode TETSponge, which carefully combines a tweakable block cipher that must have strong protections against side-channel attacks and is scarcely used, and a duplex-style permutation that only needs weak side-channel protections and is used to frugally process the message and associated data. It offers: (i) provable integrity (resp. confidentiality) guarantees in the presence of leakage during both encryption and decryption (resp. encryption only), (ii) some level of nonce misuse robustness. We conclude that TETSponge is an appealing option for the implementation of low-energy AE in settings where side-channel attacks are a concern. We also provides the first rigorous methodology for the leakage-resistance of sponge/duplex-based AEs based on a minimal non-invertibility assumption on leakages, which leads to various insights on designs and implementations.
On the Security of Sponge-type Authenticated Encryption Modes
Authors: Chakraborty Bishwajit , Jha Ashwin , Nandi Mridul
Published: November 2020

The sponge duplex is a popular mode of operation for constructing authenticated encryption schemes. In fact, one can assess the popularity of this mode from the fact that around 25 out of the 56 round 1 submissions to the ongoing NIST lightweight cryptography (LwC) standardization process are based on this mode. Among these, 14 sponge-type constructions are selected for the second round consisting of 32 submissions. In this paper, we generalize the duplexing interface of the duplex mode, which we call Transform-then-Permute. It encompasses Beetle as well as a new sponge-type mode SpoC (both are round 2 submissions to NIST LwC). We show a tight security bound for Transform-then-Permute based on b-bit permutation, which reduces to finding an exact estimation of the expected number of multi-chains (defined in this paper). As a corollary of our general result, authenticated encryption advantage of Beetle and SpoC is about T(D+r2r)/2b where T, D and r denotes the number of offline queries (related to time complexity of the attack), number of construction queries (related to data complexity) and rate of the construction (related to efficiency). Previously the same bound has been proved for Beetle under the limitation that T << min{2r, 2b/2} (that compels to choose larger permutation with higher rate). In the context of NIST LwC requirement, SpoC based on 192-bit permutation achieves the desired security with 64-bit rate, which is not achieved by either duplex or Beetle (as per the previous analysis).
Practical seed-recovery for the PCG Pseudo-Random Number Generator
Authors: Bouillaguet Charles , Martinez Florette , Sauvage Julia
Published: November 2020

The Permuted Congruential Generators (PCG) are popular conventional (non-cryptographic) pseudo-random generators designed in 2014. They are used by default in the NumPy scientific computing package. Even though they are not of cryptographic strength, their designer stated that predicting their output should nevertheless be "challenging".In this article, we present a practical algorithm that recovers all the hidden parameters and reconstructs the successive internal states of the generator. This enables us to predict the next “random” numbers, and output the seeds of the generator. We have successfully executed the reconstruction algorithm using 512 bytes of challenge input; in the worst case, the process takes 20 000 CPU hours.This reconstruction algorithm makes use of cryptanalytic techniques, both symmetric and lattice-based. In particular, the most computationally expensive part is a guessand-determine procedure that solves about 252 instances of the Closest Vector Problem on a very small lattice.
The Subterranean 2.0 Cipher Suite
Authors: Daemen Joan , Massolino Pedro Maat Costa , Mehrdad Alireza , Rotella Yann
Published: November 2020

This paper presents the Subterranean 2.0 cipher suite that can be used for hashing, MAC computation, stream encryption and several types of authenticated encryption schemes. At its core it has a duplex object with a 257-bit state and a lightweight single-round permutation. This makes Subterranean 2.0 very well suited for low-area and low-energy implementations in dedicated hardware.
Dumbo, Jumbo, and Delirium: Parallel Authenticated Encryption for the Lightweight Circus
Authors: Beyne Tim , Chen Yu Long , Dobraunig Christoph , Mennink Bart
Published: November 2020

With the trend to connect more and more devices to the Internet, authenticated encryption has become a major backbone in securing the communication, not only between these devices and servers, but also the direct communication among these devices. Most authenticated encryption algorithms used in practice are developed to perform well on modern high-end devices, but are not necessarily suited for usage on resource-constrained devices. We present a lightweight authenticated encryption scheme, called Elephant. Elephant retains the advantages of GCM such as parallelism, but is tailored to the needs of resource-constrained devices. The two smallest instances of Elephant, Dumbo and Jumbo, are based on the 160-bit and 176-bit Spongent permutation, respectively, and are particularly suited for hardware; the largest instance of Elephant, Delirium, is based on 200-bit Keccak and is developed towards software use. All three instances are parallelizable, have a small state size while achieving a high level of security, and are constant time by design.
Assessment of Ambient Air Quality around Ihetutu Minefield, Ishiagu, Nigeria
Authors: Benibo A. G. , Sha'Ato R. , Wuana R. A. , Itodo A. U.
Published: November 2020

This study assessed the levels of physicochemical characteristics and heavy metals in ambient air around Ihetutu community in Ishiagu, Nigeria, to evaluate the impact of prolonged Pb-Zn mining and several other related activities on air quality in the area. Particulates, heavy metals, microclimatic and gaseous parameters in ambient air were analyzed for the assessment. Sampling and quality measurements were done during rainy, late rainy, dry and late dry seasons between 2018 and 2019, from study and control areas. Samples were analyzed for particulates and heavy metals in the laboratory while microclimatic and gaseous parameters were measured in-situ using standard field equipment and procedures. Mean and seasonal concentrations of parameters were determined to evaluate the ambient air quality at various locations in the study area. Results showed high mean values of some parameters including; ambient temperature (35.19oC), Relative Humidity (65.78%), SO2 (0.33ppm), NO2 (0.30ppm), PM10 (89.73µg/m3), Cu (0.03mg/L), Zn (0.06mg/L), Fe (0.39mg/L), Mn (2.28mg/L), Ni (0.04mg/L) and Pb (0.05mg/L). Highest Noise level in the study area was 60.40 dB(A). SO2 and NO2 were below detection limits during the dry seasons, but with mean levels above daily average limits of DPR, NESREA, and WHO, due to their high levels during the rainy seasons, except at Amaonye Square. CO mean levels were above FMEnv daily average limit but within DPR limit. PM10 mean values were within NESREA recommended daily average limit while dry season values were above. Zn and Fe pollution along the stations were in the order of SAS3>SAS4>SAS5, while Pb pollution was SAS3>SAS4=SAS5. Generally, trend of heavy metal pollution was Mn>Fe>Pb>Zn>Cd=Cu=Ni. Highest positive correlation within the heavy metals was between Zn and Fe (r = 1.000). There were also no statistically significant differences in means of the parameters among sampling stations (p>0.05). The results revealed pollution of ambient air in the area by heavy metals and gaseous substances, especially around the mining sites and high traffic areas. Proper monitoring of the operations of mining companies and other artisan activities is recommended, to ensure that ambient air status in the area is excellent and within standard guidelines.
Lipid Composition and Antimicrobial Activity of Raw, Boiled and Fermented Seed Extracts of Pentaclethra macrophylla (BENTH)
Authors: Anowu J. N. , Aliyu A. B. , Ibrahim H. , Oyewale A. O.
Published: November 2020

Lipids possess versatile biological properties in human health and nutrition. The compositions of lipids were investigated on the raw, boiled and fermented seeds of Pentaclethra macrophylla n-hexane extracts. The seed extracts were esterified, and chemical composition of the fatty acids was evaluated using gas chromatography-mass spectrometry (GC-MS). Subsequent chromatographic purification and isolation on the lipids was carried out using column chromatography and thin layer chromatographic techniques. The antimicrobial activity of extracts was evaluated using disc diffusion and broth dilution techniques on selected bacterial and fungal species, Methicillin resistant Staphylococcus aureus (MRSA), Staphylococcus aureus, Shigella dysenterea, Salmonella typhi, Proteus mirabilis, Corynebacterium ulcerans, Escherichia coli, Candida krusei, Candida albicans and Candida tropicalis. GC-MS analysis revealed that fatty acids such as linoleic acid, butyl 9,12- octadecadienoate acid, oleic acid, hexadecanoic acid, methyl 20-methyl heneicosanoate, tetracosanoate acid, ethyl tetracosanoate and methyl stearate were common in the raw, boiled and fermented seed extracts. However, linoleic acid content was higher (60%) in fermented seeds, indicating an increased production due to fermentation effect. The extracts have demonstrated growth inhibition on bacterial and fungal species with broad-spectrum activity for the fermented seeds (17-19 mm; MIC 5 mg/mL) and the raw and boiled seeds (16-18 mm; MIC 5 mg/mL). Monoglycerides were isolated and structures elucidated using H-NMR and C-DEPT as 2,3-dihydroxypropyl tetracosanoate (1), 2,3-dihydroxypropyl pentacosanoate (2) and 2,3- dihydroxypropyl hentriacontylate (3). Compounds (2) and (3) are reported for the first time from the seeds. This report indicated the potential benefit of P. macrophylla seeds fermentation to human nutrition and health.