Internal differential collision attacks on the reduced-round Grøstl-0 hash function

We analyze the Grøstl-0 hash function, that is the version of Grøstl submitted to the SHA-3 competition. This paper extends Peyrin’s internal differential strategy, that uses differential paths between the permutations P and Q of Grøstl-0 to construct distinguishers of the compression function. This results in collision attacks and semi-free-start collision attacks on the Grøstl-0 hash function and compression function with reduced rounds. Specifically, we show collision attacks on the Grøstl-0-256 hash function reduced to 5 and 6 out of 10 rounds with time complexities 2⁴⁸ and 2¹¹² and on the Grøstl-0-512 hash function reduced to 6 out of 14 rounds with time complexity 2¹⁸³. Furthermore, we demonstrate semi-free-start collision attacks on the Grøstl-0-256 compression function reduced to 8 rounds and the Grøstl-0-512 compression function reduced to 9 rounds. Finally, we show improved distinguishers for the Grøstl-0-256 permutations with reduced rounds.     

Memoryless near-collisions via coding theory

We investigate generic methods to find near-collisions in cryptographic hash functions. We introduce a new generic approach based on methods to find cycles in the space of codewords of a code with low covering radius. We give an analysis of our approach and demonstrate it on the SHA-3 candidate TIB3.     

Recursive constructions of secure codes and hash families using difference function families

To protect copyrighted digital data against piracy, codes with different secure properties such as frameproof codes, secure frameproof codes, codes with identifiable parent property (IPP codes), traceability codes (TA codes) are introduced. In this paper, we study these codes together with related combinatorial objects called separating and perfect hash families. We introduce for the first time the notion of difference function families and use these difference function families to give generalized recursive techniques that can be used for any kind of secure codes and hash families. We show that some previous recursive techniques are special cases of these new techniques.     

Generic cryptographic weakness of k-normal Boolean functions in certain stream ciphers and cryptanalysis of grain-128

This paper considers security implications of k-normal Boolean functions when they are employed in certain stream ciphers. A generic algorithm is proposed for cryptanalysis of the considered class of stream ciphers based on a security weakness of k-normal Boolean functions. The proposed algorithm yields a framework for mounting cryptanalysis against particular stream ciphers within the considered class. Also, the proposed algorithm for cryptanalysis implies certain design guidelines for avoiding certain weak stream cipher constructions. A particular objective of this paper is security evaluation of stream cipher Grain-128 employing the developed generic algorithm. Contrary to the best known attacks against Grain-128 which provide complexity of a secret key recovery lower than exhaustive search only over a subset of secret keys which is just a fraction (up to 5%) of all possible secret keys, the cryptanalysis proposed in this paper provides significantly lower complexity than exhaustive search for any secret key. The proposed approach for cryptanalysis primarily depends on the order of normality of the employed Boolean function in Grain-128. Accordingly, in addition to the security evaluation insights of Grain-128, the results of this paper are also an evidence of the cryptographic significance of the normality criteria of Boolean functions.     

A fast and efficient chaos-based keyed hash function

This paper proposes a new chaotic keyed hash function based on a single 4-dimensional chaotic cat map whose irregular outputs are used to compute a hash value. The suggested scheme is fast, efficient and flexible. It takes an input message of arbitrary length and returns a hash value of a fixed length n, where n is a multiple of 32 (by convention, n is usually one of the numbers 128, 160, 256, 512, and 1024). Simulation results are presented to demonstrate the suggested hashing scheme’s high sensitivity to the original message and the secret key, as well as its strong capability for confusion and diffusion, and very strong collision resistance. In comparison with existing work, especially those based on chaotic maps, the proposed scheme exhibits superior performance.     

Monitoring kth order runs in binary processes

Procedures for continuously monitoring binary attribute data processes are of utmost relevance for fields like electrical engineering, chemical production, software quality engineering, healthcare monitoring, and many more. In this article, new approaches are proposed, where kth order runs in a binary process are monitored. We derive methods for evaluating the performance of the new control charts, discuss computational issues of these methods and give design recommendations for the control charts. A real-data example demonstrates the successful application of the new control procedures.     

Group theoretic properties of Rijndael-like ciphers

We provide conditions for which the round functions of an ?-bit Rijndael-like block cipher generate the alternating group on the set {0,1}^?. These conditions show that the class of Rijndael-like ciphers whose round functions generate the alternating group on their message space is large, and includes both the actual Rijndael and the block cipher used by the compression function of the Whirlpool hash function. The result indicates that there is no trapdoor design for a Rijndael-like cipher based on the imprimitivity of the group action of its proper round functions which is difficult to detect.     

On the collision and preimage security of MDC-4 in the ideal cipher model

