Preuve de sécurité | EPFL Graph Search

En cryptographie, une preuve de sécurité est la preuve qu'un ensemble d’algorithmes cryptographiques (aussi appelé schéma) respecte les définitions de sécurité qui leur sont requises. Ces définitions de sécurité sont données dans les descriptions de classes de schémas appelées primitive cryptographique. Certains travaux en cryptologie consistent à définir des primitives afin d’uniformiser ces définitions, comme ceux de Bellare, Micciancio et Warinschi pour la signature de groupe en 2003, concept qui a été défini pour la première fois par Chaum et van Heyst en 1991. Une des premières preuves de sécurité est la sécurité au sens de la théorie de l’information du masque jetable. Cette notion est introduite par Claude Shannon, dans son article Communication theory of secrecy systems paru en 1949, et la sécurité du masque jetable a été démontrée dans cet article. Le masque jetable étant un schéma de chiffrement, la notion de sécurité requise est l'indistingabilité vis-à-vis de l’uniforme.

Interpreting Hash Function Security Proofs

Juraj Sarinay

We provide a concrete security treatment of several "provably secure" hash functions. Interpreting arguments behind MQ-HASH, FSB, SWIFFTX and VSH we identify similar lines of reasoning. We aim to formulate the main security claims in a language closer to that of attacks. We evaluate designers' claims of provable security and quantify them more precisely, deriving "second order" bounds on bounds. While the authors of FSB, MQ-HASH and SWIFFT(X) prove existence of non-trivial lower bounds on security, we show that the quantification of the bounds limits the practical significance of the proofs.

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2010

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.

EPFL2011

Provable Security in Cryptography

Thomas Baignères

These lecture notes are a compilation of some of my readings while I was preparing two lectures given at EPFL on provable security in cryptography. They are essentially based on a book chapter from David Pointcheval called “Provable Security for Public Key Schemes”, on Victor Shoup’s tutorial on game playing techniques, on Coron’s Crypto’00 paper on the exact security of the Full Domain Hash, and on Victor Shoup’s Journal of Cryptology paper on OAEP+.

2007

Cryptographic Hash Functions in Groups and Provable Properties

Juraj Sarinay

EPFL2011