Search

In 2002, in two independent papers, Bellare, Kohno, and Namprempre and Joux, Martinet, and Valette introduced the notion of blockwise security for modes of operations. This notion stems from common practice, since in many applications, modes of operation for block ciphers do not process messages as atomic entities but in a incremental manner, block after block. Soon afterward, several papers showed that many modes of operation are already blockwise secure and that others can be made secure by simple modifications. In this paper, we revisit these results, by comparing possible attacks on modes of operation after the birthday bound is reached. Amusingly, in spite having essentially identical security proofs up to this bound, modes of operation in the blockwise model behave very differently than their counterparts in the regular model, once the birthday paradox bound is crossed.

The recent algebraic attacks have received a lot of attention in cryptographic literature. The algebraic immunity of a Boolean function quantifies its resistance to the standard algebraic attacks of the pseudorandom generators using it as a nonlinear filtering or combining function. Very few results have been found concerning its relation with the other cryptographic parameters or with the rth-order nonlinearity. As recalled by Carlet at CRYPTO'06, many papers have illustrated the importance of the r th-order nonlinearity profile (which includes the first-order nonlinearity). The role of this parameter relatively to the currently known attacks has been also shown for block ciphers. Recently, two lower bounds involving the algebraic immunity on the rth-order nonlinearity have been shown by Carlet . None of them improves upon the other one in all situations. In this paper, we prove a new lower bound on the rth-order nonlinearity profile of Boolean functions, given their algebraic immunity, that improves significantly upon one of these lower bounds for all orders and upon the other one for low orders.

For years, the cryptographic community has searched for good nonlinear functions. Bent functions, almost perfect nonlinear functions, and similar constructions have been suggested as a good base for cryptographic applications due to their highly nonlinear nature. In the first part of this paper, we examine using these functions as block ciphers, and present several distinguishers between almost perfect nonlinear permutations and random permutations. In the second part of the paper, we suggest a criterion to measure the effective linearity of a given block cipher. We devise a general distinguisher for block ciphers based on their effective linearity. Finally, we show that for several constructions, our distinguishing attack is better than previously known techniques.

The Demirci-Selcuk’s meet-in-the-middle attack is one of the most important methods among all the cryptanalytic vectors, which gives the best result against the round-reduced AES with respect to the rounds, and tradeoffs between data, time and memory. While we have already built provable security models against the differential cryptanalysis, linear cryptanalysis cryptanalysis, impossible differential and zero-correlation linear cryptanalysis, the provable security against the meet-in-the-middle attack is missing. In this paper, we propose the subset representation of function based on which we could give an algorithm to compute the exact number of parameters of the Demirci-Selcuk’s distinguisher given the input and output, respectively. Experiments show that this algorithm can be more efficient than the automatical tool presented by Shi et al. at Asiacrypt 2018. We further extract a formula based on this algorithm and show an upper bound for the length of the Demirci-Selcuk’s distinguisher of an iterative SPN cipher. We prove that for an SPN block cipher whose block size equals the key size, an effective Demirci-Selcuk-type meet-in-the-middle distinguisher covers at most twice the maximum of the primitive indexes of the linear layer and its inverse. As a result, we show that the known length of the Demirci-Selcuk’s distinguisher of the AES-128 cannot be improved unless the details of the S-boxes are exploited, which demonstrates that the AES has a provable security against the Demirci-Selcuk’s meet-in-the-middle attack.

In this paper we define a new (output) multiplicative differential, and the corresponding c -differential uniformity. With this new concept, even for characteristic 2, there are perfect ${c}$ -nonlinear (PcN) functions. We first characterize the ${c}$ -differential uniformity of a function in terms of its Walsh transform. We further look at some of the known perfect nonlinear (PN) functions and show that only one remains a PcN function, under a different condition on the parameters. In fact, the p -ary Gold PN function increases its c -differential uniformity significantly, under some conditions on the parameters. We then precisely characterize the c -differential uniformity of the inverse function (in any dimension and characteristic), relevant for the Rijndael (and Advanced Encryption Standard) block cipher.