We present a collision and preimage security analysis of MDC-4, a 24-years-old construction for transforming an n-bit block cipher into a 2n-bit hash function. We start with MDC-4 based on one single block cipher, and prove that any adversary with query access to the underlying block cipher requires at least \(2^{5n/8}\) queries (asymptotically) to find a collision. For the preimage resistance, we present a surprising negative result: for a target image with the same left and right half, a preimage for the full MDC-4 hash function can be found in \(2^n\) queries. Yet, restricted to target images with different left and right halves, we prove that at least \(2^{5n/4}\) queries (asymptotically) are required to find a preimage. Next, we consider MDC-4 based on two independent block ciphers, a model that is less general but closer to the original design, and prove that the collision bound of \(2^{5n/8}\) queries and the preimage bound of \(2^{5n/4}\) queries apply to the MDC-4 compression function and hash function design. With these results, we are the first to formally confirm that MDC-4 offers a higher level of provable security compared to MDC-2.     

A compact hash function for paths in PERT networks

This paper presents a method of identifying all directed paths from the source to the sink (called ‘paths’ in this paper) in a directed acyclic network with one source and one sink. Let L be the set of all the paths in this network and N = |L|. A hash function H:L → {0, 1, …, N ? 1} is constructed having the following properties: it is one-to-one and onto, the algorithms to compute H and its inverse are linea in the number of arcs in the network, it has the smallest possible range and produces no collisions. All these properties make it a very useful hash function in writing computer programs which involve storing information about all paths in the network. The techniques described in this paper can be used to construct hash functions for walks in cyclic graphs. An application to simulation of stochastic networks is described and an illustrative example is included.     

The effect of table expansion on the program complexity of perfect hash functions

It has been shown by various researchers that designing a perfect hashing function for a fixed set ofn elements requires (n) bits in the worst case. A possible relaxation of this scheme is to partition the set into pages, and design a hash function which maps keys to page addresses, requiring subsequent binary search of the page. We have shown elsewhere that (nk/2 ^k+1)(1 +o(1)) bits are necessary and sufficient to describe such a hash function where the pages are of size 2 ^k . In this paper we examine the additional scheme of expanding the address space of the table, which does substantially improve the hash function complexity of perfect hashing, and show that in contrast, it does not reduce the hash function complexity of the paging scheme.Research supported by NSF Grant CCR-9017125 and by a grant from Texas Instruments.     

Deletion algorithms for hashing that preserve randomness

This paper studies the problem of finding efficient deletion algorithms for the coalesced hashing method, in which a portion of memory (called the address region) serves as the range of the hash function while the rest of memory (called the cellar) is devoted solely to storing records that collide when inserted. First we present a deletion algorithm, which solves the open problem described in [6, Sect. 6.4–23]. The main result of this paper, Theorem 3, shows that the deletion algorithm preserves randomness for the special case of standard coalesced hashing (when there is no cellar), in that deleting a record is in some sense like never having inserted it. This means that the formulas for the search times (which are analyzed in [8, 9]) are still valid after deletions. There is as yet no known deletion algorithm that preserves randomness for the general case (when there is a cellar). We give some reasons why and then discuss some heuristics that seem to make deletions practical anyway.     

Classification and generation of disturbance vectors for collision attacks against SHA-1

The main contribution of this paper is to provide a classification of disturbance vectors used in differential collision attacks against ${\tt{SHA}-1}$ . We show that all published disturbance vectors can be classified into two types of vectors, type-I and type-II. We present a deterministic algorithm which produce efficient disturbance vectors with respect to any given cost function. We define two simple cost functions to evaluate the efficiency of a candidate disturbance vector. Using our algorithm and those cost function we retrieved all previously known vectors and found that the most efficient disturbance vector is the one first reported as Codeword2 by Jutla and Patthak, A matching lower bound on the minimum weight of SHA-1 expansion code. Cryptology ePrint Archive, Report 2005/266, (2005). We also present a statistical evaluation of local collisions?? holding probabilities and show that the common assumption of local collision independence is flawed.     

On CCZ-equivalence of addition mod 2 n

We show that addition mod 2 ⁿ is CCZ-equivalent to a quadratic vectorial Boolean function. We use this to reduce the solution of systems of differential equations of addition to the solution of an equivalent system of linear equations and to derive a fully explicit formula for the correlation coefficients, which leads to enhanced results about the Walsh transform of addition mod 2 ⁿ . The results have direct applications in the cryptanalysis of cryptographic primitives which use addition mod 2 ⁿ .     

An improvement of chaos-based hash function in cryptanalysis approach: An experience with chaotic neural networks and semi-collision attack

In this paper, the chaos-based hash function is analyzed, then an improved version of chaos-based hash function is presented and discussed using chaotic neural networks. It is based on the piecewise linear chaotic map that is used as a transfer function in the input and output of the neural network layer. The security of the improved hash function is also discussed and a novel type of collision resistant hash function called semi-collision attack is proposed, which is based on the collision percentage between the two hash values. In the proposed attack particle swarm optimization algorithm is used to define the fitness function parameters. Finally, numerical and simulation results provides strong collision resistance and high performance efficiency.     

On the complexity of the herding attack and some related attacks on hash functions

