Differential cryptanalysis is a well-known statistical attack on block ciphers. We present here a generalisation of this attack called multiple differential cryptanalysis. We study the data complexity, the time complexity and the success probability of such an attack and we experimentally validate our formulas on a reduced version of PRESENT. Finally, we propose a multiple differential cryptanalysis on 18-round PRESENT for both 80-bit and 128-bit master keys.

Let $n$ particles be independently allocated into $N$ boxes, where the $l$-th box appears with the probability $a_l$. Let $\mu_r$ be the number of boxes with exactly $r$ particles and $\mu=[ \mu_{r_1},\ldots, \mu_{r_m}]$. Asymptotical behavior of such random variables as $N$ tends to infinity was studied by many authors. It was previously known that if $Na_l$ are all upper bounded and $n/N$ is upper and lower bounded by positive constants, then $\mu$ tends in distribution to a multivariate normal low. A stronger statement, namely a large deviation local limit theorem for $\mu$ under the same condition, is here proved. Also all cumulants of $\mu$ are proved to be $O(N)$. Then we study the hypothesis testing that the box distribution is uniform, denoted $h$, with a recently introduced box-test. Its statistic is a quadratic form in variables $\mu-\mathbf{E}\mu(h)$. For a wide area of non-uniform $a_l$, an asymptotical relation for the power of the quadratic and linear box-tests, the statistics of the latter are linear functions of $\mu$, is proved. In particular, the quadratic test asymptotically is at least as powerful as any of the linear box-tests, including the well-known empty-box test if $\mu_0$ is in $\mu$.

In this paper we analyze the recently proposed light-weight block cipher PRINTCipher. Applying algebraic methods and SAT-solving we are able to break 8 rounds of PRINTCipher-48 with only 2 known plaintexts and 9 rounds under some additional assumptions. We show that it is possible to break the full 48-round cipher by assuming a moderate leakage of internal state bits or even just Hamming weights. Such a simulation side-channel attack has practical complexity. We investigate applicability of our method to cryptanalysis of the full PRINTCipher-48.

We consider linear approximations of an iterated block cipher in the presence of several strong linear approximation trails. The effect of such trails in Matsui’s Algorithm 2, also called the linear hull effect, has been previously studied by a number of authors. However, he effect on Matsui’s Algorithm 1 has not been investigated until now. In this paper, we fill this gap and examine how to exploit the linear hull in Matsui’s Algorithm 1. We develop the mathematical framework for this kind of attacks. The complexity of the attack increases with the number of strong linear trails. We show how to reduce the number of trails and thus the complexity using related keys. Further, we illustrate our theory by experimental results on a reduced round version of the block cipher PRESENT

128-EIA3 is an integrity algorithm considered for adoption as a third integrity algorithm by European Telecommunication Standard Institute (ETSI) for 4th generation of GSM networks.128-EIA3 is vul- nerable to birthday forgery attack. Birthday forgery attack requires minimum 2^16 known message-MAC pairs for nding collision in 128-EIA3. 128-EIA3 is susceptible to internal collision of its universal hash function and external collision of its Xoring transformation. Birthday forgery attack on 128-EIA3 allows message forgery with success probability greater than 1/2^32.

At IEEE RFID 2011, David et al. proposed a new cryptographic primitive for use with RFID [2]. The design is a stream cipher called A2U2. Shortly afterwards, an attack was published on IACR Eprint by Chai et al. [1], claiming to break the cipher in a chosen-plaintext attack using extremely little computational resources. Regrettably, this attack is wrong since it works with an erroneous description of the cipher. In this paper, we show why the attack is wrong and how it can be repaired. Furthermore, we describe a guess-and-determine attack which applies in a known plaintext scenario. A special design feature of A2U2 is that the number of initialization rounds varies and depends on an internal counter. The number of rounds varies from 9 to 126. We proposed a differential-style attack which enables us to find the counter value determining the number of initialization rounds. Moreover, we present an attack that recovers the masterkey in the case that only 9 initialization rounds are used.

