We present two practical attacks on the CAESAR candidate PAES. The first attack is a universal forgery for any plaintext with at least 240 bytes. It works for the nonce-repeating variant of PAES and in a nutshell it is a state recovery based on solving differential equations for the S-Box leaked through the ciphertext that arise when the plaintext has a certain difference. We show that to produce the forgery based on this method the attacker needs only 211 time and data. The second attack is a distinguisher for 264 out of 2128 keys that requires negligible complexity and only one pair of known plaintext-ciphertext. The attack is based on the lack of constants in the initialization of the PAES which allows to exploit the symmetric properties of the keyless AES round. Both of our attacks contradict the security goals of PAES.

Many hash-based authentication protocols have been proposed, and proven secure assuming that underlying hash functions are secure. On the other hand, if a hash function compromises, the security of authentication protocols based on this hash function becomes unclear. Therefore, it is significantly important to verify the security of hash-based protocols when a hash function is broken. In this paper, we will re-evaluate the security of two MD5-based authentication protocols based on a fact that MD5 cannot satisfy a required fundamental property named collision resistance. The target protocols are APOP (Authenticated Post Office Protocol) and NMAC (Nested Message Authentication Code), since they or their variants are widely used in real world. For security evaluation of APOP, we will propose a modified password recovery attack procedure, which is twice as fast as previous attacks. Moreover, our attack is more realistic, as the probability of being detected is lower than that of previous attacks. For security evaluation of MD5-based NMAC, we will propose a new key-recovery attack procedure, which has a complexity lower than that of previous attack. The complexity of our attack is 276, while that of previous attack is 2100.** Moreover, our attack has another interesting point. NMAC has two keys: the inner key and the outer key. Our attack can recover the outer key partially without the knowledge of the inner key.

We present cryptanalyses of the original version of AURORA-512 hash function, which is a round-1 SHA-3 candidate. Our attack exploits weaknesses in a narrow-pipe mode of operation of AURORA-512 named "Double-Mix Merkle-Damgård (DMMD)." The current best collision attack proposed by Joux and Lucks only gives rough complexity estimations. We first evaluate its precise complexity and show its optimization. Secondly, we point out that the current best second-preimage attack proposed by Ferguson and Lucks does not work with the claimed complexity of 2291. We then evaluate a complexity so that the attack can work with a high success probability. We also show that the second-preimage attack can be used to attack the randomized hashing scheme. Finally, we present a key-recovery attack on HMAC-AURORA-512, which reveals 512-bit secret keys with 2257 queries, 2259 AURORA-512 operations, and negligible memory. The universal forgery on HMAC-AURORA-384 is also possible by combining the second-preimage and inner-key-recovery attacks.

This paper evaluates the preimage resistance of the Tiger hash function. To our best knowledge, the maximum number of the attacked steps is 17 among previous preimage attacks on Tiger, where the full version has 24 steps. Our attack will extend the number of the attacked steps to 23. The main contribution is a pseudo-preimage attack on the compression function up to 23 steps with a complexity of 2181 following the meet-in-the-middle approach. This attack can be converted to a preimage attack on 23-step Tiger hash function with a complexity of 2187.5. The memory requirement of our attack is 222 words. A Tiger digest has 192 bits. Therefore, our attacks are faster than the exhaustive search.

In this paper, we present a new cryptanalytic tool that can reduce the complexity of integral analysis against Addition-Rotation-XOR (ARX) based designs. Our technique is based on the partial-sum technique proposed by Ferguson et al. at FSE 2000, which guesses subkeys byte to byte in turn, and the data to be analyzed is compressed for each key guess. In this paper, the technique is extended to ARX based designs. Subkeys are guessed bit by bit, and the data is compressed with respect to the value of the guessed bit position and carry values to the next bit position. We call the technique bitwise partial-sum. We demonstrate this technique by applying it to reduced-round versions of HIGHT, which is one of the ISO standard 64-bit block ciphers. Another contribution of this paper is an independent improvement specific to HIGHT. By exploiting linear computations inside the round function, the number of guessed bits during the key recovery phase can be greatly reduced. Together with the bitwise partial-sum, the integral analysis on HIGHT is extended from previous 22 rounds to 26 rounds, while full HIGHT consists of 32 rounds.