In Eurocrypt’18, Cid et al. proposed a new cryptanalysis tool called Boomerang Connectivity Table (BCT), to evaluate S-boxes of block ciphers. Later, Boura and Canteaut further investigated the new parameter Boomerang uniformity for cryptographic S-boxes. It is of great interest to find new S-boxes with low Boomerang uniformity for even dimensions. In this paper, we prove that a class of permutation quadrinomials over $\mathbb {F}_{2^{2m}}$ with $m$ odd has Boomerang uniformity four, which gives the fifth class of such kind of permutation polynomials. Further, the occurrences of 0 and 4 in the BCTs of the investigated permutation polynomials are also completely determined.

Offset codebook or ${\mathsf {OCB}}$ mode is a popular block cipher mode of operation for authenticated encryption. The latest version of this cipher, called ${\mathsf {OCB3}}$ , is one of the finalists in CAESAR. In this paper, we explore the scope of random read access and out-of-sequence decryption in ${\mathsf {OCB}}$ . We observe that the current versions of ${\mathsf {OCB}}$ are inefficient in this respect owing to the ineptness of the underlying mask generating function (MGF). We propose new candidates for MGF based on ${\mathsf {AES}}$ round function, which are efficient in direct computation and provide comparable performance in the usual setting. Our schemes are not the obvious choices for MGF in conventional sense as they do not have optimal almost XOR universal (AXU) bound. In existing ${\mathsf {OCB}}$ designs, the MGFs are required to have $ 2^{-n} $ , i.e. optimal, AXU bound in order to upper bound the distinguishing advantage to $ O(\sigma ^{2}/2^{n}) $ , where $ n $ is the block size of the underlying block cipher and $ \sigma $ is the total number of blocks among all queries. We find this specific requirement too restrictive. We abstract the ${\mathsf {OCB}}$ design, termed as ${\mathsf {GOCB}}$ , to look into the universal notion required from the underlying MGF. We propose a relaxed notion of AXU, called locally imperfect XOR universal (LIXU) hash, which can be of independent interest. Using LIXU as the underlying MGF, we recover reasonable security bounds for our schemes.

Due to recent applications to communications over powerlines, multilevel flash memories, and block ciphers, permutation codes have received a lot of attention from both coding and mathematical communities. One of the benchmarks for good permutation codes is the Gilbert–Varshamov bound. Although there have been several constructions of permutation codes, the Gilbert–Varshamov bound still remains to be the best asymptotical lower bound except for a recent improvement in the case of constant minimum distance. In this paper, we present an algebraic construction of permutation codes from rational function fields, and it turns out that, for a prime number $n$ of a symbol length, this class of permutation codes improves the Gilbert–Varshamov bound by a factor $n$ asymptotically for a minimum distance $d$ with $d=O(\sqrt {n})$ . Furthermore, for a constant minimum distance $d$ , we improve the Gilbert–Varshamov bound by a factor $n$ as well as the recent one given by Gao et al. by a factor $n/\log n$ asymptotically for all sufficiently large $n$ .

Substitution boxes (S-boxes) play a central role in the modern design of iterative block ciphers. While in substitution-permutation networks the S-boxes are bijective, thus ensuring the invertibility of the encryption algorithm, the property of being bijective is not mandatory for Feistel kind of networks. In this paper, two methods of constructing highly nonlinear balanced S-boxes (whose nonlinearity > 2 n-1 -2 n/2 is better than the nonlinearity of the commonly used inverse S-box) with good algebraic and differential properties are given. The first method employs two vectorial Boolean functions from the Maiorana-McFarland class that need to fulfill certain conditions. In particular, these conditions are shown to be satisfied by maximum length sequences. The second method is based on a suitable modification of a certain class of vectorial bent functions. The differential properties of these boxes, measured as a deviation from an optimal uniform distribution, also appear to be better than those of the inverse S-box. Both methods are susceptible to further optimizations of the relevant cryptographic parameters due to the underlying design ideas.

The Alred construction is a lightweight strategy for constructing message authentication algorithms from an underlying iterated block cipher. Even though this construction's original analyses show that it is secure against some attacks, the absence of formal security proofs in a strong security model still brings uncertainty on its robustness. In this paper, aiming to give a better understanding of the security level provided by different authentication algorithms based on this design strategy, we formally analyze two Alred variants—the Marvin message authentication code and the LetterSoup authenticated-encryption scheme,—bounding their security as a function of the attacker's resources and of the underlying cipher's characteristics.