The ALRED family of Message Authentication Codes (MAC's) is based on three principles: Using a keyless block cipher in CBC mode to process the message, choosing AES-128 as this cipher, and reducing the effective number of rounds to 4 in order to speed up the processing. In this paper we show that each one of these principles creates significant weaknesses. More specifically, we show that any ALRED-type MAC which uses a keyless block cipher is vulnerable to new time/memory tradeoff attacks which are faster than generic tradeoff attacks on one-way functions. We then use the special properties of keyless AES to attack any number of rounds (4, 10, or a million) by forging the MAC of essentially any desired message in negligible time and space after a one-time preprocessing stage requiring 2^{96} time and negligible space. For the recommended 4-round version we show how to do the same using an improved preprocessing stage with a semi-practical time complexity of 2^{65}, which is the best one can hope for in such MAC constructions. Finally, we show that even if we replace the 4-round keyless AES by a 5-round or a 6-round version with additional secret round keys we can still compute such MAC's much faster than via exhaustive search.

It's known that perfectly binding quantum computationally hiding commitment schemes can be constructed from any quantum one-way permutation. Since no quantum one-way permutations are known, it has been unknown by far whether we can get such a concrete commitment scheme. In this paper, we give a positive answer. Specifically, we present such a lattice-based commitment scheme, which is built from the results gained by Gentry et al.

The KeeLoq cipher is used in many wireless car door systems and garage openers. Recently the algorithm was studied and several attacks have been published. When a random seed is not used the attack on the system is fairly straight-forward. However when a seed is shared between the remote control and the receiver previous research suggested using highly parallel crypto hardware (like COPACOBANA) for breaking the cipher within reasonable time. In this paper we show that highly-parallel hardware is not necessary: our attack uses a single FPGA for breaking KeeLoq when using a 48-bit random seed in 17 hours using a mid-range Virtex-4, and less than 3 hours using a high-end Virtex-6 chip. We achieve these results using a combination of algorithmic improvements, FPGA design methodology, and Xilinx-specific features.

We introduce NSABC/w – Nice-Structured Algebraic Block Cipher using w -bit word arithmetics, a 4w -bit analogous of Skipjack [NSA98] with 5w -bit key. The Skipjack's internal 4-round Feistel structure is replaced with a w -bit, 2-round cascade of a binary operation (x,z)\mapsto(x\boxdot z)\lll(w/2) that permutes a text word x under control of a key word z . The operation \boxdot , similarly to the multiplication in IDEA [LM91, LMM91], bases on an algebraic group over w -bit words, so it is also capable of decrypting by means of the inverse element of z in the group. The cipher utilizes a secret 4w -bit tweak – an easily changeable parameter with unique value for each block encrypted under the same key [LRW02] – that is derived from the block index and an additional 4w -bit key. A software implementation for w=64 takes circa 9 clock cycles per byte on x86-64 processors.

We propose (T,N) multi-ciphertext scheme for symmetric encryption. The scheme encrypts a message into N distinct ciphertexts. The knowledge of the symmetric key allows decryption of the original message from any ciphertext. Moreover, knowing T+1 ciphertexts allows efficient recovery of the original message without the key (and without revealing the key as well). We define the security property of the scheme, and prove the security of the proposed scheme. We discuss several variants of the basic scheme that provides additional authenticity and efficiency.

Mobile Ad-hoc Network (MANET) is a transitory and infrastructureless network supported by no fixed trusted infrastructure. To achieve security goals like: authentication, integrity, non-repudiation, privacy, a secret key (or session key) is necessary to be shared between the sender and receiver. Because of the nature of MANET, it is unrealistic in many circumstances to implement Certification Authority (CA) concept. Some popular key exchange protocols also have some demerits in case of MANET which are due to mainly the requirement of high computational capability. In this key exchange protocol we propose an algorithm to exchange shared and session key between the sender and destination even during the route creation in various routing protocols.

The FSB (fast syndrome-based) hash function was submitted to the SHA-3 competition by Augot, Finiasz, Gaborit, Manuel, and Sendrier in 2008, after preliminary designs proposed in 2003, 2005, and 2007. Many FSB parameter choices were broken by Coron and Joux in 2004, Saarinen in 2007, and Fouque and Leurent in 2008, but the basic FSB idea appears to be secure, and the FSB submission remains unbroken. On the other hand, the FSB submission is also quite slow, and was not selected for the second round of the competition. This paper introduces RFSB, an enhancement to FSB. In particular, this paper introduces the RFSB-509 compression function, RFSB with a particular set of parameters. RFSB-509, like the FSB-256 compression function, is designed to be used inside a 256-bit collision-resistant hash function: all known attack strategies cost more than 2^128 to find collisions in RFSB-509. However, RFSB-509 is an order of magnitude faster than FSB-256. On a single core of a Core 2 Quad CPU, RFSB-509 runs at 13.62 cycles/byte: faster than SHA-256, faster than 6 of the 14 second-round SHA-3 candidates, and faster than 2 of the 5 SHA-3 finalists.

The notion of PRO (pseudorandom oracle) is an important security notion of hash functions because a PRO hash function inherits all properties of a random oracle up to the PRO bound (e.g., security against generic attacks, collision resistant security, preimage resistant security and so on). In this paper, we propose a new block cipher-based double-length hash function for PROs. Our hash function uses a single block cipher, which encrypts an $n$-bit string using a $2n$-bit key, and maps an input of arbitrary length to a $2n$-bit output. Since many block ciphers supports a $2n$-bit key (e.g. AES supports a $256$-bit key), the assumption to use the $2n$-bit key length block cipher is acceptable. We prove that our hash function is PRO up to $\order(2^n)$ query complexity as long as the block cipher is an ideal cipher. To our knowledge, this is the first time double-length hash function based on a single (practical size) block cipher with the birthday type PRO security.

Bellare and Kohno introduced a formal framework for the study of related-key attacks against blockciphers. They established sufficient conditions (output-unpredictability and collision-resistance) on the set of related-key-deriving (RKD) functions under which an ideal cipher is secure against related-key attacks, and suggested this could be used to derive security goals for real blockciphers. However, to do so requires the reinterpretation of results proven in the ideal-cipher model for the standard model (in which a blockcipher is modelled as, say, a pseudorandom permutation family). As we show here, this is a fraught activity. In particular, building on a recent idea of Bernstein, we first demonstrate a related-key attack that applies generically to a large class of blockciphers. The attack exploits the existence of a short description of the blockcipher, and so does not apply in the ideal-cipher model. However, the specific RKD functions used in the attack are provably output-unpredictable and collision-resistant. In this sense, the attack can be seen as a separation between the ideal-cipher model and the standard model. Second, we investigate how the related-key attack model of Bellare and Kohno can be extended to include sets of RKD functions that themselves access the ideal cipher. Precisely such related-key functions underlie the generic attack, so our extended modelling allows us to capture a larger universe of related-key attacks in the ideal-cipher model. We establish a new set of conditions on related-key functions that is sufficient to prove a theorem analogous to the main result of Bellare and Kohno, but for our extended model. We then exhibit non-trivial classes of practically relevant RKD functions meeting the new conditions. We go on to discuss standard model interpretations of this theorem, explaining why, although separations between the ideal-cipher model and the standard model still exist for this setting, they can be seen as being much less natural than our previous separation. In this manner, we argue that our extension of the Bellare--Kohno model represents a useful advance in the modelling of related-key attacks. Third, we consider the topic of key-recovering related-key attacks and its relationship to the Bellare--Kohno formalism. In particular, we address the question of whether lowering the security goal by requiring the adversary to perform key-recovery excludes separations of the type exhibited by us in the Bellare--Kohno model.

The second-order nonlinearity, and the best quadratic approximations, of Boolean functions are studied in this paper. We prove that cubic functions within the Maiorana-McFarland class achieve very high second order nonlinearity, which is close to an upper bound that was recently proved by Carlet et al., and much higher than the second order nonlinearity obtained by other known constructions. The structure of the cubic Boolean functions considered allows the efficient computation of (a subset of) their best quadratic approximations.

We give improved bounds on the preimage security of the three ``classical'' double-block-length, double-call, blockcipher-based compression functions, these being Abreast-DM, Tandem-DM and Hirose's scheme. For Hirose's scheme, we show that an adversary must make at least $2^{2n-5}$ blockcipher queries to achieve chance $0.5$ of inverting a randomly chosen point in the range. For Abreast-DM and Tandem-DM we show that at least $2^{2n-10}$ queries are necessary. These bounds improve upon the previous best bounds of $\Omega(2^n)$ queries, and are optimal up to a constant factor since the compression functions in question have range of size $2^{2n}$.

AES is the most widely used block cipher today, and its security is one of the most important issues in cryptanalysis. After 13 years of analysis, related-key attacks were recently found against two of its flavors (AES-192 and AES-256). However, such a strong type of attack is not universally accepted as a valid attack model, and in the more standard single-key attack model at most 8 rounds of these two versions can be currently attacked. In the case of 8-round AES-192, the only known attack (found 10 years ago) is extremely marginal, requiring the evaluation of essentially all the 2^{128} possible plaintext/ciphertext pairs in order to speed up exhaustive key search by a factor of 16. In this paper we introduce three new cryptanalytic techniques, and use them to get the first non-marginal attack on 8-round AES-192 (making its time complexity about a million times faster than exhaustive search, and reducing its data complexity to about 1/32,000 of the full codebook). In addition, our new techniques can reduce the best known time complexities for all the other combinations of 7-round and 8-round AES-192 and AES-256.

We revisit meet-in-the-middle attacks on block ciphers and recent developments in meet-in-the-middle preimage attacks on hash functions. Despite the presence of a secret key in the block cipher case, we identify techniques that can also be mounted on block ciphers, thus allowing us to improve the cryptanalysis of the block cipher KTANTAN family. The first and major contribution is that we spot errors in previous cryptanalysis, secondly we improve upon the corrected results. Especially, the technique indirect-partial-matching can be used to increase the number of matched bits significantly, as exemplified by our attacks. To the best of our knowledge, this is the first time that a splice-and-cut meet-in-the-middle attack is applied to block ciphers. When the splitting point is close to the start or the end of the cipher, the attack remains to be at very low data complexity. The secret key of the full cipher can be recovered faster than exhaustive search for all three block sizes in the KTANTAN family. The attack on KTANTAN32 works with a time complexity $2^{72.9}$ in terms of full round encryptions. The attack has a time complexity of $2^{73.8}$ and $2^{74.4}$ on KTANTAN48 and KTANTAN64, respectively. Moreover, all the three attacks work with 4 chosen ciphertexts only. These results compare favourably with the factor 2 speed-up over brute force obtained in earlier work 4 , and hence these attacks are the best cryptanalysis results so far.

We propose a simple deterministic test for deciding whether or not a non-zero element $a \in \F_{2^n}$ or $\F_{3^n}$ is a zero of the corresponding Kloosterman sum over these fields, and analyse its complexity. The test seems to have been overlooked in the literature. For binary fields, the test has an expected operation count dominated by just two $\F_{2^n}$-multiplications when $n$ is odd (with a slightly higher cost for even extension degrees), making its repeated invocation the most efficient method to date to find a non-trivial Kloosterman sum zero in these fields. The analysis depends on the distribution of Sylow $p$-subgroups in two corresponding families of elliptic curves, which we prove using a theorem due to Howe.

Searchable symmetric encryption (SSE) allows a party to outsource the storage of his data to another party in a private manner, while maintaining the ability to selectively search over it. This problem has been the focus of active research and several security definitions and constructions have been proposed. In this paper we begin by reviewing existing notions of security and propose new and stronger security definitions. We then present two constructions that we show secure under our new definitions. Interestingly, in addition to satisfying stronger security guarantees, our constructions are more efficient than all previous constructions. Further, prior work on SSE only considered the setting where only the owner of the data is capable of submitting search queries. We consider the natural extension where an arbitrary group of parties other than the owner can submit search queries. We formally define SSE in this multi-user setting, and present an efficient construction.

MDS Matrix has an important role in the design of Rijndael Cipher and is the most expensive component of the cipher. It is also used as a perfect diffusion primitive in some other block ciphers. In this paper, we propose a replacement of Mix Column Transformation in AES by equivalent Dynamic Mix Column Transformation. A Dynamic Mix Column Transformation comprises dynamic MDS Matrices which are based on default MDS Matrix of AES and m-bit additional key. Here m is a variable length that does not exceed the product of 31.97 and one less the number of encryption rounds. This mechanism increases a brute force attack complexity by m-bit to the original key and enforces the attackers to design new frameworks for different modern cryptanalytic techniques applicable to the cipher. We also present efficient implementation of this technique in Texas Instrument’s DSP C64x+ with no extra cost to default AES and in Xilinx Spartan3 FPGA with no change in AES throughput. We also briefly analyze the security achieved over it.

In this article, we provide the first independent analysis of the (2nd-round tweaked) 256-bit version of the SHA-3 candidate SHAvite-3. By leveraging recently introduced cryptanalysis tools such as rebound attack or Super-Sbox cryptanalysis, we are able to derive chosen-related-salt distinguishing attacks on the compression function on up to 8 rounds (12 rounds in total) and free-start collisions on up to 7 rounds. In particular, our best results are obtained by carefully controlling the differences in the key schedule of the internal cipher. Most of our results have been implemented and verified experimentally.

An MDS matrix is an important building block adopted by different algorithms that provides diffusion and therefore, has been an area of active research. In this paper, we present an idea of direct exponent and direct square of a matrix. We prove that direct square of an MDS matrix results in an MDS matrix whereas direct exponent may not be an MDS matrix. We also delineate direct exponent class and scalar multiplication class of an MDS matrix and determine the number of elements in these classes. In the end, we discuss the standing of design properties of a cryptographic primitive by replacing MDS matrix by dynamic one.

We present a new variant of cube attacks called a \emph{dynamic cube attack}. Whereas standard cube attacks \cite{4} find the key by solving a system of linear equations in the key bits, the new attack recovers the secret key by exploiting distinguishers obtained from cube testers. Dynamic cube attacks can create lower degree representations of the given cipher, which makes it possible to attack schemes that resist all previously known attacks. In this paper we concentrate on the well-known stream cipher Grain-128 \cite{6}, on which the best known key recovery attack \cite{15} can recover only $2$ key bits when the number of initialization rounds is decreased from $256$ to $213$. Our first attack runs in practical time complexity and recovers the full 128-bit key when the number of initialization rounds in Grain-128 is reduced to $207$. Our second attack breaks a Grain-128 variant with $250$ initialization rounds and is faster than exhaustive search by a factor of about $2^{28}$. Finally, we present an attack on the full version of Grain-128 which can recover the full key but only when it belongs to a large subset of $2^{-10}$ of the possible keys. This attack is faster than exhaustive search over the $2^{118}$ possible keys by a factor of about $2^{15}$. All of our key recovery attacks are the best known so far, and their correctness was experimentally verified rather than extrapolated from smaller variants of the cipher. This is the first time that a cube attack was shown to be effective against the full version of a well known cipher which resisted all previous attacks.

Hamsi is one of the $14$ second-stage candidates in NIST's SHA-3 competition. The only previous attack on this hash function was a very marginal attack on its 256-bit version published by Thomas Fuhr at Asiacrypt $2010$, which is better than generic attacks only for very short messages of fewer than $100$ 32-bit blocks, and is only $26$ times faster than a straightforward exhaustive search attack. In this paper we describe a different algebraic attack which is less marginal: It is better than the best known generic attack for all practical message sizes (up to $4$ gigabytes), and it outperforms exhaustive search by a factor of at least $512$. The attack is based on the observation that in order to discard a possible second preimage, it suffices to show that one of its hashed output bits is wrong. Since the output bits of the compression function of Hamsi-256 can be described by low degree polynomials, it is actually faster to compute a small number of output bits by a fast polynomial evaluation technique rather than via the official algorithm.

This paper shows that if exponentiation $b=X^{k}$ in groups of finite field units or $B=[k]X$ in elliptic curves is considered as encryption of $X$ with exponent $k$ treated as symmetric key, then the decryption or the computation of $X$ from $b$ (respectively $B$) can be achieved in polynomial time with a high probability under random choice of $k$. Since given $X$ and $b$ or $B$ the problem of computing the discrete log $k$ is not known to have a polynomial time solution, the exponentiation has a trapdoor property associated with it. This paper makes this property precise. Further the decryption problem is a special case of a general problem of solving equations in groups. Such equations lead to more such trapdoor one way functions when solvable in polynomial time. The paper considers single and two variable equations on above groups and determines their solvability.

In 2007, the E.U. FP6 SecurIST called for trustworthy international identity management (IdM) that was user-centric. In 2009, the U.S. Department of Homeland Security (DHS) called for trustworthy global-scale IdM and the U.S. National Institute of Standards and Technology (NIST) called for new cryptographic key management (CKM) designs. In this paper we outline the core architecture for (apparently) the first globally scalable, post quantum secure, symmetric key based platform for provisioning IdM, key distribution/agreement and inter-enterprise CKM services. Our proposal employs a decentralised trust model that exploits compartmentalisation, redundancy and diversification simultaneously across service provider, software developer, hardware vendor, class of cryptographic primitive, and protocol axis. It employs behavioural analysis techniques and supports the collaborative management of international name spaces, management of client transactions using public identifiers and supports user-centric cross-cutting control mechanisms. Our proposal is suitable for use with commercial off the shelf hardware and is designed to wrap-around and protect the output of existing security deployments. The platform addresses the U.S. Networking and Information Technology Research and Development Program (NITRD) call to create a digital immune system (multi-layered protection, decentralised control, diversity, pattern recognition), the DHS call for combating insider attacks and malware, achieving survivability and availability, and NIST managers' call for a CKM design supporting billions of users without the use of public key technologies. This proposal has been designed as part of our Trustworthy Resilient Universal Secure Infrastructure Platform project.

Fix positive integers B and w. Let C be a linear code over F_2 of length Bw. The 2-regular-decoding problem is to find a nonzero codeword consisting of w length-B blocks, each of which has Hamming weight 0 or 2. This problem appears in attacks on the FSB (fast syndrome-based) hash function and related proposals. This problem differs from the usual information-set-decoding problems in that (1) the target codeword is required to have a very regular structure and (2) the target weight can be rather high, so that there are many possible codewords of that weight. Augot, Finiasz, and Sendrier, in the paper that introduced FSB, pre- sented a variant of information-set decoding tuned for 2-regular decoding. This paper improves the Augot–Finiasz–Sendrier algorithm in a way that is analogous to Stern's improvement upon basic information-set decoding. The resulting algorithm achieves an exponential speedup over the previous algorithm.

Security proofs are an essential part of modern cryptography. Often the challenge is not to come up with appropriate schemes but rather to technically prove that these satisfy the desired security properties. We provide for the first time techniques for proving asymptotically optimal preimage resistance bounds for block cipher based double length, double call hash functions. More precisely, we consider for some $\keylength>\blocklength$ compression functions $H:\{0,1\}^{\keylength+\blocklength} \rightarrow \{0,1\}^{2\blocklength}$ using two calls to an ideal block cipher with an $\blocklength$-bit block size. Optimally, an adversary trying to find a preimage for $H$ should require $\Omega(2^{2\blocklength})$ queries to the underlying block cipher. As a matter of fact there have been several attempts to prove the preimage resistance of such compression functions, but no proof did go beyond the $\Omega(2^{\blocklength})$ barrier, therefore leaving a huge gap when compared to the optimal bound. In this paper, we introduce two new techniques on how to lift this bound to $\Omega(2^{2\blocklength})$. We demonstrate our new techniques for a simple and natural design of $H$, being the concatenation of two instances of the well-known Davies-Meyer compression function.

In this article, the theory of multidimensional linear attacks on block ciphers is developed and the basic attack algorithms and their complexity estimates are presented. As an application the multidimensional linear distinguisher derived by Cho for the block cipher PRESENT is discussed in detail.

The majority of current attacks on reduced-round variants of block ciphers seeks to maximize the number of rounds that can be broken, using less data than the entire codebook and less time than exhaustive key search. In this paper, we pursue a different approach, restricting the data available to the adversary to a few plaintext/ciphertext pairs. We show that consideration of such attacks (which received little attention in recent years) serves an important role in assessing the security of block ciphers and of other cryptographic primitives based on block ciphers. In particular, we show that these attacks can be leveraged to more complex attacks, either on the block cipher itself or on other primitives (e.g., stream ciphers, MACs, or hash functions) that use a small number of rounds of the block cipher as one of their components. As a case study, we consider the AES --- the most widely used block cipher, whose round function is used in various cryptographic primitives. We present attacks on up to four rounds of AES that require at most 10 known/chosen plaintexts. We then apply these attacks to cryptanalyze a variant of the stream cipher LEX, and to mount a new known plaintext attack on 6-round AES.

This paper shows that a turbo-coded communication system can be made secure with a little bit of complexity cost. The classical permutation ciphers are revisited and analyzed. Firstly, the ideal stream permutation ciphers are shown to be asymptotically information-theoretically secure in the sense that the channel from plaintext to ciphertext has a vanished capacity, while the practical stream permutation ciphers are shown to be more secure than the classical stream ciphers in terms of protecting keys. Secondly, a necessary condition to break down a block permutation cipher is derived, which is then utilized to guarantee the computational security of a modified block permutation cipher. Thirdly, turbo ciphers (turbo-like codes with private interleavers) are proposed and analyzed.

In this paper, we summarize the recent related-key differential and boomerang attacks on AES by Biryukov et al. and present a framework for protection against these attacks. Then we study an alternative AES key schedule proposed by May et al. at ACISP 2002 as a possible candidate to protect against these related key attacks. We find that there exist equivalent keys for this key schedule and in response, we propose an improvement to overcome this weakness. We proceed to prove, using our framework, that our improved May et al.'s key schedule is secure against related-key differential and boomerang attacks. Since May et al.'s key schedule is not on-the-fly (which is a requirement for some hardware implementations), we propose an on-the-fly AES key schedule that is resistant against related-key differential and boomerang attacks.

In this paper we describe a variant of existing meet-in-the-middle attacks on block ciphers. As an application, we propose meet-in-the-middle attacks that are applicable to the full 254-round KTANTAN family of block ciphers accepting a key of 80 bits. The attacks are due to some weaknesses in its bitwise key schedule. We report an attack of time complexity 2^75.170 encryptions on the full KTANTAN32 cipher with only 3 plaintext/ciphertext pairs and well as 2^75.044 encryptions on the full KTANTAN48 and 2^75.584 encryptions on the full KTANTAN64 with 2 plaintext/ciphertext pairs. All these attacks work in the classical attack model without any related keys. In the differential related-key model, we demonstrate 218- and 174-round differentials holding with probability 1. This shows that a strong related-key property can translate to a successful attack in the non-related-key setting. Having extremely low data requirements, these attacks are valid even in RFID-like environments where only a very limited amount of text material may be available to an attacker.

Several attacks on Skein.

A method for extracting cryptographic key material from DRAM used in modern computers has been recently proposed in [9]; the technique was called Cold Boot attacks. When considering block ciphers, such as the AES and DES, simple algorithms were also proposed in [9] to recover the cryptographic key from the observed set of round subkeys in memory (computed via the cipher’s key schedule operation), which were however subject to errors due to memory bits decay. In this work we extend this analysis to consider key recovery for other ciphers used in Full Disk Encryption (FDE) products. Our algorithms are also based on closest code word decoding methods, however apply a novel method for solving a set of non-linear algebraic equations with noise based on Integer Programming. This method should have further applications in cryptology, and is likely to be of independent interest. We demonstrate the viability of the Integer Programming method by applying it against the Serpent block cipher, which has a much more complex key schedule than AES. Furthermore, we also consider the Twofish key schedule, to which we apply a dedicated method of recovery.

In 2008 I. Dinur and A. Shamir presented a new type of algebraic attack on symmetric ciphers named cube attack. The method has been applied to reduced variants of stream ciphers Trivium and Grain- 128, reduced variants of the block ciphers Serpent and CTC and to a reduced version of the keyed hash function MD6. Independently a very similar attack named AIDA was introduced by M. Vielhaber. In this paper we develop quadraticity tests within the cube attack and apply them to a variant of stream cipher Trivium reduced to 709 initialization rounds. Using this method we obtain the full 80-bit secret key. In this way it eliminates the stage of brute force search of some secret key bits which occured in previous cube attacks. In this corrigendum to our previous paper the indexing of cubes and key bits was reversed making it consistent with other papers.

K$\textsc{eccak}$ is one of the five hash functions selected for the final round of the SHA-3 competition and its inner primitive is a permutation called K$\textsc{eccak}$-$f$. In this paper, we find that for the inverse of the only one nonlinear transformation of K$\textsc{eccak}$-$f$, the algebraic degrees of any output coordinate and of the product of any two output coordinates are both 3 and also 2 less than its size 5. Combining the observation with a proposition from an upper bound on the degree of iterated permutations, we improve the zero-sum distinguisher of full 24 rounds K$\textsc{eccak}$-$f$ permutation by lowering the size of the zero-sum partition from $2^{1590}$ to $2^{1579}$.

Signed difference approach was first introduced by Wang for finding collision in MD5. In this paper we introduce ternary difference approach and present it in 3 symbols. To show its application we combine ternary difference approach with conventional differential cryptanalysis and apply that to cryptanalysis the reduced round PRESENT. We also use ant colony technique to obtain the best differential characteristic. To illustrate the privilege in the result of experiment, we calculate advantage of the attack.

In this paper, we analyze collision resistance of the JH hash function in the ideal primitive model. The JH hash function is one of the five SHA-3 candidates accepted for the final round of evaluation. The JH hash function uses a mode of operation based on a permutation, while its security has been elusive even in the random permutation model. One can find a collision for the JH compression function only with two backward queries to the basing primitive. However, the security is significantly enhanced in iteration. For $c\leq n/2$, we prove that the JH hash function using an ideal $n$-bit permutation and producing $c$-bit outputs by truncation is collision resistant up to $O(2^{c/2})$ queries. This bound implies that the JH hash function provides the optimal collision resistance in the random permutation model.

We consider the problem of encrypting structured data (e.g., a web graph or a social network) in such a way that it can be efficiently and privately queried. For this purpose, we introduce the notion of structured encryption which generalizes previous work on symmetric searchable encryption (SSE) to the setting of arbitrarily-structured data. In the context of cloud storage, structured encryption allows a client to encrypt data without losing the ability to query and retrieve it efficiently. Another application, which we introduce in this work, is to the problem of controlled disclosure, where a data owner wishes to grant access to only part of a massive dataset. We propose a model for structured encryption, a formal security definition and several efficient constructions. We present schemes for performing queries on two simple types of structured data, specifically lookup queries on matrix-structured data, and search queries on labeled data. We then show how these can be used to construct efficient schemes for encrypting graph data while allowing for efficient neighbor and adjacency queries. Finally, we consider data that exhibits a more complex structure such as labeled graph data (e.g., web graphs). We show how to encrypt this type of data in order to perform focused subgraph queries, which are used in several web search algorithms. Our construction is based on our labeled data and basic graph encryption schemes and provides insight into how several simpler algorithms can be combined to generate an efficient scheme for more complex queries.

It is well-known that affine equivalence relations keep nonlineaerity invariant for all Boolean functions. The set of all Boolean functions, $\mathcal{F}_n$, over $\bbbf_2^n$, is naturally regarded as the $2^n$ dimensional vector space, $\bbbf_2^{2^n}$. Thus, while analyzing the transformations acting on $\mathcal{F}_n$, $S_{2^{2^n}}$, the group of all bijective mappings, defined from $\bbbf_2^{2^n}$ onto itself should be considered. As it is shown in \cite{ser,ser:dog,ser:dog:2}, there exist non-affine bijective transformations that preserve nonlinearity. In this paper, first, we prove that the group of affine equivalence relations is isomorphic to the automorphism group of Sylvester Hadamard matrices. Then, we show that new nonlinearity preserving non-affine bijective mappings also exist. Moreover, we propose that the automorphism group of nonlinearity classes, should be studied as a subgroup of $S_{2^{2^n}}$, since it contains transformations which are not affine equivalence relations.

Impossible differential cryptanalysis is a very popular tool for analyzing the security of modern block ciphers and the core of such attack is based on the existence of impossible differentials. Currently, most methods for finding impossible differentials are based on the miss-in-the-middle technique and they are very ad-hoc. In this paper, we concentrate SPN ciphers whose diffusion layer is defined by a linear transformation $P$. Based on the theory of linear algebra, we propose several criteria on $P$ and its inversion $P^{-1}$ to characterize the existence of $3/4$-round impossible differentials. We further discuss the possibility to extend these methods to analyze $5/6$-round impossible differentials. Using these criteria, impossible differentials for reduced-round Rijndael are found that are consistent with the ones found before. New $4$-round impossible differentials are discovered for block cipher ARIA. And many $4$-round impossible differentials are firstly detected for a kind of SPN cipher that employs a $32\times32$ binary matrix proposed at ICISC 2006 as its diffusion layer. It is concluded that the linear transformation should be carefully designed in order to protect the cipher against impossible differential cryptanalysis.

In this paper we develop a technique of constructing bent--negabent Boolean functions by using complete mapping polynomials. Using this technique we demonstrate that for each $\ell \ge 2$ there exits bent--negabent functions on $n = 12\ell$ variables with algebraic degree $\frac{n}{4}+1 = 3\ell + 1$. It is also demonstrated that there exist bent--negabent functions on $8$ variables with algebraic degrees $2$, $3$ and $4$.

Recently, various cryptanalysis methods related to Cube Attack have attracted a lot of interest. We designed a practical platform to perform such cryptanalysis attacks. We also developed a web-based application at \url{http://cube-attack.appspot.com/}, which is open to public for simple testing and verification. In this paper, we focus on linearity testing and try to verify the data provided in several papers. Some interesting results produced in our work indicate certain improper assumptions were made in these papers.

In this paper we give more insights on the security of blockcipher-based hash functions. We give a very simple criterion to build a secure large class of Single-Block-Length (SBL) or double call Double-Block-Length (DBL) compression functions based on $(kn, n)$ blockciphers, where $kn$ is the key length and $n$ is the block length and $k$ is an integer. This criterion is simpler than previous works in the literature. Based on the criterion, we can get many results from this criterion, and we can get a conclusion on such class of blockcipher-based hash functions. We solved the open problem left by Hirose. Our results show that to build a secure double call DBL compression function, it is required $k >= m+1$ where $m$ is the number of message blocks. Thus, we can only build rate 1/2 secure double DBL blockcipher-based compression functions if $k==2$. At last, we pointed out flaws in Stam's theorem about supercharged functions and gave a revision of this theorem and added another condition for the security of supercharged compression functions.

This paper presents an analysis of the stream cipher Mixer, a bit-based cipher with structural components similar to the well-known Grain cipher and the LILI family of keystream generators. Mixer uses a 128-bit key and 64-bit IV to initialise a 217-bit internal state. The analysis is focused on the initialisation function of Mixer and shows that there exist multiple key-IV pairs which, after initialisation, produce the same initial state, and consequently will generate the same keystream. Furthermore, if the number of iterations of the state update function performed during initialisation is increased, then the number of distinct initial states that can be obtained decreases. It is also shown that there exist some distinct initial states which produce the same keystream, resulting in a further reduction of the effective key space.

Differential Fault Analysis (DFA) attack is a powerful cryptanalytic technique that could be used to retrieve the secret key by exploiting computational errors in the encryption (decryption) procedure. In the present paper, we propose a new DFA attack on SMS4 using a single fault. We show that if a random byte fault is induced into either the second, third, or fourth word register at the input of the $28$-th round, the 128-bit master key could be recovered with an exhaustive search of $22.11$ bits on average. The proposed attack makes use of the characteristic of the cipher's structure, the speciality of the diffusion layer, and the differential property of the S-box. Furthermore, it can be tailored to any block cipher employing a similar structure and an SPN-style round function as that of SMS4.

In this note we show that the message authentication code 128-EIA3 considered for adoption as one of the integrity algorithms of the emerging mobile standard LTE is vulnerable to a simple existential forgery attack. This attack allows, given any message and the associated MAC value under an unknown integrity key and an initial vector, to predict the MAC value of a related message under the same key and the same initial vector with a success probability 1/2.

The SC2000 block cipher has a 128-bit block size and a user key of 128, 192 or 256 bits, which employs a total of 6.5 rounds if a 128-bit user key is used. It is a CRYPTREC recommended e-government cipher. In this paper we describe two 4.75-round differential characteristics with probability $2^{-126}$ of SC2000 and seventy-six 4.75-round differential characteristics with probability $2^{-127}$. Finally, we present a differential cryptanalysis attack on a 5-round reduced version of SC2000 when used with a 128-bit key; the attack requires $2^{125.68}$ chosen plaintexts and has a time complexity of $2^{125.75}$ 5-round SC2000 encryptions. It suggests for the first time that the safety margin of SC2000 with a 128-bit key decreases below one and a half rounds.

In this paper we show a quantum preimage attack on CubeHash-512-normal with complexity 2^192 . This kind of attack is expected to cost 2^256 for a good 512-bit hash function, and we argue that this violates the expected security of CubeHash. The preimage attack can also be used as a collision attack, given that a generic quantum collision attack on a 512-bit hash function require 2^256 operations, as explained in the CubeHash submission document. This attack only uses very simple techniques, most of which are borrowed from previous analysis of CubeHash: we just combine symmetry based attacks [1,8] with Grover's algorithm. However, it is arguably the first attack on a second-round SHA-3 candidate that is more efficient than the attacks considered by the designer.

In this paper, we identify higher-order differential and zero-sum properties in the full Keccak-f permutation, in the Luffa v1 hash function, and in components of the Luffa v2 algorithm. These structural properties rely on a new bound on the degree of iterated permutations with a nonlinear layer composed of parallel applications of smaller balanced Sboxes. These techniques yield zero-sum partitions of size $2^{1590}$ for the full Keccak-f permutation and several observations on the Luffa hash family. We first show that Luffa v1 applied to one-block messages is a function of 255 variables with degree at most 251. This observation leads to the construction of a higher-order differential distinguisher for the full Luffa v1 hash function, similar to the one presented by Watanabe et al. on a reduced version. We show that similar techniques can be used to find all-zero higher-order differentials in the Luffa v2 compression function, but the additional blank round destroys this property in the hash function.

In this work, we present a collision attack on 5 out of 8 rounds of the ECHO-256 hash function with a complexity of $2^{112}$ in time and $2^{85.3}$ memory. In this work, we further show that the merge inbound phase can still be solved in the case of hash function attacks on ECHO. As correctly observed by Jean et al., the merge inbound phase of previous hash function attacks succeeds only with a probability of $2^{-128}$. The main reason for this behavior is the low rank of the linear SuperMixColumns transformation. However, since there is enough freedom in ECHO we can solve the resulting linear equations with a complexity much lower than $2^{128}$. On the other hand, also this low rank of the linear SuperMixColumns transformation allows us to extend the collision attack on the reduced hash function from 4 to 5 rounds. Additionally, we present a collision attack on 6 rounds of the compression function of ECHO-256 and show that a subspace distinguisher is still possible for 7 out of 8 rounds of the compression function of ECHO-256. Both compression function attacks have a complexity of $2^{160}$ with memory requirements of $2^{128}$ and chosen salt.

We propose an improved preimage attack on one-block MD4 with the time complexity $2^{94.98}$ MD4 compression function operations, as compared to $2^{107}$ in \cite{AokiS-sac08}. We research the attack procedure in \cite{AokiS-sac08} and formulate the complexity for computing a preimage attack on one-block MD4. We attain the result mainly through the following two aspects with the help of the complexity formula. First, we continue to compute two more steps backward to get two more chaining values for comparison during the meet-in-the-middle attack. Second, we search two more neutral words in one independent chunk, and then propose the multi-neutral-word partial-fixing technique to get more message freedom and skip ten steps for partial-fixing, as compared to previous four steps. We also use the initial structure technique and apply the same idea to improve the pseudo-preimage and preimage attacks on Extended MD4 with $2^{25.2}$ and $2^{12.6}$ improvement factor, as compared to previous attacks in \cite{SasakiA-acisp09}, respectively.

In 2008 I. Dinur and A. Shamir presented a new type of algebraic attack on symmetric ciphers named cube attack. The method has been applied to reduced variants of stream ciphers Trivium and Grain- 128, reduced variants of the block ciphers Serpent and CTC and to a reduced version of the keyed hash function MD6. Independently a very similar attack named AIDA was introduced by M. Vielhaber. In this paper we develop quadraticity tests within the cube attack and apply them to a variant of stream cipher Trivium reduced to 709 initialization rounds. Using this method we obtain the full 80-bit secret key. In this way it eliminates the stage of brute force search of some secret key bits which occured in previous cube attacks.

A method is proposed to construct resilient Boolean functions on $n$ variables ($n$ even) satisfying strict avalanche criterion (SAC) with nonlinearity $>2^{n-1}-2^{n/2}$. A large class of cryptographic Boolean functions which were not known earlier are obtained.

One of the most basic properties expected from block ciphers and hash functions is passing statistical randomness testing, as they are expected to behave like random mappings. Previously, testing of AES candidate block ciphers was done by concatenating the outputs of the algorithms obtained from various input types. In this work, a more convenient method, namely the cryptographic randomness testing is introduced. A package of statistical tests are designed based on certain cryptographic properties of block ciphers and hash functions to evaluate their randomness. The package is applied to the AES finalists, and produced more precise results than those obtained in similar applications.

At Eurocrypt 2001, Biryukov and Shamir investigated the security of AES-like ciphers where the substitutions and affine transformations are all key-dependent and successfully cryptanalysed two and a half rounds. This paper considers PRESENT-like ciphers in a similar manner. We focus on the settings where the S-boxes are key dependent, and repeated for every round. We break one particular variant which was proposed in 2009 with practical complexity in a chosen plaintext/chosen ciphertext scenario. Extrapolating these results suggests that up to 28 rounds of such ciphers can be broken. Furthermore, we outline how our attack strategy can be applied to an extreme case where the S-boxes are chosen uniformly at random for each round and where the bit permutation is secret as well.

It is proved that there does not exist a linearized polynomial $L(x)\in\mathbb{F}_{2^n}[x]$ such that $x^{-1}+L(x)$ is a permutation on $\mathbb{F}_{2^n}$ when $n\geq5$, which is proposed as a conjecture in \cite{li}. As a consequence, a permutation is EA-equivalent to the inverse function over $\mathbb{F}_{2^n}$ if and only if it is affine equivalent to it when $n\geq 5$.

We present a chosen-plaintext attack on KIST, a recently proposed encryption scheme based on splay trees. Our attack recovers a 128-bit key with approximately 2^28 bit operations and fewer than 2^19 chosen-plaintext queries.

Protecting the confidentiality in large databases without degrading their performance is a challenging problem, especially when encryption and decryption must be performed at the database-level or at the application-level. We here focus on symmetric ciphers for database encryption since they are the only type of ciphers with acceptable performance for most applications. We point out that stream ciphers are the adequate type of encryption schemes. We present an attack on a dedicated stream cipher proposed by Ge and Zdonic in 2007, and on a variant of this encryption scheme.

A (2,n)-Visual Cryptography Scheme (VCS) is a kind of secret sharing scheme, where n participants share a secret image, and any two of them can recover the secret image visually without any cryptographic knowledge and computation devices, but any one of them cannot get any information about the secret image other than the size of the secret image. This paper studies the (2,n)-VCS_{XOR}, and shows the smallest (optimal) pixel expansion of such schemes, and the largest possible contrast for the (2,n)-VCS_{XOR} given its optimal pixel expansion. It also shows the largest (optimal) contrast of the (2,n)-VCS_{XOR}, and the smallest possible pixel expansion of such schemes given their optimal contrast. The results of this paper show that the (2,n)-VCS_{XOR} can achieve smaller pixel expansion and larger contrast than that of (2,n)-VCS_{OR}. It also shows that the construction of the basis matrix of optimal contrast (2,n)-VCS_{XOR} is equivalent to the construction of binary codes when they reach the maximum capability, and the construction of a specific class of optimal contrast (2,n)-VCS_{XOR} for n=2^{k}-1 is given.

In this paper we combine the recent rotational cryptanalysis with the rebound attack, which results in the best cryptanalysis of Skein, a candidate for the SHA-3 competition. The rebound attack approach was so far only applied to AES-like constructions. For the first time, we show that this approach can also be applied to very different constructions. In more detail, we develop a number of techniques that extend the reach of both the inbound and the outbound phase, leading to rotational collisions for about 53/57 out of the 72 rounds of the Skein-256/512 compression function and the Threefish cipher. At this point, the results do not threaten the security of the full-round Skein hash function. The new techniques include an analytical search for optimal input values in the rotational cryptanalysis, which allows to extend the outbound phase of the attack with a precomputation phase, an approach never used in any rebound-style attack before. Further we show how to combine multiple inside-out computations and neutral bits in the inbound phase of the rebound attack, and give well-defined rotational distinguishers as certificates of weaknesses for the compression functions and block ciphers.

The AES block cipher has a 128-bit block length and a user key of 128, 192 or 256 bits, released by NIST for data encryption in the USA; it became an ISO international standard in 2005. In 2008, Demirci and Selccuk gave a meet-in-the-middle attack on 7-round AES under 192 key bits. In 2009, Demirci et al. (incorrectly) described a new meet-in-the-middle attack on 7-round AES under 192 key bits. Subsequently, Dunkelman et al. described an attack on 8-round AES under 192 key bits by taking advantage of several advanced techniques, including one about the key schedule. In this paper, we show that by exploiting a simple observation on the key schedule, a meet-in-the-middle attack on 8-round AES under 192 key bits can be obtained from Demirci and Selccuk's and Demirci et al.'s work; and a more efficient attack can be obtained when taking into account Dunkelman et al.'s observation on the key schedule. In the single-key attack scenario, attacking 8 rounds is the best currently known cryptanalytic result for AES in terms of the numbers of attacked rounds, and our attack has a dramatically smaller data complexity than the currently known attacks on 8-round AES under 192 key bits.

Recent developments in the field of cryptanalysis of hash functions has inspired NIST to announce a competition for selecting a new cryptographic hash function to join the SHA family of standards. One of the 14 second-round candidates is CubeHash designed by Daniel J. Bernstein. CubeHash is a unique hash function in the sense that it does not iterate a common compression function, and offers a structure which resembles a sponge function, even though it is not exactly a sponge function. In this paper we analyze reduced-round variants of CubeHash where the adversary controls the full 1024-bit input to reduced-round CubeHash and can observe its full output. We show that linear approximations with high biases exist in reduced-round variants. For example, we present an 11-round linear approximation with bias of 2^{−235}, which allows distinguishing 11-round CubeHash using about 2^{470} queries. We also discuss the extension of this distinguisher to 12 rounds using message modification techniques. Finally, we present a linear distinguisher for 14-round CubeHash which uses about 2^{812} queries.

In this paper, three constructions of balanced Boolean functions with optimum algebraic immunity are proposed. The cryptographical properties such as algebraic degree and nonlinearity of the constructed functions are also analyzed.

In this paper we present a new statistical cryptanalytic technique that we call improbable differential cryptanalysis which uses a differential that is less probable when the correct key is used. We provide data complexity estimates for this kind of attacks and we also show a method to expand impossible differentials to improbable differentials. By using this expansion method, we cryptanalyze 13, 14, and 15-round CLEFIA for the key sizes of length 128, 192, and 256 bits, respectively. These are the best cryptanalytic results on CLEFIA up to this date.

EnRUPT is a cryptographic primitive with a variable block and key length. We show several attacks on it that stem from properties of its keying, including a very fast related-key attack.

Addition modulo $2^{31}-1$ is a basic arithmetic operation in the stream cipher ZUC. For evaluating ZUC in resistance to linear cryptanalysis, it is necessary to study properties of linear approximations of the addition modulo $2^{31}-1$. In this paper we discuss linear approximations of the addition modulo $2^n-1$ for integer $n\ge2$. As results, an exact formula on the correlations of linear approximations of the addition modulo $2^n-1$ is given for the case when two inputs are involved, and an iterative formula for the case when more than two inputs are involved. For a class of special linear approximations with all masks being equal to 1, we further discuss the limit of their correlations when $n$ goes to infinity. Let $k$ be the number of inputs of the addition modulo $2^n-1$. It's shows that when $k$ is even, the limit is equal to zero, and when $k$ is odd, the limit is bounded by a constant depending on $k$.

The notion of indifferentiability, introduced by Maurer et al., is an important criterion for the security of hash functions. Concretely, it ensures that a hash function has no structural design flaws and thus guarantees security against generic attacks up to the exhibited bounds. In this work we prove the indifferentiability of Grøstl, a second round SHA-3 hash function candidate. Grøstl combines characteristics of the wide-pipe and chop-Merkle-Damgård iterations and uses two distinct permutations P and Q internally. Under the assumption that P and Q are random l-bit permutations, where l is the iterated state size of Grøstl, we prove that the advantage of a distinguisher to differentiate Grøstl from a random oracle is upper bounded by O((Kq)^4/2^l), where the distinguisher makes at most q queries of length at most K blocks. For the specific Grøstl parameters, this result implies that Grøstl behaves like a random oracle up to q=O(2^{n/2}) queries, where n is the output size. Furthermore, we show that the output transformation of Grøstl, as well as `Grøstail' (the composition of the final compression function and the output transformation), are clearly differentiable from a random oracle. This renders out indifferentiability proofs which rely on the idealness of a final state transformation.

This paper presents a byte-oriented stream cipher -- Loiss, which takes a 128-bit initial key and a 128-bit initial vector as inputs, and outputs a key stream of bytes. The algorithm is based on a linear feedback shift register, and uses a structure called BOMM in the filter generator, which has good property on resisting against algebraic attacks, linear distinguishing attacks and fast correlation attacks. In order for BOMM to be balanced, the S-boxes in BOMM must be orthomorphic permutations. To further improve the capability in resisting against those attacks, the S-boxes in BOMM must also possess some good cryptographic properties, for example, high algebraic immunity, high nonlinearity, and so on. However current researches on orthomorphic permutations pay little attention on their cryptographic properties, and we believe that Loiss not only enriches applications of orthomorphic permutations in cryptography, but also motivates the research on a variety of cryptographic properties of orthomorphic permutations.

In this paper, inspired from the notion of impossible differentials, we present a model to use differentials that are less probable than a random permutation. We introduce such a distinguisher for 2 rounds of Crypton, and present an attack on 6 rounds of this predecessor AES candidate. As a special case of this idea, we embed parts of the additional rounds around the impossible differential into the distinguisher to make a probabilistic distinguisher with more rounds. We show that with this change, the data complexity is increased but the time complexity may be reduced or increased. Then we discuss that this change in the impossible differential cryptanalysis is commodious and rational when the data complexity is low and time complexity is marginal.

We revisit narrow-pipe designs that are in practical use, and their security against preimage attacks. Our results are the best known preimage attacks on Tiger, MD4, and reduced SHA-2, with the result on Tiger being the first cryptanalytic shortcut attack on the full hash function. Our attacks runs in time $2^{188.8}$ for finding preimages, and $2^{188.2}$ for second-preimages. Both have memory requirement of order $2^{8}$, which is much less than in any other recent preimage attacks on reduced Tiger. Using pre-computation techniques, the time complexity for finding a new preimage or second-preimage for MD4 can now be as low as $2^{78.4}$ and $2^{69.4}$ MD4 computations, respectively. The second-preimage attack works for all messages longer than 2 blocks. To obtain these results, we extend the meet-in-the-middle framework recently developed by Aoki and Sasaki in a series of papers. In addition to various algorithm-specific techniques, we use a number of conceptually new ideas that are applicable to a larger class of constructions. Among them are (1) incorporating multi-target scenarios into the MITM framework, leading to faster preimages from pseudo-preimages, (2) a simple precomputation technique that allows for finding new preimages at the cost of a single pseudo-preimage, and (3) probabilistic initial structures, compared with deterministic ones, to enable more neutral words, and hence to reduce the attack time complexity. All the techniques developed await application to other hash functions. To illustrate this, we give as another example improved preimage attacks on SHA-2 members.

In [Solving Multiple Right Hand Sides linear equations. Designs, Codes and Cryptography, 49:147–160, 2008] Raddum and Semaev propose a technique to solve systems of polynomial equations over GF(2) as occurring in algebraic attacks on block ciphers. This approach is known as MRHS, and we present a special purpose architecture to implement MRHS in a dedicated hardware device. Our preliminary performance analysis of this Parallel Elimination Technique Supporting Nice Algebraic Key Elimination shows that the use of ASICs seems to enable significant performance gains over a software implementation of MRHS. The main parts of the proposed architecture are scalable, the limiting factor being mainly the available bandwidth for interchip communication. Our focus is on a design choice that can be implemented within the limits of available fab technology. The proposed design can be expected to offer a running time improvement in the order of several magnitudes over a software implementation. We do not make any claims about the practical feasibility of an attack against AES-128 with our design, as we do not see the necessary theoretical tools to be available: deriving reliable running time estimates for an algebraic attack with MRHS when being applied to a full-round version of AES-128 is still an open problem.

In this paper we study the strength of two hash functions which are based on Generalized Feistels. Our proposed attacks themselves are mostly independent of the round function in use, and can be applied to similar hash functions which share the same structure but have different round functions. We start with a 22-round generic attack on the structure of Lesamnta, and adapt it to the actual round function to attack 24-round Lesamnta. We then show a generic integral attack on 20-round Lesamnta (which can be used against the block cipher itself). We follow with an attack on 9-round SHAvite-3_{512} which is the first cryptanalytic result on the hash function (which also works for the tweaked version of SHAvite-3_{512}).

In this paper we study six 2nd round SHA-3 candidates from a side-channel cryptanalysis point of view. For each of them, we give the exact procedure and appropriate choice of selection functions to perform the attack. Depending on their inherent structure and the internal primitives used (Sbox, addition or XOR), some schemes are more prone to side channel analysis than others, as shown by our simulations.

In this paper, we present a class of $2k$-variable balanced Boolean functions and a class of $2k$-variable $1$-resilient Boolean functions for an integer $k\ge 2$, which both have the maximal algebraic degree and very high nonlinearity. Based on a newly proposed conjecture by Tu and Deng, it is shown that the proposed balanced Boolean functions have optimal algebraic immunity and the $1$-resilient Boolean functions have almost optimal algebraic immunity. Among all the known results of balanced Boolean functions and $1$-resilient Boolean functions, our new functions possess the highest nonlinearity. Based on the fact that the conjecture has been verified for all $k\le 29$ by computer, at least we have constructed a class of balanced Boolean functions and a class of $1$-resilient Boolean functions with the even number of variables $\le 58$, which are cryptographically optimal or almost optimal in terms of balancedness, algebraic degree, nonlinearity, and algebraic immunity.

We present improved cryptanalysis of two second-round SHA-3 candidates: the AES-based hash functions ECHO and GROSTL. We explain methods for building better differential trails for ECHO by increasing the granularity of the truncated differential paths previously considered. In the case of GROSTL, we describe a new technique, the internal differential attack, which shows that when using parallel computations designers should also consider the differential security between the parallel branches. Then, we exploit the recently introduced start-from-the-middle or Super-Sbox attacks, that proved to be very efficient when attacking AES-like permutations, to achieve a very efficient utilization of the available freedom degrees. Finally, we obtain the best known attacks so far for both ECHO and GROSTL. In particular, we are able to mount a distinguishing attack for the full GROSTL-256 compression function.

The operations addition modulo 2^n and exclusive-or have recently been combined to obtain an efficient mechanism for nonlinearity in block cipher design. In this paper, we show that ciphers using this approach may be approximated by pseudo-linear expressions relating groups of contiguous bits of the round key, round input, and round output. The bias of an approximation can be large enough for known plaintext attacks. We demonstrate an application of this concept to a reduced-round version of the Threefish block cipher, a component of the Skein entry in the secure hash function competition.

In this note we show a consequence of the recent observation that narrow-pipe hash designs manifest an abberation from ideal random functions for finding collisions for those functions with complexities much lower than the so called generic birthday paradox lower bound. The problem is generic for narrow-pipe designs including classic Merkle-Damgard designs but also recent narrow-pipe SHA-3 candidates. Our finding does not reduces the generic collision security of n/2 bits that narrow-pipe functions are declaring, but it clearly shows that narrow-pipe designs have a property when we count the calls to the hash function as a whole, the birthday paradox bound of 2^{n/2} calls to the hash function is clearly broken. This is yet another property in a series of similar non-ideal random properties (like HMAC or PRF constructions) that narrow-pipe hash function manifest and that are described in [1] and [2].

The n-cell GF-NLFSR (Generalized Feistel-NonLinear Feedback Shift Register) structure [8] is a generalized unbalanced Feistel network that can be considered as a generalization of the outer function FO of the KASUMI block cipher. An advantage of this cipher over other n-cell generalized Feistel networks, e.g. SMS4 [11] and Camellia [5], is that it is parallelizable for up to n rounds. In hardware implementations, the benefits translate to speeding up encryption by up to n times while consuming similar area and significantly less power. At the same time n-cell GF-NLFSR structures offer similar proofs of security against differential cryptanalysis as conventional n-cell Feistel structures. We also ensure that parallelized versions of Camellia and SMS4 are resistant against other block cipher attacks such as linear, boomerang, integral, impossible differential, higher order differential,interpolation, slide, XSL and related-key differential attacks.

In this paper, we proposed a new encryption algorithm called KIST. This algorithm uses an asynchronous key sequence and a splay tree. It is very efficient in the usage of both space and time. Some elementary security tests have been done.

In this note we consider the Shabal permutation function $\mathcal{P}$ as a block cipher with input $A_p$,$B_p$ and key $C$,$M$ and describe a distinguisher with a data complexity of $2^{23}$ random inputs with a given difference. If the attacker can control one chosen bit of $B_p$, only $2^{21}$ inputs with a given difference are required on average. This distinguisher does not appear to lead directly to an attack on the full Shabal construction.

Since its announcement, AES has been subject to different DFA attacks. Most of these attacks target the AES with 128-bit key. However, the two other variants are nowadays deployed in various applications and are also submitted to the same attack path. In this paper, we adapt the DFA techniques originally used on AES-128 in order to obtain the keys of AES-192 and AES-256. To illustrate this method, we propose efficient attacks on AES-192 and AES-256 based on a known DFA on KeyExpansion.

Recent iterated ciphers have been designed to be resistant to differential cryptanalysis. This implies that cryptanalysts have to deal with differentials having so small probabilities that, for a fixed key, the whole codebook may not be sufficient to detect it. The question is then, do these theoretically computed small probabilities have any sense? We propose here a deep study of differential and differential trail probabilities supported by experimental results obtained on a reduced version of PRESENT.

We analyze the Grøstl hash function, which is a 2nd-round candidate of the SHA-3 competition. Using the start-from-the-middle variant of the rebound technique, we show collision attacks on the Grøstl-256 hash function reduced to 5 and 6 out of 10 rounds with time complexities $2^{48}$ and $2^{112}$, respectively. Furthermore, we demonstrate semi-free-start collision attacks on the Grøstl-224 and -256 hash functions reduced to 7 rounds and the Grøstl-224 and -256 compression functions reduced to 8 rounds. Our attacks are based on differential paths between the two permutations $P$ and $Q$ of Grøstl, a strategy introduced by Peyrin to construct distinguishers for the compression function. In this paper, we extend this approach to construct collision and semi-free-start collision attacks for both the hash and the compression function. Finally, we present improved distinguishers for reduced-round versions of the Grøstl-224 and -256 permutations.

Security of data stored in bulk storage devices like the hard disk has gained a lot of importance in the current days. Among the variety of paradigms which are available for disk encryption, low level disk encryption is well accepted because of the high security guarantees it provides. In this paper we view the problem of disk encryption from a different direction. We explore the possibility of how one can maintain secure backups of the data, such that loss of a physical device will mean neither loss of the data nor the fact that the data gets revealed to the adversary. We propose an efficient solution to this problem through a new cryptographic scheme which we call as the double ciphertext mode (DCM). In this paper we describe the syntax of DCM, define security for it and give some efficient constructions. Moreover we argue regarding the suitability of DCM for the secure backup application and also explore other application areas where a DCM can be useful.

This paper proposes improved post analysis methods for Differential Fault Analysis (DFA) against AES. In detail, we propose three techniques to improve the attack efficiency as 1) combining previous DFA methods, 2) performing a divide-and-conquer attack by considering the AES key-schedule structure, and 3) taking the linearity of the MixColumns operation into account. As a result, the expectation of the analysis time in the previous work can be reduced to about one sixteenth. Notice that these improvements are based on the detailed analysis of the previous DFA methods and the calculation time and memory cost in practical implementations. Moreover, the proposed techniques can be widely applied to DFA attacks under different assumptions.

In this paper we study the security of the SHA-3 candidate SIMD. We first show a new free-start distinguisher based on symmetry relations. It allows to distinguish the compression function of SIMD from a random function with a single evaluation. However, we also show that this property is very hard to exploit to mount any attack on the hash function because of the mode of operation of the compression function. Essentially, if one can build a pair of symmetric states, the symmetry property can only be triggered once. In the second part, we show that a class of free-start distinguishers is not a threat to the wide-pipe hash functions. In particular, this means that our distinguisher has a minimal impact on the security of the hash function, and we still have a security proof for the SIMD hash function. Intuitively, the reason why this distinguisher does not weaken the function is that getting into a symmetric state is about as hard as finding a preimage. Finally, in the third part we study differential path in SIMD, and give an upper bound on the probability of related key differential paths. Our bound is in the order of $2^{n/2}$ using very weak assumptions. Resistance to related key attacks is often overlooked, but it is very important for hash function designs.

SIMD is one of the second round candidates of the SHA-3 competition hosted by NIST. In this paper, we present some results on the compression function of SIMD 1.1 (the tweaked version) using the modular difference method. For SIMD-256, We give a free-start near collision attack on the compression function reduced to 20 steps with complexity $2^{-107}$. And for SIMD-512, we give a free-start near collision attack on the 24-step compression function with complexity $2^{208}$. Furthermore, we give a distinguisher attack on the full compression function of SIMD-512 with complexity $2^{398}$. Our attacks are also applicable for the final compression function of SIMD.

\begin{abstract} In this paper we will study 2 security results ``above the birthday bound'' related to secret key cryptographic problems.\\ 1. The classical problem of the security of 4, 5, 6 rounds balanced Random Feistel Schemes.\\ 2. The problem of the security of unbalanced Feistel Schemes with contracting functions from $2n$ bits to $n$ bits. This problem was studied by Naor and Reingold~\cite{NR99} and by~\cite{YPL} with a proof of security up to the birthday bound.\\ These two problems are included here in the same paper since their analysis is closely related, as we will see. In problem 1 we will obtain security result very near the information bound (in $O(\frac {2^n}{n})$) with improved proofs and stronger explicit security bounds than previously known. In problem 2 we will cross the birthday bound of Naor and Reingold. For some of our proofs we will use~\cite{A2} submitted to Crypto 2010. \end{abstract}

In this paper we study the lower bounds of second-order nonlinearities of bent functions constructed by modifying certain cubic Maiorana-McFarland type bent functions.

Bernstein's CubeHash is a hash function family that includes four functions submitted to the NIST Hash Competition. A CubeHash function is parametrized by a number of rounds r, a block byte size b, and a digest bit length h (the compression function makes r rounds, while the finalization function makes 10r rounds). The 1024-bit internal state of CubeHash is represented as a five-dimensional hypercube. The submissions to NIST recommends r=8, b=1, and h in {224,256,384,512}. This paper presents the first external analysis of CubeHash, with: improved standard generic attacks for collisions and preimages; a multicollision attack that exploits fixed points; a study of the round function symmetries; a preimage attack that exploits these symmetries; a practical collision attack on a weakened version of CubeHash; a study of fixed points and an example of nontrivial fixed point; high-probability truncated differentials over 10 rounds. Since the first publication of these results, several collision attacks for reduced versions of CubeHash were published by Dai, Peyrin, et al. Our results are more general, since they apply to any choice of the parameters, and show intrinsic properties of the CubeHash design, rather than attacks on specific versions.

BLAKE is a hash function selected by NIST as one of the 14 second round candidates for the SHA-3 Competition. In this paper, we follow a bottom-up approach to exhibit properties of BLAKE and of its building blocks: based on differential properties of the internal function G, we show that a round of BLAKE is a permutation on the message space, and present an efficient inversion algorithm. For 1.5 rounds we present an algorithm that finds preimages faster than in previous attacks. Discovered properties lead us to describe large classes of impossible differentials for two rounds of BLAKE’s internal permutation, and particular impossible differentials for five and six rounds, respectively for BLAKE- 32 and BLAKE-64. Then, using a linear and rotation-free model, we describe near-collisions for four rounds of the compression function. Finally, we discuss the problem of establishing upper bounds on the probability of differential characteristics for BLAKE.

In this paper we consider cubic bent functions obtained by Leander and McGuire (J. Comb. Th. Series A, 116 (2009) 960-970) which are concatenations of quadratic Gold functions. A lower bound of second-order nonlinearities of these functions is obtained. This bound is compared with the lower bounds of second-order nonlinearities obtained for functions belonging to some other classes of functions which are recently studied.

In this note we present the first attack with feasible complexity on the 13-round AES-256. The attack runs in the related-subkey scenario with four related keys, in 2^{76} time, data, and memory.

XXTEA, or Corrected Block TEA, is a simple block cipher in Roger Needham and David Wheeler's TEA series of algorithms. We describe a chosen plaintext attack for XXTEA using about $2^{59}$ queries and negligible work.

While differential behavior of modern ciphers in a single secret key scenario is relatively well understood, and simple techniques for computation of security lower bounds are readily available, the security of modern block ciphers against related-key attacks is still very ad hoc. In this paper we make a first step towards provable security of block ciphers against related-key attacks by presenting an efficient search tool for finding differential characteristics both in the state and in the key (note that due to similarities between block ciphers and hash functions such tool will be useful in analysis of hash functions as well). We use this tool to search for the best possible (in terms of the number of rounds) related-key differential characteristics in AES, byte-Camellia, Khazad, FOX, and Anubis. We show the best related-key differential characteristics for 5, 11, and 14 rounds of AES-128, AES-192, and AES-256 respectively. We use the optimal differential characteristics to design the best related-key and chosen key attacks on AES-128 (7 out of 10 rounds), AES-192 (full 12 rounds), byte-Camellia (full 18 rounds) and Khazad (7 and 8 out of 8 rounds). We also show that ciphers FOX and Anubis have no related-key attacks on more than 4-5 rounds.

Modular Multiplication based Block Cipher (MMB) is a block cipher designed by Daemen \emph{et al.} as an alternative to the IDEA block cipher. In this paper, we give a practical-time attack on the full MMB with adaptive chosen plaintexts and ciphertexts. By the constructive sandwich distinguisher for 5 of the 6 rounds of MMB with amazingly high probability 1, we give the key recovery attack on the full MMB with data complexity $2^{40}$ and time complexity $2^{13.4}$ MMB encryptions. Then a rectangle-like sandwich attack on the full MMB is presented, with $2^{66.5}$ chosen plaintexts, $2^{64}$ MMB encryptions and $2^{70.5}$ memory bytes. By the way, we show an improved differential attack on the full MMB with data complexity of $2^{96}$ chosen plaintexts and ciphertexts, time complexity $2^{64}$ encryptions and $2^{66}$ bytes of memory.