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.

This paper shows a known-key distinguisher on the internal block cipher of tweaked Lesamnta reduced to 31 (out of 32) rounds, which is one of the hash functions submitted to the SHA-3 competition. Moreover, the paper presents a distinguisher for full internal block cipher of Lesamnta with stronger assumption. For its tweaked version, all previous cryptanalysis can work no more than 24 rounds. We search for a new integral characteristic for the internal block cipher, and discover a 19-round integral characteristic for forward direction. We then search for an integral characteristic for backward direction, and the characteristics can be combined to full rounds with some assumption. The distinguisher for the internal block cipher of Lesamnta-256 requires 2192 query complexity and negligible memory. This is the best attack on Lesamnta compression function and its internal block cipher after the tweak.

In this paper, we propose password recovery attacks against challenge-response authentication protocols. Our attacks use a message difference for a MD5 collision attack proposed in IEICE 2008. First, we show how to efficiently find a message pair that collides with the above message difference. Second, we show that a password used in authenticated post office protocol (APOP) can be recovered practically. We also show that the password recovery attack can be applied to a session initiation protocol (SIP) and digest authentication. Our attack can recover up to the first 31 password characters in a short time and up to the first 60 characters faster than the naive search method. We have implemented our attack and confirmed that 31 characters can be successfully recovered.

This paper proposes a new algorithm for evaluating the number of chaining variable conditions (CVCs) in the selecting step of a disturbance vector (DV) for the analysis of SHA-1 collision search. The algorithm is constructed by combining four strategies, that can evaluate the number of CVCs more strictly compared with the previous approach. By using our method, we found some DVs that have 57 (or 59) essential CVCs for 1st (or 2nd) block in the case if we assume that we can modify messages up to step 25, which we have not confirmed the practicability of the assumption.

This paper presents two types of cryptanalysis on a Merkle-Damgård hash based MAC, which computes a MAC value of a message M by Hash(K||l||M) with a shared key K and the message length l. This construction is often called LPMAC. Firstly, we present a distinguishing-H attack against LPMAC instantiated with any narrow-pipe Merkle-Damgård hash function with O(2n/2) queries, which indicates the incorrectness of the widely believed assumption that LPMAC instantiated with a secure hash function should resist the distinguishing-H attack up to 2n queries. In fact, all of the previous distinguishing-H attacks considered dedicated attacks depending on the underlying hash algorithm, and most of the cases, reduced rounds were attacked with a complexity between 2n/2 and 2n. Because it works in generic, our attack updates these results, namely full rounds are attacked with O(2n/2) complexity. Secondly, we show that an even stronger attack, which is a powerful form of an almost universal forgery attack, can be performed on LPMAC. In this setting, attackers can modify the first several message-blocks of a given message and aim to recover an internal state and forge the MAC value. For any narrow-pipe Merkle-Damgård hash function, our attack can be performed with O(2n/2) queries. These results show that the length prepending scheme is not enough to achieve a secure MAC.

This paper presents differential-based distinguishers against double-branch compression functions and applies them to ISO standard hash functions RIPEMD-128 and RIPEMD-160. A double-branch compression function computes two branch functions to update a chaining variable and then merges their outputs. For such a compression function, we observe that second-order differential paths will be constructed by finding a sub-path in each branch independently. This leads to 4-sum attacks on 47 steps (out of 64 steps) of RIPEMD-128 and 40 steps (out of 80 steps) of RIPEMD-160. Then new properties called a (partial) 2-dimension sum and a q-multi-second-order collision are considered. The partial 2-dimension sum is generated on 48 steps of RIPEMD-128 and 42 steps of RIPEMD-160, with complexities of 235 and 236, respectively. Theoretically, the 2-dimension sum is generated faster than the brute force attack up to 52 steps of RIPEMD-128 and 51 steps of RIPEMD-160, with complexities of 2101 and 2158, respectively. The results on RIPEMD-128 can also be viewed as q-multi-second-order collision attacks. The practical attacks have been implemented and examples are presented. We stress that our results do not impact to the security of full RIPEMD-128 and RIPEMD-160 hash functions.

SIMON is a lightweight block cipher designed by NSA in 2013. NSA presented the specification and the implementation efficiency, but they did not provide detailed security analysis nor the design rationale. The original SIMON has rotation constants of (1,8,2), and Kölbl et al. regarded the constants as a parameter (a,b,c), and analyzed the security of SIMON block cipher variants against differential and linear attacks for all the choices of (a,b,c). This paper complements the result of Kölbl et al. by considering integral and impossible differential attacks. First, we search the number of rounds of integral distinguishers by using a supercomputer. Our search algorithm follows the previous approach by Wang et al., however, we introduce a new choice of the set of plaintexts satisfying the integral property. We show that the new choice indeed extends the number of rounds for several parameters. We also search the number of rounds of impossible differential characteristics based on the miss-in-the-middle approach. Finally, we make a comparison of all parameters from our results and the observations by Kölbl et al. Interesting observations are obtained, for instance we find that the optimal parameters with respect to the resistance against differential attacks are not stronger than the original parameter with respect to integral and impossible differential attacks. Furthermore, we consider the security against differential attacks by considering differentials. From the result, we obtain a parameter that is potential to be better than the original parameter with respect to security against these four attacks.

In this paper, we present practical password recovery attacks against two challenge and response authentication protocols using MD4. For attacks on protocols, the number of queries is one of the most important factors because the opportunity where an attacker can ask queries is very limited in real protocols. When responses are computed as MD4(Password||Challenge), which is called prefix approach, previous work needs to ask 237 queries to recover a password. Asking 237 queries in real protocols is almost impossible. In our attack, to recover up to 8-octet passwords, we only need 1 time the amount of eavesdropping, 17 queries, and 234 MD4 off-line computations. To recover up to 12-octet passwords, we only need 210 times the amount of eavesdropping, 210 queries, and 241 off-line MD4 computations. When responses are computed as MD4(Password||Challenge||Password), which is called hybrid approach, previous work needs to ask 263 queries, while in our attack, up to 8-octet passwords are practically recovered by 28 times the amount of eavesdropping, 28 queries, and 239 off-line MD4 computations. Our idea is guessing a part of passwords so that we can simulate values of intermediate chaining variables from observed hash values. This enables us to use a short local collision that occurs with a very high probability, and thus the number of queries becomes practical.

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.