04-02-2013, 10:39 AM
A Family of Fast Syndrome Based Cryptographic Hash Functions
1A Family of Fast.pdf (Size: 460.49 KB / Downloads: 108)
Abstract.
Recently, some collisions have been exposed for a variety of cryptographic
hash functions [20, 21] including some of the most widely used today. Many other
hash functions using similar constructions can however still be considered secure.
Nevertheless, this has drawn attention on the need for new hash function designs.
In this article is presented a family of secure hash functions, whose security is directly
related to the syndrome decoding problem from the theory of error-correcting codes.
Taking into account the analysis by Coron and Joux [4] based onWagner’s generalized
birthday algorithm [19] we study the asymptotical security of our functions. We
demonstrate that this attack is always exponential in terms of the length of the hash
value.
We also study the work-factor of this attack, along with other attacks from coding
theory, for non asymptotic range, i.e. for practical values. Accordingly, we propose a
few sets of parameters giving a good security and either a faster hashing or a shorter
description for the function.
Introduction
The main cryptographic hash function design in use today iterates a so called compression
function according to Merkle’s and Damg°ard’s constructions [6, 12]. Classical compression
functions are very fast [13, 16] but, in general, cannot be proven secure. However, provable
security may be achieved with compression functions designed following public key principles,
at the cost of being less efficient. This has been done for instance by Damg°ard in [6],
where he designed a hash function based on the Knapsack problem. Accordingly, this function
has been broken by Granboulan and Joux [8], using lattice reduction algorithms. The
present paper contributes to the hash function family by designing functions based on the
syndrome decoding problem, which is immune to lattice reduction based attacks.
Unlike most other public key cryptosystems, the encryption function of the McEliece
cryptosystem [10] (or of Niederreiter’s version [14]) is nearly as fast as a symmetric cipher.
Using this function with a random matrix instead of the usual parity check matrix of a
Goppa code, a provably secure one-way function has been constructed in [1]: since there is
no trapdoor, its security can be readily related to the difficulty of syndrome decoding. For
instance, there is no polynomial time algorithm to decode a random code, thus there is no
polynomial time algorithm to invert the compression function and/or find a collision.
General Construction of Hash Functions
We follow Merkle’s and Damg°ard’s design principle of hash functions [6, 12]: iterating a
compression function (here denoted F), which takes as input s bits and returns r bits (with
s > r). The resulting function is then chained to operate on strings of arbitrary length (see
Fig. 1). The validity of such a design has been established [6, 12], and its security is proven
not worse than the security of the compression function. Therefore we will only concentrate
on the security of the latter.
Theoretical Security
As stated in [11, 17], a cryptographic hash function has to be pre-image resistant, second
pre-image resistant and collision resistant. As the second pre-image resistance is strictly
weaker than collision resistance, we will only check that the hash function is collision free
and resistant to inversion. We show that the inversion and collision finding are related to
two problems very close to syndrome decoding, which is a hard problem [3]. We describe
them here and show (in appendix) that they are also NP-complete.
Security Reduction
In this section we will recall how finding collisions or inverting the FSB hash function is
exactly as hard as solving an instance of one of the NP-complete problems described in the
previous section.
Let us be given an algorithm for the inversion of the compression function, which, given
a hash value S, finds an inverse m such that F(m) = S, in time T with probability p
of success. Then it is a tautology that this algorithm is able to solve any instance of the
problem Regular Syndrome Decoding, in the same time and with the same probability
of success. Similarly an algorithm which is able to find a collision gives in fact two different
regular words c1 and c2 of weight w such Hct
1 = Hct
2. Then c = c1©c2 is a non null 2-regular
word and has a null syndrome. So c is directly a solution for 2-Regular Null Syndrome
Decoding.
These reductions to NP-complete problems only prove worst case difficulty. However,
following Gurevich and Levin [7, 9] discussion for syndrome decoding, we believe that both
these problems are difficult on average.
Average Case Consideration
From a cryptographic point of view, knowing that some instances of a problem are hard is
not enough to consider it a hard problem. It is more important that the number of weak
instances is small enough, that is, the probability of having to solve such a weak instance
when attacking the system is negligible.
However, defining a weak instance is not so simple as it will depend on the algorithm
used to attack the system: the instances solved with the smallest complexity will vary when
changing algorithm. A weak instance should hence be defined as an instance which is weak
for at least one algorithm: an instance for which one algorithm yields a noticeably smaller
complexity than the average complexity of the best algorithm.