People.irisa.fr

Christophe Petit, Nicolas Veyrat-Charvillon, Jean-Jacques Quisquater christophe.petit,nicolas.veyrat, jjq@uclouvain.be Recent breakthroughs concerning the current standard SHA-1 prompted NISTto launch a competition for a new secure hash algorithm [1, 13]. Provably securehash functions (in the sense that their security relates to the hardness of somemathematical problems [5, 7, 9, 12]) are particularly interesting from a theoreticalpoint of view but are often much slower than heuristic functions like SHA.
In this paper, we consider a variant of ZT hash, a provably secure hash func-tion designed by Z´ emor and Tillich proposed in 1994 [12]. Despite some attack proposals, its security has not been fundamentally challenged to this day. Ourfunction is twice as fast as ZT hash and has enhanced security properties. Wepropose optimized parameters and algorithms to increase the speed of both hashfunctions. This makes our function one of the most efficient “provably secure”hash functions to this day. Finally, we show that our hash function successfullypasses most pseudo-randomness tests in the Dieharder suite [2].
Hash functions are widely used in cryptographic applications such as commitmentschemes, digital signature schemes, key derivation, message authentication codes orpassword encryption. Typical properties required for a hash function are: • preimage resistance : it must be computationally hard to find a preimage to a • collision resistance : it must be computationally hard to find two messages hash- Additionally, a hash function is often required to behave indistinguishably from arandom function.
The SHA family has spread since its publication in 1993 as a cryptographic hash standard [3]. However, recently discovered vulnerabilities in SHA-1 [13] promptedNIST to launch a competition for a New Cryptographic Hash Algorithm [1].
NIST competition is stimulating research on hash functions in the cryptographic community and a lot of new schemes have recently been designed and put forward.
Particularly interesting from a theoretical point of view, some of these schemes areprovably secure, in the sense that their security relies on the hardness of some mathe-matical problems [5, 7, 9, 12]. A good reduction to a simply formulated mathematical challenge facilitates the evaluation process and increases the confidence once the func-tion has resisted first cryptanalytic attempts. However, it also gives the cryptanalyst alead on how to break the scheme, especially when the mathematical problem involvedhas not been studied for years or even decades. Indeed, the LPS hash presented in [5]is now completely broken [10, 14].
In this paper, we consider a variant of ZT hash, a provably secure hash function emor and Tillich at CRYPTO’94 [12]. Since 1994, a few attacks have been presented against ZT hash [4, 6, 8, 11]. Although these attacks are either unpracticalor targeting particular weak parameters, they still lead to a lack of confidence in thefunction. The ZT hash has been forgotten for more than ten years, until it recentlyregained interest due to the LPS hash proposal [5].
Indeed, the design principles of ZT and LPS hashes are very similar. The input messages are decomposed into bits or k-its, and a walk is performed in some regular(Cayley) graph according to the k-its, the hash value being the last vertex reached bythe walk. The security of both functions can be expressed both in algebraic form and interms of some properties of the corresponding graphs. LPS and ZT hashes only differin the graphs that are used, but as the attacks discovered in [10, 14] exploit structuralproperties specific to LPS graphs, they do not seem to generalize to ZT hashes. Today,14 years after its publication, the collision and preimage resistance of the Z´ hash function has not been significantly broken.
Besides its positive security properties, ZT hash has two major weaknesses com- pared to classical hash functions like SHA: first, it is inherently malleable, i.e. the hashvalues of related messages are also related, and second, it is actually not preimage re-sistant when the images of short messages are considered. The variant we propose isaimed to solve these problems and to be twice as fast.
emor and Tillich in their paper [12], the arithmetic of the ZT hash function operates in a field of characteristic 2, hence it is efficient in both software andhardware. However and to the best of our knowledge, no running times for an actualimplementation of ZT hash has been given so far. Here, we present computational opti-mizations for our variant, including a careful choice of the parameters and appropriatedata paths, and give running time results. These optimizations allow us to reduce thecomputation time to less than 25 times the one for SHA-256. We point out that ouroptimizations are fully applicable to the original ZT hash that will however be twiceas slow.
Cryptographic hash functions have been used for key derivation: assuming it be- haves indistinguishably from a random function, a hash function is used to derive manyuncorrelated subkeys from a single seed key. Using a malleable hash function like theZT hash in this application might create serious security threats. In order to certifythe use of our variant for this application, we tested its pseudo-randomness using theDieharder battery of tests [2]. Our variant passes these tests.
This paper is organized as follows. In Sections 2 and 3, we remind Z´ hash function and present our variant. In Section 4, we describe an implementationof our construction and the algorithmic tricks we use to improve its efficiency. Section5 discusses the pseudo-randomness of our construction and Section 6 concludes anddiscusses work in progress and future improvements of our work.
emor-Tillich hash function, following [12]. Let m = m1m2.mk be the bit string representation of the message to be hashed. Let Pn(X) be an ir- reducible polynomial of degree n and let F2n = F2/(Pn(X)). Let A0 and A1 be the The hashcode of m is just the matrix product where the arithmetic is made modulo Pn(X), that is in the field F2n. For a message m of length k, computing hZT (m) seems to require k matrix-by-matrix multiplicationsbut multiplying by A0 or A1 can actually be done with only a few SHIFT and XOR The security of ZT hash can be related to both algebraic and graph-theoretical problems that we will not detail here [5, 12]. Existing attacks against the ZT hashfunction are either unpractical, giving long messages at the price of discrete logarithmcomputations in F22n [8], or targeting particular weak parameters [6, 11]. The largest binary field where discrete logarithms have been computed is F2607, but as the colli- sions produced in [8] have expected length 2 practical even for n ≈ 128. In particular in the rest of the paper we will considern = 127, 251, 509, 1021 and 2039 that are safe with respect to the attacks developedin [6, 11].
Although fundamentally unbroken in the sense of preimage and collision resistance, emor-Tillich hash function has two main security problems: it is malleable in a sense we will explain below, and it is invertible when short messages are hashed.
The malleability property directly results from the design strategy of dealing with themessage bits one after the other. Given the hash h(m) of an unknown message m, thehash value of any message x1||m||x2 can easily be computed.
The invertibility for short messages was observed in [11]. When the message size k is smaller than n, no polynomial reduction is performed. The hash value has the form depending on whether the last message bit is 0 or 1 (the subscript indices are the degreesof the polynomials). Consequently, an adversary can easily recover the message bitsone by one.
For particular polynomials with very sparse coefficients (like the polynomials in Figure 1), the polynomial reductions change very few bits. For such polynomials weobserved that the hash values of large messages (up to a few times n-length) with longsequences of bits 0 also have long sequences of bits 0, an artifact that can be seen bothas an additional malleability or as invertibility of larger message sets.
None of these weaknesses contradicts the preimage nor the collision resistance prop- erty, because the formal definition of preimage resistance only requires the function tobe computationally non-invertible on randomly chosen inputs. However, ZT hash cancertainly not be used for some important applications of hash functions that require agood random function. The variant of ZT hash that we present now solves the securityproblems of the original function.
We propose to use the following hash function: where hvec(m) is the concatenation of the entries (1, 1) and (1, 2) of h the same parameters n and Pn(X), and σ : {0, .22n − 1} → {0, .22n − 1} : x →x ⊕ c. The parameter c is some fixed constant whose bits “look like random”; in ourimplementations c is the binary representation of pi.
The function hvec(m) corresponds to the first row of h puted one bit at a time like hZT (m), and each matrix-by-matrix multiplication isnow replaced by a vector-by-matrix multiplication that is twice as fast. The func-tion σ is of course very efficient.
The second instance of hvec, namely computing (m))), only requires 2n additional vector- by-matrices multiplications for the bits of σ(hvec(m)). It is thus negligible for long Like the original ZT hash, our variant can be related to both algebraic and graph- theoretical problems, which are very close and partially equivalent to the original prob-lems. We now argue on its non-malleability and its preimage resistance even for shortmessages.
emor-Tillich hash function, the preimage problem is easy for messages of length k < n because in that case no polynomial reduction is done, an effect amplifiedfor particular polynomials like those of Figure 1. However, the preimage problem forZT hash is still believed to be hard if the input space is not restricted to some particularmessage sets. Thanks to the function σ, the bit string that is the input of the secondinstance of hvec does not belong to a weak preimage set. Consequently, it cannot be inverted and neither can the whole function.
Now, consider a simple malleability issue present in both hZT and hvec, that is a relation between the hash values of m and m = m||0: Consider H(m) = hvec(m||σ(hvec(m))). Although they are strongly correlated, the hash values hvec(m) and hvec(m ) will differ in many bits in general, so σ(hvec(m)) and σ(hvec(m )) will differ in many bits and H(m) and H(m ) will be completely uncorrelated. Of course some particular values (m, m ) such that hvec(m) and hvec(m ) are very close, for example differ by only the last bit, but finding such a pair withoutinverting hvec already seems a hard problem. Moreover, any such m and m will differ in many bits, so again H(m) and H(m ) will be completely uncorrelated.
Considering more elaborated malleability relations involving for example the hash values of more than one message, leads to the same conclusion: the hash function Hdoes not suffer from apparent malleability properties.
We now show how to efficiently compute our function. We point out that all theoptimized parameters and algorithms we give are also applicable to the original ZThash.
The computational time of our hash function can be characterized as follows X2039 + X10 + X9 + X8 + X7 + X5 + X4 + X2 + 1 Figure 1: Irreducible polynomials that allow cheap modular reductions where ti is the time needed to multiply by Ai and ki(m) is the number of bits i inm||σ(hvec(m)). Clearly t (a, b)A0 = (aX + b, a),(a, b)A1 = (aX + b, aX + a + b), so multiplying by A0 requires one multiplication by X and one addition in the fieldF2n while multiplying by A1 requires one addition more.
The arithmetic is in a field of characteristic 2 and is thus very efficient. In our C implementation on a 32-bit processor, we represent an element a = an−1Xn−1 +an−2Xn−2 + .a1X + a0 as an array A of L := architectures). An addition requires only L XORs, and a multiplication a by X requires L SHIFTs and a polynomial modular reduction. The operations aX + b and aX + a can be performed with L SXORs and a modular reduction.
In general a polynomial reduction would cost one TEST and L XORs, but for the well-chosen parameters of Figure 1 we reduce this cost to a TEST instruction and twoXORs. For example, reducing by X1021 + X5 + X2 + X + 1 amounts to testing whether A[31] ∧ 20000000h is equal to 0, and if not to compute A[31] = A[31] ⊕ 20000000h andA[0] = A[0] ⊕ 27h. For long messages, the TEST instruction will return 1 half of the t1 = L(tXOR + tSXOR) + tXOR + tT EST + C1 where C0 and C1 are constant times needed to call the functions.
We obtain additional speedup by grouping the computation of consecutive message (a, b)A0A0 = (aX2 + bX + a, aX + b),(a, b)A0A1 = (aX2 + bX + a, aX2 + aX + bX + a + b),(a, b)A1A0 = (aX2 + aX + bX + a + b, aX + b),(a, b)A1A1 = (aX2 + aX + bX + a + b, aX2 + bX + a).
The last product can be computed by computing first aX + b, then (aX + b)X + a =aX2 + bX + a and finally (aX2 + bX + a) + (aX + b). The cost of this sequence ofinstructions is at most t11 = L(tXOR + 2tSXOR) + 2tXOR + 2tT EST + C11 Figure 2: Running time (seconds) of different algorithms for H with different parame-ters Figure 3: Running time (seconds) for the SHA family which is about 25% smaller than 2t1. We generalized this approach to more matrixgroupings with the help of a computer program. More specifically, we wrote a Mapleprogram that • Computes the vector-by-matrices product; • Looks for the best data paths with respect to the operations a → aX, (a, b) → • Selects the very best data path according to an optimization function includ- ing the computation times of individual operations and the number of registersneeded in a C implementation; • Writes a C code computing the products.
The running time results for our function and SHA are shown at Figure 2 and 3.
All tests were performed on an 32-bit intel Q6600 quad processor running at 2.4 GHz,with 2Go DDR2 Ram. The OS is Ubuntu running kernel 2.6.24. Test vectors forperformance evaluation were 500Mo random files generated using /dev/urandom.
The performances of our function should be further improved by using the multime- dia sets of instructions available on processors. The computation time is linear in theword size in the processor, so it should be roughly halved on a 64-bit word computer(SHA-512 should also run faster).
We now show that our hash function can be used to generate good sequences of pseudo-random numbers. More specifically, we consider the bitstring sequences s2(H) = H(0)||H(H(0))||H(3)(0)||.H(10000)(0) for H = hvec, H = H, and give them as inputs to the Dieharder battery of tests of Results for hvec exhibit a high correlation in the outputs, with a Chi square distri- bution exceeded only 0.01% of the time by a random value, for all the polynomials ofFigure 1.
H seems to behave undistinguishibly from a random stream, as it passes successfully all tests in the Dieharder suite, and exhibits good Chi square distribution results, withvalues exceeded between 25 and 90% of the time.
In this paper, we present a new provable cryptographic hash function that is twiceas fast as Z´ emor and Tillich hash function and has enhanced security properties. We proposed optimal parameters and algorithms for both ZT hash and our construction,and analyzed the pseudo-randomness properties of our function. A careful implemen-tation of the hash function allows for performances within a factor 23 of SHA-256 foran equivalent level of security (127 bit polynomial), and only 6.5 for SHA-512 (251bit polynomial). Our hashing scheme H passes all tests in the ent and Dieharder testsuites without exhibiting any particular behavior.
Our function is very efficient (for a “provably secure” hash function) because it uses the arithmetic of a binary field, but it is still slow for large parameters as intermediaryresults have to be stored in large integer arrays. In a future work, we will investigatehow MMX instructions can partially solve this problem in software.
implement the function on an FPGA, for which we expect a throughput of 800M b/sfor 1024-bit parameters, only one half of the very best SHA-2 implementation. Finally,the provable security aspects of our construction will be presented in an oncomingpaper.
Part of this work is supported by Belgian Interuniversity Attraction Pole P6/26 BCRYPT.
Christophe Petit is a research fellow F.R.S.-F.N.R.S. at UCL Crypto group, Univer-sit´ e catholique de Louvain. Nicolas Veyrat-Charvillon is a post-doctoral fellow at UCL e catholique de Louvain, supported by the Translogistic project [1] http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Nov07.pdf.
[2] Dieharder. http://www.phy.duke.edu/ rgb/General/dieharder.php.
[3] FIPS 180-2 secure hash standard.
[4] K. S. Abdukhalikov and C. Kim. On the security of the hashing scheme based on SL2. In FSE ’98: Proceedings of the 5th International Workshop on Fast SoftwareEncryption, pages 93–102, London, UK, 1998. Springer-Verlag.
[5] D. X. Charles, E. Z. Goren, and K. E. Lauter. Cryptographic hash functions from expander graphs. To appear in Journal of Cryptology.
[6] C. Charnes and J. Pieprzyk. Attacking the SL2 hashing scheme. In ASIACRYPT ’94: Proceedings of the 4th International Conference on the Theory and Applica-tions of Cryptology, pages 322–330, London, UK, 1995. Springer-Verlag.
[7] S. Contini, A. K. Lenstra, and R. Steinfeld.
collision-resistant hash function. In S. Vaudenay, editor, EUROCRYPT, volume4004 of Lecture Notes in Computer Science, pages 165–182. Springer, 2006.
[8] W. Geiselmann. A note on the hash function of Tillich and Z´ [9] V. Lyubashevsky, D. Micciancio, C. Peikert, and A. Rosen. Provably secure FFT hashing. In NIST 2nd Cryptogaphic Hash Workshop, 2006.
[10] C. Petit, K. E. Lauter, and J.-J. Quisquater. Full cryptanalysis of LPS and Mor- genstern hash functions. Preprint, 2008.
[11] R. Steinwandt, M. Grassl, W. Geiselmann, and T. Beth.
SL2(F2n) hashing scheme. In Proceedings of Advances in Cryptology - CRYPTO 2000: 20th Annual International Cryptology Conference, 2000.
emor. Hashing with SL2. In Y. Desmedt, editor, CRYPTO, volume 839 of Lecture Notes in Computer Science, pages 40–49. Springer, 1994.
[13] X. Wang, Y. L. Yin, and H. Yu. Finding collisions in the full SHA-1. In V. Shoup, editor, CRYPTO, volume 3621 of Lecture Notes in Computer Science, pages 17–36.
Springer, 2005.
emor and J.-P. Tillich. Collisions for the LPS expander graph hash function.
To appear in the proceedings of Advances in Cryptology - EUROCRYPT 2008,2008.

Source: http://people.irisa.fr/Nicolas.Veyrat-Charvillon/files/articles/ICECS_2008.pdf