In this article, we analyze the complexity of the construction of the 2 ^k -diamond structure proposed by Kelsey and Kohno (LNCS, Vol 4004, pp 183–200, 2006). We point out a flaw in their analysis and show that their construction may not produce the desired diamond structure. We then give a more rigorous and detailed complexity analysis of the construction of a diamond structure. For this, we appeal to random graph theory (in particular, to the theory of random intersection graphs), which allows us to determine sharp necessary and sufficient conditions for the message complexity (i.e., the number of hash computations required to build the required structure). We also analyze the computational complexity for constructing a diamond structure, which has not been previously studied in the literature. Finally, we study the impact of our analysis on herding and other attacks that use the diamond structure as a subroutine. Precisely, our results shows the following:

1. The message complexity for the construction of a diamond structure is ${\sqrt{k}}$ times more than the amount previously stated in literature.

1. The time complexity is n times the message complexity, where n is the size of hash value.

Due to the above two results, the herding attack (Kelsey and Kohno, LNCS, Vol 4004, pp 183–200, 2006) and the second preimage attack (Andreeva et?al., LNCS, Vol 4965, pp 270–288, 2008) on iterated hash functions have increased complexity. We also show that the message complexity of herding and second preimage attacks on “hash twice” is n times the complexity claimed by Andreeva et?al. (LNCS, Vol 5867, pp 393–414, 2009), by giving a more detailed analysis of the attack.     

Md2 is not Secure Without the Checksum Byte

In 1989, Ron Rivest introduced the MD2 Message Digest Algorithm which takes as input a message of arbitrary length and produces as output a 128-bit message digest, by appending some redundancy to the message and then iteratively applying a 32 bytes to 16 bytes compression function. MD2 Message Digest Algorithm is one of the most frequently used hashing function with MD4, MD5, SHA, SHA-1. Some attacks against MD4 and MD5 have been presented by Dobbertin. Up to now, no attack against MD2 has been presented.This function has been updated in 1993 in the RFC 1423 document. It was conjectured that the number of operations needed to get two messages having the same message digest is on the order of 2⁶⁴ (using the birthday paradox), and that the complexity of inverting the hash function is on the order of 2¹²⁸ operations. No attack against this function has been published so far. In this paper, we propose a low complexity method to find collisions for the compression function of MD2. The easiness to find these collisions could imply that the first conjecture is false if these collisions can be used to make global collisions for MD2.     

Linear hulls with correlation zero and linear cryptanalysis of block ciphers

Linear cryptanalysis, along with differential cryptanalysis, is an important tool to evaluate the security of block ciphers. This work introduces a novel extension of linear cryptanalysis: zero-correlation linear cryptanalysis, a technique applicable to many block cipher constructions. It is based on linear approximations with a correlation value of exactly zero. For a permutation on n bits, an algorithm of complexity 2 ^n-1 is proposed for the exact evaluation of correlation. Non-trivial zero-correlation linear approximations are demonstrated for various block cipher structures including AES, balanced Feistel networks, Skipjack, CLEFIA, and CAST256. As an example, using the zero-correlation linear cryptanalysis, a key-recovery attack is shown on 6 rounds of AES-192 and AES-256 as well as 13 rounds of CLEFIA-256.     

Collision analysis of a chaos-based hash function with both modification detection and localization capability

The collision problem of a chaos-based hash function with both modification detection and localization capability is investigated [Xiao D, Shih FY, Liao XF. A chaos-based hash function with both modification detection and localization capabilities. Commun Nonlinear Sci Numer Simulat 2010;15(9):2254-61]. The simulation gives the same detection and localization hash values for distinct messages. The expense of the birthday attack on the hash function is far less than expected. The certain symmetries of message distribution may result in the same detection hash value for distinct messages.     

Universal hashing and authentication codes

In this paper, we study the application of universal hashing to the construction of unconditionally secure authentication codes without secrecy. This idea is most useful when the number of authenticators is exponentially small compared to the number of possible source states (plaintext messages). We formally define some new classes of hash functions and then prove some new bounds and give some general constructions for these classes of hash functions. Then we discuss the implications to authentication codes.A preliminary version of this paper was presented at CRYPTO '91 and appeared in Lecture Notes in Computer Science, vol. 576, pp. 74–85, Springer-Verlag, 1992.     

Optimal implementation of selectors in a data-base

The records of a data base can be accessed from other records or from a set of data items (inverted access, primary and secondary index of IMS, search keys of CODASYL etc.) which we call selectors. The implementation of this selectors can use different techniques as hash coding, inverted lists or hierarchical index (indexed sequential, B-trees etc…) We consider here the last one and we search for a given set of selectors an optimal index structure. We show how this problem can be put as the search of an optimal rooted tree among the partial subgraphs of a given graph G (this problem is known in graph theory as Steiner problem) and we give several properties which allow the graph G to be notabily reduced. Then we present a branch and bound algorithm to solve this problem.