Zacheusz Siedlecki | 27 Dec 18:53 2009
Picon

Re: Which fast one way hash function for secure comparison?

Thanks a lot. This is very usefull information, but I think I have
just found a better solution - one way function VMPC.
http://www.vmpcfunction.com/vmpc.pdf
http://www.vmpcfunction.com/function.htm It's very simple and has a
strong first preimage attack resistance.
            Regards,
                  Zacheusz Siedlecki

On Sun, Dec 27, 2009 at 3:35 PM, Omar Herrera <oherrera@...> wrote:
> 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 secure
> to be used outside VMAC (unless you are considering redundancy codes such as
> 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) states:
>
> "...
>
>  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 authentication
> but rather in message integrity and message authentication, this shouldn't
> 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, since
> it is used for key generation in VMAC).
>
> I hope you succeed in your project; maintaining a good balance of security
> and performance is not easy as Jeffrey pointed out. Don't forget to let us
> 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 and
>>> 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
>>
>>
>
>


Gmane