27 Dec 2009 18:53
Re: Which fast one way hash function for secure comparison?
Zacheusz Siedlecki <Zacheusz.Siedlecki@...>
2009-12-27 17:53:09 GMT
2009-12-27 17:53:09 GMT
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 >> >> > >