In this paper, we propose a new double-piped mode of operation for multiproperty-preserving domain extension of message authentication codes (MACs), pseudorandom functions (PRFs), and pseudorandom oracles (PROs). Our mode of operation performs twice as fast as the original double-piped mode of operation of Lucks while providing comparable security. Our construction, which uses a class of polynomial-based compression functions proposed by Stam, makes a single call to a $3n$ -bit to $n$ -bit primitive $f_{1}$ at each iteration and uses a finalization function $f_{2}$ at the last iteration, producing an $n$ -bit hash function $H[f_{1},f_{2}]$ satisfying the following properties. $H[f_{1},f_{2}]$ is unforgeable up to $O(2^{n}/n)$ query complexity as long as $f_{1}$ and $f_{2}$ are unforgeable.

In 2004, we introduced the related-key boomerang/ rectangle attacks, which allow us to enjoy the benefits of the boomerang attack and the related-key technique, simultaneously. The new attacks were used since then to attack numerous block ciphers. While the claimed applications are significant, most of them have a major drawback. Their validity cannot be verified experimentally due to their high complexity. Together with the lack of rigorous justification of the probabilistic assumptions underlying the technique, this lead Murphy to claim that attacks using the related-key boomerang/rectangle technique are not legitimate. This paper contains two contributions. The first is a rigorous analysis of the related-key boomerang/rectangle attacks, including devising provably optimal distinguishers and computing their success rate, and discussing the underlying independence assumptions. The second contribution is an extensive experimental verification of the related-key boomerang attack against the GSM block cipher, KASUMI. Our experiments reveal that the success probability of the distinguisher, when averaged over different choices of the keys, is close to the theoretical prediction. However, the exact probability depends on the key, such that for some por- tion of the keys, the distinguisher holds with a higher probability than expected, while for the rest of the keys, the distinguisher fails completely.

This paper shows that many independent pseudorandom permutations over {0,1}n can be obtained from a single public random permutation and secret n bits. It is then proved that a slightly modified IAPM (an authenticated-encryption scheme) is secure even if the underlying block cipher F is publicly accessible (as a blackbox). A similar result is derived for OCB mode, too. The security proofs are based on our first result, and they are extremely simple. Finally, it is shown that our security bound is tight within a constant factor.

This paper describes several constructions of tweakable strong pseudorandom permutations (SPRPs) built from different modes of operations of a block cipher and suitable universal hash functions. For the electronic codebook (ECB) mode based construction, an invertible blockwise universal hash function is required. We simplify an earlier construction of such a function described by Naor and Reingold. The other modes of operations considered are the output feedback (OFB) mode and a counter-like mode. All the constructions make the same number of block cipher calls and the same number of multiplications. Combined with a class of polynomials defined by Bernstein, the new constructions provide the currently best known algorithms for the important practical problem of disk encryption.

The notion of tweakable block ciphers was formally introduced by Liskov-Rivest-Wagner at Crypto 2002 (the 2002 Annual International Cryptology Conference). The extension and the first construction, called CMC, of this notion to tweakable enciphering schemes which can handle variable length messages was given by Halevi-Rogaway at Crypto 2003. In this paper, we present HCH, which is a new construction of such a scheme. The construction uses two universal hash computations with a counter mode of encryption in-between. This approach was first proposed by McGrew-Viega to build a scheme called XCB and later used by Wang-Feng-Wu, to obtain a scheme called HCTR. A unique feature of HCH compared to all known tweakable enciphering schemes is that HCH uses a single key, can handle arbitrary length messages, and has a quadratic security bound. An important application of a tweakable enciphering scheme is disk encryption. HCH is well suited for this application. We also describe a variant, which can utilize precomputation and makes one less block cipher call. This compares favorably to other hash-encrypt-hash-type constructions, supports better key agility and requires less key material.

We examine the information leakage between sets of plaintext and ciphertext bits in symmetric-key block ciphers. The paper demonstrates the effectiveness of information leakage as a measure of cipher security by relating information leakage to linear cryptanalysis and by determining a lower bound on the amount of data required in an attack from an upper bound on information leakage. As well, a model is developed which is used to estimate the upper bound on the information leakage of a general Feistel (1975) block cipher. For a cipher that fits the model well, the results of the analysis can be used as a measure in determining the number of rounds required for security against attacks based on information leakage. It is conjectured that the CAST-128 cipher fits the model well and using the model it is predicted that information leaked from 20 or fewer plaintext bits is small enough to make an attack on CAST-128 infeasible.