This paper presents key recovery attacks on Sandwich-MAC instantiating MD5, where Sandwich-MAC is an improved variant of HMAC and achieves the same provable security level and better performance especially for short messages. The increased interest in lightweight cryptography motivates us to analyze such a MAC scheme. Our attacks are based on a distinguishing-H attack on HMAC-MD5 proposed by Wang et al. We first improve its complexity from 297 to 289.04. With this improvement, we then propose key recovery attacks on Sandwich-MAC-MD5 by combining various techniques such as distinguishing-H for HMAC-MD5, IV Bridge for APOP, dBB-near-collisions for related-key NMAC-MD5, meet-in-the-middle attack etc. In particular, we generalize a previous key-recovery technique as a new tool exploiting a conditional key-dependent distribution. Surprisingly, a key which is even longer than the tag size can be recovered without the knowledge of the key size. Finally, our attack also improves the previous partial-key (K1) recovery on MD5-MAC, and extends it to recover both of K1 and K2.

In this paper, we present the first results on the preimage resistance against step-reduced versions of ISO standard hash functions RIPEMD-128 and RIPEMD-160, which were designed as strengthened versions of RIPEMD. While preimage attacks on the first 33 steps and intermediate 35 steps of RIPEMD (48 steps in total) are known, no preimage attack exists on RIPEMD-128 (64 steps) or RIPEMD-160 (80 steps). This paper shows three variations of preimage attacks of RIPEMD-128; the first 33 steps, intermediate 35 steps, and the last 32 steps. Because of the large security margin, full RIPEMD-128 is still enough secure, however, it is interesting that the number of attacked steps for RIPEMD-128 reaches the same level as for RIPEMD. We also show that our approach can be applied to RIPEMD-160, and present preimage attacks on the first 30 steps and the last 31 steps.

In this paper, we study a boomerang attack approach on MD4-based hash functions, and present a practical 4-sum distinguisher against the compression function of the full 5-pass HAVAL. Our approach is based on the previous work by Kim et al., which proposed the boomerang distinguisher on the encryption mode of MD4, MD5, and HAVAL in the related-key setting. Firstly, we prove that the differential path for 5-pass HAVAL used in the previous boomerang distinguisher contains a critical flaw and thus the attack cannot work. We then search for new differential paths. Finally, by using the new paths, we mount the distinguisher on the compression function of the full 5-pass HAVAL which generates a 4-sum quartet with a complexity of approximately 211 compression function computations. As far as we know, this is the first result on the full compression function of 5-pass HAVAL that can be computed in practice. We also point out that the 4-sum distinguisher can also be constructed for other MD4-based hash functions such as MD5, 3-pass HAVAL, and 4-pass HAVAL. Our attacks are implemented on a PC and we present a generated 4-sum quartet for each attack target.

We explore ways to optimize online, permutation-based authenticated encryption (AE) schemes for lightweight applications. The lightweight applications demand that AE schemes operate in resource-constrained environments, which raise two issues: 1) implementation costs must be low, and 2) ensuring proper use of a nonce is difficult due to its small size and lack of randomness. Regarding the implementation costs, recently it has been recognized that permutation-based (rather than block-cipher-based) schemes frequently show advantages. However, regarding the security under nonce misuse, the standard permutation-based duplex construction cannot ensure confidentiality. There exists one permutation-based scheme named APE which offers certain robustness against nonce misuse. Unfortunately, the APE construction has several drawbacks such as ciphertext expansion and bidirectional permutation circuits. The ciphertext expansion would require more bandwidth, and the bidirectional circuits would require a larger hardware footprint. In this paper, we propose new constructions of online permutation-based AE that require less bandwidth, a smaller hardware footprint and lower computational costs. We provide security proofs for the new constructions, demonstrating that they are as secure as the APE construction.

In this paper, we present known-key attacks on block cipher Rijndael for 192-bit block and 256-bit block. Our attacks work up to 8 rounds for 192-bit block and 9 rounds for 256-bit block, which are one round longer than the previous best known-key attacks. We then search for the parameters for the ShiftRow operation which is stronger against our attacks than the one in the Rijndael specification. Finally, we show a parameter for 192-bit block which forces attackers to activate more bytes to generate a truncated differential path, and thus enhances the security against our attacks.

