Features Download
From: Zacheusz Siedlecki <Zacheusz.Siedlecki-Re5JQEeQqe8AvxtiuMwx3w <at> public.gmane.org>
Subject: Re: Which fast one way hash function for secure comparison?
Newsgroups: gmane.comp.security.cryptography.securityfocus
Date: Sunday 27th December 2009 17:53:09 UTC (over 8 years ago)
Thanks a lot. This is very usefull information, but I think I have
just found a better solution - one way function VMPC.
It's very simple and has a
strong first preimage attack resistance.
                  Zacheusz Siedlecki

On Sun, Dec 27, 2009 at 3:35 PM, Omar Herrera
> Indeed. VMAC itself is not a hash function, but it has a an internal hash
> function component called VHASH. However, VHASH does not seem to be
> to be used outside VMAC (unless you are considering redundancy codes such
> CRC32 or Adler32, as other have suggested). From VMAC's IETF draft
>  (http://fastcrypto.org/vmac/draft-krovetz-vmac-01.txt):
> "...
> 5  VHASH: Universal hash function
>  VHASH is a keyed hash function, which takes as input a string and
>  produces a string output with length that is a multiple of 64 bits.
>  VHASH is a three-layered hash function.  A message is first hashed by
>  L1-HASH, its output is then hashed by L2-HASH, whose output is then
>  hashed by L3-HASH.  This process is done once for each 64 bits of
>  output.
>  Note that VHASH has certain combinatoric properties making it
>  suitable for Wegman-Carter message authentication.  VHASH is not a
>  cryptographic hash function and is not a suitable general replacement
>  for functions like SHA-1.
> ..."
> Regarding the security of VMAC and the description of the internal hash
> algorithm, VMAC's IETF draft
> (http://fastcrypto.org/vmac/draft-krovetz-vmac-01.txt)
> "...
>  The theory of Wegman-Carter MACs and the analysis of VMAC show that
>  if one "instantiates" VMAC with truly random keys and pads then the
>  probability that an attacker (even a computationally unbounded one)
>  produces a correct tag for messages of its choosing is less than
>  1/2^60 or 1/2^120 when the tags are of length 64 or 128 bits,
>  respectively (here the symbol ^ represents exponentiation).  When an
>  attacker makes N forgery attempts the probability of getting one or
>  more tags right increases linearly to less than N/2^60 or N/2^120.
>  In a real implementation of VMAC, using AES to produce keys and pads,
>  these forgery probabilities increase by a small amount related to the
>  security of AES.  As long as AES is secure, this small additive term
>  is insignificant for any practical attack.  See Section 6.2 for more
>  details.  Analysis relevant to VMAC security is in [5, 6].
> ..."
> MACs have also some additional security requirements, such as existential
> forgery resistance. But since you are not interested in party
> but rather in message integrity and message authentication, this
> be a problem. There are not many analyses on VMAC yet (as it is still a
> draft), but apparently preimage attacks are not an issue. If others have
> updated information on this it would be good to have it posted.
> It seems that you may be able to use the full message authentication code
> for your application with a performance gain over other hash algorithms,
> while still maintaining adequate security as long as you use truly random
> keys (or as long as no one finds significant vulnerabilities in AES,
> it is used for key generation in VMAC).
> I hope you succeed in your project; maintaining a good balance of
> and performance is not easy as Jeffrey pointed out. Don't forget to let
> know the results (it is an interesting application).
> Regards,
> Omar Herrera
>>> Hi Zacheusz,
>>> I suggest you to take a look at VMAC and GMAC. Both are based on AES
>>> designed to be very fast (VMAC is designed for 64bit computers though).
>>> Both
>>> have a higher throughput than MD5, but you have to consider key and IV
>>> setup; that takes some time at the beginning (you don't have this
>>> requirement for algorithms such as MD5).
>>> See the following references:
>>> http://www.cryptopp.com/benchmarks.html
>>> http://fastcrypto.org/
>>> http://www.faqs.org/rfcs/rfc4543.html
>>> Regards,
>>> Omar Herrera
>> Thanks for the links. VMAC performance looks interesting, but it is
>> message authentication code, not exactly one way function. What about
>> first preimage attack resistance?
>>            Regards,
>>                     Zacheusz
CD: 3ms