Hash-and-Sign with Weak Hashing Made Secure

Digital signatures are often proven to be secure in the random oracle model while hash functions deviate more and more from this idealization. Liskov proposed to model a weak hash function by a random oracle together with another oracle allowing to break some properties of the hash function, e.g. a preimage oracle. To avoid the need for collision-resistance, Bellare and Rogaway proposed to use target collision resistant (TCR) randomized pre-hashing. Later, Halevi and Krawczyk suggested to use enhanced TCR (eTCR) hashing to avoid signing the random seed. To avoid the increase in signature length in the TCR construction, Mironov suggested to recycle some signing coins in the message preprocessing. In this paper, we develop and apply all those techniques. In particular, we obtain a generic preprocessing which allows to build strongly secure signature schemes when hashing is weak and the internal (textbook) signature is weakly secure. We model weak hashing by a preimage-tractable random oracle.

Secure communication using authenticated channels

Sylvain Pasini

Our main motivation is to design more user-friendly security protocols. Indeed, if the use of the protocol is tedious, most users will not behave correctly and, consequently, security issues occur. An example is the actual behavior of a user in front of an SSH certificate validation: while this task is of utmost importance, about 99% of SSH users accept the received certificate without checking it. Designing more user-friendly protocols may be difficult since the security should not decrease at the same time. Interestingly, insecure channels coexist with channels ensuring authentication. In practice, these latters may be used for a string comparison or a string copy, e.g., by voice over IP spelling. The shorter the authenticated string is, the less human interaction the protocol requires, and the more user-friendly the protocol is. This leads to the notion of SAS-based cryptography, where SAS stands for Short Authenticated String. In the first part of this thesis, we analyze and propose optimal SAS-based message authentication protocols. By using these protocols, we show how to construct optimal SAS-based authenticated key agreements. Such a protocol enables any group of users to agree on a shared secret key. SAS-based cryptography requires no pre-shared key, no trusted third party, and no public-key infrastructure. However, it requires the user to exchange a short SAS, e.g., five decimal digits. By using the just agreed secret key, the group can now achieve a secure communication based on symmetric cryptography. SAS-based authentication protocols are often used to authenticate the protocol messages of a key agreement. Hence, each new secure communication requires the interaction of the users to agree on the SAS. A solution to reduce the user interaction is to use digital signature schemes. Indeed, in a setup phase, the users can use a SAS-based authentication protocol to exchange long-term verification keys. Then, using digital signatures, users are able to run several key agreements and the authentication of protocol messages is done by digital signatures. In the case where no authenticated channel is available, but a public-key infrastructure is in place, the SAS-based setup phase is avoided since verification keys are already authenticated by the infrastructure. In the second part of this thesis, we also study two problems related to digital signatures: (1) the insecurity of digital signature schemes which use weak hash functions and (2) the privacy issues from signed documents. Digital signatures are often proven to be secure in the random oracle model. The role of random oracles is to model ideal hash functions. However, real hash functions deviate more and more from this idealization. Indeed, weaknesses on hash functions have already been discovered and we are expecting new ones. A question is how to fix the existing signature constructions based on these weak hash functions. In this thesis, we first try to find a better way to model weak hash function. Then, we propose a (randomized) pre-processing to the input message which transforms any weak signature implementation into a strong signature scheme. There remains one drawback due to the randomization. Indeed, the random coins must be sent and thus the signature enlarges. We also propose a method to avoid the increase in signature length by reusing signing coins. Digital signatures may also lead to privacy issues. Indeed, given a message and its signature, anyone can publish the pair which will confirm the authenticity of the message. In certain applications, like in electronic passports (e-passports), publishing the authenticated data leads to serious privacy issues. In this thesis, we define the required security properties in order to protect the data privacy, especially in the case of e-passport verification. The main idea consists for the e-passport to keep the signature secret. The e-passport should only prove that it knows a valid signature instead of revealing it. We propose a new primitive, called Offline Non-Transferable Authentication Protocol (ONTAP), as well as efficient implementations that are compatible with the e-passport standard signature schemes.

EPFL2009

An Analysis of the Blockcipher-Based Hash Functions from PGV

Martijn Stam

Preneel, Govaerts, and Vandewalle (1993) considered the 64 most basic ways to construct a hash function H: {0, 1}*->{0, 1}(n) from a blockcipher E: {0, 1}(n) x {0, 1}(n)->{0,1}(n). They regarded 12 of these 64 schemes as secure, though no proofs or formal claims were given. Here we provide a proof-based treatment of the PGV schemes. We show that, in the ideal-cipher model, the 12 schemes considered secure by PGV really are secure: we give tight upper and lower bounds on their collision resistance. Furthermore, by stepping outside of the Merkle-Damgard approach to analysis, we show that an additional 8 of the PGV schemes are just as collision resistant (up to a constant). Nonetheless, we are able to differentiate among the 20 collision-resistant schemes by considering their preimage resistance: only the 12 initial schemes enjoy optimal preimage resistance. Our work demonstrates that proving ideal-cipher-model bounds is a feasible and useful step for understanding the security of blockcipher-based hash-function constructions.

Springer Verlag2010

Cryptographic Hash Functions in Groups and Provable Properties

Juraj Sarinay

We consider several "provably secure" hash functions that compute simple sums in a well chosen group (G,*). Security properties of such functions provably translate in a natural way to computational problems in G that are simple to define and possibly also hard to solve. Given k disjoint lists Li of group elements, the k-sum problem asks for gi ∊ Li such that g1 * g2 ... gk = 1G. Hardness of the problem in the respective groups follows from some "standard" assumptions used in public-key cryptology such as hardness of integer factoring, discrete logarithms, lattice reduction and syndrome decoding. We point out evidence that the k-sum problem may even be harder than the above problems. Two hash functions based on the group k-sum problem, SWIFFTX and FSB, were submitted to NIST as candidates for the future SHA-3 standard. Both submissions were supported by some sort of a security proof. We show that the assessment of security levels provided in the proposals is not related to the proofs included. The main claims on security are supported exclusively by considerations about available attacks. By introducing "second-order" bounds on bounds on security, we expose the limits of such an approach to provable security. A problem with the way security is quantified does not necessarily mean a problem with security itself. Although FSB does have a history of failures, recent versions of the two above functions have resisted cryptanalytic efforts well. This evidence, as well as the several connections to more standard problems, suggests that the k-sum problem in some groups may be considered hard on its own, and possibly lead to provable bounds on security. Complexity of the non-trivial tree algorithm is becoming a standard tool for measuring the associated hardness. We propose modifications to the multiplicative Very Smooth Hash and derive security from multiplicative k-sums in contrast to the original reductions that related to factoring or discrete logarithms. Although the original reductions remain valid, we measure security in a new, more aggressive way. This allows us to relax the parameters and hash faster. We obtain a function that is only three times slower compared to SHA-256 and is estimated to offer at least equivalent collision resistance. The speed can be doubled by the use of a special modulus, such a modified function is supported exclusively by the hardness of multiplicative k-sums modulo a power of two. Our efforts culminate in a new multiplicative k-sum function in finite fields that further generalizes the design of Very Smooth Hash. In contrast to the previous variants, the memory requirements of the new function are negligible. The fastest instance of the function expected to offer 128-bit collision resistance runs at 24 cycles per byte on an Intel Core i7 processor and approaches the 17.4 figure of SHA-256. The new functions proposed in this thesis do not provably achieve a usual security property such as preimage or collision resistance from a well-established assumption. They do however enjoy unconditional provable separation of inputs that collide. Changes in input that are small with respect to a well defined measure never lead to identical output in the compression function.