HMAC is the most widely used hash based MAC scheme. Recently, several generic attacks have been presented against HMAC with a complexity between 2n/2 and 2n, where n is the output size of an underlying hash function. In this paper, we investigate the security of strengthened HMAC instantiated with a Merkle-Damgård hash function in which the key is used to process underlying compression functions. With such a modification, the attacker is unable to precompute the property of the compression function offline, and thus previous generic attacks are prevented. In this paper, we show that keying the compression function in all blocks is necessary to prevent a generic internal state recovery attack with a complexity less than 2n. In other words, only with a single keyless compression function, the internal state is recovered faster than 2n. To validate the claim, we present a generic attack against the strengthened HMAC instantiated with a Merkle-Damgård hash function in which only one block is keyless, thus pre-computable offline. Our attack uses the previous generic attack by Naito et al. as a base. We improve it so that the attack can be applied only with a single keyless compression function while the attack complexity remains unchanged from the previous work.

We present a new cryptanalysis approach to analyze the security of a class of authenticated encryption schemes, which shares similarity with the previous length extension attack against hash-function-based MACs. Hence we name our approach by message extension attack. For an authenticated encryption from the target class, it consists of three phases; initialization with nonce and key as input, state update function with associated data and message as input and tag generation with updated state as input. We will show how to mount a forgery attack in the nonce-repeating model under the chosen-plaintext scenario, when both state update function and tag generation is built based on the same function. To demonstrate the effectiveness of our message extension attack approach, we apply it to a dedicated authenticated encryption called PANDA, which is a candidate of the ongoing CAESAR cryptographic competition. We successfully found an existential forgery attack on PANDA with 25 chosen plaintexts, 264 computations, and a negligible memory, and it breaks the claimed 128-bit security for the nonce-repeating model. We note that this is the first result that breaks the security claim of PANDA, which makes it withdrawn from the CAESAR competition by its designer.

Even though meet-in-the-middle preimage attack framework has been successfully applied to attack most of narrow-pipe hash functions, it seems difficult to apply this framework to attack double-branch hash functions. Only few results have been published on this research. This paper proposes a refined strategy of applying meet-in-the-middle attack framework to double-branch hash functions. The main novelty is a new local-collision approach named one-message-word local collision. We have applied our strategy to two double-branch hash functions RIPEMD and RIPEMD-128, and obtain the following results.·On RIPEMD. We find a pseudo-preimage attack on 47-step compression function, where the full version has 48 steps, with a complexity of 2119. It can be converted to a second preimage attack on 47-step hash function with a complexity of 2124.5. Moreover, we also improve previous preimage attacks on (intermediate) 35-step RIPEMD, and reduce the complexity from 2113 to 296. ·On RIPEMD-128. We find a pseudo-preimage on (intermediate) 36-step compression function, where the full version has 64 steps, with a complexity of 2123. It canl be converted to a preimage attack on (intermediate) 36-step hash function with a complexity of 2126.5. Both RIPEMD and RIPEMD-128 produce 128-bit digests. Therefore our attacks are faster than the brute-force attack, which means that our attacks break the theoretical security bound of the above step-reduced variants of those two hash functions in the sense of (second) preimage resistance. The maximum number of the attacked steps on both those two hash functions is 35 among previous works based to our best knowledge. Therefore we have successfully increased the number of the attacked steps. We stress that our attacks does not break the security of full-version RIPEMD and RIPEMD-128. But the security mergin of RIPEMD becomes very narrow. On the other hand, RIPEMD-128 still has enough security margin.

We propose preimage attacks against PKC98-Hash and HAS-V. PKC98-Hash is a 160-bit hash function proposed at PKC 1998, and HAS-V, a hash function proposed at SAC 2000, can produce hash values of 128+32k (k=0,1,...,6) bits. These hash functions adopt the Merkle-Damgård and Davies-Meyer constructions. One unique characteristic of these hash functions is that their step functions are not injective with a fixed message. We utilize this property to mount preimage attacks against these hash functions. Note that these attacks can work for an arbitrary number of steps. The best proposed attacks generate preimages of PKC98-Hash and HAS-V-320 in 264 and 2256 compression function computations with negligible memory, respectively. This is the first preimage attack against the full PKC98-Hash function.

We study the security of AES in the open-key setting by showing an analysis on hash function modes instantiating AES including Davies-Meyer, Matyas-Meyer-Oseas, and Miyaguchi-Preneel modes. In particular, we propose preimage attacks on these constructions, while most of previous work focused their attention on collision attacks or distinguishers using non-ideal differential properties. This research is based on the motivation that we should evaluate classical and important security notions for hash functions and avoid complicated attack models that seem to have little relevance in practice. We apply a recently developed meet-in-the-middle preimage approach. As a result, we obtain a preimage attack on 7 rounds of Davies-Meyer AES and a second preimage attack on 7 rounds of Matyas-Meyer-Oseas and Miyaguchi-Preneel AES. Considering that the previous best collision attack only can work up to 6 rounds, the number of attacked rounds reaches the best in terms of the classical security notions. In our attacks, the key is regarded as a known constant, and the attacks thus can work for any key length in common.

We revisit the design of Lesamnta-LW, which is one of the three lightweight hash functions specified in ISO/IEC 29192-5:2016. Firstly, we present some updates on the bounds of the number of active S-boxes for the underlying 64-round block cipher. While the designers showed that the Viterbi algorithm ensured 24 active S-boxes after 24 rounds, our tool based on Mixed Integer Linear Programming (MILP) in the framework of Mouha et al. ensures the same number of active S-boxes only after 18 rounds. The tool completely evaluates the tight bound of the number of active S-boxes, and it shows that the bound is 103 for full (64) rounds. We also analyze security of the Shuffle operation in the round function and resistance against linear cryptanalysis. Secondly, we present a new mode for a pseudorandom function (PRF) based on Lesamnta-LW. It is twice as efficient as the previous PRF modes based on Lesamnta-LW. We prove its security both in the standard model and the ideal cipher model.

At Eurocrypt'05, Wang et al. presented efficient collision attacks on MD5 and MD4 hash functions. They found a collision of MD5 with a complexity of less than 237 MD5 hash operations, and a collision of MD4 with complexity less than 28 MD4 hash operations. In their attack, the procedure to generate a collision is divided into 4 steps. First, they determine the message differential and output differentials of chaining variables in each step, which generates a collision with small complexity. Second, they construct sufficient conditions that guarantee that the desired differential is always calculated. Third, they find a message modification that can satisfy the sufficient conditions with high probability. Finally, they search for a message that satisfies all sufficient conditions. In this paper, we focus on the message modification of MD5 and MD4, and propose a new message modification. Using our message modification, a collision of MD5 can be found with complexity less than 229 MD5 hash operations, and a collision of MD4 can be found with complexity less than 3 MD4 hash operations. To improve the complexity from previous attacks, we mainly use two ideas. The first idea is to use message modification that can satisfy more sufficient conditions in the second round than in previous attacks. The second idea is to use message modification that can enable us to search for a collision starting from an intermediate step.

In this paper, generic attacks are presented against hash functions that are constructed by a hashing mode instantiating a Feistel or generalized Feistel networks with an SP-round function. It is observed that the omission of the network twist in the last round can be a weakness against preimage attacks. The first target is a standard Feistel network with an SP round function. Up to 11 rounds can be attacked in generic if a condition on a key schedule function is satisfied. The second target is a 4-branch type-2 generalized Feistel network with an SP round function. Up to 15 rounds can be attacked in generic. These generic attacks are then applied to hashing modes of ISO standard ciphers Camellia-128 without FL and whitening layers and CLEFIA-128.

The current paper presents an integral cryptanalysis in the single-key setting against light-weight block-cipher LBlock reduced to 22 rounds. Our attack uses the same 15-round integral distinguisher as the previous attacks, but many techniques are taken into consideration in order to achieve comprehensive understanding of the attack; choosing the best balanced-byte position, meet-in-the-middle technique to identify right key candidates, partial-sum technique, relations among subkeys, and combination of the exhaustive search with the integral analysis. Our results indicate that the integral cryptanalysis is particularly useful for LBlock like structures. At the end of this paper, which factor makes the LBlock structure weak against the integral cryptanalysis is discussed. Because designing light-weight cryptographic primitives is an actively discussed topic, we believe that this paper returns some useful feedback to future designs.

In 2005, collision resistance of several hash functions was broken by Wang et al. The strategy of determining message differences is the most important part of collision attacks against hash functions. So far, many researchers have tried to analyze Wang et al.'s method and proposed improved collision attacks. Although several researches proposed improved attacks, all improved results so far were based on the same message differences proposed by Wang et al. In this paper, we propose new message differences for collision attacks on MD4 and MD5. Our message differences of MD4 can generate a collision with complexity of less than two MD4 computations, which is faster than the original Wang et al.'s attack, and moreover, than the all previous attacks. This is the first result that improves the complexity of collision attack by using different message differences from Wang et al.'s. Regarding MD5, so far, no other message difference from Wang et al.'s is known. Therefore, study for constructing method of other message differences on MD5 should be interesting. Our message differences of MD5 generates a collision with complexity of 242 MD5 computations, which is slower than the latest best attack. However, since our attack needs only 1 bit difference, it has some advantages in terms of message freedom of collision messages.